Submit | All submissions | Best solutions | Back to list |
ABCD - Colours A, B, C, D |
Consider a table with 2 rows and 2N columns (a total of 4N cells). Each cell of the first row is coloured by one of the colours A, B, C, D such that there are no two adjacent cells of the same colour. You have to colour the second row using colours A, B, C, D such that:
- There are exactly N cells of each colour (A, B, C and D) in the table.
- There are no two adjacent cells of the same colour. (Adjacent cells share a vertical or a horizontal side.)
It is guaranteed that the solution, not necessarily unique, will always exist.
Input
[a natural number N ≤ 50000]
[a string of 2N letters from the set {A, B, C, D}, representing the first row of the table]
Output
[a string of 2N letters from the set {A, B, C, D}, representing the second row of the table]
Example
Input: 1 CB Output: AD
Input: 2 ABAD Output: BCDC
Added by: | Adrian Satja Kurdija |
Date: | 2011-03-13 |
Time limit: | 0.300s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | inspired by a math puzzle |
hide comments
|
|||||||||||||
2015-05-27 12:31:32 CoNtRaDiCtIoN
awesome problem :) |
|||||||||||||
2015-03-28 00:56:52 Rajat (1307086)
There are several solutions, but if you apply the correct logic you will get one and only one. Nice problem indeed. |
|||||||||||||
2015-02-13 23:46:34 chamini2
It's not test 18, it's wrong answer in general. |
|||||||||||||
2014-12-25 16:23:20 Malinga
Getting wrong answer in 18th test case...any suggestions please ?? |
|||||||||||||
2014-12-18 14:10:04 Anubhav Balodhi
got AC, after lot of tries :-) |
|||||||||||||
2014-12-07 07:40:41 Retaliation
I got an internal error while submitting the code in python. id is 13082356 [reply by cyclops: Python 3.4 is not available on Pyramid cluster, but as all problems are being migrated to Cube this will soon be a non-issue.] Last edit: 2014-12-07 16:56:26 |
|||||||||||||
2014-05-14 07:22:42 Francis
after WA,TLE,SIGSEGV finally get AC in a simple way in O(n), but still TLE with backtrace and dfs. hints: (1)input format is: 1 CB rather than: 1 CB (2)test cases found in the forum and below 3 ABACAD 2 ABAD 3 DBADBA 3 ACBACB 3 ADCADC 7 ABCDABDADBDABD Last edit: 2014-05-14 07:23:12 |
|||||||||||||
2014-03-11 11:42:21 Rishav Goyal
weo ! nice indeed! |
|||||||||||||
2014-03-05 18:51:10 Kushagra Sinha
Finally AC ... not "simple" by any means ... it is an NP-complete problem ... do not waste time trying to find a "simple" closed-form solution ... |
|||||||||||||
2014-01-31 13:43:49 newbie
@author...i am getting wa many times...can you plz check submission no. 10976986 |