Олимпиадные задачи (с окончившихся олимпиад), ТОЛЬКО условия и ПРОВЕРЕННЫЕ решения Опции

[AlaRic]

Внимание!
В этой теме публикуем только сами задачи и их решения... Обсуждения - в отдельных темах!!!

------------------------------------------------------------

Автобусные билеты в рулоне пронумерованы от 000001 до 999999. Составить программу, выводящую на экран количество и номера (в несколько столбиков) всех счастливых билетов в некотором диапазоне, организовав запрос начального и конечного номера билета диапазона.
Примечание: Счастливым считать тот билет, у которого сумма первых трех цифр равна сумме трех последних.

------------------------------------------------------------

На судоверфь для докового ремонта пришли пять судов А, В, С, D, Е. В доке судоверфи может находиться только одно судно. Необходимое время стоянки в доке каждого судна различно и составляет соответственно МА, МВ, МС, MD и МЕ. Составить программу, определяющую и выводящую на экран очередность постановки судов в док, при которой суммарные потери от простоя судов минимальны.

------------------------------------------------------------

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

------------------------------------------------------------

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

------------------------------------------------------------

В клетках таблицы расставлены числа. Расставить в этих клетках K ферзей так, чтобы они друг друга не били и чтобы сумма чисел, ими закрываемых, была максимальной.

------------------------------------------------------------

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

------------------------------------------------------------

По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S-тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

------------------------------------------------------------

Заменить буквы цифрами так, чтобы соотношение оказалось верным:
ХРУСТ*ГРОХОТ=РРРРРРРРРРР

------------------------------------------------------------

При поступлении в вуз абитуриенты, получившие двойку на первом экзамене, ко второму не допускаются. В массиве A[n] записаны оценки, полученные на первом экзамене. Подсчитать, сколько человек не допущено ко второму экзамену.

------------------------------------------------------------

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

[Altair]

------------------------------------------------------------

<<Умная пчела>> (6 баллов, 1 секунда на тест)

__F
E__A
D__B
__C
В улье, изображенном на рисунке, ползает пчела. Соты улья представляют собой правильные шестиугольники, поэтому пчела может переползти из одной соты в соседнюю ней через любую из 6 граней. Каждое направление движения обозначается заглавными латинскими буквами от A до F, как показано на рисунке. При записи пути движения пчелы указывается направление движения и число последовательных переходов, совершенных в этом направлении. Так, например, 4 перехода в направлении В записываются как В4. Утром пчела начала свой путь и к вечеру оказалась в некоторой точке улья. Требуется написать программу, которая определяет, за какое минимальное число переходов пчела сможет вернуться в исходную точку, если известна полная запись маршрута. Размер улья можно считать бесконечным.

Формат входных данных:
Текстовый файл input.txt, содержащий одну строку, представляющую запись пути пчелы. Считать, что входная строка не более 80 символов и не содержит синтаксических ошибок. Между командами никакие разделители не ставятся. Число повторений, указанное после команды, находится в диапазоне от 1 до 999 включительно.
Формат выходных данных (вывод на экран):
Целое неотрицательное число - искомое минимальное число переходов
Пример 1
файл input.txt: A1B1C1D1E1
Выходные данные: 1
Пример 2
файл input.txt: A32B33D32A1
Выходные данные: 34

------------------------------------------------------------

<<Произведение дробей>> (12 баллов, 10 секунд на тест)Найти произведение N обыкновенных дробей, записав ответ в виде обыкновенной несократимой дроби.
Например, (3/8)*(2/8)*(14/9)=(7/30).
Формат входных данных:
Текстовый файл input.txt, в первой строке которого записано натуральное число N (1М<10000). В каждой из последующих строк указана пара натуральных чисел - числитель и знаменатель одной дроби. Данные таковы, что числители и знаменатели исходных дробей и числитель и знаменатель ответа после его сокращения не превосходят 30 000.
Формат выходных данных (вывод на экран):
Два натуральных числа - числитель и знаменатель ответа.
Пример:
файл input.txt
3 8
2 5
14 9
Выходные данные:
7 30

