Задачи для старшей группы 
(школьники до 12 класса включительно)

Задача 1-го этапа 	“Часовой на посту!”.
Доблестные пограничники Анчурии задержали на границе контейнер с подрывной литературой - многотомной Encyclopaedia Britannica. Известно, что тома энциклопедии пронумерованы по порядку, начиная с 1, и по крайней мере один экземпляр каждого тома в контейнере был. 
Напишите программу, которая определяет
1)	номер последнего тома (т.е. количество томов в энциклопедии);
2)	сколько полных комплектов  энциклопедии можно собрать из задержанных книг;
3)	какой том присутствует в контейнере в наибольшем количестве (и каково это количество); если в наибольшем количестве встречается несколько различных томов, то определять наименьший из таких номеров;
4)	какое максимально возможное количество полных комплектов можно собрать, если разрешается заменять любые два тома на любой том по выбору.
5)	программе предоставляется список томов в том порядке, в каком их извлекали из контейнера - требуется определить, сколько книг пришлось извлечь из контейнера, прежде чем впервые из них удалось собрать полный комплект энциклопедии. 

Входные данные. Входной текстовый файл INPUT.TXT в первой строке содержит натуральное число N (2 <= N <= 10000) - количество книг в контейнере. В следующих N строках содержатся номера томов. Каждая строка содержит номер одного тома - одно натуральное число, не превосходящее N.

Выходные данные. Выходной текстовый файл OUTPUT.TXT должен состоять из пяти строк. В каждой строке должно находиться одно целое число: в первой строке - ответ на первый вопрос, во второй - на второй, в третьей строке должно содержаться наибольшее количество повторяющихся экземпляров одного какого-либо тома, а в четвертой строке - номер этого тома (если таких номеров несколько, то выводит наименьший из них), в пятой строке должен находиться ответ на четвертый вопрос, в шестой строке - на пятый вопрос. 
Пример. 	 	
INPUT.TXT	OUTPUT.TXT	
7	3	
3	1	
2	3	
2	1	
1	2	
1	4	
2		
1		

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

Задача 2-го этапа    "...с чувством уверенности в завтрашнем дне."

  Вовочка очень любил заботиться о старушках и об их благосостоянии. Каждый N-й день он переводил старушек через дорогу, каждый K-й день он объявлял, что благосостояние старушек повысилось, а каждый M-й день он обещал, что скоро им будет еще лучше. Сегодня Вовочка делал все три дела: и переводил, и объявлял, и обещал, и очень устал, но был доволен собой. Напишите программу, которая определяет
1). через сколько дней у Вовочки снова случится такой содержательный день?
2). сколько до этого момента будет у Вовочки скучных дней, когда он не занимался ни одним из любимых дел?
3). случится ли когда-нибудь так, что у Вовочки будет три интересных дня подряд (интересным Вовочка считает день, когда он занимался хотя бы одним из трех любимых дел); если да, то когда это случится впервые?

Входные данные. Входной текстовый файл INPUT.TXT состоит из трех строк: первая строка содержит натуральное число N, вторая – натуральное число K, и третья - натуральное число M. Каждое из этих чисел не превосходит тысячи.

Выходные данные. Выходной текстовый файл OUTPUT.TXT должен состоять из трех строк, каждая из которых должна содержать одно целое число - ответ на соответствующий вопрос. Если такого особо счастливого дня, когда Вовочка занимался всеми тремя любимыми делами сразу, больше никогда не случится, то первая строка должна содержать -1. Если у Вовочки никогда не случится трех интересных дней подряд, то третья строка должна содержать -1, если же случится, то следует выводить номер первого из тех трех дней, когда такое случится впервые. Считаем, что сегодняшний день имеет номер 0.

Пример.     INPUT.TXT        OUTPUT.TXT
            5                30 
            2                8
            3                2

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

Задача 3-го этапа.    "В праздничных колоннах..."

  Организаторы шествия решают, как им построить участников. Это очень важно с тактической точки зрения - митинги и шествия в Анчурии, как известно, сопровождаются мордобоем, и от расположения участников зависит успех мероприятия. В то же время, эстетическая сторона дела не должна страдать - строй должен выглядеть красиво. Организаторы решили расставить участников шествия в несколько групп одинаковой формы (но, может быть, разного размера). Рассматриваются три возможности: расставлять манифестантов в квадраты, в треугольники или "свиньей". "Свинья" - это старинное построение, имеет форму клина, получающегося при соединии квадрата и треугольника. На рисунке показаны соответствующие фигуры ширины 4:
                            x    
                           x x
      x x x x             x x x              x
      x x x x            x x x x            x x
      x x x x            x x x x           x x x  
      x x x x            x x x x          x x x x
                         x x x x 

      квадрат            "свинья"        треугольник

