SPOJ.com - Problem ABCD

ABCD - Colours A, B, C, D

no tags

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 Next >

	Aman: 2015-05-30 20:23:24 I think all possible permutations are not considered in the solution that's why its giving wrong ans on 18th test case... can any tell me what is 18th case.I have tried all possible test cases...can't find the error....
	CoNtRaDiCtIoN: 2015-05-27 12:31:32 awesome problem :)
	Rajat (1307086): 2015-03-28 00:56:52 There are several solutions, but if you apply the correct logic you will get one and only one. Nice problem indeed.
	chamini2: 2015-02-13 23:46:34 It's not test 18, it's wrong answer in general.
	Malinga: 2014-12-25 16:23:20 Getting wrong answer in 18th test case...any suggestions please ??
	Anubhav Balodhi : 2014-12-18 14:10:04 got AC, after lot of tries :-)
	Retaliation: 2014-12-07 07:40:41 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
	californiagurl: 2014-07-19 11:22:20 once you figure how it can be done in O(n), it just isn't a trouble anymore. AC in first O(n) attempt . though dfs seems like the more natural solution,, it sure gives TLE
	Francis: 2014-05-14 07:22:42 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
	Rishav Goyal: 2014-03-11 11:42:21 weo ! nice indeed!

Submit solution!

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