Задача A. cd-DOS
Условие
В операционной системе cd-DOS поддерживается иерархическая структура
каталогов, аналогичная MS-DOS. Полный путь к каталогу здесь
записывается как строка, содержащая последовательность имен
каталогов, разделенных знаком "\", имени диска в пути не указывается.
Например, "ff\sample\path".
В отличие от MS-DOS, cd-DOS понимает только упрощенный вариант
команды cd (Change Directory - смена текущего каталога). При помощи
этой команды в cd-DOS можно перейти только на один уровень вверх или
вниз по иерархии каталогов (например, команды "cd .." или "cd MyDir"
разрешены, но "cd ..\..\otherdir" или "cd some\moredir" запрещены).
Требуется по данным полным путям к двум каталогам определить
минимальное количество команд cd, необходимых для перехода из одного
каталога в другой.
Формат входного файла
В первой строке входного файла записан первый путь, во второй — второй путь.
Формат выходного файла
Единственное число — количество команд cd.
Ограничения
Длина строк во входном файле — от 1 до 255 символов.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
a\b\c
a\c\d
|
4
|
| 2 |
same
same\a
|
1
|
Задача B. Таймер
Условие
Таймер — это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени.
Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
Формат входного файла
В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями).
При этом оно удовлетворяет ограничениям: ЧЧ — от 00 до 23, ММ и СС — от 00 до 60.
Во второй строке записан интервал времени, который должен быть измерян.
Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей).
Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены.
Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0.
А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
Формат выходного файла
В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал.
При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days.
Например, если сигнал прозвучит на следующий день - то +1 days.
Примеры тестов
| № |
Входной файл (g.in) |
Выходной файл (g.out) |
|---|
| 1 |
01:01:01
48:0:0
|
01:01:01+2 days
|
| 2 |
01:01:01
58:119
|
02:01:00
|
| 3 |
23:59:59
1
|
00:00:00+1 days
|
Задача C. Квадраты
Условие
Рассмотрим целочисленную решетку размера N x N.
Пусть некоторые ее узлы покрашены в белый, а некоторые - в черный цвет.
Требуется определить количество квадратов на заданной решетке, то есть квадтаров,
вершины которых совпадают с узлами заданной решетки и покрашены в одинаковый цвет.
Например, на решетке размера 4 x 4, изображенной на рисунке 1 такой квадрат один, он показан на рисунке 2.
Формат входного файла
Первая строка входного файла содержит число
N - размер решетки.
Следующие
N строк содержат по
N символов из множества {"0", "1"} и задают решетку.
Если точка с координатами (i, j) покрашена в белый цвет, то j-ый символ i-ой строки есть "0",
а если в черный, то "1".
Формат выходного файла
Количество квадратов на решетке из входного файла.
Ограничения
2 ≤
N ≤ 50.
Примеры тестов
| № |
Входной файл (f.in) |
Выходной файл (f.out) |
|---|
| 1 |
4
0100
0011
1000
0111
|
1
|
Задача D. Переворот бокалов
Условие
На столе стоят в ряд
N бокалов, пронумерованных слева направо от 1 до
N.
Первоначально все бокалы стоят дном вниз. Над бокалами можно выполнить операцию переворот.
За один переворот ровно
M любых бокалов переворачиваются так, что те бокалы, которые
стояли дном вниз, оказываются перевернутыми вверх дном, а остальные из
M бокалов ставятся вниз дном.
Требуется за минимальное количество переворотов добиться того,
чтобы все бокалы оказались перевернутыми вверх дном, или определить, что это невозможно.
Формат входного файла
Входной файл содержит числа
N и
M.
Формат выходного файла
Выходной файл должен в первой строке содержать число переворотов
K,
а в последующих
K строках - разделенные пробелами номера бокалов,
которые нужно перевернуть при очередном перевороте.
Если перевернуть все бокалы невозможно, то выходной файл должен содержать
единственное число 0 (ноль).
Ограничения
0 ≤
M ≤
N ≤ 1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
7 3
|
3
1 2 3
3 4 5
3 6 7
|
