7 комплексная олимпиада по математике, физике и информатике
Задания 3 тура(информатика)


Задача начальника тюрьмы. (50 баллов)

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

Технические условия.

Программа должна прочитать данные задачи из файла prison.dat. В первой строке этого файла содержатся три числа - количество заключенных в каждой камере (не больше 100).

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

Пример входных и выходных данных.
prison.dat

2 3 4

prison.sol

2

2 1

1 3

Развлечение на скучном уроке. (25 баллов)

Вам всем известны игры на бумажке, за которыми вы коротаете время на уроках: Однажды я отобрал у учеников листик на котором было нарисовано вот что: (как вы понимаете - это только кусочек)

2 17 16 15 14 13 30
1 18 5 4 3 12 29
0 19 6 1 2 11 28
-1 20 7 8 9 10 27
-2 21 22 23 24 25 26
  -2 -1 0 1 2 3

Установив начало декартовых координат в клеточке с числом 1, найдите координаты произвольной клетки по ее содержимому. Например, клетка с числом 2 имеет координаты (1,0), а клетка с числом 7 - (-1,-1).

Технические условия.

Входной файл cell.dat содержит одно число - номер клетки (не больше 1,000,000).

Выходной файл cell.sol должен содержать 2 числа - ее координаты.

Пример входных и выходных данных.

cell.dat

10

cell.sol

2 -1

Новые шахматы. (25 баллов)

В продажу поступили новые доски для шахматной игры: стандартный размер 8х8, однако с прямоугольным симметричным вырезом в центре. За какое минимальное количество ходов и каким образом ферзь может попасть из одной клетки такой доски в другую.

8                
7                
6                
5                
4                
3                
2                
1                
  1 2 3 4 5 6 7 8

Технические условия.

Входной файл chess.dat содержит в первой строчке два числа через пробел - ширина и высота выреза, а в двух следующих - координаты начальной и конечной клетки.

Выходной файл chess.sol - в первой строке количество ходов - N, а в последующей N+1 строчке - координаты начального, промежуточных и конечного положений ферзя.

Пример входных и выходных данных
chess.dat

4 2

4 7

8 3

chess.sol

2

4 7

8 7

8 3

Памятка участникам. (баллов это не добавит, но прочитать все равно придется)

Решения задач - файлы с исходными текстами программ должны быть записаны на диске под именами prison.pas, cell.pas, chess.pas (или prison.c, cell.c, chess.c). Программы должны читать данные из текстовых файлов с расширением dat и записывать решения в файлы с расширением sol.

Программа не должна ничего выводить на экран и, тем более, ожидать ввода с клавиатуры!

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

Программы проверяются на наборе тестов; за каждый правильно решенный тест начисляются баллы. В исходный текст программ изменения не вносятся, и сам он не оценивается.

Успехов!

3 мая 2000 г. Винница

© LIKT 1998-2018