В г. Москве 9-11 класс Задача



Скачать 34.44 Kb.
НазваниеВ г. Москве 9-11 класс Задача
в г.Москве<><> <> <>9-11 класс<><> <> <>Задача
Дата21.04.2013
Размер34.44 Kb.
ТипЗадача
источник

Городской этап

Всероссийской олимпиады школьников по информатике в г.Москве

9-11 класс

Задача 1. ЛИФТ

Чтобы поднять на N-й этаж М-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков производится так: за подъем холодильника на один этаж требуется заплатить 200 рублей, за спуск на один этаж - 100 рублей. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в Витином доме есть лифт, ему возможно все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом К-м этаже, начиная с первого (то есть на этажах с номерами 1, К+1, 2К.+ 1, ЗК+1, ...). Требуется вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.

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

Во входном файле записаны три числа: М (2<=М<=100), N (2<=N<=M) и К (2<=К<=М-1), разделенные пробелами.

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

В выходной файл выведите одно число - минимальную стоимость подъема холодильника.

Примеры



вход

выход

20 7 4

200

20 7 2

0



^ Задача 2. ПИЛООБРАЗНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1,2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 - нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.

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

В первой строке входного файла записано одно число N (1последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10000 – члены последовательности.

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

В выходной файл выведите одно число - минимальное количество членов, которые необходимо вычеркнуть.

Примеры


вход

выход

5

1 2 3 1 2

1

5

1 2 1 3 2

0

3

1 2 3 4 5

3

5

1 1 2 1 1


2



Задача 3. ИНОСТРАННЫЕ ЯЗЫКИ

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

Папа знает словарный запас сына. Считается, что Вася мог иметь в виду словарное слово Р, если оно входит как подпоследовательность в слово Т (то, что он сказал). Другими словами, если существует такая возрастающая последовательность индексов i1 < i2 <... < im (где m - длина Р), что РЦ] = T[ij] для всех j = l..m.

Вам дается словарный запас Васи и сказанное им слово. Для каждого словарного слова надо определить, мог ли Вася иметь его в виду.

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

В первой строке входного файла содержится единственное число К.

В следующих К строках идут слова из словаря, по одному на каждой строке. На последней (К + 2)-й строке входного файла содержится слово, сказанное Васей, длиной не более 100 000 символов. Все слова в словаре непустые.

Все слова состоят из строчных латинских букв. Гарантируется, что суммарная длина слов из словаря не превышает 1 000 000 символов.

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

В выходной файл выведите К строк. В i-й строке должно быть записано 'YES', если Вася мог иметь в виду слово номер i из словаря, и 'NO' в противном случае.

k. in

Lout

4

hi

|hello

bye

oh

ahhinellation


YES

YES

NO

NO

5

want

drink

ink

ant

in

]iwanttosleep


YES

NO

NO

YES

YES

Добавить документ в свой блог или на сайт


Похожие:



Если Вам понравился наш сайт, Вы можеть разместить кнопку на своём сайте или блоге:
refdt.ru


©refdt.ru 2000-2013
условием копирования является указание активной ссылки
обратиться к администрации
refdt.ru