Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1891

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1891

Removing Coins in the Kem Kradan

 

By Marcos Kawakami, Universidade de São Paulo BR Brazil

Timelimit: 1

Andréh and his friend Andréas are board-game aficionados. They know many of their friends would love to go on a trip to Phuket, Thailand, and so they want to challenge them at Kem Kradãn, a

traditional Thai board game.

Kem Kradãn (เกมกระดาน) has been played since the 2nd century AD. The game is played with N coins where each coin has two faces, one of which is golden and the other is white. The game starts with all coins arranged in a line on the board and they are numbered from 1 to N from left to right. When a coin numbered i has its golden face up, it can be removed from the board. When this is done, the coins numbered i-1 and i+1 are flipped, if they're still there. The goal is to remove all game coins.

Before challenging their friends, Andréh and Andréas want to make sure their initial configurations have a solution. To help them, given an initial configuration, you must determine if it is possible to remove all game coins and, if so, you must show how to do it.

 

Input

 

The first line of the input has an integer T corresponding to the number of instances.

Each instance is given by an integer N (0 ≤ N ≤ 105), the number of coins, followed by a string of length N, containing the characters 'B' (white face up) and 'D' (golden face up). This string represents the initial configuration of the game.

 

Output

 

For each instance, print in a single line Y if it is possible to remove all the coins, and N otherwise. If it is possible to remove all the coins, print another line containing a space-separated sequence of N integers corresponding to the sequence in which the coins can be removed. In the case that there is more than one possible sequence, choose the lexicographically smallest.

 

 

 

Input Sample Output Sample

4

3

BDB

5

DBDDB

5

DDBDD

6

DBBBBB

Y

2 1 3

Y

1 2 4 3 5

N

Y

1 2 3 4 5 6

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <set>
#include <vector>
#define MAXN 100010
using namespace std;
int descartado[MAXN], estado[MAXN], TC, n;
char entrada[MAXN];
set < int> possiveis, alternativos;
void shuffle(int x) {
    if (x < 0) return;
    if (x >= n) return;
    if (descartado[x]) return;
    if (estado[x] == 1) {
        estado[x] = 0;
        possiveis.erase(x);
    } else {
        estado[x] = 1;
        possiveis.insert(x);
    }
}
int main() {
    scanf("%d", &TC);
    while (TC--) {
        scanf("%d", &n);
        scanf("%s", entrada);
        vector<int> resposta;
        possiveis.clear();
        for (int i = 0; i  <  n; i++) {
            descartado[i] = 0;
            estado[i] = int(entrada[i] == 'D');
        }
        for (int i = 0; i  <  n; i++) {
            if (estado[i] == 1) {
                possiveis.insert(i);
            }
        }
        for (int i = 0; i  <  n; i++) {
            if (possiveis.empty()) {
                break;
            }
            int davez = *(possiveis.begin());
            descartado[davez] = 1;
            estado[davez] = 0;
            shuffle(davez - 1);
            shuffle(davez + 1);
            resposta.push_back(davez);
            possiveis.erase(davez);
        }
        if (resposta.size() == n) {
            printf("Y\n");
            printf("%d", resposta[0] + 1);
            for (int i = 1; i  <  n; i++) {
                printf(" %d", resposta[i] + 1);
            }
            printf("\n");
        } else {
            printf("N\n");
        }
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
4
3
BDB
5
DBDDB
5
DDBDD
6
DBBBBB

Output

x
+
cmd
Y
2 1 3
Y
1 2 4 3 5
N
Y
1 2 3 4 5 6
Advertisements

Demonstration


Previous
#1890 Beecrowd Online Judge Solution 1890 Putting Plates on the Tuk-tuks Solution in C, C++, Java, Js and Python
Next
#1893 Beecrowd Online Judge Solution 1893 Moon Phases Solution in C, C++, Java, Js and Python