| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Максимальное время работы на каждом тесте: | 10 секунд |
| Максимальная оценка: | 20 баллов |
Координатная плоскость разбита на единичные квадраты с целочисленными координатами. Требуется перечислить координаты левых нижних углов всех квадратов, которые пересекаются с прямой, проходящей через точки (x1, y1) и (x2, y2). Порядок перечисления квадратов может быть произвольным.
Во входном файле заданы целые числа x1 y1 x2 y2. Все числа по абсолютной величине не превосходят 10000. Указанные точки различны, то есть либо x1 ≠ x1, либо y2 ≠ y2.
Выведите в выходной файл координаты левых нижних углов единичных квадратов, которые имеют хотя бы одну общую точку с заданной прямой.
| input.txt | output.txt |
-1 -1 1 2 | -2 -2 -2 -1 -1 -2 -1 -1 -1 0 0 0 0 1 0 2 1 1 1 2 |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Максимальное время работы на каждом тесте: | 10 секунд |
| Максимальная оценка: | 20 баллов |
Имеется N коробок, каждая выкрашена в свой отдельный цвет. В эти коробки положено M шаров, тех же N цветов. Расположение шаров по коробкам известно. Требуется разложить шары по коробкам так, чтобы в каждой коробке оказались только шары ее цвета и для перекладывания потребовалось минимальное число действий. Одним действием считается обмен двух шаров местами или перекладывание одного шара из коробки в коробку.
Во входном файле записаны числа N и M (2 ≤ N ≤ 10, 1 ≤ M ≤ 100). Далее следуют M пар чисел, задающих цвет очереднего шара и номер коробки, в которой он находится.
В первую строку выходного файла выведите число действий K, требуемуемых для перекладывания шаров. Далее выведите К строк с тремя или четырьмя числами, описывающими действия в том порядке, в котором их следует производить. Если это перекладывание, то первое число означает номер коробки, откуда вынимается шар, второе число задает цвет шара, а третье число . номер коробки, в которую шар кладется. Если это действие обмен, то первые два числа означают номер коробки и цвет первого шара, а вторые два числа задают номер коробки и цвет второго шара.
| input.txt | output.txt |
4 8 1 3 2 4 3 2 4 1 2 4 1 1 2 4 3 4 | 6 1 4 4 3 1 3 3 1 2 3 3 4 2 2 4 2 2 4 2 2 |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Максимальное время работы на каждом тесте: | 10 секунд |
| Максимальная оценка: | 20 баллов |
В конце полного приключений и опасностей путешествия Индиана Джонс добрался до входа в подземный замок крестоносцев, где хранится чаша Грааля. В руках у него находится план замка, состоящего из M этажей размера N×N. Хотя путь до чаши тернист и извилист, у профессора археологии есть все, что беспрепятственно передвигаться по замку – кнут, лестницы и динамит. Узкие коридоры и тупики-ловушки не могут остановить Джонса, единственной проблемой остаются преграды, которые необходимо взрывать, рискуя быть похороненным под обломками древнего замка. Напишите программу, определяющую наименьшее количество стен, которые необходимо уничтожить, чтобы можно было добраться до чаши Грааля.
В первой строке входного файла записаны числа M и N (1 ≤ M, N ≤ 20). Далее приведены планы M этажей, каждый из которых задан таблицей N×N символов, где символ "." (точка) означает свободное пространство, а "#" соответствует монолитной стене. Местоположение Индианы указано буквой "I", а чаши Грааля – буквой "G". Планы этажей разделяются пустыми строками.
Выведите в выходной файл наименьшее количество стенок, которые требуется уничтожить, чтобы по образовавшимся полостям можно было добраться до чаши Грааля. Далее выведите в выходной файл план замка с разрушенными стенками в том же формате, что и в файле входных данных. Разрушенную стенку обозначайте на плане знаком "-". Пример входных данных выходных данных
| input.txt | output.txt |
3 4 #### ...# #### ###I .### ##.. ###. #### G### ###. ###. ###. | 2 -### ...# #### ###I .### ##.. ###. ###- G### ###. ###. ###. |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Максимальное время работы на каждом тесте: | 10 секунд |
| Максимальная оценка: | 40 баллов |
Во входном файле заданы числа N и M (0 ≤ M, N < 10100). Определите, сколько есть чисел, не превосходящих N, в десятичной записи которых встречается число M. Все числа рассматриваются без ведущих нулей.
В первой строке входного файла записано число N, а во второй – число M.
Выведите в выходной файл искомое количество чисел. Сами числа выводить не надо.
| input.txt | output.txt |
99 1 | 19 |