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

hide comments
Xx100m: 2012-01-26 01:48:06

Same Problem! Getting WA in test case 18.
I think their output file does not contain all the possible solutions (permutations) for the test case 18. The author of the problem needs to review his output file.

Neeraj Pradhan: 2012-01-07 19:06:59

Same problem! WHY do i get WA in test case 18..?

Abhishek Mishra: 2012-01-03 19:29:32

i m getting WA in case 18 plz explain.?PLZ EXPLAIN ASAP WHERE MY PROGRAM FAILS?

Last edit: 2012-01-03 21:18:00
Aerofoil Kite: 2011-12-26 13:37:02

WHY do i get WA in test case 18..?

Sotirios Nikoloutsopoulos: 2011-09-27 11:14:12

@Adrian Satja Kurdija

at testcase
3
DBADBA

My output is
CABCDC

is this wrong? if so why?

Adrian Satja Kurdija: 2011-09-14 09:34:58

@Sotirios: your code fails on the following test case:

3
ADCADC

Adrian Satja Kurdija: 2011-09-14 09:34:58

@Pranit: your code fails on the following test case:

3
DBADBA

Romal Thoppilan: 2011-09-14 09:34:58

...... TRickY but straightforward !

Adrian Satja Kurdija: 2011-09-14 09:34:58

Your solution prints debug information, like "Scanning to fill space"

Last edit: 2011-05-22 11:56:32
Ravi Kiran: 2011-09-14 09:34:58

Nice problem! :-)
Beware: Take care of initialisation of maximum length to 2*MAXN and not MAXN. (Took me 3 SIGABRT's to realise it.)

Last edit: 2011-04-27 09:12:01

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