hdu 4503 추 추 시리즈 이야기 - 식목일

2295 단어 수학.
추 추 시리즈 이야기 - 식목일
                                                                          Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Problem Description
오늘 은 1 년 에 한 번 있 는 식목일 입 니 다. 텐 센트 유치원 은 모든 선생님 들 에 게 반 에서 몇 명의 어린 이 를 뽑 아 야외 에 가서 작은 묘목 을 심 으 라 고 요구 합 니 다. 학교의 전체적인 배정 에 따라 추 추 선생님 의 반 에서 세 명의 어린 이 를 뽑 아야 합 니 다.  이미 추 추 의 반 에는 모두 n 명의 아이 가 있 고 모든 아이 에 게 Bi 친구 (i 1 부터 n 까지) 가 있 으 며 친구 관 계 는 서로 있 습 니 다. 만약 에 a 어린이 와 b 어린이 가 친구 라면 b 어린이 와 a 어린이 도 좋 은 친구 가 될 것 입 니 다.선택의 공평 성 을 위해 추 추 선생님 은 무 작위 로 세 명의 어린 이 를 뽑 아 낸다 (모든 사람 이 뽑 힐 확률 이 같다). 그러나 그녀 는 이 세 명의 어린이 간 의 관계 가 완전히 같 기 를 바란다. 추 추 선생님 은 그녀 가 뽑 은 세 명의 어린이 가 똑 같은 관 계 를 가 질 확률 이 얼마 인지 계산 해 달라 고 부탁 하고 싶다.
PS. 관계 가 같다 는 것 은 세 사람 이 서로 좋 은 친구 이거 나 세 사람 이 서로 좋 은 친구 가 아니 라 는 것 을 말 하 는 것 입 니까?
 
Input
입력 데이터 의 첫 줄 은 정수 T (1 < = T < = 1000) 로 입력 데이터 의 그룹 수 를 나타 낸다.각 그룹의 데이터 의 첫 줄 은 정수 n 으로 아이의 총수 (2 < n < = 1000) 를 나타 내 고, 두 번 째 줄 은 n 개의 수 Bi (i 는 1 에서 n) 로 각각 어린이 들 의 친구 의 개 수 를 나타 낸다.
 
Output
각 그룹의 데이터 에 대해 추출 한 세 명의 어린이 관계 가 같은 확률 로 출력 하 십시오. 결 과 는 세 개의 소 수 를 유지 합 니 다.
 
Sample Input

   
   
   
   
1 5 3 3 3 3 4

 
Sample Output

   
   
   
   
0.400

 
이 문 제 는 직접적 으로 구하 기 가 쉽 지 않 기 때문에 우 리 는 그것 의 반면 을 구 할 수 있다. 즉, 3 명의 관계 가 다른 상황 을 구 한 다음 에 총수 로 다른 것 을 빼 면 똑같다.다른 상황 은 두 사람 이 친구 이지 만 세 번 째 사람과 친구 가 아니 기 때문에 두 번 째 사람 에 대해 서 는 그의 친구 중에서 하 나 를 고 를 수 있 고 그 가 아 닌 친구 중에서 하 나 를 고 른 다음 에 그 자신 을 더 해서 마지막 에 2 를 구 하 는 것 과 나 누 는 것 이 다른 수량 (모든 사람 이 두 번 을 계 산 했 기 때문이다) 이다.
#include<stdio.h>
int main()
{
    int a, t, n, i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int num = 0;
        for(i = 0; i < n; i++)
        {
             scanf("%d",&a);
             num += a * (n - 1 - a);
        }
        num /= 2;
        int sum = n * (n-1) * (n-2) / 6;
        printf("%.3lf
",(sum - num)*1.0 / sum); } return 0; }

좋은 웹페이지 즐겨찾기