Матч 45, Сворачивание бумаги (PaperUnfolding)

Лист бумаги, изображенный на рисунке 1, можно свернуть либо по часовой (рисунок 2) или против часовой стрелки (рисунок 3).

После каждого заворачивания бумага становится вдвое короче и вдвое толще. После определенного числа сворачиваний Вы решили развернуть листок. На нем остались метки от сгибов. Сгибы по часовой стрелке будем обозначать 1 (OUT), а по часовой 0 (IN).

Рассмотрим строку, полученную в результате конкатенации всех строк массива code. Необходимо определить, содержит ли она действительную последовательность меток сгибов листа бумаги после ее разворачивания. Вернуть следует соответственно “YES” или “NO”.

Например, на рисунке 6 изображен вдвое сложенный лист бумаги, метки сгибов которого после разворачиваний будут характеризоваться строкой “100”.

Класс: PaperUnfolding

Метод: string isValidUnfolding(vector<string> code)

Ограничения: code содержит от 0 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘0’ и ‘1’. Общее количество символов в массиве равно 2ⁿ - 1 для некоторого натурального n.

Вход. Массив строк code, описывающий сгибы бумаги после ее разворачивания.

Выход. Строка “YES” или “NO” в зависимости от того, содержит ли code действительную последовательность меток сгибов листа бумаги после ее разворачивания..

Пример входа

code

{}

{"1000110"}

{"000"}

{"10001101100111001000110010011101100011011001110110",

"00110010011101100011011001110010001100100111001000",

"11011001110110001100100111001000110110011100100011",

"00100111011000110110011101100011001001110010001101",

"10011100100011001001110010001101100111011000110010",

 "01110"}

Пример выхода

"YES"

"YES"

"NO"

"YES"

РЕШЕНИЕ

перебор

Входная строка содержит нечетное количество символов. Если строка code действительна, то первое сворачивание обеспечит равенство code[i] = 1 – code[code.size() – i – 1], i = 0, 1, …, code.size() / 2. Второе сворачивание обеспечит выполнение этого условия для первой и второй половины строки. При этом значение среднего символа может быть любым. Проверяем приведенное условие для всех префиксов строки code длин 2ⁱ – 1, i = n = code.size(), n – 1, n – 2, …, 1. Если оно истинно для всех префиксов, то возвращаем “YES”, иначе “NO”.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <numeric>

using namespace std;

int check(string code)

{

int i,len = code.size();

if (!len) return 1;

for(i = 0; i < len/2; i++)

if (code[i] == code[len-i-1]) return 0;

return check(code.substr(0,len/2));

}

class PaperUnfolding

{

public:

string isValidUnfolding(vector<string> code)

{

string cod = accumulate(code.begin(),code.end(),string());

return check(cod) ? "YES" : "NO";

}

};