| Submit | All submissions | Best solutions | Back to list |
PAAAARTY - Party! |
Kate is preparing a party. She have bought a very strange garland for it. The garland is a closed chain of bulb. Each bulb can be in one of the following states: N - don't glow, R - glow red, G - glow green, B - glow blue. Each second the state of each bulb changes according to the following table:
| N | R | G | B | |
| N | N | R | G | B |
| R | R | N | B | G |
| G | G | B | N | R |
| B | B | G | R | N |
where row is chosen by the current state of the bulb and column is chosen by the state of the bulb on the right. The value at the intersection of the chosen row and column gives the new state of the bulb. For example, if the bulb glows red (R) and the bulb on its right glows green (G) then in the next second the bulb will glow blue (B). And if the bulb and its right neighbour both glow blue then the bulb won't glow at all in the next second. Also all the bulbs change their states simultaneously. Such behaviour should (theoretically) lead to constant twinkling of the garland. Unfortunately it turns out that sometimes eventually the garland goes into such a state that all bulb don't glow. So the garland stops twinkling. Kate is rather worried that this can spoil the party. She is going to set the initial states of each bulb as she like. Help her determine for how long the garland will twinkle starting from this initial state.
Input
The input file consists of a single string containing characters 'N', 'R', 'G' and 'B', which describes the initial state of the garland. Each character defines the initial state of some bulb. The bulbs are listed from left to right. There is the first bulb on the right of the last one. The length of the string will be no more than 1234567 characters.
Output
Print the number of seconds during which the garland will twinkle. If the garland won't stop twinkling (at least until the power is turned off) print "Party!" (quotes for clarity).
Example
Input: RGBG Output: 4
Explanation
The garland will change the state in such a way:
RGBG BRRB GNGN GGGG NNNN
| Added by: | Spooky |
| Date: | 2011-05-22 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Open All-Ukrainian Collegiate Contest Semi-Final, 2011 |
hide comments
|
2018-06-25 13:11:38 koushik s
can number of seconds be greater than 2^64? no need to use big integer,it seems answer fits in 64 bits Last edit: 2018-06-25 14:02:38 |
|
|
2015-10-10 06:30:06 Alex Anderson
My algorithm which passes is O(n log n) runtime. Constant of 1, essentially. |
|
|
2014-06-07 04:38:09 Questa Notte
I think my code is not perfect because I think sometimes it won't give a right answer.I think the correct solution may be O(n log^2 n),but even my O(n log n)'s imperfect solution got TLE! :( Last edit: 2014-06-07 13:03:20 |
|
|
2012-06-01 16:42:27 pulkit
TL is REALLY strict :-/ @Spooky: Can you please look at my code and tell if there's a better soln? Last edit: 2012-06-01 16:46:11 |
|
|
2011-06-12 11:58:30 krabathor
@spooky can the answer be greater than 4 if yes can you give a case thanks |
|
|
2011-05-25 07:35:15 Spooky
@mukul gupta Your algorithm is straight-forward. You need to think of smth better to cope with long garlands. @Siarhei Khamenka The garland won't twinkle at all. So it's 0. |
|
|
2011-05-24 09:05:28 Siarhei Khamenka
"NNN" will result in 0 or 1? |
|
|
2011-05-23 19:10:48 mukul gupta
my submission id is 5132990...i'm getting TLE again and again..plz help me wt can i do to improve my code....thanx in advance. |
RSS