Page 1 of 2
467 - Synching Signals
Posted: Thu Jul 03, 2003 1:30 pm
by 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!
Posted: Thu Jul 03, 2003 2:45 pm
by 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
Posted: Thu Jul 03, 2003 3:55 pm
by 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
Sorry
Posted: Thu Jul 03, 2003 4:09 pm
by 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
Posted: Fri Sep 09, 2005 5:57 pm
by 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++);
}
Posted: Mon Dec 19, 2005 9:14 pm
by 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.
Posted: Fri Dec 23, 2005 7:38 pm
by mamun
Somebody verify my I/O please.
Posted: Sun Dec 25, 2005 6:35 pm
by mamun
Hallooo
Am I too far from correct?
Posted: Sun Jan 01, 2006 8:58 pm
by 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.
Posted: Sun Jan 01, 2006 10:28 pm
by mamun
Thank you Jan
I've got it accepted.
You are really a great helper and in no time you'll become a Guru.
some clarifications
Posted: Tue May 15, 2007 12:04 am
by 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.
Re: Easy 467
Posted: Fri Dec 27, 2013 8:08 am
by uDebug
kenneth wrote: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.
Re: Easy 467
Posted: Wed Jul 16, 2014 1:02 pm
by 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;
}
Re: Easy 467
Posted: Wed Jul 16, 2014 7:59 pm
by brianfry713
Input:
AC output:
Code: Select all
Set 1 synchs again at 60 minute(s) and 0 second(s) after all turning green.
Re: Easy 467
Posted: Wed Jul 16, 2014 8:10 pm
by lighted
Thanks!
This test helped me too.