п»ї
Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов
\(1\) и \(2\), которые плохо смешиваются одна с другой. У неё также есть две различных
колбы бесконечной емкости наполненные \(N\) \((1 \leq N \leq 10^5)\) единицами
смесей жидкостей этих двух цветов. Смеси делятся на слои отдельных цветов.
Поэтому колбы можно рассматривать как строки
\(f_1f_2\ldots f_N\) Рё
\(s_1s_2\ldots s_N\)
РіРґРµ
\(f_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц
от дна первой колбы,
\(s_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц
от дна второй колбы,
Беси хочет разделить эти жидкости так, чтобы каждая колба содержала
все единицы жидкости одного цвета.
У Беси есть также пустой стакан бесконечной емкости, чтобы помочь ей решить
её задачу. Когда Беси делает одно переливание, она переливает всю жидкость цвета
\(i\) наверх из одной колбы в другую или в стакан.
Определите минимальное количество переливаний, чтобы разделить жидкости
по колбам и серию переливаний, которые необходимо для этого выполнить.
Не имеет значения какого цвета жидкость будет содержаться в какой колбе,
но стакан должен быть пустым.
В каждом тесте будет \(T\) (\(1 \leq T \leq 10\)) подтестов с параметром
\(P\) для каждого подтеста.
Предположим, что минимальное количество переливаний, чтобы разделить
жидкости по колбам равно \(M\).
- если \(P=1\), Вы получите баллы, если выведите только \(M\).
- Если \(P=2\), Вы получите баллы, если выведите целое число \(A\) такое, что
\(M \leq A \leq M+5\), за которым следует \(A\) строк, которые конструируют
это решение за \(A\) ходов. Каждая строка должна содержать описание источника
и приемника жидкости (\(1\), \(2\), или \(3\) для стакана).
Колба-источник должна быть непустой перед переливанием,
и нельзя переливать в себя.
- If \(P=3\), Вы получите баллы, если выведите \(M\), за которым
следует правильная конструкция, использующая это количество ходов.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\), количество подтестов.
Для каждого подтеста следующая строка содержит
\(N\) Рё
\(P\),
насколько изначально заполнена каждая колба и тип запроса.
Следующая строка содержит
\(f_1f_2f_3\ldots f_N\) представляющая первую колбу.
\(f_i \in \{ 1,2 \}\) Рё
\(f_1\) представляет дно первой колбы.
Следующая строка содержит
\(s_1s_2s_3\ldots s_N\) представляет вторую колбу, где S
1
\(s_i \in \{ 1,2 \}\) b
\(s_1\) представляет дно второй колбы.
Гарантируется, что в каждой из этих входных строк числа
\(1\) и \(2\) встретятся не менее, чем по одному разу.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите одно целое число представляющее
минимальное количество переливаний, необходимое чтобы разделить жидкости по двум колбам.
В зависимости от вида запроса, Вы должны вывести корректную конструкцию.
ПР�МЕРВВОДА:
6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222
ПР�МЕРВЫВОДА:
4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2
В первых трёх подтестах минимальное количество переливаний, чтобы
разделить жидкости по колбам равно \(4\).
Вот как это делается
1: 1221
2: 2211
3:
После шага "1 2":
1: 122
2: 22111
3:
После шага "1 3":
1: 1
2: 22111
3: 22
После шага "2 1":
1: 1111
2: 22
3: 22
После шага "3 2":
1: 1111
2: 2222
3:
В последнем подтесте пминимальное количество переливаний - \(5\).
Однако, поскольку \(P=2\),
то данная конструкция с \(6\)-ю ходами корректна, посокльку она не более чем на \(5\)
переливаний от оптимального ответа.
ОЦЕН�ВАН�Е:
- Тесты 2-6: \(P = 1\)
- Тесты 7-11: \(P=2\)
- Тесты 12-21: Нет дополнительных ограничений.
Дополнительно, гарантируется, что \(T=10\) для всех подтестов, кроме
тех что приведены в условии.
Автор: Suhas Nagar