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

[AlaRic]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[renesko]

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



B. Волшебные вектора
Назовем упорядоченный по неубыванию набор из N натуральных чисел волшебным N-вектором, если сумма этих чисел равна их произведению. Задано число N. Найдите все волшебные N-вектора.
Например, существует 3 волшебных 5-вектора:
1 1 1 2 5
1 1 1 3 3
1 1 2 2 2
Ограничение на N поставьте сами.


C. Интервалы
Петя совершил хакерский налет на сервер компании Macrohard, в результате чего ему достался объектный файл, в котором содержится скомпилированный код некоторой функции secret. Эта функция берет в качестве параметра целое число и возвращает 0 либо 1.
Петя решил исследовать эту функцию и выяснить, что она делает. С этой целью он хочет вызвать ее для всех чисел от 1 до 106 и те значения параметра, на которых функция выдает 1 вывести на экран. Однако, поскольку количество различных чисел, которые придется вывести на экран может оказаться очень велико, то Петя хочет выводить их в виде интервалов подряд идущих чисел, причем если интервал имеет длину 1, то выводить только одно число. Например, вместо
1,3,4,5,6,7,8,10,12,20,21,22,23,24,…
Петя хочет выводить
1,3-8,10,12,20-24,…
Напишите программу, которая выведет значения параметра, на которых функция выдает 1, в нужном формате. Считайте, что Ваш язык программирования дополнен функцией secret:
function secret(x: longint): integer;
int secret(long int x);
function secret(x as long) as integer
Помните, что компьютер, на котором Петя запустит свою программу довольно слабый, и у него мало оперативной памяти, поэтому хранить все значения, на которых функция вернет 1 в памяти даже в виде интервалов может оказаться невозможным.


D. Наименьшее кратное подмножество
Задано множество из N натуральных чисел: . Требуется найти такое минимальное положительное M, чтобы можно было выбрать M чисел из заданного множества так, чтобы их сумма делилась на N. Например, для множества из пяти элементов
1 3 1 7 1
M=2, т.к. можно выбрать 2 числа (3 и 7), сумма которых 3+7=10 делится на N=5, а одно число кратное 5 выбрать нельзя.
Задано число N1000 и числа . Найти соответствующее минимальное положительное M, либо выяснить, что такого M не существует, т.е. нельзя выбрать из заданного множества несколько чисел, чтобы их сумма делилась на N.


E. K двоичных единиц
Найдите количество чисел Z, удовлетворяющих неравенству , таких, что в записи двоичного разложения Z используется ровно единиц. ( , ) Например, если A=10; B=20; K=2, то таких чисел 5 (это числа 10=10102; 12=11002; 17=100012; 18=100102; 20=101002).
Помните, что перебор всех чисел неэффективен, так как при данных ограничениях занимает слишком много времени.



F. Частотный анализ
Дан текст, в котором встречаются слова, состоящие из букв русского и латинского алфавитов и цифр, знаки препинания, пробелы и переводы строк. Требуется найти количество вхождений каждого слова в этот текст и вывести слова отсортированными по невозрастанию этого количества. Для каждого слова при выводе в скобках указать количество его вхождений в текст. Например, для текста
один, два - это 2, три один два, много слов один
надо вывести
один(3) два(2) это(1) 2(1) три(1) много(1) слов(1)
Слова, которые встречаются в тексте одинаковое количество раз, должны быть выведены в том порядке, в котором они впервые встречаются в тексте.

другие задачи и коментарии здесь------------>  _________Microsoft_Word.doc ( 68.5 килобайт ) Кол-во скачиваний: 1827