467 - Synching Signals

[eXon]

I thought it is a simple problem (my prog works on all samples), but know I get only WA.
Can someone tell me: if given cycle time is 30 seconds, what color would have a traffic light
1) at 0 sec.;
2) at 25 sec.;
3) at 29 sec.;
4) at 30 sec.;
5) at 60 sec.;
6) at 61 sec.?

If you need, I can give a code of "solution", just say!
Thanks!

[titid_gede]

if i'm not mistaken :
1) at 0 sec.; -> ???
2) at 25 sec.; -> green
3) at 29 sec.; ->yellow
4) at 30 sec.; ->yellow
5) at 60 sec.; -> red
6) at 61 sec.? -> green

but i think this quote can help you, since i got WA because of this (before AC)

The output line will begin with the signal set ID number and state the number of minutes ( <= 60)

hope it can help and good luck.

titid

[eXon]

Thank you, titid_gede! But I still have WA!
Here is the code of color detecting routine (it returns the color of traffic light number t at a time sec given in seconds):
[cpp]
clr color(int t, int sec){
t = traf[t]; // in t -> cycle time of traffic light #t
int d = (sec) / t; // in d -> full cycles number

if (!((d + 1) % 2))
return red;
if (sec >= t * (d + 1) - 5 && sec < t * (d + 1))
return yel;
return green;
}
[/cpp]
Here:
[cpp]int traf[300][/cpp] - stores cycle times of traffic lights
[cpp]enum clr{red, yel, green}[/cpp] - defines color

[eXon]

It was a my mastake : my program printed
Set X is unable to synch at 3 etc. without a dot at the end.
And I've got AC

[kenneth]

I have tried different methods and I still got TLE

Would someone be able to inform me some quicker way of solving this problem?

Code: Select all

#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)

    string line;
    int cases = 1;

    while (getline(cin, line))
    {
        set <int> freq;

        istringstream iss(line);
        int a;

        while (iss >> a)
            freq.insert(a);

        vector <bool> lights(3601, true);

        REP(j, 3601)
            FOREACH(i, freq)
                if (j % (2 * (*i)) >= (*i) - 5)
                    lights[j] = false;

        int minimum = *(freq.begin());
        bool found = false;

        for (int i = 2 * minimum; i < 3601; i++)
        {
            if (lights[i])
            {
                printf("Set %d synchs again at %d minute(s) and %d second(s) after all turning green.\n", cases++, i / 60, i % 60);

                found = true;
                break;
            }
        }

        if (!found)
            printf("Set %d is unable to synch after one hour.\n", cases++); 
    }

[mamun]

I am getting WA. Can anybody verify following random I/O? If I'm correct then provide with some tricky ones please.
Input

Code: Select all

43 67 26 55 18 67
58 59 29 31 71 75 62 86 59
46 73 24 22 73 39 61 42 60 15
64 41 32 69 59
66 41 79 81 15 64 43
42 89 90 48 50 56 60 68 10 27
58 74 60 28 67 86 71 58 72
12 50 59 36 50
40 17 89 10 57 59
76 68 46 74 17 36 77
27 64 78 25 52 27 53 44 34
61 41 55 63 34 79 88
83 32
44 12 64 84 54 38 88 90 32
58 89 82 40
23 86 65 73 62 39 74
83 85
22 48
26 30 75 88 77 12
16 40 14 10 63 59 80 28 63 53

Output

Code: Select all

Set 1 synchs again at 11 minute(s) and 28 second(s) after all turning green.
Set 2 is unable to synch after one hour.
Set 3 is unable to synch after one hour.
Set 4 synchs again at 4 minute(s) and 36 second(s) after all turning green.
Set 5 synchs again at 3 minute(s) and 0 second(s) after all turning green.
Set 6 synchs again at 10 minute(s) and 0 second(s) after all turning green.
Set 7 is unable to synch after one hour.
Set 8 synchs again at 2 minute(s) and 24 second(s) after all turning green.
Set 9 synchs again at 4 minute(s) and 0 second(s) after all turning green.
Set 10 synchs again at 5 minute(s) and 8 second(s) after all turning green.
Set 11 is unable to synch after one hour.
Set 12 synchs again at 53 minute(s) and 18 second(s) after all turning green.
Set 13 synchs again at 3 minute(s) and 12 second(s) after all turning green.
Set 14 synchs again at 15 minute(s) and 12 second(s) after all turning green.
Set 15 synchs again at 4 minute(s) and 0 second(s) after all turning green.
Set 16 synchs again at 52 minute(s) and 8 second(s) after all turning green.
Set 17 synchs again at 2 minute(s) and 50 second(s) after all turning green.
Set 18 synchs again at 1 minute(s) and 36 second(s) after all turning green.
Set 19 synchs again at 6 minute(s) and 4 second(s) after all turning green.
Set 20 synchs again at 53 minute(s) and 20 second(s) after all turning green.

[mamun]

Somebody verify my I/O please.

[mamun]

Hallooo
Am I too far from correct?

[Jan]

My Accepted code returns..

Code: Select all

