7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2005

Подразделы

Другие разделы

Дата и время

25/04/2024 08:52:57

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи командных соревнований областной олимпиады школьников по информатике 2005

1. Шифровка

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Алиса и Боб решили шифровать свою переписку и начали обсуждать шифр.
Алиса: Предлагаю следующий простой шифр. Буква 'A' будет записываться как 1, 'B' – 2, и так далее до 'Z' – 26.
Боб: Это глупый шифр. Если я пошлю тебе слово 'BEAN' (боб), оно будет закодировано как 25114. Но это сообщение можно расшифровать несколькими способами.
Алиса: Ты прав, но другие слова бессмысленны. Кроме 'BEAN' получаются слова 'BEAAD', 'YAAD', 'YAN', 'YKD' и 'BEKD'. Я думаю, что можно догадаться о корректной расшифровке.
Боб: Ладно, это был слишком простой пример. А если я пошлю сообщение из 500 цифр или больше, как ты найдешь среди миллиардов возможных расшифровок единственно правильную?
Алиса: Так много? Не может быть…
Напишите программу, которая подсчитывает число возможных расшифровок некоторого сообщения, закодированного шифром Алисы.
Во входном файле содержится несколько строк с шифровками. Все шифровки корректны и не начинаются с цифры 0. Строка, содержащая только 0, служит признаком конца ввода и не обрабатывается.
В выходной файл для каждой шифровки из входного файла вывести в соответствующей строке число возможных расшифровок. Шифровки могут быть очень длинными, но гарантируется, что число расшифровок меньше `2^32`.

Пример ввода

25114
1111111111
4444444444
0

Пример вывода

6
89
1

2. Фотографии

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Программа для просмотра фотографий выводит их в прямоугольном окне слева направо. Если в одной строке недостаточно места для размещения очередного фото, оно выводится ниже всех фото первой строки у левого края. Очередные фото выводятся в новой строке слева направо, при необходимости создается очередная строка.
Например, окно для вывода имеет максимальную ширину 35, фотографии имеют размеры `10\ times\ 5`, `20\ times\ 12` и `8\ times\ 13`. Размещение фото в окне происходит как показано на рисунках. Окончательные размеры окна вывода равны `30\ times\ 25`, так как ширина первой строки равна `10+20=30`, а сумма высот двух строк `12+13=25`.
Напишите программу для определения окончательных размеров окна вывода.
В первой строке входного файла содержится целое число `W` (`1\ ≤\ W\ ≤\ 80`) – максимальная ширина окна вывода. Далее следует от одной до 15 строк. В каждой строке два целых числа через пробел – ширина (от 1 до `W`) и высота (от 1 до 100) очередной выводимой фотографии. Пара чисел `-1\ -1` обозначает конец списка фотографий.
В первой строке выходного файла вывести два целых числа, разделенных пробелом – окончательные ширину и высоту окна вывода.

Пример ввода

35
10 5
20 12
8 13
-1 -1

Пример вывода

30 25

3. Хоттабыч

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

- Прекрасная игра футбол, – сказал Хоттабыч, побывав на футбольном матче, на котором команда "Шайба" не без его участия забила 24 безответных гола команде "Зубило". – Надо помочь болельщикам и других команд.
Сказано – сделано. Хоттабыч создал частное предприятие, которое обязуется сделать любую команду чемпионом. Достаточно ему побывать на матче и нужный счет обеспечен, хоть 100:0. Но Хоттабыч не может влиять результаты матчей, которые уже завершились. Поэтому он должен тщательно выбирать болельщикам какой команды он сможет помочь. Для этого он должен определить команды, которые могли бы стать чемпионами при удачном стечении обстоятельств, а уж обстоятельства он обеспечит. Одна беда – Хоттабыч никогда не учился в школе и не знает арифметики, но для джинна это не проблема – один волосок из бороды, и перед ним команда программистов из Челябинской области.
- Повелеваю вам, о достойные отроки, написать программу, определяющую каким болельщикам стоит помогать, а каким – нет.
В чемпионате участвует `N` команд. Каждая команда должна сыграть по одной игре с каждой из других команд. Всего должно быть проведено `N*(N-1)/2` матчей. Если команда выигрывает, то она получает 3 очка, если проигрывает – 0 очков, а если матч закончится вничью, то обе команды получают по одному очку. Чемпионом становится команда, получившая наибольшее количество очков. При равенстве числа очков первое место занимает команда с наибольшей разницей между числом забитых и пропущенных мячей. Если и таких команд окажется несколько, то между ними проводятся дополнительные матчи. Каждая команда не сыграла еще как минимум один матч.
В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество команд `N` (`2\ ≤\ N\ ≤\ 8`), участвующих в турнире и количество уже прошедших матчей `M` (`0\ ≤\ M\ ≤\ N*(N-2)/2`). Далее следует `M` строк, в каждой строке содержатся четыре целых числа, разделенных пробелом – номера двух команд (от 1 до `N`), участвовавших в матче, и количество мячей (от 0 до 10), забитых командами.
В выходной файл вывести `N` строк, в `i`-ой строке нужно вывести YES, если `i`-ая команда может стать чемпионом, или NO, в противном случае.

