Решение задачи Киану Ривз с Codeforces

Без пояснения   Просмотров: 22


После исполнения роли Нео в легендарной трилогии «Матрица», Киану Ривз начал сомневаться: возможно, мы действительно живем в виртуальной реальности? Чтобы это выяснить, ему нужно решить следующую задачу.

Будем называть строку состоящую только из нулей и единиц хорошей, если она содержит различное число нулей и единиц. К примеру, строки 1, 101, 0000 являются хорошими, а 01, 1001 and 111000 не являются хорошими.

Дана строка s длины n состоящая только из нулей и единиц. Мы должны разрезать s на минимально возможное количество подстрок s1,s2,…,sk таким образом, чтобы все они были хорошими. Более формально, мы должны найти минимальную по количеству строк последовательность хороших строк s1,s2,…,sk такую, что их конкатенация (последовательное склеивание) равно s, то есть s1+s2+⋯+sk=s.

К примеру, разрезания 110010 на 110 и 010 или на 11 и 0010 удовлетворяют условию, так как 110, 010, 11, 0010 являются хорошими, а на меньшее число разрезать 110010 нельзя, так как 110010 хорошей не является. В то же время, разрезание 110010 на 1100 и 10 не удовлетворяет условию, так как обе строки не являются хорошими. Также, разрезание 110010 на 1, 1, 0010 не удовлетворяет условию, так как не является минимальным, хоть все 3 строки и являются хорошими.

Можете ли вы помочь Киану? Можно показать, что решение всегда существует. Если существует несколько оптимальных решений, выведите любое из них.

Код

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,n,s=0;
	string str;
	cin>>n;
	cin>>str;
	for(i=0;i<n;i++)
		s+=(int)str[i]-48;
	if(s==n-s)
		cout<<"2\n"<<str[0]<<" "<<str.substr(1,n);
	else
		cout<<"1\n"<<str;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться