Задача A. Шахматная доска
Условие
— Это не шахматная доска! Это черт знает что! — возмущался
Иван Петрович.
— Ну, не было у меня целой шахматной доски под рукой, — пытался оправдываться
Петр Иванович, — дед у меня такой, как проиграет мне в шахматы,
так сразу разобьет доску об угол стола. Только щепки летят... Вот, склеил
из кусков...
— Но это же просто нонсенс! Как можно играть на такой доске... Вы,
наверное, каждую клетку из отдельной доски вырезали!
— Да нет, всего-то три куска склеил...
Иван Петрович и Петр Иванович решили поиграть в шахматы. Однако у них
не нашлось целой шахматной доски, поэтому Петр Иванович склеил
ее из нескольких кусков. Каждый кусок вырезан из правильной шахматной доски.
Однако Иван Петрович считает что на полученной доске просто невозможно
играть в шахматы. Поэтому вместо игры в шахматы они решили выяснить —
а из какого минимального количества кусков шахматной доски Петр Иванович
мог склеить эту доску. Помогите им!
Например, доска на рисунке слева может быть склеена из четырех кусков, как
показано справа.
Формат входного файла
Входной файл содержит восемь строк, состоящих из восьми символов
W и
B,
не разделенных пробелами.
Символ
W обозначает белую клетку, а символ
B — черную.
Формат выходного файла
Выведите в выходной файл одно число — минимальное количество кусков, из которых могла
быть склеена заданная во входном файле доска.
Примеры тестов
| № |
Входной файл (board.in) |
Выходной файл (board.out) |
|---|
| 1 |
WBWBWBBW
BWBBWBWB
WBWWBWBW
WBWWBWWB
BWBBWBWB
WBWBWWBW
BWBWBBWB
WBWBWWBW
|
4
|
Задача B. Гиперпространства
Условие
Недавно Миша узнал о существовании многомерных пространств. В n-мерном
пространстве точка задается набором из n вещественных координат.
Миша сразу же догадался как измерить расстояние между двумя точками —
расстояние между точками (x1, x2, …, xn) и (y1, y2, …, yn)
равно sqrt((x1 − y1)2 + (x2 − y2)2 + … + (xn − yn)2).
Для начала он стал исследовать отрезки. Отрезок, соединяющий точки
(x1, x2, …, xn) и (y1, y2, …, yn) — это множество точек
с координатами
(λ x1 + (1 − λ)y1, λ x2 + (1 − λ)y2, …, λ xn + (1 − λ)yn),
где λ ∈ [0,1].
Миша называет точку с целочисленными координатами видимой, если на отрезке,
соединяющем эту точку с началом координат (точкой, все координаты которой равны нулю),
не лежит других целочисленных точек. Например, в двумерном пространстве точка
(2, 1) является видимой, а точка (2, 2) — нет, во втором случае соответствующий отрезок
содержит точку (1, 1).
Теперь Мишу заинтересовал вопрос — а в пространстве какой минимальной размерности
существует видимая точка, расстояние от которой до начала координат равно sqrt(l).
Также его интересует, а сколько видимых точек в пространстве этой размерности
находятся на расстоянии sqrt(l) от начала координат.
Помогите ему решить эту задачу.
Формат входного файла
Входной файл содержит целое число l.
Формат выходного файла
На первой строке выходного файла выведите n — минимальную размерность
пространства, в которой существует искомая точка. На второй строке выведите
n целых чисел — координаты любой такой точки. На третьей строке
выведите количество таких точек в пространстве размерности n.
Ограничения
1 ≤ l ≤ 50,000.
Примеры тестов
| № |
Входной файл (hyper.in) |
Выходной файл (hyper.out) |
|---|
| 1 |
8
|
5
1 2 1 1 1
160
|
Задача D. Посылка
Условие
Почтовый поезд уже готов к отправлению, и тут рядом с
платформой останавливается дилижанс, из которого
выскакивает сам начальник почтового отделения.
Он подбегает к поезду и вручает Бобу посылку.
Боб заходит внутрь вагона и обнаруживает, что места на
такую большую посылку уже точно не осталось.
Свободна только одна маленькая полочка под самым потолком.
Но начальник уверяет, что эту посылку просто необходимо
доставить. Похоже, придется переставлять коробки
с одной полки на другую. А ведь времени осталось так мало!
Согласно инструкции, Боб может действовать следующим образом:
за одно действие он может взять коробку с некоторой полки
и перенести ее на другую полку.
Для каждой полки известен максимальный вес коробки,
которую можно на ней разместить.
При этом, поскольку времени очень мало, Бобу нужно постараться
освободить полку для вновь прибывшей посылки,
совершив минимальное количество действий.
К сожалению, Боб не очень быстро соображает, так что вы
очень поможете ему, если напишете программу, которая
найдет для него нужный порядок действий.
Формат входного файла
На первой строке записано целое число n —
количество полок в вагоне.
На второй строке содержатся n целых чисел ci, разделенных пробелами.
i-е из них задает максимальный вес предмета, который можно
поставить на полку номер i.
На третьей строке задано n − 1 натуральное число wi — веса коробок,
стоящих на соответствующих полках (последняя полка изначально пуста).
В последней строке задан вес a новой посылки, которую требуется поставить.
Формат выходного файла
На первой строке выходного файла запишите минимальное число действий m,
которое придется совершить Бобу.
На второй строке выведите описания этих действий — m − 1 натуральное число,
задающие, предмет с какой полки перемещается на ту, которая свободна в
текущий момент времени (последним действием ставится привезенная посылка).
Если поставить посылку невозможно ни при какой последовательности действий,
выходной файл должен содержать число −1.
Ограничения
1 ≤ n ≤ 100,000,
1 ≤ wi ≤ ci ≤ 109.
Примеры тестов
| № |
Входной файл (parcel.in) |
Выходной файл (parcel.out) |
|---|
| 1 |
4
4 5 7 2
1 3 4
6
|
3
1 3
|
| 2 |
4
4 3 7 2
1 2 5
6
|
-1
|
