Решение задачи Троичный XOR с Codeforces

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


Число называется троичным, если оно содержит только цифры 0, 1 и 2. Например, следующие числа являются троичными: 1022, 11, 21, 2002.

Вам задано длинное троичное число x. Первая (самая левая) цифра числа x гарантированно является 2, остальные цифры числа x могут быть 0, 1 или 2.

Определим троичную операцию XOR ⊙ над двумя троичными числами a и b (оба имеют длину n) как число c=a⊙b длины n, где ci=(ai+bi)%3 (где % — операция взятия по модулю). Другими словами, сложим соответствующие цифры и возьмем остатки от сумм при делении на 3. Например, 10222⊙11021=21210.

Ваша задача — найти такие троичные числа a и b (оба длины n и без лидирующих нулей), что a⊙b=x и max(a,b) — минимально возможный.

Вам нужно ответить на t независимых наборов входных данных.

Код

#include <bits/stdc++.h>
using namespace std;
 
int main() {string s,a,b;
	int t;cin>>t;
	while(t--)
	{
		int n,c=0;cin>>n;cin>>s;a="";b="";
		for(int i=0;i<n;i++)
		{
			if(!c)
		{	if(s[i]=='2')
			{a+='1';b+='1';}
			else
			if(s[i]=='1')
			{
				c=1;
				a+='1';b+='0';
			}
			else
			if(s[i]=='0')
			{a+='0';b+='0';}
		}
		else
		b+=s[i],a+='0';
		}
		cout<<a<<"\n"<<b<<"\n";
	}
	return 0;
}

         

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




Комментарии

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