Задача Нечетное число (ODD)

В ряд выписаны степени двойки от до . Над числами в ряду производится следующая операция - любые два числа заменяются на модуль их разности. Если эту операцию произвести раз, то останется одно нечетное число. Требуется найти такую последовательность операций, которая приводит к заданному нечетному числу или установить, что это число получить невозможно.

Формат ввода/вывода:

Напишите программу ODD, которая читает входные данные из файла ODD.DAT и записывает ответ в файл ODD.SOL.

В единственной строке файла ODD.DAT находятся два числа и .

Если получить число невозможно, файл ODD.SOL должен содержать единственное число . В противном случае, файл ODD.SOL должен содержать строк, по количеству операций. В каждой строке должно находится два числа, над которыми производится очередная операция. Если существует несколько различных решений, выведите любое из них.

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

Пример:

ODD.DAT:

6 37

ODD.SOL:

16 8

2 1

4 1

8 3

32 5

64 27

Задача Пирожные (PASTRY)

На витрине стоит ряд различных пирожных, цены на которые могут быть 2, 3 или 5 грн. С целью увеличения продаж маркетинговый отдел рекомендует начинать этот ряд с пирожного за 2 грн и заканчивать его пирожным за 3 грн. Чтобы требования маркетологов удовлетворялись, можно снять с витрины некоторое количество пирожных. Сколькими различными способами можно это сделать?

Формат ввода/вывода:

Напишите программу PASTRY, которая читает исходные данные из файла PASTRY.DAT и записывает ответ в файл PASTRY.SOL.

В первой строке файла PASTRY.DAT записано число - количество пирожных. Во второй строке находятся чисел (, , ) - цены пирожных.

Единственная строка файла PASTRY.SOL должна содержать ответ: остаток от деления на , где - количество способов.

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

Пример:

PASTRY.DAT:

2 5 2 3

PASTRY.SOL:

Задача Столкновение (CRASH)

В плоскости движутся два выпуклых многоугольника. Известны координаты всех их вершин в момент времени , когда фигуры гарантированно не пересекаются, не соприкасаются и не вложены друг в друга. Начиная с этого момента, фигуры двигаются равномерно, прямолинейно и поступательно (без вращений). Скорость каждой фигуры задана в виде проекций на обе оси координат.

Определите, столкнутся ли фигуры. Если они столкнутся, то определите время столкновения. Если они не столкнутся, то определите минимальное расстояние между фигурами за всё последующее время (что происходило до момента времени , неизвестно и не рассматривается). Расстояние между фигурами следует считать как расстояние между ближайшими их частями (т. е. как длину кратчайшего из отрезков, один из концов которого принадлежит одному многоугольнику, другой - другому). Известно, что фигуры либо сталкиваются, либо не касаются друг друга.

Формат ввода/вывода:

Напишите программу CRASH, которая читает входные данные из файла CRASH.DAT и записывает ответ в файл CRASH.SOL. В первой строке файла CRASH.DAT задано сначала количество вершин первой фигуры ,потом два действительных числа - проекции ее скорости; во второй строке записано действительных чисел - координаты вершин в порядке обхода. 3-я и 4-я строки содержат описание второй фигуры в таком же формате. Файл CRASH.SOL должен содержать в первой строке либо целое число (фигуры не сталкиваются), либо (сталкиваются); во второй строке - одно действительное число (минимальное расстояние в случае или момент столкновения в случае ). Действительное число можно выводить в любом виде (экспоненциальном или десятичной дробью). Ответ засчитывается, если первое число правильно, а второе отличается от правильного не более, чем на .

Ограничения: , значения координат и проекций скоростей действительные и не превышают по модулю .

Примеры:

CRASH.DAT:

CRASH.SOL:

4 1.0 0.0

-1.0 1.0 -1.0 3.0 -3.0 3.0 -3.0 1.0

4 -1.0 0.0

1.0 -1.0 1.0 -3.0 3.0 -3.0 3.0 -1.0

2.0

CRASH.DAT:

CRASH.SOL:

4 0.0 -1.0

5.0 5.0 7.0 6.0 7.5 4.5 6.0 4.0

3 3.0 0.0

1.0 6.0 -0.5 3.5 1.0 2.0

1.333333333333

Памятка участника

Решения задач - файлы с текстами программ, должны быть записаны на диск под именами gnomes, hanoi, necklace. Расширение файлов должно быть одним из следующих: pas, cpp, pp, cc. Решения будут откомпилированы различными компиляторами в зависимости от расширения файла с исходным текстом:

pas Borland Pascal 7.0 cpp Borland C 3.1

pp Free Pascal 2.0 cc GNU C++ 3.4

Программы должны читать входные данные из текстовых файлов с расширением dat и записывать результаты в файлы с расширением sol, которые находятся в текущем каталоге. Программа не должна ничего выводить на экран и не должна ждать ввода с клавиатуры! Программа должна завершаться с кодом выхода 0.

Решения проверяются автоматически на наборе тестов. В текст программ изменения не вносяться, и сам он не оценивается.