(100 баллов) Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Школьный этап олимпиады по программированию 201
6

год.

9
-
11 классы

Задача 1
.
Король

(100 баллов)

Поле шахматной доски определяется парой чисел (a, b), каждое от 1 до 8, первое число задает
номер столбца, второе


номер строки. Заданы две клетки. Определите
, может ли шахматный
король попасть с первой клетки на вторую за один ход. (Король ходит только на одну клетку по
горизонтали или по вертикали или по диагонали)

Формат входных данных


Даны 4 целых числа от 1 до 8 каждое, первые два задают начальную клетку,

вторые два
задают конечную клетку. Начальная и конечная клетки не совпадают. Числа записаны в отдельных
строках.

Формат выходных данных

Программа должна вывести YES, если из первой клетки ходом короля можно попасть во
вторую, или NO в противном случае.

П
ример

Ввод

Вывод

1

2

2

2

YES


Задача 2. Подготовка к олимпиаде (100 баллов)

Юра решил подготовиться к региональной олимпиаде по информатике. Он выбрал на сайте
informatics.mccme.ru
N
задач, чтобы решить их на каникулах. В первый день Юра решил
K
задач,

а
в каждый следующий день Юра решал на одну задачу больше, чем в предыдущий день.
Определите, сколько дней уйдет у Юры на подготовку к олимпиаде.

Входные данные

Программа получает на вход два целых положительных числа
N
и
K
(
1
 ≤
N
,
K

≤ 
30000)
,
записанны
х в отдельных строках


количество задач, которые намерен решить Юра, и
количество задач, которые он решил в первый день подготовки.

Выходные данные

Программа должна вывести единственное число


количество дней, которое потребовалось Юре
для решения зада
ч.

Примечание

В примере в первый день Юра решит 3 задачи, во второй день


4, в третий день


5, итого на
решение 10 задач у Юры уйдет 3 дня.

Примеры

Входные данные

Выходные данные

10

3

3


Задача

3
.
Воды слонам! (100 баллов)

Кроме Земли, пандорианцы

уже много тысячелетий исследуют и другие планеты. Большой
интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований
на Земле финансирование исследований на Арракисе было существенно урезано, и местным
агентам
-
исследовател
ям пришлось искать дополнительные источники дохода.

К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило
труда проанализировать политические, экономические и психологические тенденции, а также
некоторые другие факторы, не

имеющих названий на земных языках и на основе этих данных
точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода
на этой планете является главной ценностью после золота, на которое эту воду можно купить.

Изначально па
ндорианцы обладают некоторым запасом золота. Они решили в один из дней года
купить на все это золото воды
, а в какой
-
то последующий день продать всю купленную воду и
получить прибыль за счет разницы стоимости. Конечно же, пандорианцы хотят максимизировать
свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и
продажи воды!

Входные данные

В первой строке задано целое число
N (
2 ≤
N
≤ 1000)


количество дней в году на планете
Арракис.

Во второй строке заданы
N
целых положительных чисел
a
i
(
1 ≤
i

N
, 1 ≤
a
i
≤ 5000
), задающих
стоимость воды на Арракисе в день
i
.

Выходн
ые данные

Выведите два целых числа: первое число



номер дня, в который стоит купить воду, второе
число



номер дня, в который следует воду продать. Дни нумеруются с единицы. Если
оптимальных пар дней для покупки/продажи несколько, то выведите любую из ни
х.

Выведите два нуля, если покупка и продажа воды по указанной схеме не принесет пандорианцам
прибыли.

Примеры

Входные данные

Выходные данные

6

10 3 5 3 11 9

2 5

4

5 5 5 5

0 0


Задача 4.
Сканворд (100 баллов)

Маленький Тѐма недавно начал изучать бук
вы. На днях ему попался сканворд, который
разгадывала его любимая бабушка. Артѐм долго крутил его в руках, но так и не смог понять, для
чего он нужен, и что с ним нужно сделать. Тогда в его маленькую голову пришла большая и
светлая мысль.

Сканворд


разнов
идность кроссворда. Полем сканворда является прямоугольная
таблица, состоящая из
M

строк и
N

столбцов, внутри которой расположены вопросы, на которые
нужно дать ответ, изображения и клетки для записи ответа.

Для каждого столбца Тѐма захотел выбрать одну бу
кву, которая встречается в нѐм чаще всего.
Если таких букв несколько, то Артѐм выбирает любую из них. Затем все выбранные буквы Артѐм
записывает в одну строку и получает слово. Обратите внимание, что Тѐма слишком мал, чтобы
различать регистр букв, т.е. он
считает строчные и прописные буквы одинаковыми.

Артѐм хочет, чтобы записанное слово было как можно красивее. Слово
S
1

считается красивее
слова
S
2
, если
S
1

лексикографически меньше
S
2
.

Помогите Артѐму найти самое красивое слово из всех, которые он может пол
учить.

Входные данные

Первая строка содержит целые числа
N

и
M
, разделѐнные пробелом

(
1 ≤ 
N
, 
M
 ≤ 100
).
В следующих
M

строках записано по
N

символов, описывающих клетки сканворда. Если в клетке стоит пробел,
значит бабушка не смогла отгадать слово, к которо
му относится данная клетка. Символ '#'
означает, что эта клетка является частью изображения. Символ '?' означает, что в этой клетке
находится вопрос. В противном случае в клетке записан один из символов ['A'..'Z', 'a'..'z'],
означающих, что бабушка отгадал
а слово, к которому относится эта клетка. Регистр буквы
значения не имеет.

Гарантируется, что в каждом столбце есть хотя бы одна буква.

Выходные данные

Выведите самое красивое слово из тех, которые может получить Артѐм.

Примеры тестов

Входные данные

Выход
ные данные

4 4

Aguc

?ful

ag#l

word

agul




Приложенные файлы

  • pdf 11078507
    Размер файла: 212 kB Загрузок: 3

Добавить комментарий