Дана полоса клетчатой бумаги длиной N клеток и шириной 1 клетка, в которой некоторые клетки покрашены в черный цвет, а остальные — в белый. Такая полоса называется палиндромом, если последовательность черных и белых клеток при просмотре этой полосы слева направо оказывается такой же, как при просмотре справа налево.
Вам дана полоса длины N. Требуется разрезать ее на полоски, являющиеся палиндромами, так, чтобы количество получившихся полосок было строго меньше величины (2/5)N + 3.
Первая строка входного файла содержит число N — длину исходной полосы (N — натуральное число, не превышающее 100000). Далее идет N чисел, описывающих раскраску полосы: 0 означает черную клетку, а 1 — белую.
В выходной файл выведите в возрастающем порядке номера клеток исходной полосы, после которых нужно сделать разрезы.
Примеры
| Входные данные | Выходные данные | Пояснение |
| 6 0 1 0 1 1 0 | 3 5 | Из исходной полосы мы получим 3 полосы-палиндрома, сделав разрезы после 3-й клетки (то есть между 3-й и 4-й) и после 5-й (то есть между 5-й и 6-й) |
| 6 0 1 1 0 0 0 | 1 3 | Данную полосу можно разрезать на 2 полосы-палиндрома, однако по условию не требуется искать решение с минимальным числом получившихся полосок — достаточно, чтобы число полосок удовлетворяло указанному в условии ограничению. |
| 5 0 0 0 0 0 |
| Исходная строка уже является палиндромом, поэтому можно ничего не разрезать |
Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.
Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.
3 5 X.... ..... .....
XXXXX XXXXX XXXXX
3 3 ... ..X ...
/X\ X.X \X/
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.
В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
ABC
ABC
O2A3O2AO
OAAOOOAAO
A2B3C4D5E6F7G
ABBCCCDDDDEEEEEFFFFFFGGGGGGG
Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.
На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.
3
0.00 30.00 25.00
0.00 -30.00 25.00
40.00 0.00 16.00
NO
-833.3333340000 -552.7707973875
833.3333340000 552.7707973875
3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00
YES
В фирме MacroHard работают \(N\) сотрудников, каждый из которых получает зарплату, выражающуюся целым числом рублей. Известно, что ни один сотрудник не получает меньше 5000 рублей, и никто не получает больше 100000 рублей. Также известно, что средняя зарплата сотрудника в этой фирме выражается целым числом копеек и составляет \(A\) рублей \(B\) копеек.
Журналист, готовя публикацию об этой фирме, решил привести зарплаты всех сотрудников. Однако оказалось, что это коммерческая тайна. Журналиста это не смутило, и он решил придумать всем сотрудникам зарплаты. Однако у него возникла сложность – для правдоподобности должны выполняться все общеизвестные ограничения (зарплаты должны выражаться целым числом рублей из диапазона от 5000 до 100000, и вычисление средней зарплаты должно в точности приводить к результату \(A\) рублей \(B\) копеек).
Помогите ему! Напишите программу, которая по введенным числам \(N\), \(A\), \(B\) «придумает» и выведет \(N\) зарплат.
Вводятся натуральное число \(N\) (1 ≤ \(N\) ≤ 100), натуральное число \(A\) (10000 ≤ \(A\) ≤ 30000) и целое число \(B\) (0 ≤ \(B\) ≤ 99).
Выведите \(N\) целых чисел, выражающих зарплаты сотрудников в рублях. Если возможных вариантов распределения зарплат несколько, выведите любой из них. Если распределить зарплаты с учетом наложенных условий невозможно, выведите одно число 0.