Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 4
Подождите немного. Документ загружается.
(количество прибывших автобусов), во второй строке
содержится последовательность целых чисел - время
прибытия автобусов на остановку , задаваемое в минутах
целыми числами от 0 до 59.
Выходные данные помещаются в текстовый файл Output.txt,
каждая строка которого должна содержать данные для
одного маршрута: время прибытия первого автобуса и
интервал движения , заданный в минутах . Порядок
расположения маршрутов не важен. Если возможно
несколько решений , достаточно получить только один из
вариантов.
Пример
Input.txt Output.txt
17 0 13
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
3 12 5 8
Задачи по номинациям
Номинация «Физкультура и спорт»
«Эстафета»
В лыжной эстафете 4 по 10 км участвуют N команд. В
судейскую коллегию поступает информация о том , за какое
время каким участником пройден очередной этап эстафеты .
а) Расположить участников каждой отдельной команды по
возрастанию результатов эстафеты , т.е. первой в команде
должна стоять фамилия участника, показавшего
наименьшее время прохождения этапа 10 км среди других
членов команды , последней - фамилия участника с
наибольшим временем прохождения этапа.
б) Определить победителя в индивидуальном первенстве
среди всех участников эстафеты .
в) Определить команду - победительницу, набравшую
наименьшее суммарное время
Номинация «Искусство»
"Конкурс пианистов"
В конкурсе пианистов выступления участников оценивает
жюри, в состав которого входят шесть музыкантов.
Максимальная оценка, которую может выставить каждый
член жюри, 10 баллов, минимальная – ноль. Требуется
разработать алгоритм (программу) для
- построения линейной таблицы , содержащей фамилии и
инициалы участников, и прямоугольной таблицы ,
содержащей оценки каждого члена жюри;
- определения фамилии участника – победителя конкурса;
- номер самого строгого члена жюри.
Номинация «Первокурсники»
"Предметы ".
Требуется распределить N предметов (N<15), масса
каждого из которых известна, в два рюкзака так, чтобы
наполненные рюкзаки минимально отличались друг от
друга по весу .
Технические требования
Входные данные берутся из текстового файла Input.txt. В его
первой строке находится число N, вторая строка содержит
последовательность чисел, задающих вес предметов по
порядку их номеров.
Результат выводится на экран в виде двух строк , каждая из
которых содержит последовательность номеров предметов,
помещаемых в рюкзак, и его вес.
Номинация «Информатика, как общеобразовательная
дисциплина»
"Морской бой "
Требуется смоделировать поле для игры в «морской бой»
и подсчитать количество одно-, двух-, трех- и
четырехпалубных кораблей , расположенных на нем .
Корабли не могут быть «изогнутыми» и друг с другом не
соприкасаются . Поле для игры имеет размер 10х10 клеток .
Технические требования
Входные данные – количество занятых клеток N и набор из
N пар целых чисел (координат клеток ) - берутся из
текстового файла INPUT.TXT, его первая строка содержит
целое число N, в каждой следующей строке – координаты
занятой клетки.
Результаты – тип кораблей и их количество - выводятся
построчно на экран.
Номинация «Информатика как профилирующая
дисциплина»
"Лабиринт"
Лабиринт представляет собой набор одинаковых
комнат, каждая из которых может иметь от 1 до 4 дверей в
соседние комнаты . Путник , войдя в лабиринт, долго
блуждал по нему, пока не нашел выход. Каждый раз, при
переходе в другую комнату , он делал запись в блокноте,
отмечая направление движения из комнаты в комнату
буквами: N – север , E – восток , S – юг, W- запад.
Требуется по заданному описанию маршрута путника
определить самый короткий путь, состоящий из комнат, в
которых путник побывал , и ведущий из входа в лабиринт к
его выходу .
Технические требования
Входные данные берутся из текстового файла Input.txt, в
первой строке файла указывается количество переходов из
комнаты в комнату , каждая следующая строка содержит
одну из букв N, E, S, W.
Выходные данные – строка литер – выводится на экран и в
текстовый файл Output.txt.
Номинация «Студенты гуманитарных специальностей»
"А и Б "
Введенный текст представляет собой предложение , в
котором встречается перечисление двух объектов,
связанных союзом «и» . Требуется поменять местами слова,
соединенные этим союзом . Например , текст «А и Б сидели
на трубе» после преобразования должен иметь вид «Б и А
сидели на трубе» .
Секция прикладного программного обеспечения
Задание 1
Создать эмблему школы -олимпиады по программированию
и компьютерному моделированию .
Требования:
1) Работа может быть выполнена в любом редакторе.
2) Помимо графических элементов эмблема должна
содержать название или аббревиатуру названия школы -
олимпиады .
Задание 2
Создать гипертекстовый документ, содержащий
информацию об авторе, его группе и учебном заведении, в
котором учится автор .
Требования:
1) Дизайнерское решение должно включать фото автора,
фото группы (подгруппы ), работающей в компьютерном
классе и фото здания вуза.
2) Все файлы должны содержаться в одном каталоге.
Ссылки должны быть относительными.
Задание 3
Средствами Excel создать файл, содержащий решение
задачи произведения двух матриц размера 4х4.
Требования:
1) Наличие заголовков.
2) Сохранение формул.
3) Расположение исходных данных и решения на одном
экране.
English version
(Перевод выполнен студентами 5 курса факультета ПММ
Дмитрием Сустретовым, Даниилом Бронякиным и
Виктором Хатько под руководством доктора филологических
наук, проф. М .А.Стерниной)
The first tour of the competition will start on 17 September 2002.
Any student of any institute of higher education of Voronezh region
and neighboring regions is welcome to participate.
The first tour will be held via Internet. If the institution does
not have Internet connection, the tasks can be obtained in one of the
following ways:
1. Get them from the organizational committee
(Universitetskaya pl, 1, room 8).
2. Go to the nearest Internet salon.
3. Send task request via e-mail to t0140@fromru.com.
University affiliates (Lisky, Verkhny Mamon, Stary Oskol) can get
the tasks from the university representatives.
There will be two tasks in the first tour: the first one is of general
character, the second one considers participants' specialty.
The organizational committee warns that the programs differing only
in identifiers will be dismissed.
The solutions should be sent to t0140@fromru.com or brought to the
organizational committee personally before 5pm 24 September
2002. It is required that in the very beginning of the program source
code you place the descriptive commentary containing the following
information:
- the author’s full name
- the name of the institute of higher education
- the address of the institute of higher education
- the name of the department
- the majoring subject
- the form of education (day/evening department)
- the dean’s full name and degree
- the full name and degree of the teacher the author considers
his/her trainer (if present).
- the home address
- the e-mail, the homepage URL, ICQ UIN
Only works created by students will be considered by the
organizational committee.
The competition is divided into two sections:
- algorithmization and programming
- applied software
The participant can choose the task from any section.
The first tour has the following nominations:
- 1
st
year students
- students having informatics among major subjects (students
majoring in applied mathematics, mathematics, mechanics,
physics, computer science, CAD/CAM, computing systems,
system programming, economics, economical cybernetics,
information systems, information security)
- students not having informatics among major subjects
- students majoring in humanities
- students majoring in the field of art, culture or sport.
The 1
st
year students may optionally move to another section
according to their majoring subject.
1
st
tour tasks
Programming and informational modeling section
Task (common for all nominations)
A passenger arrived at the bus stop at 8 a.m. and stayed there till
8:59 a.m. During that time he wrote down the time of arrival of every
bus. For every particular route buses arrive at the bus stop after the
same interval. It is also known that during the given period of time at
least two buses of every route arrived at the bus stop.
The task is to determine according to the passenger’s records the
least number of bus routes passing through the given bus stop and
the routes schedule.
Technical requirements.
The number of routes <= 17.
Input data is in the input.txt file of the following format. The fist line
contains a number n <= 300 (the number of buses arrived), the
second one contains a sequence of integers from 0 to 59 denoting
arrival time in minutes.
Output data should be placed into the output.txt file of the following
format. Every line should contain data for one particular root: Time of
arrival of the first bus and interval between bus arrivals. The root
order does not matter. If there are many solutions only one solution
is enough.
Example:
Input.txt Output.txt
17 0 13
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
3 12 5 8
Nomination “ Sports”
Relay-race
N teams take part in the skiing race (4 times 10km). The jury gets the
information what time has been spent by each participant for a
particular stage of the race.
The task is:
a) To make a list of participants of a concrete team in the
increasing order of the race results, i.e. the name of the
participant who showed the less time among other members
of the same team should be the first, while the name of the
participant who showed the maximum time should be the
last.
b) To find the winner in the individual championship among all
race participants.
c) To find the team which showed the minimum total time.
Nomination “ Art”
Pianist contest
There is a jury at the pianist contest, consisting of 6 musicians.
The maximum mark the jury member can give is 10(ten), the
minimum is 0(zero). You should develop an algorithm (a
program) for:
- making a linear table containing participants surnames and
names and a rectangular one containing the marks given by
each jury member,
- finding the name of the winner of the contest,
- finding the number of the most strict jury member.
Nomination “ The Fresher (Fist Year Student)”
Objects
Distribute N objects (N<15) with a definite weight into two
rucksacks so that the difference in weights of the rucksacks is
minimal.
Technical requirements
Input data are taken from the text file input.txt. Its first line
contains the number N, the second one – the sequence of the
numbers defining the weights of the objects according to their
numbers.
The result is printed on the screen in two lines each containing
the list of the numbers of the objects, put in each rucksack and
its weight.
Nomination “ For students not having informatics among major
subjects” .
“ Naval battle”
You need to model the field for the game “naval battle” and calculate
the number of one-, two-, three- and four-deckers situated there.
Ships cannot be bended and do not touch each other. The game
field measures 10x10 checks.
Technical requirements
Input data - the number of the occupied checks N and the set of N
pairs of integers (check coordinates) – taken from the text file
INPUT.TXT which first line contains integer N and each next one
contains the coordinates of the occupied squares.
The results - the type and the number of the ships are displayed
line-by-line.
Nomination “ For students majoring in informatics” .
“ Labyrinth”
Labyrinth is a set of identical rooms. Each of them has from 1 to 4
doors to the neighboring rooms. A traveler entered the labyrinth and
wandered there until he found the way out. Each time while turning
into another room he made a note, marking the direction of the
movement with the letters: N – North, E – East, S – South, W –
West.
By the given route description you need to determine the shortest
way which leads from the entrance to the exit and covers the rooms
where the traveler has been.
Technical requirements
Input data are taken from the text file INPUT.TXT. Its first line
contains the number of the passages from one room to another, and
each next contains one of the letters N, E, S, W.
Output data is a line of characters which is output to the text file
OUTPUT.TXT and to the screen.
Nomination “ For students majoring in humanities” .
“ A and B”
The input text is a sentence containing enumeration of two objects
joined by “and”. You need to swap the words joined by this
conjunction. For example, the text “A and B were sitting on a tube”
after transformation should be “B and A were sitting on a tube”
Applied software section.