the last two lines are said to provide two lists: the documents he has and the documents he still needs.

in some test cases (like case #4) some documents are missing from both lists so, what to do with these missing documents? shall he still require them or not? in test #4 if ignore these documents, it is WA. but if these documents are still required, it is AC.

then i am quite wondering what test case #5 expects if it has some missing documents: are they still requred or not? i have tested many understandings with #5 but had all WA with them.

well, #5 is 'No Solution'
stuck with #7

can someone advise on this code?

i put tests somewhere with 'puts(NULL)' so if the thing i expect happens, i will get 'ACCESS VIOLATION' there.

the method is to just get the closest document done as possible until all is finished. if no document can be done in the weekday length period, there is no solution.

in this version in input line by line so if there is any garbage at the end of a line, it is ignored.

i dont see any other problems though.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#include <sstream>

using namespace std;

const int Inf = 1000000000;
//const int Inf = 1000000;

char buf[4096];

int main (void) {
    int n, l;
    gets(buf);
    sscanf(buf, "%d %d", &n, &l);
    if (n < 1 || n > 100) puts(NULL);
    if (l < n || l > 100) puts(NULL);
    int w[128] = {0};
    gets(buf);
    istringstream is0(buf);
    for (int i = 1, j; i <= n; ++ i) {
//        scanf("%d", &j);
        if (!(is0 >> j)) puts(NULL);
        if (j < 1 || j > l) puts(NULL);
//        if (w[j]) puts(NULL);
        w[j] = i;
    }
    bool d[102][102] = {{false}};
    int nd[128] = {0};
    for (int i = 1, j; i <= n; ++ i) {
        gets(buf);
        istringstream is(buf);
        while (is >> j && j) {
//        while (1 == scanf("%d", &j) && j) {
            if (!d[i][j]) {
                d[i][j] = true;
                ++ nd[i];
            }
            else puts(NULL);
        }
    }
    int now;
    gets(buf);
    sscanf(buf, "%d", &now);
    if (now < 1 || now > l) puts(NULL);
    bool having[128] = {false}, need[128] = {false};
    gets(buf);
    istringstream is1(buf);
    for (int i; is1 >> i && i; having[i] = true);
    gets(buf);
    istringstream is2(buf);
    for (int i; is2 >> i && i; need[i] = true);

    for (int i = 1; i <= n; ++ i) {
        if (having[i]) {
// testing if a document he has is also required, no failure yet till test #7
//            if (need[i]) puts(NULL);
//            need[i] = false;
            for (int j = 1; j <= n; ++ j) {
                if (d[j][i]) {
                    d[j][i] = false;
                    -- nd[j];
                }
            }
        }
        else need[i] = true;   // the missing documents are all needed
    }

    int rest = 0;
    for (int i = 1; i <= n; ++ i) {
// the following line fail on test #4, thus there are missing documents in test #4
//        if (having[i] == need[i]) puts(NULL);
        if (need[i]) ++ rest;
    }

    int days = 0, seq[128], k = 0;
    -- days;
    -- now;
    while (rest && days < Inf) {
        bool nothing = true;
//        while (days < Inf) {
        for (int i = l; i >= 0; -- i) {
            ++ now;
            ++ days;
            if (now > l) now = 1;
            int x;
            if ((x = w[now]) && 0 == nd[x] && need[x]) {
                -- rest;
                need[x] = false;
                for (int i = 1; i <= n; ++ i) {
                    if (d[i][x]) {
                        d[i][x] = false;
                        -- nd[i];
                    }
                }
                seq[k ++] = x;
                nothing = false;
                break;
            }
        }
        if (nothing) days = Inf;
    }

    if (days < Inf) {
        if (days < 0) days = 0;
        printf("%d\n", days);
        if (k) {
            for (int i = 0; i < k; ++ i) {
                if (i) putchar(' ');
                printf("%d", seq[i]);
            }
            putchar('\n');
        }
    }
    else {
//        puts(NULL);
        puts("No Solution");
    }

    return 0;
}


Edited by author 25.10.2004 06:30

Edited by author 25.10.2004 06:34

in test 7 we have all necessary documents, so the answer is 0.

thanks.

the question is: how was it represented in #7 to 'have all documents'? was it a full list in the having-list, or was it a null list in the needing-list, or was it a full list in the having-list but some dup documents still in the needing-list, or was there simply some missing documents in both lists? it seems all these things can happen considering the tests i have met before #7.

i have tried this way: if a document is in the having-list, i just remove it from the needing-list (having list has higer priority to needing-list) so if the having-list is a full list, my code will detect it and since there is no document, my output is '0'. this way fails. hence i think it is expressed in another way in #7 to have a full document set.

or this time in #7, the needing-list have higher priority? that if the needing list is empty, the having-list shall be full? but this understanding contradicts to the test cases prior to #7. then i see the tests are contradicting themselves.

now i check this before everything:

if the needing-list is empty, the having-list is full.

it passes #7. but now, stuck with #10 for some reason. another understanding to data there?

can the test data be ever consistant? or if there are any priority rules be applied, can it be stated clearly in the problem?


Edited by author 25.10.2004 18:52

I get WA on test 21. What can be in this test? If who knows, share, please.

I can give you tests which I used to solve this problem.
5 18
5 3 18 12 1
2 3 4 5 0
0
4 5 0
5 0
2 0
3
0
1 2 3 4 5 0
The answer is
38
2 5 4 3 1

And

5 18
5 3 18 12 1
2 3 4 5 0
0
4 5 0
5 0
2 0
3
0
3 0
The answer is
33
2 5 4 3

Thank you a lot! Very strange days counting rules in this problem. Starting day is not counted in answer, but can be used to get documents.

Simple test for this (like in statement, but current day of week 2 instead of 1):
2 7
1 2
0
1 0
2
1 0
2 0

Answer:
0
2