11341 - Term Strategy

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 11341 - Term Strategy

Post by afruizc » Sun Jan 20, 2013 8:06 pm

Hello guys.
I keep getting WA in this problem, I tried to solved it using backtracking and Memoization. The idea as follows: for each subject, you can choose to study certain amount of hours and jump right to the next subject, or you can choose no to study and ignore this current hour, this would lead to study the current subject but with some additional hours. You only study a subject this hour if you are assured that the score you will obtain for that exam is greater or equal to 5. I don't know what I'm doing wrong.

here is my code:

Code: Select all

#include <stdio.h>
#include <string.h>

#define EPS 1e-9

int T, N, M, board[15][110], i, j;
int memo[110][15][110];

int max(int a, int b) {
    return a > b ? a : b;
}

int solve(int h_left, int id, int hour) {
    if (h_left <= 0 || id >= N || hour > M)
        return 0;
    if (h_left < hour)
        return 0;
    if (memo[h_left][id][hour] != -1) return memo[h_left][id][hour];
    int ans = solve(h_left, id, hour+1);
    if (board[id][hour] >= 5)
        ans = max(ans, board[id][hour] + solve(h_left - hour, id+1, 1));

    return memo[h_left][id][hour] = ans;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &N, &M);
        for (i=0 ; i<N ; i++) {
            for (j=1 ; j<=M ; j++)
                scanf("%d", &board[i][j]);
        }
        
        memset(memo, -1, sizeof memo);
        int res = solve(M, 0, 1);
        if (res >= 5 * N)
            printf("Maximal possible average mark - %.2lf.\n", (res / (double)N));
        else 
            printf("Peter, you shouldn't have played billiard that much.\n");
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11341 - Term Strategy

Post by brianfry713 » Mon Jan 21, 2013 11:06 pm

input:

Code: Select all

