Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Учение об администрировании представляет собою совокупность принципов, правил и приёмов, имеющих целью облегчение управления предприятиями всех типов...полностью>>
'Документ'
Самым великим даром, ниспосланным человеку Богом (Разумом Вселенной, Сознанием Космоса), является потенциальная возможность, частично реализуемая спо...полностью>>
'Документ'
Додаток 13до пункту 7.9 Інструкції про порядок перерахування, обліку та витрачання страхових коштів Фонду соціального страхування від нещасних випадк...полностью>>
'Книга'
"Книга о табу" – возможно, наиболее известная из книг Алана Уотса. В ней автор исследует не признаваемое, однако довольно сильное табу – на...полностью>>

Задача А. Однорукий программист Ограничение по времени: 2 секунды

Главная > Задача
Сохрани ссылку в одной из сетей:

Университетская олимпиада по программированию

среди студентов 1-3 курсов

Оренбург 2003г.

Задача А. Однорукий программист

Ограничение по времени: 2 секунды.

Один опытный программист Нео уже давно освоил десятипальцевый метод печати. По этому методу каждую клавишу нажимает всегда один и тот же палец. Например, буквы Q, A и Z нажимаются мизинцем левой руки. А буквы Y, U, H, J, N, M указательным пальцем правой руки.

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

ВВОД

Входной файл содержит набор строк. В первой строке указано число пальцев F (0≤F≤10) и число слов W (0≤W≤10 000). Во второй строке через пробел перечислены номера пальцев, которые не испачканы. 1 соответствует мизинцу левой руки (буквы Q, A и Z), 2 безымянному (буквы W, S и X) и т.д. Мизинец правой руки имеет номер 10 (буква P). 5 и 6 - это большие пальцы рук, нажимают пробел.

Далее в каждой новой строке содержится слово. Слова могут содержать только буквы латинского алфавита в верхнем регистре. Длина слов не превышает 50 символов.

В таблице ниже приведены номера пальцев и буквы, которые печатаются этими пальцами.

Номер пальца

Печатаемые буквы

1

Q, A, Z

2

W, S, X

3

E, D, C

4

R, F, V, T, G, B

5, 6

Пробел

7

Y, H, N, U, J, M

8

I, K

9

O, L

10

P

ВЫВОД

Выходной файл должен содержать количество слов, которые Нео может напечатать, не испачкав клавиатуры и сами слова. Каждое слово находится на новой строке. Слова выводятся в том же порядке, в котором они указаны во входном файле.

Примечание: вам гарантируется, что выходной файл не будет содержать более 1000 слов.

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

6 7

1 3 5 7 8 9

HELLO
WORLD

THIS
IS

A

CONTEST

ZOO

3

HELLO

A

ZOO

Задача B. Протекающая крыша

Ограничение по времени: 5 секунд.

Нео живет в квартире на последнем этаже. И у него есть одна проблема – в дождь и по весне крыша начинает протекать. Так получилось, что крыша протекает почти только в одном месте, вдоль одной стены. На этой стене прибиты книжные полки. Книги с полки он уже давно переложил к себе под кровать, но проблема, тем не менее, не решена.

Нео, как любой программист, очень ленив. У него никогда нет времени ни на то чтобы залатать крышу, ни на то чтобы нормально заняться полками. Поэтому и полки у него весят все криво, и вода, стекая по ним, продолжает течь к соседям. Чтобы устранить последние, Нео не придумал ничего лучше чем ставить ведро там, где течет. Помогите ему определить эти места.

ВВОД

Входной файл состоит из двух секций.

Сначала идет число полок N (0≤N≤1000), каждая из которых задана координатами x1, y1, x2 и y2 в следующих N строках. Все четыре координаты полки находятся на отдельной строке, и разделены одним пробелом между собой.

Примечание: полки между собой не пересекаются (не имеют общих точек), не примыкают друг другу, нет ни вертикальных (x1 всегда не равно x2), ни горизонтальных полок (y1 всегда не равно y2).

Во второй части входного файла указаны точки на стене, в которых начинает течь вода. Сначала идет число точек M (0≤M≤500). Далее в M строках указаны координаты точек x и y, разделенные одним пробелом между собой.

Все указанные во входном файле координаты целого типа и не отрицательны.

В случае, когда вода попадает точно на верхнюю точку полки, считается, что она не падает вниз, а течет по полке.

ВЫВОД

Для каждой точки протечки в выходной файл нужно выдать одно число – координату x, где вода закончит свой путь, пройдя все полки.

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

4

14 7 3 4

11 13 16 11

1 10 6 7

2 1 4 3

3

10 4

14 14

2 13

10

16

2

ПРИМЕЧАНИЕ

Рисунок, приведенный ниже, объясняет пример.

Задача C. Неправильный сумматор

Ограничение по времени: 2 секунды.