Для примера в таблице приведены количество человек, которые необходимы для построения той или иной фигуры при изменении ширины от 1 до 10.
 
 | Ширина фигуры| 1 | 2 |  3 |  4 |  5 |  6 |  7 |  8 |   9 |  10 |
 ------------------------------------------------------------------
 | Квадрат      | 1 | 4 |  9 | 16 | 25 | 36 | 49 | 64 |  81 | 100 |
 ------------------------------------------------------------------
 | Треугольник  | 1 | 3 |  6 | 10 | 15 | 21 | 28 | 36 |  45 |  55 |
 ------------------------------------------------------------------
 | "Свинья"     | 1 | 5 | 12 | 22 | 35 | 51 | 70 | 92 | 117 | 145 |
 ------------------------------------------------------------------

Хочется, чтобы групп получилось как можно меньше, чтобы ими было легче управлять. Напишите программу, которая определяет, в какое наименьшее количество групп можно расставить всех участников шествия, если строить их квадратами, если строить их треугольниками и если строить их "свиньями". 
Входные данные. Входной текстовый файл INPUT.TXT состоит из одной строки, содержащей одно натуральное число, не превосходящее  миллиона, - количество участников шествия.
Выходные данные. Выходной текстовый файл OUTPUT.TXT должен состоять из шести строк. Первая строка должна содержать одно натуральное число N - наименьшее количество квадратных групп, в которые можно расставить всех участников шествия. Вторая строка должна содержать N натуральных чисел - размеры (ширину) соответствующих групп. Каждые два соседних числа во второй строке должны разделяться ровно одним пробелом. Если участников можно разбить на N квадратных групп несколькими способами, то достаточно привести один любой. Третья и четвертая строки должны содержать аналогичное описание разбиения участников на наименьшее возможное количество треугольных групп, пятая и шестая - на наименьшее возможное количество групп в форме "свиньи".
   Каждое из трех разбиений будет оцениваться отдельно, поэтому, если Вам не удастся решить какую-нибудь из трех подзадач, то все равно выводите в соответствующих строках какие-нибудь числа (например, 0).

Примеры.       1.    INPUT.TXT              OUTPUT.TXT
                     8                      2
                                            2 2
                                            3 
                                            1 1 3 
                                            4 
                                            1 1 1 2 
               2.    INPUT.TXT              OUTPUT.TXT
                     1225                   1     
                                            35 
                                            1  
                                            49  
                                            2  
                                            27 10

Задача 4-го этапа.    "Мешочники"

Депутаты парламента Анчурии уже давно очень озабочены одной проблемой - что делать с доставшимися им мешками с секретными компрометирующими материалами. Что делать - непонятно, но что-то делать надо, и поэтому они решили переложить бумаги из мешков в специальные ящики. Все ящики абсолютно одинаковые (для большей секретности), и каждый ящик вмещает ровно N кг бумаги, не больше и не меньше (если ящик недогружен, то его нельзя запереть - так уж устроен механизм ящика). Требуется разложить бумаги из мешков по ящикам так, чтобы осталось как можно меньше мешков. При этом содержимое любого вскрытого мешка должно быть полностью разложено по ящикам. Количество ящиков не ограничено.

Входные данные. Входной текстовый файл INPUT.TXT в первой строке содержит два натуральных числа N и M, разделенных пробелом: N - это вместимость (в килограммах) одного ящика, M - количество мешков, оба числа не превосходят 3000. В каждой из следующих M строк содержится ровно одно натуральное число, не превосходящее 10000, - вес одного мешка. Веса мешков идут в неубывающем порядке.

Выходные данные. Выходной текстовый файл OUTPUT.TXT в первой строке должен содержать одно натуральное число K - количество мешков, которые не удалось растолкать по ящикам. В каждой из следующих K строк должно содержаться ровно одно натуральное число - вес мешка, оставшегося "непристроенным". Эти числа могут идти в произвольном порядке. Ваша задача - добиться как можно меньшего значения величины K.

Программе на каждый тест дается 3 секунды. От программы не требуется найти наименьшее возможное значение K, но, конечно, чем оно окажется меньше, тем больше очков получит программа. Программа должна за отведенные три секунды создать выходной файл и закончить работу. Если программа не закончит работу за три секунды, то, даже если она и успеет создать некоторый файл OUTPUT.TXT, то оцениваться данный тест не будет, и программа получит за него 0. 

Пример.
             INPUT.TXT              OUTPUT.TXT
             10 8                   2
             2                      2
             2                      9  
             3                        
             3                        
             5
             8                       
             9
             9