Информатика и информационные технологии

Задания олимпиады по информатике

Задания олимпиады по информатике разбиты на две части - теоретическую и практическую. В теоретичекой части требуется в произвольной форме (например, в виде словесного описания) привести алгоритм, предназначенный для решения задачи. В практической части требуется написать программу на языке Паскаль или Си, удовлетворяющую условиям задачи.

Теоретическая часть

1. Замкнутая ломаная

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

2. Алгоритм

Определить, что делает данный алгоритм:

N:=0;
ДЛЯ K ОТ 1 ДО 10000 ВЫПОЛНИТЬ
  X:=СЛУЧ;
  Y:=СЛУЧ;
  ЕСЛИ X*X+Y*Y<=1 ТО N:=N+1;
КОНЕЦ_ЦИКЛА
X:=N/2500;
ВЫВЕСТИ(X);

{примечание: функция СЛУЧ выдает случайное вещественное число от -1 до 1}

3. Поезд

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

4. Общие делители

Из последовательности натуральных чисел a, a+1, a+2, ..., N выделить наибольшую возрастающую последовательность, каждый последующий член которой имеет с предыдущим наибольший общий делитель, равный произведению двух различных простых чисел.

5. Социальная справедливость

На предприятии работают N сотрудников с зарплатами x1, x2, ..., xN. Директор решил выделить M рублей на повышение зарплат сотрудников. Деньги распределяются следующим образом: один рубль добавляется к самой низкой зарплате, после этого снова ищут человека с самой низкой зарплатой и добавляют рубль к его зарплате, и так далее. Данный процесс продолжают до тех пор, пока не израсходуются все M выделенных рублей. Определить наименьшую зарплату на предприятии после такого повышения.

Практическая часть

1. Социальная справедливость

На предприятии работают N сотрудников с зарплатами x1, x2, ..., xN. Директор решил выделить M рублей не повышение зарплат сотрудников. Деньги распределяются следующим образом: один рубль добавляется к самой низкой зарплате, после этого снова ищут человека с самой низкой зарплатой и добавляют рубль к его зарплате, и так далее. Данный процесс продолжают до тех пор, пока не израсходуются все M выделенных рублей. Определить наименьшую зарплату на предприятии после такого повышения.

Ограничения:

Количество сотрудников: N<30000
Зарплата сотрудников: целые неотрицательные числа
x1, x2,...,xN < 30000
Выделенная для повышения зарплаты сумма: M<1000000

Исходные данные

расположены в файле input.txt и имеют следующий формат:
в первой строке через пробел следуют два числа - N и M,
в последующих строках указаны зарплаты сотрудников.

Результат

- наименьшая зарплата после повышения - должен быть выведен на экран.

Пример файла input.txt

Результат, соответствующий примеру: 7

2. Игра

Имеются N пустых коробок. За один ход разрешается положить в K (K<N) коробок по 1 рублю. Выигрывает тот, после хода которого в какой-то из коробок впервые окажется ровно M рублей. Следует написать программу, играющую в данную игру.

Ограничения:

N<1000;
K<N;
M<10000.

Исходные данные:

расположены в файле input.txt
В первой строке через пробел идут числа N, K, M
В последующих N строках расположены числа - - количество денег в соответствующих коробках на данный момент.

Результат

помещается в файл output.txt:
в K строках располагаются K чисел (по 1 числу в строке),
соответствующих номерам коробок, в которые кладется по 1 рублю.

Помимо вывода в файл output.txt, программа должна записывать в файл moves.txt свои ходы в следующем формате:
1 строка: K чисел - номера коробок, в которые программа кладет по 1 рублю за свой первый ход;
2 строка: K чисел - номера коробок, в которые программа кладет по 1 рублю за свой второй ход;...
и так далее.

3. Замкнутая ломаная

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

Ограничения:

Количество точек (N) не превосходит 30000.

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

расположены в файле input.txt и имеют следующий формат:
первая строка - количество точек (N), в следующих N строках - координаты точек через пробел.

Результат

- номера точек в порядке соединения в ломаной - записываются в файл output.txt через пробел.

Пример файла input.txt:

Пример выходного файла, соответствующего примеру:

1 5 2 4 3


Примечания к задаче:

*) Задача может обладать несколькими правильными решениями -
- требуется привести хотя бы одно.

**) В приведенном выше примере точки соединяются в такой
последовательности: 1-5-2-4-3, после чего точка N3 соединяется
с точкой N1. Второй раз записывать точку N1 в выходной файл
не нужно.
 


Желаем удачи!


Со всеми вопросами  обращайтесь:  

E-mail:  inform@edu.yar.ru
тел: (0852) 32-88-91, 30-29-62
 Богомолов Юрий Викторович.