I - Exhibition

Time Limit: 1 sec
Memory Limit: 16MB

Some friends have the same hobby, they are collecting stamps. Once upon a time they decided to make an exhibition. Exhibition brought them some money and now they do not know how to divide their income. They decided to divide their money according this rule: "The percent of whole income that i-th friend will get is equal to the part of his unique stamp's type."

The stamp type is called unique if and only if this type of stamps of owned only by one person.

INPUT:

OUTPUT:

SAMPLE INPUT:

1
3
3 1 2 3
2 4 5
3 4 2 6

SAMPLE OUTPUT:

Case 1: 50.000000% 25.000000% 25.000000%

Problem setters: Aleksej Viktorchik, Leonid Shishlo.
Huge Easy Contest #1

題目不難，但有陷阱，一個人可能擁有多個同一種郵票。

因此在獨特郵票的判定上，要特別小心，只要只有一個人有，他仍是一張獨特的郵票。

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase, cases = 0;
    int A[50][50], Am[50];
    int n, i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        int mark[10005] = {};
        for(i = 0; i < n; i++) {
            scanf("%d", &Am[i]);
            for(j = 0; j < Am[i]; j++)
                scanf("%d", &A[i][j]);
            sort(A[i], A[i]+Am[i]);
            mark[A[i][0]]++;
            for(j = 1; j < Am[i]; j++)
                if(A[i][j] != A[i][j-1])
                    mark[A[i][j]]++;
        }
        int unique = 0;
        for(i = 0; i <= 10000; i++)
            unique += (mark[i] == 1);
        printf("Case %d:", ++cases);
        for(i = 0; i < n; i++) {
            int cnt = 0;
            cnt += (mark[A[i][0]] == 1);
            for(j = 1; j < Am[i]; j++) {
                if(A[i][j] != A[i][j-1])
                    cnt += (mark[A[i][j]] == 1);
            }
            printf(" %.6lf%%", (double)cnt*100.0/unique);
        }
        puts("");

    }
    return 0;
}

您可能對以下文章有興趣

c112. Optimal Array Multiplication Sequence

[UVA][bitmap、搜索、博弈] 322 - Ships

[UVA][博奕dp] 1500 - Alice and Bob

[UVA][Math] 1264 - Binary Search Tree