99
4 20
1 2 3 8 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
5 5 8 8 8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8
1 7 10 10 10 10 10 10
6 9 10 10 10 10 10 10
6 6 6 8 9 10 10 10
1 9 10 10 10 10 10 10
2 4 10 10 10 10 10 10
10 2
4 5
6 7
4 7
5 10
9 9
4 4
3 8
9 9
10 10
3 3
10 12
6 7 10 10 10 10 10 10 10 10 10 10
0 1 8 10 10 10 10 10 10 10 10 10
4 4 6 8 8 10 10 10 10 10 10 10
7 7 10 10 10 10 10 10 10 10 10 10
0 8 9 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
2 5 9 10 10 10 10 10 10 10 10 10
3 9 9 10 10 10 10 10 10 10 10 10
1 2 3 5 5 9 9 9 10 10 10 10
3 7 9 10 10 10 10 10 10 10 10 10
1 10
4 5 6 7 7 9 9 10 10 10
5 15
2 9 9 9 9 9 10 10 10 10 10 10 10 10 10
6 7 9 9 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 8 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10
9 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
3 4 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10
6 9 10 10 10 10 10 10 10 10
2 9 10 10 10 10 10 10 10 10
1 10 10 10 10 10 10 10 10 10
7 8 8 8 9 10 10 10 10 10
5 7 7 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10
5 10
10 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10
7 8 10 10 10 10 10 10 10 10
3 5 5 5 9 10 10 10 10 10
0 0 3 4 4 7 8 8 9 9
3 4
10 10 10 10
1 2 10 10
9 10 10 10
10 16
4 6 9 9 10 10 10 10 10 10 10 10 10 10 10 10
3 6 8 10 10 10 10 10 10 10 10 10 10 10 10 10
2 5 6 10 10 10 10 10 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 4 8 9 9 9 9 9 9 9 10 10 10 10 10 10
7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 7 8 8 8 9 9 9 9 9 9 10 10 10 10
4 10
7 7 7 8 10 10 10 10 10 10
9 9 9 10 10 10 10 10 10 10
8 8 8 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
9 9
5 6 6 6 6 9 9 10 10
0 10 10 10 10 10 10 10 10
3 8 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
7 7 8 10 10 10 10 10 10
1 2 7 8 9 9 10 10 10
3 6 10 10 10 10 10 10 10
3 6 7 7 10 10 10 10 10
6 4
8 10 10 10
5 9 9 10
3 8 10 10
0 3 5 5
5 9 10 10
8 9 9 10
2 10
6 7 10 10 10 10 10 10 10 10
3 6 10 10 10 10 10 10 10 10
8 7
8 9 10 10 10 10 10
0 6 10 10 10 10 10
6 6 9 9 9 10 10
7 10 10 10 10 10 10
9 10 10 10 10 10 10
0 2 9 9 9 9 10
9 10 10 10 10 10 10
4 5 9 9 10 10 10
7 13
7 9 10 10 10 10 10 10 10 10 10 10 10
1 1 9 10 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10
6 8 9 10 10 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10 10 10 10 10
7 18
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 5 5 8 8 8 9 9 9 9 9 9 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 8 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 8
7 10 10 10 10 10 10 10
5 6 9 10 10 10 10 10
9 9 10 10 10 10 10 10
10 10 10 10 10 10 10 10
0 3 3 8 9 10 10 10
4 10 10 10 10 10 10 10
1 15
6 6 9 9 10 10 10 10 10 10 10 10 10 10 10
7 12
1 5 8 9 9 9 10 10 10 10 10 10
5 8 8 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10
1 6 6 8 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10
2 8 9 10 10 10 10 10 10 10 10 10
3 6 8 10 10 10 10 10 10 10 10 10
2 16
8 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
2 8 8 8 9 10 10 10 10 10 10 10 10 10 10 10
5 20
5 7 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 19
1 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9
9 10 10 10 10 10 10 10 10
6 6 10 10 10 10 10 10 10
1 6 9 10 10 10 10 10 10
0 2 9 10 10 10 10 10 10
1 9 9 9 10 10 10 10 10
1 1 1 5 10 10 10 10 10
5 6 7 8 9 10 10 10 10
4 8 10 10 10 10 10 10 10
5 8 8 8 10 10 10 10 10
8 11
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
6 6 6 9 9 10 10 10 10 10 10
5 9 10 10 10 10 10 10 10 10 10
6 7 10 10 10 10 10 10 10 10 10
8 9 9 9 9 9 10 10 10 10 10
0 0 4 7 8 8 10 10 10 10 10
3 4 5 10 10 10 10 10 10 10 10
4 17
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 3 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 13
5 8 10 10 10 10 10 10 10 10 10 10 10
2 7 7 7 7 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10 10 10 10
6 8 9 9 9 9 10 10 10 10 10 10 10
5 9 10 10 10 10 10 10 10 10 10 10 10
1 10 10 10 10 10 10 10 10 10 10 10 10
0 3 9 10 10 10 10 10 10 10 10 10 10
1 5 5 8 9 9 9 10 10 10 10 10 10
10 5
7 10 10 10 10
1 10 10 10 10
5 5 8 8 8
6 10 10 10 10
3 6 8 10 10
6 8 8 10 10
9 9 9 9 10
5 7 8 9 9
7 10 10 10 10
1 4 6 8 8
10 1
10
3
0
8
3
6
2
7
3
4
2 17
4 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 13
2 10 10 10 10 10 10 10 10 10 10 10 10
0 2 9 9 9 9 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
1 18
2 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9
2 5 9 10 10 10 10 10 10
3 9 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10
4 4 4 10 10 10 10 10 10
0 7 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10 10
3 15
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 9 9 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 17
3 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 7 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 7 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 14
1 3 5 8 9 10 10 10 10 10 10 10 10 10
3 7
5 6 6 8 9 10 10
9 9 9 10 10 10 10
6 9 10 10 10 10 10
1 3
7 8 9
6 9
5 8 10 10 10 10 10 10 10
3 7 9 10 10 10 10 10 10
4 8 9 10 10 10 10 10 10
7 8 10 10 10 10 10 10 10
0 7 8 10 10 10 10 10 10
5 7 8 8 10 10 10 10 10
3 13
10 10 10 10 10 10 10 10 10 10 10 10 10
0 1 3 8 9 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10
1 19
0 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 12
7 10 10 10 10 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10 10
4 6 7 9 9 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10
3 3 5 7 9 9 9 9 9 9 9 9
1 2 9 10 10 10 10 10 10 10 10 10
6 7 7 10 10 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10
1 4 7 8 10 10 10 10 10 10 10 10
6 9 10 10 10 10 10 10 10 10 10 10
10 10
3 9 10 10 10 10 10 10 10 10
3 3 3 7 9 9 9 10 10 10
4 6 10 10 10 10 10 10 10 10
2 4 4 8 8 9 9 10 10 10
3 8 10 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10 10 10
3 4 9 9 10 10 10 10 10 10
2 4 4 9 10 10 10 10 10 10
4 5 8 10 10 10 10 10 10 10
1 8 10 10 10 10 10 10 10 10
1 15
4 4 5 7 9 10 10 10 10 10 10 10 10 10 10
3 9
10 10 10 10 10 10 10 10 10
4 9 10 10 10 10 10 10 10
2 2 9 10 10 10 10 10 10
1 8
4 9 9 9 9 10 10 10
1 7
5 7 8 9 9 9 9
5 3
3 7 7
10 10 10
2 4 10
6 9 9
1 7 8
6 8
10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10
1 8 10 10 10 10 10 10
1 2 10 10 10 10 10 10
7 9 9 9 9 9 9 9
4 15
2 2 2 2 5 8 8 9 9 9 9 10 10 10 10
9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 1
7
10 9
4 8 9 9 10 10 10 10 10
8 10 10 10 10 10 10 10 10
6 9 10 10 10 10 10 10 10
8 8 8 8 10 10 10 10 10
0 4 6 8 8 8 10 10 10
4 7 9 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10
3 3 7 9 10 10 10 10 10
4 9 10 10 10 10 10 10 10
6 17
4 6 8 8 9 9 9 9 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 7 8 8 8 10 10 10 10 10 10 10 10 10 10 10 10
8 8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 19
5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9
1 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
0 9 10 10 10 10 10 10 10
2 7 10 10 10 10 10 10 10
5 6 6 10 10 10 10 10 10
7 9 9 9 9 10 10 10 10
7 8 10 10 10 10 10 10 10
6 9 9 9 9 10 10 10 10
3 12
10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10
2 2 7 7 7 9 10 10 10 10 10 10
4 12
6 8 9 10 10 10 10 10 10 10 10 10
5 8 9 10 10 10 10 10 10 10 10 10
2 2 3 8 9 9 9 10 10 10 10 10
4 4 10 10 10 10 10 10 10 10 10 10
8 2
1 8
4 10
2 7
9 9
6 10
9 10
3 8
10 10
5 9
0 8 8 9 9 10 10 10 10
6 8 9 10 10 10 10 10 10
0 2 9 9 10 10 10 10 10
4 7 8 8 10 10 10 10 10
2 6 8 8 8 8 9 9 10
5 10
5 6 10 10 10 10 10 10 10 10
2 5 6 10 10 10 10 10 10 10
2 7 7 9 9 9 9 9 10 10
10 10 10 10 10 10 10 10 10 10
4 6 10 10 10 10 10 10 10 10
9 7
6 10 10 10 10 10 10
10 10 10 10 10 10 10
7 8 9 9 10 10 10
3 3 3 4 9 10 10
7 9 9 10 10 10 10
2 6 7 10 10 10 10
0 3 10 10 10 10 10
3 4 9 9 9 10 10
8 10 10 10 10 10 10
3 17
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 8 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10
4 6 8 8 8 10 10 10 10 10 10 10 10 10 10 10 10
4 8
2 8 9 9 9 10 10 10
5 8 8 9 9 10 10 10
6 8 9 10 10 10 10 10
3 7 9 10 10 10 10 10
8 16
5 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
6 6 8 8 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 2 7 7 9 9 9 9 9 10 10 10 10 10 10 10
0 5 6 8 9 9 9 10 10 10 10 10 10 10 10 10
2 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 7
9 9 9 9 10 10 10
2 4 4 8 9 9 10
2 9 10 10 10 10 10
7 17
9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
2 2 4 8 8 9 9 10 10 10 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 2 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 15
3 9 9 10 10 10 10 10 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 8 8 8 9 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 3 8 10 10 10 10 10 10 10 10 10 10 10 10
2 5 6 9 10 10 10 10 10 10 10 10 10 10 10
2 7
3 4 8 10 10 10 10
2 5 5 5 6 6 9
1 14
1 2 6 6 8 10 10 10 10 10 10 10 10 10
6 10
10 10 10 10 10 10 10 10 10 10
4 6 7 7 10 10 10 10 10 10
3 7 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10
4 9 9 10 10 10 10 10 10 10
7 7 10 10 10 10 10 10 10 10
7 9
9 10 10 10 10 10 10 10 10
6 7 9 10 10 10 10 10 10
2 2 10 10 10 10 10 10 10
3 8 10 10 10 10 10 10 10
5 6 9 10 10 10 10 10 10
4 6 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10
4 14
7 8 9 10 10 10 10 10 10 10 10 10 10 10
1 9 9 9 9 9 9 10 10 10 10 10 10 10
2 10 10 10 10 10 10 10 10 10 10 10 10 10
1 8 9 9 9 10 10 10 10 10 10 10 10 10
2 5
10 10 10 10 10
6 6 8 9 10
4 10
5 5 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
4 7 9 10 10 10 10 10 10 10
5 19
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 4 6 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 15
5 9 9 9 9 10 10 10 10 10 10 10 10 10 10
5 6 6 8 9 9 10 10 10 10 10 10 10 10 10
1 6 10 10 10 10 10 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10 10 10 10
9 1
6
2
8
9
8
5
10
1
2
10 1
8
1
1
4
6
3
6
2
10
7
10 12
7 7 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10
6 6 9 9 10 10 10 10 10 10 10 10
0 8 8 9 10 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10 10
1 9 10 10 10 10 10 10 10 10 10 10
3 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
6 9 9 9 9 9 10 10 10 10 10 10
3 4 10 10 10 10 10 10 10 10 10 10
9 17
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 5 5 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 5 6 6 9 9 9 9 9 10 10 10 10 10 10 10 10
6 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 4 4 5 8 10 10 10 10 10 10 10 10 10 10 10 10
4 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 17
0 8 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10
0 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 7 7 7 10 10 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 4 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 19
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10
9 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10
1 3 8 10 10 10 10 10 10 10
6 6 8 9 10 10 10 10 10 10
6 9 9 10 10 10 10 10 10 10
5 6 8 10 10 10 10 10 10 10
0 2 2 3 4 9 10 10 10 10
3 5 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10
4 5 7 10 10 10 10 10 10 10
7 2
2 6
2 2
5 9
9 10
9 9
0 6
4 9
3 10
5 10 10 10 10 10 10 10 10 10
4 10 10 10 10 10 10 10 10 10
1 8 10 10 10 10 10 10 10 10
2 14
3 10 10 10 10 10 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10 10 10 10 10
10 6
2 5 8 9 10 10
6 7 7 8 10 10
2 3 3 9 10 10
9 9 9 10 10 10
5 7 9 9 10 10
0 1 2 9 9 9
2 2 3 10 10 10
2 10 10 10 10 10
9 10 10 10 10 10
7 8 9 9 9 9
7 7
9 9 10 10 10 10 10
10 10 10 10 10 10 10
4 6 6 8 8 8 10
4 6 8 8 10 10 10
8 9 9 9 9 10 10
3 9 9 9 9 9 9
1 9 9 9 9 9 9
5 5
5 6 6 8 8
1 5 9 9 10
3 4 8 9 10
2 2 8 8 10
10 10 10 10 10
6 10
9 9 9 10 10 10 10 10 10 10
4 5 7 8 9 10 10 10 10 10
7 9 9 9 10 10 10 10 10 10
2 2 8 8 9 9 10 10 10 10
3 7 8 9 9 10 10 10 10 10
1 6 8 8 8 9 10 10 10 10
2 6
3 3 9 10 10 10
8 9 9 9 9 10
5 15
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 5 9 9 9 10 10 10 10 10 10 10 10 10 10
3 9 9 10 10 10 10 10 10 10 10 10 10 10 10
8 6
1 4 5 7 10 10
3 4 10 10 10 10
6 6 10 10 10 10
4 6 10 10 10 10
7 9 9 9 10 10
3 4 6 9 9 10
0 2 7 7 8 8
3 4 4 7 10 10
9 1
10
8
5
3
7
0
10
3
0
1 20
5 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 15
1 4 6 7 9 9 9 10 10 10 10 10 10 10 10
2 4 4 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 7 7 9 9 10 10 10 10 10 10 10 10 10 10
4 4 7 8 9 9 9 9 9 9 9 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 8
1 1 3 10 10 10 10 10
3 3 7 7 8 8 10 10
4 7 7 7 8 9 10 10
1 9 9 10 10 10 10 10
9 10 10 10 10 10 10 10
6 8 10 10 10 10 10 10
9 9 9 9 9 9 10 10
10 10 10 10 10 10 10 10
4 4 6 8 10 10 10 10
6 1
6
10
8
1
1
7
3 4
2 9 9 9
3 9 10 10
8 8 9 9
AC output:

