|
Х Всеукраинская олимпиада по информатике 1 тур
1. Домино Задание. Написать программу DOMINO.*, подсчитывающую количество вариантов покрытия прямоугольника 2хN прямоугольниками 2х1. Покрытия, которые преобразуются одно в другое симметриями, считать различными. Входные данные. Входной файл DOMINO.DAT содержит число N (0<N<65536). Выходные данные. Выходной файл DOMINO.SOL должен содержать одно число: количество вариантов.
Примеры ввода и вывода
2. Монеты Имеются монеты з различными фиксированными номиналами, выраженными в копейках (например, 3 i 5 копеек) в достаточном количестве. Написать программу COINS.*, которая: а) определяет, можно ли представить заданную сумму S (выраженную в копейках), пользуясь монетами заданных номиналов, б) если это возможно, то представляет эту сумму с помощью минимального количества монет. Входные данные: Входной файл COINS.DAT содержит в первой строке сумму S (0£ S£ 1000000000), во второй строке - N - количество различных номиналов (0£ S£ 20), а в следующих N строках - А1 ... АN - номиналы (в порядке возрастания), которые можно использовать (0<A1<A2<...<AN£ 1000000000). Выходные данные: Выходной файл COINS.SOL должен содержать в первой строке знак "+", если заданную сумму S можно представить, и знак "-", если нельзя. Если представленная сумма существует, то следующие N строк должны содержать количества монет каждого номинала, которые необходимы для представления суммы S с помощью минимального количества монет.
Примеры ввода i вывода Представить 514 копеек с помощью монет номиналом в 3 и 5 копеек
Представить 27 копеек с помощью монет номиналом в 5 и 13 копеек
3. Прямоугольники На плоскости задан многоугольник. Необходимо написать программу RECT.*, определяющую прямоугольник минимальной площади, который содержит в себе заданный многоугольник. Например, для многоугольника соответствующим прямоугольником будет
Входные данные: Входной файл RECT.DAT содержит в 1-й строке целое число N - количество вершин многоугольника (3£ N£ 3000), в последующих N строках - по два действительных числа Xi, Yi - координаты вершин многоугольника в порядке их обхода по часовой стрелке. Выходные данные: Выходной файл RECT.SOL должен содержать 5 строк: в первой строке число S - площадь прямоугольника, а в следующих 4-х строках - пары координат Xi, Yi вершин прямоугольника в порядке их обхода (в произвольном направлении). Технические условия. 1. Все координаты в входном и выходном файлах даются в виде действительных чисел в формате, который обрабатывается стандартными функциями ввода-вывода. 2. Рекомендуемый тип данных для координат - Real в Pascal и float в С и С++. 3. Оптимальную площадь и координаты прямоугольника необходимо вычислить с точностью до 10-5. Пример ввода и вывода
2 тур
Ним
В игру Ним играют двое. Имеется (2£ N£ 100) кучек камней. Игроки по очереди берут камешки из кучек. Выигрывает тот, кто возьмет последний камешек. На каждом ходу игрок может брать камешки не более чем из K (1£ K£ N) кучек, но обязан взять хотя бы один камешек. Вначале игры в каждой кучке 0<H[i]<1000000000 камней. Задание. Напишите программу, которая будет играть в Ним и, по возможности, выигрывать. Технические условия. Во время проверки к Вашей программе будет присоединен (linked) модуль проверки, который называется CHECK.* (PAS, C или CPP). Этот модуль содержит 3 функции: InitGame, JudgeTurn, PartTurn. Функция InitGame используется для считывания входных данных из тестового файла. Она имеет 4 выходных параметра: N и K - количества кучек: массив Н - количества камней в кучках, First - кто первый ходит. После вызова этой функции N и K получат соответствующие значения, в первых N элементах массива Н будут количества камней в кучках, а First принимает значения 0, если первой ходит программа проверки (жюри) и 1, если первой ходит программа участника. Обратите внимание, что Ваша программа не должна самостоятельно читать входные данные, это нужно делать только с помощью функции InitGame. Функцию JudgeTurn Ваша программа будет вызывать, когда ей нужно будет получить очередной ход жюри. Единственный выходной параметр этой функции - массив Т, первые N элементов которого содержат количества камешков, которые проверяющая программа берет из кучек. Соответствие хода условиям игры гарантируется. Функцию PartTurn Ваша программа будет вызывать, чтобы сообщить проверяющей программе свой ход. Запишите свой ход в первые N элементов массива Т. Каждая из этих функций возвращает 1, если все хорошо, или 0, если возникла ошибка, и Ваша программа может прекратить работу. На полученной Вами дискете будет модуль проверки (CHECK.*) и главный модуль (NIM_KBD.*). Они предоставляются только для того, чтобы Вы могли быстро начать работу над решением, не теряя время на технические проблемы. Модуль CHECK выполняет считывание данных с клавиатуры, проверку ходов участника и последовательности вызовов функции, но очень плохо играет. Жюри при проверке будет использовать другой. Модуль NIM_KBD вызывает функции модуля CHECK в нужной последовательности, но вместо вычисления следующего хода участника читает его с клавиатуры. Ваша задача и состоит в том, чтобы функция MakeTurn вычисляла следующий ход. Жюри не настаивает на использовании указанных файлов, но Ваше решение должно корректно взаимодействовать с модулем CHECK. Примечание. При проверке среди тестов будут такие частные случаи: 1) N=2, K=1; 2) N=3, K=1; 2) N>3, K=1.
Программа- решение - NIM.PAS, NIM.CPP, NIM.C.
Пример N=4, K=2, First=1, H=(3,4,5,6). Участник: (1,1,0,0), осталось (2,3,5,6) Жюри: (0,0,1,1), осталось (2,3,4,5) Участник: (0,0,1,1), осталось (2,3,3,4) Жюри: (1,1,0,0), осталось (1,2,3,4) Участник: (0,0,0,4), осталось (1,2,3,0) Жюри: (0,0,1,0), осталось (1,2,2,0) Участник: (1,2,0,0), осталось (0,0,2,0) Жюри: (0,0,2,0), осталось (0,0,0,0) Выиграло жюри (но участник имел шанс!!!)
|
Полный архив олимпиады (943 Kb)
© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"