Set 1 synchs again at 11 minute(s) and 28 second(s) after all turning green.
Set 2 is unable to synch after one hour.
Set 3 is unable to synch after one hour.
Set 4 synchs again at 4 minute(s) and 36 second(s) after all turning green.
Set 5 synchs again at 0 minute(s) and 30 second(s) after all turning green.
Set 6 synchs again at 0 minute(s) and 20 second(s) after all turning green.
Set 7 is unable to synch after one hour.
Set 8 synchs again at 0 minute(s) and 24 second(s) after all turning green.
Set 9 synchs again at 4 minute(s) and 0 second(s) after all turning green.
Set 10 synchs again at 5 minute(s) and 8 second(s) after all turning green.
Set 11 is unable to synch after one hour.
Set 12 synchs again at 53 minute(s) and 18 second(s) after all turning green.
Set 13 synchs again at 1 minute(s) and 4 second(s) after all turning green.
Set 14 synchs again at 0 minute(s) and 24 second(s) after all turning green.
Set 15 synchs again at 4 minute(s) and 0 second(s) after all turning green.
Set 16 synchs again at 52 minute(s) and 8 second(s) after all turning green.
Set 17 synchs again at 2 minute(s) and 50 second(s) after all turning green.
Set 18 synchs again at 1 minute(s) and 36 second(s) after all turning green.
Set 19 synchs again at 6 minute(s) and 4 second(s) after all turning green.
Set 20 synchs again at 53 minute(s) and 20 second(s) after all turning green.

Hope it works.

[mamun]

Thank you Jan I've got it accepted.
You are really a great helper and in no time you'll become a Guru.

[Sedefcho]

Suppose we number the seconds of time with 0,1,2,3,... i.e.
we assume we have discrete steps in time numbered with 0,1,2,...

If the period of one of the traffix lights
(the period given in the input) is N then
this traffic light:
1) shows green in the interval [0, N-6] secs
2) shows yellow in the interval [N-5, N-1] secs
3) shows red in the interval [N, 2*N-1] secs
After that it repeats its behavior. So the real period length is 2*N.

Here by [A,B] we denote the closed interval from A to B
which includes both A and B and all the integers between A and B.

The tricky part about this problem is that we need to
observe ( to simulate in our programs) the state of the
given traffic lights in the discrete steps of time
numbered with:
0, 1, 2, ..., 3599, 3600
If we assume that each discrete step of time lasts for 1 sec then
this all is a period of time having length of 1 hour and 1 second ( !!! )
and not a period of time having length of 1 hour as I originally thought.

Hope these thoughts might help to someone. I wanted to
share them as it took me too much time to solve this
easy (in principle easy) problem.

Good luck to everyone.

[uDebug]

I have tried different methods and I still got TLE

Would someone be able to inform me some quicker way of solving this problem?

I ran into the exact same issue and I struggled with this for a few hours until I realized that there's nothing wrong with my algorithm.

There's something else that you need to be aware of, though. The hint here is to think about the size of the (judge's) input and a certain variable that's being incremented in each loop.

[jddantes]

Why WA? Any other sample input?

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <sstream>
#include <algorithm>

using namespace std;

int numDig(int n){
    if(n == 0)
        return 1;
    int cnt = 0;
    while(n){
        n/=10;
        cnt++;
    }
    return cnt;
}

int isGreen(int t, int cycle){
    cycle *= 2;
    t = t % (cycle);
    if(t > cycle/2 || t == 0 ){
        return 2; // Red
    } else if (t <=cycle/2 && t > cycle/2 - 5){
        return 1; // Yellow
    } else {
        return 0; // Green
    }
}

int main(){

    int e = 0;
    char buff[500];

    while(fgets(buff, 500, stdin)!=NULL){
        e++;
        vector<int> arr;

        istringstream iss;
        iss.str(buff);

        int d;
        while( !(iss >> d).eof()){
            arr.push_back(d);
        }

        int n = arr.size();
        int state[n];
        memset(state, 0, sizeof(n));

        int t = 1;
        int good = 0;
        int sync = 0;
        while(t<=3600){
            // Update
            for(int i = 0; i<n; i++){
                state[i] = isGreen(t, arr[i]);
                //printf("%d ", state[i]);
            } //printf("\n");

            // Check if yellow
            if(!good){
                for(int i = 0; i<n; i++){
                    if(state[i] == 1){
                        good = 1;
                        break;
                    }
                }
            } else {
                int localSync = 1;
                for(int i = 0; i<n; i++){
                    if(state[i] != 0){
                        localSync = 0;
                        break;
                    }
                }
                if(localSync){
                    sync = 1;
                    break;
                }
            }

            t++;

        }
        t--;
        if(sync){
            printf("Set %d synchs again at %d minute(s) and %d second(s) after all turning green.\n",e,t/60, t%60);

        } else {
            printf("Set %d is unable to synch after one hour.\n", e);
        }

    }

    return 0;

}

[brianfry713]

Input:

Code: Select all

60 75 69 78 31 89 74 72

AC output:

Code: Select all

Set 1 synchs again at 60 minute(s) and 0 second(s) after all turning green.

[lighted]

Thanks!
This test helped me too.