Решение задачи Троичный XOR с Codeforces
Без пояснения   Просмотров: 198
Число называется троичным, если оно содержит только цифры 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 независимых наборов входных данных.
Вам задано длинное троичное число 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 независимых наборов входных данных.