Code: Select all

Maximal possible average mark - 9.75.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.30.
Maximal possible average mark - 9.25.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.14.
Maximal possible average mark - 9.29.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.67.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.67.
Maximal possible average mark - 9.00.
Maximal possible average mark - 6.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.50.
Maximal possible average mark - 7.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.33.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.75.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.60.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.75.
Maximal possible average mark - 8.00.
Maximal possible average mark - 8.67.
Maximal possible average mark - 9.14.
Maximal possible average mark - 8.57.
Maximal possible average mark - 7.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.75.
Maximal possible average mark - 9.50.
Maximal possible average mark - 9.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.33.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.11.
Maximal possible average mark - 9.14.
Maximal possible average mark - 9.56.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.50.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.14.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Check input and AC output for thousands of problems on uDebug!

connor
New poster
Posts: 4
Joined: Wed Jan 09, 2013 1:41 pm

Re: 11341 - Term Strategy

Post by connor » Sat Feb 02, 2013 8:36 am

[quote="brianfry713"][/quote]
NICE TO MEET YOU AGAIN
I really got trouble with 11341
i try every in put i could found here and got same
then i also try 1e-9
but i still keep getting WA
i really don't know why
plz help
3ks

here is my code

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
int main(){
//	freopen("out.txt","w",stdout);
	int cost[15][11];
	int map[15][110];
	int k,z;
	scanf("%d",&z);
	for(k=1;k<=z;k++){
		int m,n;
		scanf("%d%d",&m,&n);
		int i,j;
		for(i=1;i<=m;i++){for(j=1;j<=n;j++)scanf("%d",&map[i][j]);map[i][0]=0;}
		for(i=1;i<=m;i++)for(j=0;j<=6;j++)cost[i][j]=999;
		for(i=1;i<=m;i++){
			int pcost=0;
			for(j=1;j<=n-m+1;j++){
				if(map[i][j]>=5+pcost){
					cost[i][pcost]=j;
					j--;
					pcost++;
					}
				}
			}	
		int time=n,score=0;
		for(i=1;i<=m;i++){
			time-=cost[i][0];
			score+=5;
			}
		if(time<0){printf("Peter, you shouldn't have played billiard that much.\n");continue;}
		int dp[11][110];
		for(i=1;i<=10;i++)for(j=1;j<=100;j++)dp[i][j]=0;
		for(i=0;i<=n;i++){
			dp[1][i]=map[1][i];
			}
		int s=cost[1][0];
		for(i=2;i<=m;i++){
			for(j=s+cost[i][0];j<=n;j++){
				int d=cost[i][0];
				dp[i][j]=dp[i-1][j-d]+map[i][d];
				for(;d<=j;d++){
					dp[i][j]=max(dp[i][j],dp[i-1][j-d]+map[i][d]);
					}
				}
			s+=cost[i][0];
			}
		double res=(double)dp[m][n]/(double)m;
		if(dp[m][n]>=5*m)printf("Maximal possible average mark - %.2lf.\n",res);
		else printf("Peter, you shouldn't have played billiard that much.\n");

		}
	return 0;
	}
