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 >

	slothsphereoj: 2024-03-07 11:03:40 Good question. We have a pair of rows... Please ignore this case for your testing: 3 CCADAD CC are same characters in a pair... the Q said "there are no two adjacent cells of the same colour"... Possible cases: [input] 3 ABDBCD [possible output] CDACAB [input] 3 ABACAD [possible output #1] CDBDBC [possible output #2] DCBDCB [input] 3 DBADBA [possible output #1] ACBCDC [possible output #2] CACBCD
	nikhil_0305: 2020-02-23 12:24:55 nice q
	jopdhiwaala: 2020-02-22 05:28:09 Nice question Last edit: 2020-06-25 06:28:11
	aarya_121: 2019-07-24 11:38:27 READ IT AGAIN AND AGAIN.*super simple. Last edit: 2019-07-24 11:44:23*
	adi1992: 2019-01-16 12:23:13 nice question Last edit: 2019-01-16 12:24:03
	rc_4594: 2018-09-30 09:26:06 If you are thinking of a greedy solution which places the least frequency letter which is valid(which does'nt match with the adjacent letters) at every point try this 3 CCADAD
	nadstratosfer: 2018-01-27 16:56:15 Got best time in Py3 with the same O(n) code that TLEd until I made a certain assumption about test cases. Also, with 18 separate testfiles my runtime of 0.37s mostly measures the total of interpreter startups (same code ACs in 0.08s in Py2 where interpreter launches faster). Pointless trying to optimize when AC itself is a lottery. Frustratingly stupid way of setting an otherwise interesting problem. Last edit: 2018-01-27 17:38:19
	mark42: 2018-01-27 09:49:44 AC in one go.. seriously this piece of spoj made my day
	biswajitk123: 2018-01-12 22:32:40 awesome logic!simply beautiful!!!
	d_y1997: 2017-12-22 13:19:18 18th testcase if wrong .. try: 3 ABDBCD possible ans: CDACAB

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