Однажды Нео делал программную эмуляцию двоичного сумматора. Сумматор – это устройство для сложения двух чисел. Эмуляция у него получилась, числа складывались, но только не совсем правильно. Результат получался неправильным, из-за того, как выяснил Нео позже, что его сумматор не учитывал перенос от сложения двух предыдущих битов. Так если сложить 789 и 123 сумматором Нео, то получится 878:

(789) 1100010101

+

(123) 0001111011

=

(878) 1101101110

ВВОД

Входной файл содержит набор строк. В каждой строке записано два числа a и b разделенных пробелом. Входной файл заканчивается двумя нулями. Во входном файле не более 1000 строк.

ВЫВОД

Для каждой строки входного файла нужно выдать найденное значение K. Значение K есть разница между реальной суммой чисел a и b, и суммой полученной сумматором Нео.

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

789 123

89745 45

34580 6883

666 777

0 0

34

2

1024

1040

Задача D. Вычисление формул

Ограничение по времени: 4 секунды.

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

Нео написал программу буквально за пять минут, но у него появилось сомнение в правильности ее работы. Напишите программу, проверяющую вычисления программы Нео.

ВВОД

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

Константы задаются следующим образом: в первой строке записано количество констант N (0≤N≤26), далее следует N строк с заданием значений константам. Константы именуются одной латинской буквой в верхнем регистре. Далее, через один пробел, следует значение константы.

В первой строке секции описания формул записано количество формул M (0≤M≤1000). Затем в M строках записаны формулы. До знака равно записывается сама формула, после – ответ, который выдала программа Нео. В строке с формулой не содержится никаких символов кроме +, -, =, цифр и латинских букв в верхнем регистре. Все выражения записаны корректно. Длина выражения не длиннее 250 символов.

ВЫВОД

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

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

4

A 6

B 78

D 90

X -5

3

1+2+3=6

A+B+D+X=66

D-B-12+X=-5

YES

NO

YES

Задача E. Светофоры

Ограничение по времени: 5 секунд.

Очень часто работа находиться далеко от дома. Вот и Нео в таком положении. Каждый день ему приходиться добираться до работы на машине. Очень часто, добираясь на работу, он останавливается на перекрестках на красный свет.

Вот так, в очередной раз, застряв, он начал размышлять и искать закономерности. Он заметил, что все светофоры имеют цикл длиной несколько секунд. Половину этого цикла горит красный, 5 секунд желтый и оставшееся время зеленый. Ему стало интересно, могут ли все светофоры вдоль улицы, по которой он едет, одновременно загореться зеленым светом, хотя бы на секунду, если знать длительность цикла каждого светофора. Помогите Нео разобраться.

ВВОД

Входной файл содержит набор строк. В каждой строке задан список длительности циклов для каждого светофора вдоль улицы. Каждый список заканчивается нулем. В списке всегда не менее двух и не более 100 значений. Длительность циклов задается целым числом. Например, число 25 означает, что 20 секунд горит зеленый, 5 секунд - желтый и 25 – красный.

Следует учесть, что после красного следует зеленый свет, а не желтый. Длительность цикла не может быть менее 10 и превышать 90 секунд. Входной файл заканчивается тремя нулями.

ВЫВОД

Для каждой строки входного файла в выходной нужно записать время, через которое все светофоры будут гореть зеленым светом. Известно, что в первый момент времени все светофоры горят зеленым. Другими словами, в выходной файл нужно выдать время, через которое светофоры вновь загорятся зеленым. Формат времени можно увидеть в примере.

Если через 5 часов светофоры так и не загорятся зеленым светом, нужно выдать надпись – «No solution in 5 hours» (без кавычек).

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

19 20 0

30 25 35 0

0 0 0

00:00:40

00:05:00

Задача F. Кофейные пятна

Ограничение по времени: 2 секунды.

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

Однажды к нему пришел его друг Морфеус и поразился состоянию исходных текстов программ Нео. «Сколько же ты вылил на них кофе?!» - поразился он.

А Нео после этого задался вопросом, а и в правду сколько? Упрощая себе задачу, он стал просто считать пятна на листах. О состоянии текстов его программ вы можете сделать вывод сами, посчитав пятна самостоятельно.

ВВОД

Входной файл содержит несколько строк. В первой содержится размер страницы, на которой считаются пятна. Размер представлен двумя числами: N количество строк (0<N≤50) и M количество столбцов (0<M≤50). Далее следуют N строк длиной M символов. Чистые участки листа представлены символом “.”, испачканные кофе – “#”.

ВЫВОД

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

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

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

7 8

......##

.##.##.#

.#.#....

.#...##.

.#..####

.##.#..#

..#.####

5

Задача G. Большие числа

Ограничение по времени: 3 секунды.

Как-то раз Нео написал неплохую программу шифрования. Для того чтобы расшифровать (или зашифровать) данные нужен ключ. Ключ в свою очередь является обыкновенной суммой двух чисел. Чтобы избежать элементарного взлома и исключить перебор, Нео для ключей использовал длинные числа до 250 знаков. Он утверждает, что может сложить два таких длинный числа в уме. Напишите программу, которая проверит Нео.