anyway thank you a lot

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11341 - Term Strategy

Post by brianfry713 » Mon Feb 04, 2013 11:32 pm

More input:

Code: Select all

99
7 4
3 6 9 10
5 10 10 10
6 7 10 10
7 9 9 9
0 2 7 7
5 5 10 10
6 8 10 10
5 20
1 1 5 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 13
3 4 4 9 9 9 9 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
8 9
1 8 9 10 10 10 10 10 10
4 4 7 9 9 10 10 10 10
7 9 9 10 10 10 10 10 10
1 7 8 9 10 10 10 10 10
1 9 10 10 10 10 10 10 10
5 5 9 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10
2 9 10 10 10 10 10 10 10
8 12
10 10 10 10 10 10 10 10 10 10 10 10
7 8 9 10 10 10 10 10 10 10 10 10
6 6 10 10 10 10 10 10 10 10 10 10
4 4 7 9 9 10 10 10 10 10 10 10
6 7 9 9 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
5 8 9 9 10 10 10 10 10 10 10 10
8 11
2 3 4 4 5 5 8 10 10 10 10
2 6 10 10 10 10 10 10 10 10 10
9 9 9 9 9 9 10 10 10 10 10
6 6 9 10 10 10 10 10 10 10 10
0 0 10 10 10 10 10 10 10 10 10
7 8 9 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
0 6 8 10 10 10 10 10 10 10 10
10 4
6 7 9 10
6 6 10 10
3 4 6 10
7 10 10 10
9 10 10 10
3 9 9 9
1 7 9 9
6 10 10 10
0 0 6 10
1 9 10 10
2 13
6 8 8 10 10 10 10 10 10 10 10 10 10
4 6 8 10 10 10 10 10 10 10 10 10 10
5 15
3 7 10 10 10 10 10 10 10 10 10 10 10 10 10
6 7 9 9 9 9 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
0 0 2 8 8 9 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 8
6 10 10 10 10 10 10 10
2 14
3 6 9 9 10 10 10 10 10 10 10 10 10 10
5 8 10 10 10 10 10 10 10 10 10 10 10 10
8 10
3 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
0 3 7 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
1 6 6 10 10 10 10 10 10 10
6 17
2 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 6 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10
6 6 7 8 8 9 9 9 9 10 10 10 10 10 10 10 10
4 6 6 6 10 10 10 10 10 10 10 10 10 10 10 10 10
1 3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 11
2 10 10 10 10 10 10 10 10 10 10
6 6 9 9 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10
2 7 9 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10
1 6 7 9 10 10 10 10 10 10 10
3 9 10 10 10 10 10 10 10 10 10
4 8
8 9 9 9 10 10 10 10
1 5 10 10 10 10 10 10
5 9 10 10 10 10 10 10
6 7 10 10 10 10 10 10
10 10
5 7 10 10 10 10 10 10 10 10
4 5 6 6 7 7 9 9 10 10
5 6 6 8 9 9 10 10 10 10
0 9 10 10 10 10 10 10 10 10
0 7 7 10 10 10 10 10 10 10
2 7 9 10 10 10 10 10 10 10
1 4 10 10 10 10 10 10 10 10
0 2 8 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10
2 12
4 9 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
5 1
5
10
3
7
1
2 19
6 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 2
1 9
9 10
4 7
2 3
2 4
10 10
8 10
8 9
4 9
7 10
8 18
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 7 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 13
3 4 10 10 10 10 10 10 10 10 10 10 10
0 6 7 7 8 10 10 10 10 10 10 10 10
0 2 7 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 9 9 10 10 10 10 10 10 10 10
3 5 7 7 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
2 3 5 9 9 10 10 10 10 10 10 10 10
5 12
2 3 8 8 9 9 10 10 10 10 10 10
7 8 8 9 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10
1 2 2 8 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10
9 3
0 6 8
3 4 5
9 9 10
8 8 9
4 5 5
3 6 9
4 4 10
7 7 8
2 9 9
10 7
4 6 10 10 10 10 10
6 6 7 7 8 9 10
0 6 6 7 9 10 10
3 9 10 10 10 10 10
5 8 8 8 9 10 10
6 10 10 10 10 10 10
0 4 6 6 8 10 10
0 7 10 10 10 10 10
4 9 10 10 10 10 10
4 9 10 10 10 10 10
6 10
2 5 6 6 7 10 10 10 10 10
4 8 8 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
5 9 9 9 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
8 8
6 6 8 10 10 10 10 10
8 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10
5 6 9 9 9 9 9 10
8 10 10 10 10 10 10 10
4 9 9 9 10 10 10 10
9 10 10 10 10 10 10 10
1 5 10 10 10 10 10 10
9 11
1 2 4 4 6 9 10 10 10 10 10
5 7 8 10 10 10 10 10 10 10 10
0 1 9 9 9 10 10 10 10 10 10
4 9 9 9 9 10 10 10 10 10 10
0 6 9 10 10 10 10 10 10 10 10
2 2 6 10 10 10 10 10 10 10 10
1 7 10 10 10 10 10 10 10 10 10
2 9 10 10 10 10 10 10 10 10 10
3 8 9 10 10 10 10 10 10 10 10
5 2
1 5
7 10
4 5
10 10
0 9
7 18
0 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 7 8 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10
1 9
0 6 9 9 10 10 10 10 10
8 4
7 7 7 10
4 5 5 8
4 8 10 10
3 7 7 9
3 6 6 6
4 6 7 7
3 9 9 10
4 10 10 10
2 20
0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 11
0 8 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10
1 6 6 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10
7 7 8 10 10 10 10 10 10 10 10
3 5 8 9 10 10 10 10 10 10 10
1 6
1 4 7 8 10 10
2 3
5 5 7
7 10 10
7 18
3 3 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 7 7 7 8 9 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 6 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
0 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 14
8 9 9 9 10 10 10 10 10 10 10 10 10 10
4 4 8 9 10 10 10 10 10 10 10 10 10 10
3 6 10 10 10 10 10 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10 10 10 10 10 10 10
0 7 9 9 9 9 9 10 10 10 10 10 10 10
6 10
3 4 5 7 10 10 10 10 10 10
6 8 8 8 10 10 10 10 10 10
3 8 10 10 10 10 10 10 10 10
4 4 10 10 10 10 10 10 10 10
4 5 7 7 9 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
4 3
1 10 10
4 10 10
7 9 10
9 9 9
1 12
8 9 9 9 9 9 9 10 10 10 10 10
2 4
2 4 8 8
1 3 9 9
6 7
9 9 10 10 10 10 10
0 8 10 10 10 10 10
8 9 9 10 10 10 10
0 8 8 8 10 10 10
8 9 9 10 10 10 10
9 10 10 10 10 10 10
2 17
2 4 8 8 8 9 10 10 10 10 10 10 10 10 10 10 10
7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 19
2 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 5 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 15
2 9 10 10 10 10 10 10 10 10 10 10 10 10 10
3 14
9 10 10 10 10 10 10 10 10 10 10 10 10 10
5 5 9 10 10 10 10 10 10 10 10 10 10 10
8 8 8 10 10 10 10 10 10 10 10 10 10 10
3 13
8 10 10 10 10 10 10 10 10 10 10 10 10
1 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 10 10 10 10 10 10 10 10 10 10
2 2
5 8
6 6
9 1
6
4
2
7
6
9
5
2
4
2 12
4 4 7 7 9 10 10 10 10 10 10 10
6 7 9 10 10 10 10 10 10 10 10 10
5 4
4 8 8 10
9 9 9 10
2 6 9 10
2 3 8 8
4 10 10 10
3 17
1 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 11
1 8 8 10 10 10 10 10 10 10 10
0 4 6 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
4 5 10 10 10 10 10 10 10 10 10
0 0 7 10 10 10 10 10 10 10 10
0 5 8 8 10 10 10 10 10 10 10
6 8 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10
4 8 10 10 10 10 10 10 10 10 10
4 5 10 10 10 10 10 10 10 10 10
8 17
6 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 3 3 3 3 9 10 10 10 10 10 10 10 10 10 10 10
1 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 4 8 8 8 10 10 10 10 10 10 10 10 10 10 10 10
6 6 7 7 7 9 9 10 10 10 10 10 10 10 10 10 10
8 9
7 7 10 10 10 10 10 10 10
4 8 8 8 8 8 9 10 10
4 5 9 9 9 9 10 10 10
9 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10
0 2 8 9 9 9 10 10 10
3 8 9 9 9 10 10 10 10
5 10 10 10 10 10 10 10 10
10 19
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 4 6 7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 4 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 7 8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
3 3 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 4
2 2 10 10
0 0 5 10
1 20
0 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 20
2 5 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 3 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 7 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8
0 9 10 10 10 10 10 10
3 3 7 10 10 10 10 10
0 4 8 10 10 10 10 10
0 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10
3 17
4 8 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 3 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 13
3 9 10 10 10 10 10 10 10 10 10 10 10
8 9 10 10 10 10 10 10 10 10 10 10 10
8 8 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10
5 13
6 9 10 10 10 10 10 10 10 10 10 10 10
1 7 7 8 8 8 9 9 10 10 10 10 10
2 4 5 6 8 8 8 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
5 9 10 10 10 10 10 10 10 10 10 10 10
6 14
0 4 8 9 10 10 10 10 10 10 10 10 10 10
9 9 9 10 10 10 10 10 10 10 10 10 10 10
1 3 6 8 8 9 9 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10 10 10 10
3 10 10 10 10 10 10 10 10 10 10 10 10 10
8 15
3 3 3 6 10 10 10 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 3 9 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 9 9 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 13
9 10 10 10 10 10 10 10 10 10 10 10 10
5 5 9 9 10 10 10 10 10 10 10 10 10
6 10 10 10 10 10 10 10 10 10 10 10 10
2 5 6 8 9 10 10 10 10 10 10 10 10
3 4 5 5 6 6 8 9 10 10 10 10 10
5 7 8 8 8 10 10 10 10 10 10 10 10
2 2 6 6 10 10 10 10 10 10 10 10 10
4 19
6 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 5 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 15
7 8 10 10 10 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 1 8 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 7 8 8 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 2
6 7
0 6
6 8
3 15
5 7 9 10 10 10 10 10 10 10 10 10 10 10 10
6 7 10 10 10 10 10 10 10 10 10 10 10 10 10
1 6 7 9 9 10 10 10 10 10 10 10 10 10 10
9 4
9 10 10 10
1 3 3 8
8 8 8 10
8 10 10 10
0 7 8 9
5 9 10 10
9 9 9 9
4 5 5 5
9 10 10 10
1 3
0 9 9
4 19
2 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 3 4 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 7 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 19
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
1 8 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 5
7 7 9 9 9
6 9 10 10 10
9 10 10 10 10
2 9 9 10 10
5 10
2 9 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10
1 3 10 10 10 10 10 10 10 10
0 6 9 10 10 10 10 10 10 10
5 14
7 7 9 10 10 10 10 10 10 10 10 10 10 10
2 2 6 10 10 10 10 10 10 10 10 10 10 10
0 6 9 10 10 10 10 10 10 10 10 10 10 10
4 9 9 9 10 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10 10 10 10 10
10 1
4
5
8
8
7
3
5
1
0
6
4 2
6 8
8 8
2 9
0 2
6 10
6 7 9 9 9 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
0 10 10 10 10 10 10 10 10 10
8 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10
3 5 6 6 10 10 10 10 10 10
8 8
6 10 10 10 10 10 10 10
4 8 10 10 10 10 10 10
10 10 10 10 10 10 10 10
8 9 9 10 10 10 10 10
5 7 9 10 10 10 10 10
8 9 9 10 10 10 10 10
9 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10
10 2
4 8
9 9
5 10
6 9
1 3
3 5
6 10
2 2
8 8
9 9
10 19
5 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 6 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
5 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 6 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 20
6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 1 8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8 8 8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8 6
3 7 8 10 10 10
0 9 9 10 10 10
7 8 10 10 10 10
2 8 9 10 10 10
2 5 8 10 10 10
7 8 9 10 10 10
8 10 10 10 10 10
1 4 9 9 10 10
5 5
7 10 10 10 10
6 8 9 9 10
9 10 10 10 10
8 10 10 10 10
4 7 10 10 10
1 3
4 5 7
8 18
8 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10
6 7 8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
0 4 4 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 8 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
5 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
6 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 7 8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10
1 15
5 9 10 10 10 10 10 10 10 10 10 10 10 10 10
6 16
8 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10
5 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
1 2 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 7 9 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
7 15
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 6 10 10 10 10 10 10 10 10 10 10 10 10 10
2 4 4 9 9 9 10 10 10 10 10 10 10 10 10
7 8 9 10 10 10 10 10 10 10 10 10 10 10 10
3 3 10 10 10 10 10 10 10 10 10 10 10 10 10
9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4 9 9 10 10 10 10 10 10 10 10 10 10 10 10
2 4
1 5 6 10
2 9 9 9
8 12
4 9 10 10 10 10 10 10 10 10 10 10
9 9 9 9 9 9 10 10 10 10 10 10
3 4 5 6 7 8 10 10 10 10 10 10
7 9 10 10 10 10 10 10 10 10 10 10
7 8 9 9 10 10 10 10 10 10 10 10
6 9 9 9 9 10 10 10 10 10 10 10
7 7 9 9 9 9 9 10 10 10 10 10
0 5 7 10 10 10 10 10 10 10 10 10
2 18
0 2 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
5 8 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10
8 8
2 5 8 9 10 10 10 10
0 4 8 9 9 10 10 10
5 5 5 5 10 10 10 10
0 10 10 10 10 10 10 10
5 5 6 9 9 10 10 10
2 6 6 10 10 10 10 10
3 10 10 10 10 10 10 10
3 5 5 9 10 10 10 10
8 9
4 9 9 10 10 10 10 10 10
7 7 8 9 9 10 10 10 10
2 9 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
6 7 8 10 10 10 10 10 10
3 8 8 9 10 10 10 10 10
10 10 10 10 10 10 10 10 10
2 10 10 10 10 10 10 10 10
2 9
5 7 7 10 10 10 10 10 10
8 8 9 10 10 10 10 10 10
4 15
0 3 5 7 10 10 10 10 10 10 10 10 10 10 10
7 8 8 10 10 10 10 10 10 10 10 10 10 10 10
1 8 9 9 9 9 10 10 10 10 10 10 10 10 10
3 6 8 8 10 10 10 10 10 10 10 10 10 10 10
AC output:

