В новом космическом эксперименте участвуют N объектов, пронумерованных от 1 до N.
Известно, что N - нечетно. Каждый объект имеет уникальную, но неизвестную энергию Y, выражающуюся
натуральным числом, 1<=Y<=N. Назовем объектом с медианной энергией такой объект X, для которого
количество объектов с энергией, меньшей чем у X, равно количеству объектов с энергией, большей чем
у X. Требуется написать программу, которая определяет объект с медианной энергией. К сожалению,
сравнивать энергии можно только с помощью устройства, способного для трех различных заданных
объектов определить, какой из них имеет медианную энергию.
Вам предоставляется библиотека device с тремя операциями:
GetN, вызывается только один раз в начале программы; не имеет аргументов; возвращает значение N.
Med3, вызывается с тремя различными номерами объектов в качестве аргументов; возвращает номер объекта, имеющего медианную (среднюю) энергию.
Answer, вызывается только один раз в конце программы; единственный аргумент - номер объекта X, имеющего медианную энергию. Эта функция корректно завершает выполнение вашей программы.
Библиотека device генерирует два текстовых файла MEDIAN.OUT и MEDIAN.LOG. Первая строка файла
MEDIAN.OUT содержит одно целое число: номер объекта, переданного библиотеке при вызове Answer.
Вторая строка содержит одно целое число: количество вызовов Med3, которое было сделано вашей
программой. Диалог между вашей программой и библиотекой записывается в файл MEDIAN.LOG.
Инструкция для программирующих на языке Pascal: включите строку
uses device;
в текст вашей программы.
Инструкция для программирующих на C/C++ : Включите строку
#include ?device.h?
в текст вашей программы, создайте проект MEDIAN.PRJ и добавьте файлы MEDIAN.C (MEDIAN.CPP) и DEVICE.OBJ в этот проект.
Вы можете поэкспериментировать с библиотекой, создав текстовый файл DEVICE.IN. Файл должен
содержать две строки. Первая строка должна содержать одно целое число: количество объектов N.
Вторая строка должна содежать целые числа от 1 до N в некотором порядке: i-ое число является
энергией объекта с номером i.
Файл DEVICE.IN , указанный выше, описывает 5 объектов с их энергиями:
Номер объекта 1 2 3 4 5
---------------------------------------------------------
Энергия 2 5 4 3 1
Ниже приведена корректная последовательность с пятью обращениями к библиотеке:
1. GetN (in Pascal) or GetN() (in C/C++) возвращает 5.
2. Med3(1,2,3) возвращает 3.
3. Med3(3,4,1) возвращает 4.
4. Med3(4,2,5) возвращает 4.
5. Answer(4)
Количество объектов N нечетно и 5<=N<=1499.
Для объекта с номером i выполняется 1<=i<=N.
Для энергии объекта Y выполняется 1<=Y<=N и все энергии различны.
Библиотека для Pascal содержится в файле: device.tpu
Объявление функций и процедуры на Pascal:
function GetN: integer;
function Med3(x,y,z:integer):integer;
procedure Answer(m:integer);
Библиотека для C/C++ : device.h, device.obj (используйте модель памяти large)
Заголовки функций для C/C++ :
int GetN(void);
int Med3(int x, int y, int z);
void Answer(int m);
В ходе исполнения программы разрешается использовать не более 7777 вызовов функции Med3.
Ваша программа не должна читать или писать какие-либо файлы.
