II этап (городской)

1. РОБОТЫ (20 баллов)

Сообщество роботов живет по следующим законам: один раз в начале года они объединяются в группы по 3 или 5 роботов. За год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых. Роботы собираются в группы так, чтобы собрать за год наибольшее количество. Каждый робот живет 3 года после сборки.

Задание:

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

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

Первая строка входного файла ROBOT.DAT содержит целые числа K и N - количество роботов, которые только что собраны, и число лет, через которые надо определить число роботов.

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

Первая строка выходного файла ROBOT.SOL содержит количество, насчитываемое в сообществе роботов через N лет.

ROBOT.DAT

25 2

ROBOT.SOL

196

2. ЦИФРА (30 баллов)

Задан диапазон целых чисел от А до В (1

Задание:

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

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

Первая строка входного файла DIGIT.DAT содержит два целых числа А и В.

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

Первая строка выходного файла DIGIT.SOL содержит целое число, являющееся наиболее часто встречающейся цифрой в записи всех простых чисел из заданного диапазона от А до В.

DIGIT.DAT

30 80

DIGIT.SOL

7

3. ВОКЗАЛ (40 баллов)

На вокзале N платформ. К каждой платформе подходит 2 пути, как показано на рисунке (платформы чередуются с путями). С каждого пути в течение каждого часа отправляется одна электричка. Время отправления электричек (в минутах) сохраняется в массиве A[N+1] со значениями от 0 до 59. Рассмотрим некоторую расстановку электричек по путям и найдем для каждого I - D_i - разницу во времени (в минутах) между отправлением с этой платформы. Найдем min D_i (I=1,...,N).

Задание:

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

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

Первая строка входного файла RAILWAY.DAT содержит количество платформ, вторая строка - время отправления электричек через пропуск.

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

Первая строка выходного файла RAILWAY.SOL содержит размещение электричек по номерам, вторая строка - min D_i для данного размещения.

RAILWAY.DAT

4

50 3 2 52 1

RAILWAY.SOL

5 1 3 4 2

48

III этап (областной)

1-й тур

1. ПАЛИНДРОМ (20 баллов)

Дана строка S. Число символов в ней не превышает 80.

Задание:

Напишите программу PALINDR, которая определяет минимальное количество символов, которые надо добавить к строке S (комментарий жюри: к концу строки), чтобы получился палиндром (т. е. строка, которая читается как слева направо, так и справа налево).

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

Единственная строка входного файла PALINDR.DAT содержит исходную строку.

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

Первая строка выходного файла PALINDR.SOL содержит количество добавленных символов, а вторая строка - полученный палиндром.

PALINDR.DAT

малшалаш

PALINDR.SOL

3

малшалашлам

2. МАССИВ (50 баллов)

Задан целочисленный одномерный массив, состоящий из N элементов (1<=N<=100)

Задание:

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

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

Первая строка входного файла MASSIF.DAT содержит целое положительное число N - число элементов исходного массива. Вторая строка входного файла содержит элементы массива через пробел.

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

Первая строка выходного файла MASSIF.SOL содержит количество вычеркнутых элементов исходного массива, а вторая строка - искомый массив, представляющий собой неубывающую последовательность. Если существует несколько вариантов решения, найдите любой из них.

MASSIF.DAT

8

9 -13 23 37 0 41 56 89

MASSIF.SOL

2

-13 23 37 41 56 89

2-й тур

1. КВАДРАТЫ (30 баллов)

В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной а метров, покупатель платил а^2 (комментарий: a*a) квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это, безусловно, можно было сделать, приобретя участки размером 1*1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. "Так мне будет легче общаться с Квадратной Налоговой Инспекцией", - сказал он. Сделка состоялась.

Задание:

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

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

Единственная строка входного файла SQUARE.DAT содержит целое положительное число N<=60000 - число квадриков, которое было у жителя.

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

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

SQUARE.DAT

344

SQUARE.SOL

3

2. ОТРЕЗКИ (70 баллов)

Некоторое количество отрезков расположено на прямой. Каждый отрезок задан координатами своих концов. Отрезки пронумерованы от 1 до N (0

Задание:

Напишите программу SEGMENT, определяющую число отрезков в наиболее длинной последовательности отрезков, вложенных друг в друга (т. е. каждый отрезок в последовательности, кроме последнего, содержит предыдущий; последний отрезок является наиболее длинным).

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

Первая строка входного файла SEGMENT.DAT содержит целое положительное число N - количество отрезков. Последующие N строк содержат по два целых числа из интервала [-10000,10000], которые задают координаты начала и конца отрезков. Отрезки пронумерованы согласно порядку их следования в файле исходных данных, начиная с 1.

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

Первая строка

Ответить

Не поместилось малость:

2. ОТРЕЗКИ (70 баллов)

Некоторое количество отрезков расположено на прямой. Каждый отрезок задан координатами своих концов. Отрезки пронумерованы от 1 до N (0

Задание:

Напишите программу SEGMENT, определяющую число отрезков в наиболее длинной последовательности отрезков, вложенных друг в друга (т. е. каждый отрезок в последовательности, кроме последнего, содержит предыдущий; последний отрезок является наиболее длинным).

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

Первая строка входного файла SEGMENT.DAT содержит целое положительное число N - количество отрезков. Последующие N строк содержат по два целых числа из интервала [-10000,10000], которые задают координаты начала и конца отрезков. Отрезки пронумерованы согласно порядку их следования в файле исходных данных, начиная с 1.

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

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

SEGMENT.DAT

4

-2 2

-1 1

-3 3

4 5

SEGMENT.SOL

3

2 1 3

Условия:

II этап:

- Turbo Pascal 7.0

- Borland C++ 3.0

- Norton Commander 5.0

3 часа

III этап:

- Turbo Pascal 7.0

- Borland C++ 3.0

- Norton Commander 5.0

2.5 часа - 1-й тур; перерыв 0.5 часа; 2.5 часа - 2-й тур

Ответить

Ответить