Пример ввода

4 3
1 3 2 0
2 3 3 1
1 2 1 1

Пример вывода

YES
YES
NO
YES

4. Охрана

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Офисное здание известной корпорации расположен в центре Лондона. На квадратной крыше здания есть несколько люков. Чтобы предотвратить проникновение агентов-парашютистов в здание через эти люки, на крышу выпустили злую собаку. Но она вскоре свалилась с крыши. На заседании совета директоров было решено привязать следующую собаку в какой-нибудь точке крыши. Однако, если привязь будет слишком короткой, то собака не достанет до всех люков, а если слишком длинной, то снова упадет с крыши. Напишите программу, определяющую точку на крыше, куда нужно привязать собаку. Длина привязи должна позволять собаке доставать до центра каждого люка, но не переходить через край крыши (доставать до края крыши можно). Точка для прикрепления привязи должна иметь целые координаты и не может совпадать с координатами какого-нибудь люка. Если подходящей точки не окажется, программа должна предлагать приобрести вместо глупой собаки более дорогого и умного робота-охранника.
В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10`) – количество наборов исходных данных. Далее следует `N` блоков, в первой строке блока содержатся два целых числа, разделенных пробелом – размеры крыши `S` (`2\ ≤\ S\ ≤\ 40`) и количество люков `H` (`1\ ≤\ H\ ≤\ 50`). Далее следует `H` строк, в каждой строке два целых числа, разделенных пробелом – координаты люка `x` и `y` (`0\ <\ x\ <S`, `0\ <\ y\ <\ S`). Нет люков с одинаковыми координатами. Центр координат – один из углов крыши, а оси направлены вдоль краев крыши.
В выходной файл для каждого набора исходных данных вывести строку, содержащую либо слово dog и два целых числа `X` и `Y`, разделенных пробелами – координаты точки для прикрепления привязи, либо только слово robot, если точку найти не удастся. Если возможно несколько подходящих точек, то вывести точку с наименьшим `X`, а если и таких точек несколько, то точку с наименьшим `Y` среди точек с наименьшим `X`.

Пример ввода

3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3

Пример вывода

dog 3 6
robot
dog 2 2

5. Юбилей

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сегодня день рождения Теда (Ted). Ему исполнилось 100 лет. Вам нужно составить список его потомков, упорядоченный по убыванию их возраста. Но для составления списка имеется только список, содержащий имя отца, имя ребенка и возраст отца в момент рождения ребенка.
В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ <\ 100`) – количество потомков Теда. Далее следует `N` строк, в каждой строке содержатся два имени (не более 20 букв) и одно целое число, разделенные пробелами – имя отца, имя ребенка и возраст отца в момент рождения ребенка. Все имена уникальны и не содержат пробелов.
В выходной файл вывести `N` строк, в каждой строке нужно вывести имя потомка и его возраст в 100-летний юбилей Теда через пробел. Потомки должны быть выведены в порядке уменьшения их возраста. Потомки с одинаковым возрастом выводятся в алфавитном порядке.

Пример ввода

4
Ray James 40
James Beelzebub 17
Ray Mark 75
Ted Ray 20

Пример вывода

Ray 80
James 40
Beelzebub 23
Mark 5

6. Адресация

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

В электронных таблицах можно использовать два вида адресации. Первый вариант – обращаться к ячейке по номеру ее строки и столбца в форме R`n`C`m`, где `n` – номер строки, а `m` – номер столбца, например, R1C1. Второй вариант – использовать буквенные обозначения для столбцов. Столбец 1 обозначается A, столбец 2 – B, …, столбец 26 – Z. Следующие столбцы обозначаются двумя буквами, столбец 27 – AA, столбец 28 – AB, …, столбец 52 – AZ, столбец 53 – BA и так далее. Аналогично, после столбца ZZ идет столбец AAA, затем AAB и так далее. Напишите программу, которая преобразует адреса ячеек из формы R1C1 в форму A1.
Во входном файле содержится несколько строк. В каждой строке записан адрес ячейки в форме R`n`C`m` (`1\ ≤\ n\ ≤\ 300\ 000\ 000`, `1\ ≤\ m\ ≤\ 300\ 000\ 000`).
В выходной файл для каждой строки входного файла вывести строку с адресом соответствующей ячейки, преобразованным в форму A1.