Code: Select all

Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.25.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.60.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.17.
Maximal possible average mark - 7.86.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.63.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.29.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.50.
Maximal possible average mark - 8.71.
Maximal possible average mark - 8.83.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.83.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 5.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.75.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.70.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.43.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.80.
Maximal possible average mark - 9.00.
Maximal possible average mark - 8.25.
Maximal possible average mark - 6.43.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.43.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.86.
Maximal possible average mark - 7.75.
Maximal possible average mark - 9.40.
Maximal possible average mark - 9.40.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.20.
Maximal possible average mark - 9.22.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.00.
Maximal possible average mark - 8.25.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.67.
Maximal possible average mark - 9.14.
Maximal possible average mark - 7.00.
Maximal possible average mark - 6.88.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.25.
Check input and AC output for thousands of problems on uDebug!

eric7237cire
New poster
Posts: 4
Joined: Sat Mar 30, 2013 4:06 pm

Re: 11341 - Term Strategy

Post by eric7237cire » Sat Mar 30, 2013 4:17 pm

A couple hints for those getting WA.

The problem description is misleading, do not use the ` character in the phrase "Peter, you shouldn't have played billiard that much."

Also, I did confirm that exam grades are non decreasing via an assert.

One last thing, you can do the average at the very end and only keep track of the maximum sum of points on the exams.

I can confirm you do need to adjust the average somewhat to pass.
Here is what makes all the difference (thanks to a previous post:

//WA
printf("Maximal possible average mark - %.2lf.\n", ((double)ans) / nExams);

//Accepted
printf("Maximal possible average mark - %.2lf.\n", (1e-9 + ans) / nExams);

Essam92
New poster
Posts: 1
Joined: Mon Jun 24, 2013 3:38 am

Re: 11341 - Term Strategy

Post by Essam92 » Mon Jun 24, 2013 3:44 am

I got AC just by using %.2lf instead of %.2llf, and adding 1e-9

Post Reply

Return to “Volume 113 (11300-11399)”