In all new problems of Timus Online Judge on default last line of input data always should be terminated with end of line characters.

Edited by author 03.01.2009 14:05

You need some graph theory and common sense to solve it.
Basically after you do the logic the problem breaks down to
simple bfs/dfs and counting degrees. The idea comes from
the problem of decompossing graph to a minimum amount of
paths which is solved by some simple logic - you should be
able to prove it yourself.


Hint - it has something to do with Euler ...

Helpfull to have math invariant(which right for every algo)
I think that answer=Nc+Ndb/2
where Ndb- sum of disbalances of vertices of grid's graph.
and Nc- number of alternating loops which unreached from
disbalanced vertices by alternating pathes.
But can't go far then test 8.

AC 0.031 now.Idea is right. It taken 3 days to
convert idea in quick algo.

Edited by author 04.01.2009 10:13

try test "!I AM DONT UNDERSTEND WHAT IS TEST 9!")))

There were empty lines before the number in the Test 5.
We have fixed all tests in this problem. Now they don't contain leading or trailing spaces and empty lines.

I think, "int.Parse(Console.ReadLine())" should be OK now.

It's 2.
I got it!

Changed my solution and Accept

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

STL set rules.... :)