Пример ввода

R1C1
R1C3
R299999999C26
R52C52
R53C17602

Пример вывода

A1
C1
Z299999999
AZ52
YZZ53

7. Список

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

Шеф Гессер приказал вам напечатать список сотрудников Ночного дозора, но, когда вы принесли ему список сотрудников в алфавитном порядке, сказал, что список выглядит неряшливо, и приказал, чтобы имена в списке были упорядочены сначала по их длине, а затем уже по алфавиту. Так как вручную выполнять эту работу вам было лень, вы решили написать специальную программу для переупорядочивания списка.
В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество сотрудников. Далее следует `N` строк, в каждой строке одно имя длиной от 1 до 20 букв без пробелов. Имена в списке упорядочены по алфавиту.
В выходной файл вывести `N` строк, в каждой строке нужно вывести одно имя из списка во входном файле. Имена в выходном файле должны быть упорядочены сначала по их длине, а затем уже по алфавиту.

Пример ввода

7
Анна
Антон
Иван
Игорь
Ольга
Светлана
Семен

Пример вывода

Анна
Иван
Антон
Игорь
Ольга
Семен
Светлана

8. Пирамида

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На колышек нанизаны `N` дисков различного размера. Ребенок умеет выполнять только одно действие – снимать `K` (`2\ ≤\ K\ ≤\ N`) верхних дисков, переворачивать их и снова нанизывать на колышек. Сейчас пирамидка собрана неправильно – диски на колышке не расположены в порядке увеличения их размера от вершины к основанию. Напишите программу, подсказывающую ребенку последовательность действий (не обязательно кратчайшую) для упорядочения пирамидки. Количество действий не должно превышать `2*N` (т.о. на установку каждого диска в правильное положение должно тратиться не более двух действий).
7198.jpg
    2 верхних -->     3 верхних -->     2 верхних -->
В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 30`) – количество дисков в пирамидке. Вторая строка содержит `N` целых чисел от 1 до `N`, разделенных пробелами – размеры дисков на пирамидке сверху вниз, каждое число встречается в строке только один раз.
В выходной файл вывести одну строку, содержащую сначала число `M` – количество действий, а затем `M` чисел от 2 до `N`, разделенных пробелами – действия, выполняемые ребенком для упорядочения пирамидки.

Пример ввода 1

3
1 3 2

Пример вывода 1

3 2 3 2

Пример ввода 2

5
4 3 2 5 1

Пример вывода 2

3 3 4 5

9. Zuma

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Zuma – это популярная компьютерная игра. Лягушку в центре экрана можно поворачивать с помощью мыши, а нажимая кнопку – стрелять шариками, которые вставляются в цепочку из катящихся разноцветных шаров. Если в цепочке в результате образуется группа из 3 или больше шариков, они аннигилируют. Рассмотрим упрощенную версию этой игры. Пусть есть цепочка из разноцветных шариков. Вы можете добавить в цепочку новый шарик некоторого цвета рядом с шариком того же цвета. Если при этом образуется группа, включающая новый шарик и содержащая 3 или более стоящих рядом шариков одного цвета, они аннигилируют, и вам добавляются очки, равные квадрату длины группы. После аннигиляции цепочка смыкается, и, если при этом слева и справа были шарики одного цвета, и при их соприкосновении образовалась новая группа из 3 или более одноцветных шариков, они опять аннигилируют и приносят вам очки. И так далее. В начальной цепочке могут быть группы из 3 или более одноцветных шариков, но они будут аннигилировать только при добавлении нового шарика в группу или соприкосновении с группой шариков того же цвета после аннигиляции.
Напишите программу, вычисляющую максимальное количество очков, которое вы можете получить после полного уничтожения начальной цепочки.
В первой строке входного файла содержится начальная цепочка, состоящая из букв от A до Z. Длина цепочки от 1 до 100 букв, соответствующим шарикам. Разные буквы обозначают разные цвета.
В выходной файл вывести строку, содержащую одно целое число – максимальное количество очков, которое можно получить после полного уничтожения начальной цепочки.

Пример ввода 1

AAABAAA

Пример вывода 1

45

Пример ввода 2

ABBBBBA

Пример вывода 2

54
loading