ВВОД

Входной файл содержит набор строк. Количество строк кратно трем. В первой строке записано первое слагаемое, во второй – второе, в третьей ответ который дал Нео. Далее все повторяется. Входной файл заканчивается концом файла. Во входном файле не более 3000 строк.

ВЫВОД

Для каждых трех чисел в отдельной строке выдать CORRECT, если Нео верно сложил числа, и правильный ответ в противном случае.

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

2

2

4

812347602347075893475023479

28347987523465876234934

234897234652634823487

45683450982387623

3475683846583465230409834578345763847

3475683846583465230455518029328151470

679234568230

470

45743628340987537489570

CORRECT

812375950334599359351258413

CORRECT

679234568700

Задача H. Простые суммы

Ограничение по времени: 7 секунд.

Изучая математику, программист Нео наткнулся в литературе на очень интересную гипотезу Гольдбаха-Эйлера, которая гласит, что любое натуральное четное число можно представить в виде суммы двух простых чисел. Например: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 100 = 47 + 53, 21000 = 17 + 20983, и так далее.

Эта гипотеза не доказана и до сих пор, лишь проверена для очень больших чисел на ЭВМ. Однако, Нео очень заинтересовал вопрос сколькими различными способами можно представить данное четное число в виде суммы двух простых чисел. Например, 10 = 5 + 5 и 10 = 3 + 7. Таким образом, число 10 представимо в виде суммы двух простых чисел двумя способами. Число различных способов, означает, что 10 = 3 + 7 и 10 = 7 + 3 считаются одинаковыми разложениями. Помогите ему решить эту проблему.

ВВОД

Входной файл содержит не более 1000 строк. В каждой строке дано четное число N (4≤N≤50000). Ввод заканчивается строкой содержащей ноль. Это число не следует обрабатывать.

ВЫВОД

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

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

6

12

26

72

734

0

1

1

3

6

15

Задача I. Числа Колатца

Ограничение по времени: 7 секунд.

Функция Колатца обладает свойством, что длина последовательности чисел порождаемой функцией не может быть непосредственно вычислено от аргумента. Функция Колатца определенная для целых чисел имеет вид:

Данная функция определяет одну из известных нерешенных задач в математике. Задача состоит в доказательстве, что для любого целого начального значения Xn≥1, эта функция порождает последовательность, которая сходится к значению 1. Ниже приведено несколько примеров. В квадратных скобках указано начальное значение Xn, далее приведена порождаемая последовательность, в фигурных скобках приведена длина порождаемой последовательности.

[10] 5 16 8 4 2 1 {6}

[13] 40 20 10 5 16 8 4 2 1 {9}

[14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}

[19] 58 29 88 44 22 ... 2 1 {20}

[32] 16 8 4 2 1 {5}

[1] 4 2 1 {3}

Ваша программа должна считать из входного файла два числа L и H. Требуется найти какое начальное значение Xn, в промежутке [L, H], которое порождает самую длинную последовательность. Если два и более числа из промежутка порождают наидлиннейшую последовательность, то вывести меньшее число.

ВВОД

Во входном файле через пробел находятся два целых положительных числа L и H.

(1≤L, H100000, L H)

ВЫВОД

В выходной файл вывести на одной строке через пробел числа V и S, где Vминимальное число из промежутка [L, H], порождающее самую длинную последовательность, Sколичество чисел в полученной последовательности.

ПРИМЕР ВХОДНОГО ФАЙЛА (input.txt)

ПРИМЕР ВЫХОДНОГО ФАЙЛА (output.txt)

1 20

18 20



Скачать документ

Похожие документы:

  1. По узкой горной тропинке шел человек. Казалось, он никуда не торопится, это выглядело тем более странным, что мир постепенно окутывали сумерки

    Документ
    По узкой горной тропинке шел человек. Казалось, он никуда не торопится, это выглядело тем более странным, что мир постепенно окутывали сумерки. В этих местах и днем-то ходить опасно, а пробираться по ним ночью… С низкого грозового
  2. G-модератора-1 Ветхий завет

    Документ
    (9 священных книг эзотерически-сатирическо-философски-исторической мистификации с моралью высшей пробы и поучительнейшими наставлениями для правильных пацанов)
  3. Учебное пособие по интерпретации образов и сновидений

    Учебное пособие
    О23 Образ и бессознательное: Учебное пособие по интерпритации образов и сновидений /Пер. с итальянского - М.: ННБФ «Онтопсихология», 2 , с.448, ил. 13.
  4. Форд и Сталин: о том, как жить по-человечески

    Документ
    В связи с тем, что разные системы один и тот же файл по-разному раскладывают по страницам, необходимо обновить оглавление. Для обновления оглавления перейти в режим просмотра страницы и ввести в оглавление курсор, после чего нажать “F9”.
  5. Сергей проснулся от храпа, который раздавался как раз над его правым глазом

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

Другие похожие документы..