------------------------------------------------------------

«Часы» (12 баллов, 1 секунда на тест)
Каждая цифры в электронных часах изображена некоторыми из 7 штрихов. Штрихи пронумерованы сверху вниз, слева направо, как показано на рисунке. Цифры получаются следующими штрихами: 0-1,2,3,5,6,7; 1-3,6; 2-1,3,4,5,7; 3-1,3,4,6,7; 4-2,3,4,6; 5-1,2,4,6,7; 6-1,2,4,5,6,7; 7-1,3,6; 8-1,2,3,4,5,6,7; 9-1,2,3,4,6,7. Часы выпущены фирмой «VREMENI.NET», и поэтому в некоторых цифрах часть штрихов пропала. По имеющемуся изображению цифр на часах определить, какое время часы могли бы показывать. Все возможные варианты вывести в порядке возрастания времени.
Формат входных данных:
Текстовый файл input.txt содержит четыре строки (часы и минуты) по семь символов в каждой. Один символ может быть либо нулем либо единицей: 0 - соответствующий штрих в цифре не горит, 1 - штрих в цифре горит. Например, последовательность 1100010 означает, что горят штрихи 1, 2 и 6.
Формат выходных данных:
Текстовый файл output.txt, содержащий строки в формате ЧЧ:ММ - возможное время в порядке возрастания.
Пример:
файл input.txt:
1110111
1110111
1110111
1110111
файл output.txt:
00:00
00:08
08:00
08:08

------------------------------------------------------------

«Бассейн» (15 баллов, 1 секунда на тест)
Бассейн емкостью 500 м3 наполняется из трех труб A, В, С со скоростями потоков 20, 40 и 100 м3/ч соответственно. Слив производится через три стока D, Е, F с пропускными способностями 30, 50 и 80 м3/ч соответственно, либо через естественный перелив. Открытие и закрытие труб/стоков производится только на границе некоторого часа. Имеется журнал открытия и закрытия труб и стоков за сутки, при этом одна и та же труба/сток может за сутки открываться (закрываться) неоднократно. В один и TOT же час возможно несколько операций (над различными трубами/стоками). Определить, в течении какого количества часов (с точностью до 0.001 часа) вода переливалась через край бассейна при условии, что в 0 часов бассейн был пуст.
Формат входных данных:
В первой строке файла input.txt записано натуральное число N - количество записей в журнале. В каждой из N последующих строк указано целое число - номер часа и через пробел название трубы/стока. Если труба/сток была закрыта - она открывается, если открыта - закрывается.
Формат выходных данных (вывод на экран):
Действительное число с тремя десятичными знаками после запятой - количество часов, в течение которых
вода переливалась через край бассейна.
Пример:
файл input.txt:
4
0 A
5 С
10 F
11 С
Выходные данные:
2.667

------------------------------------------------------------

<<Стираем числа>> (25 баллов, 1 секунда на тест)
На доске записаны подряд натуральные числа от 1 до N (N < 1 000 000 000). Сначала стирают все нечетные числа. Из оставшихся стирают все числа, стоящие на четных местах, затем снова стирают все числа, стоящие на нечетных местах, и так далее, пока не останется одно число. Какое это число?
Пример:
Входные данные: 10
Выходные данные: 6

------------------------------------------------------------

<<Строки>> (30 баллов, 1 секунда на тест)
На вход подаются строки A и В. Необходимо преобразовать строку A в строку В с минимальным суммарным штрафом, который определяется следующим образом: a) удаление символа из строки A - х баллов; б) вставка символа в строку A - у баллов; в) замена символа в строке A на любой другой символ - z баллов. Напишите программу, определяющую минимальный суммарный штраф при преобразовании строки A в строку В.
Формат входных данных:
Файл input.txt, содержащий две строки A, В (длины строк < 255) и три целых неотрицательных числа х, у, z - по одному числу в строке.
Формат выходных данных (вывод на экран):
Одно целое неотрицательное число - минимальный суммарный штраф.
Пример:
файл input.txt:
мама
папа
1
1
10
Выходные данные:
4