Задача № 1.      По справедливости (25 баллов).

N (2£N£4) жадных медвежат делят сыр. После того, как каждый из них изловчился отщипнуть себе кусочек весом в целое число грамм, оказалось, что  сыра у них не поровну. Огорченные медвежата крепко подрались. Чтобы восстановить спокойствие в лесу хитрая лиса вызвалась помочь поделить сыр.  Лиса равняет сыр следующим образом: от любых двух кусочков она одновременно отрезает и съедает по 1 грамму.

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

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

Ввод производится из файла CHEESE.DAT.  В первой строке файла указано количество медвежат N, в последующих N строках указано количество сыра у каждого медвежонка.

Формат вывода.

Вывод производится в файл leftovers.DAT.

Если уравнять сыр невозможно, программа выводит в файл сообщение: "impossible".

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

Например, для такого начального распределения сыра:

4

4

1

вывод будет таким:

1

3 3 1

2 2 1

1 1 1 

Задача № 2.      Упрощенная Машина Поста (УМП)(40 баллов)

УМП состоит из бесконечной ленты, поделенной на ячейки и печатающей каретки. Каретка может перемещаться от ячейки к ячейке вправо и влево. Находясь над ячейкой, каретка может поставить в нее метку, если ячейка пуста, и стереть метку, если ячейка помечена.

Для УМП можно составить программу, состоящую из команд. Каждая команда имеет порядковый номер в программе и действие, которое нужно совершить машине.

i   =>      переход на одну ячейку вправо  

i   <=       переход на одну ячейку влево

i   V          поставить метку в ячейку, над которой находится каретка

i   X          стереть метку из ячейки, над которой находится каретка

i   stop    остановить работу программы

Все команды в программе должны быть записаны по порядку номеров. Например:

1   =>

2   V

3   stop  

4   Х

Вышеприведенная последовательность команд является программой.

1   =>

2   <=

3   V

5   stop  

4   Х

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

Программа завершает свою работу, выполняя команду "stop". Это нормальное завершение работы. Программа завершает свою работу и тогда, когда не может выполнить действие: нельзя поставить метку в уже помеченную ячейку, нельзя стереть метку из непомеченной ячейки. В этом случае происходит ненормальное завершение.

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

Для удобства задания состояния выберем нулевую ячейку и будем считать, что все ячейки, расположенные правее нулевой нумеруются так: 1,2,3,4 …. Ячейки, расположенные левее нулевой имеют номера: -1,-2,-3,-4, …. Состояние УМП зависит только от положения меток и каретки и не зависит от нумерации. Т.е. следующие две таблицы представляют одно состояние.

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

Например, программа

1   <=

2   <=

3   V

4   =>

5   stop

переводит машину из состояния

в состояние

Формат ввода. Ввод производится из файла UMP.DAT.

Файл описывает начальное и конечное состояние ленты. Состояние ленты описывается двумя строками.

Первая строка описания содержит последовательность звездочек "*" и меток "v" (не более 255). Символом "v" обозначаются помеченные, а символом "*" - непомеченные ячейки ленты. Вторая строка описания содержит позицию каретки (ячейки в первой строке описания нумеруются с единицы).

Например файл:

******v****

6

***v**v****

3

означает, что начальное состояние УМП -

конечное -

Вывод производить в файл CODE.DAT в виде последовательности команд. Каждая команда должна быть записана в отдельной строке. Номер команды и действие должны быть разделены пробелами.

Например, для вышеуказанного примера выходной файл может выглядеть так:

1 <=  

2 <=  

3 V

4 <=

5      стоп

Задача № 3.      Авиапассажирская (35 баллов)

Пусть на координатной плоскости XOY расположены N материальных точек с массами x_i M_i и координатами x_i,y_i. Тогда координаты центра масс такой системы можно найти по формулам

x_m=(S(x_im_i))/S(m_i)

y_m=(S(y_im_i))/S(m_i)

В авиакомпании "Летайте с нами" при продаже билета учитывается вес пассажира.

В салонах самолета имеется N  пассажирских кресел (N£10).

Центр тяжести самолета принимается за точку с координатами 0,0. Тогда кресла имеют координаты x_i, y_i  (1£ i£ N).

Билеты на самолет приобретают M (M£N) человек с массами m₁,…,m_i,..m_M соответственно.

Координаты кресел и массы пассажиров задаются целыми числами.

Требуется написать программу, которая "рассаживала" бы пассажиров по креслам с таким расчетом, чтобы центр масс рассаженных пассажиров был на минимальном расстоянии от центра тяжести самолета.