Задача День рождения гномов (GNOMES)

Со времен Белоснежки клан гномов сильно изменился. Теперь их уже не 7, а N. Гномы очень любят праздновать дни рождения. Лучшим подарком считается связка воздушных шариков (их потом можно передаривать другому имениннику). На день рождения собирается весь клан, и каждый гость дарит имениннику по крайней мере один шарик. Старинная традиция требует, чтобы каждый следующий именинник получал больше шариков, чем предыдущий. Какое минимальное количество шариков суммарно придётся купить, чтобы отпраздновать K дней рождения, если изначально нет ни одного шарика? Известно, что никакие два дня рождения не празднуются в одно и тоже время.

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

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

В единственной строке файла GNOMES.DAT содержится два числа: N - количество гномов и K - количество дней рождений. Единственная строка файла GNOMES.SOL должна содержать одно число - минимальное число шариков.

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

Пример:

GNOMES.DAT:

4 5

GNOMES.SOL:

Задача Ханойские Башни (HANOI)

Задача "Ханойские Башни" состоит в следующем. Имеется три стержня и N дисков различных размеров. Изначально диски нанизаны на первый стержень и упорядочены по размеру, т.е. самый большой диск лежит в самом низу, а каждый из оставшихся дисков лежит на диске большего размера. Требуется перенести все диски на второй стержень. Для этого можно совершать следующую операцию: взять верхний диск с какого-либо стержня и переложить его на другой стержень. При этом, диск нельзя класть на диск меньшего размера.

Хорошо известно, что существует единственный оптимальный способ решить эту задачу за минимальное число перемещений. Пусть заданы три целых неотрицательных числа: A, B и C, такие что A+B+C=N. Ответьте на такой вопрос: сколько раз при решении задачи оптимальным способом возникнет такая конфигурация, что на первом стержне находится A дисков, на втором стержне - B дисков и на третьем стержне - C дисков? Следует учитывать, в том числе, и первоначальное, и конечное положение дисков.

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

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

В единственной строке файла HANOI.DAT находятся три числа: A, B, C - количество дисков на стержнях. В единственной строке файла HANOI.SOL должно содержаться одно число - количество конфигураций.

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

Пример:

HANOI.DAT:

1 2 3

HANOI.SOL:

Задача Ожерелье (NECKLACE)

Замкнутая цепочка состоит из N звеньев. Все звенья цепочки имеют разную величину от 1 до N. Переместить звено можно, удалив его с текущего места и вставив его между любыми двумя звеньями. Какое минимальное число звеньев нужно переместить, чтобы начиная с некоторого звена, звенья выстроились в убывающем или возрастающем порядке?

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

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

В первой строке файла NECKLACE.DAT находится число N - количество звеньев в цепочке. Во второй строке содержится N различных целых чисел от 1 до N - размеры звеньев, перечисленные в порядке обхода против часовой стрелки начиная с некоторого звена.

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

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

Пример:

NECKLACE.DAT:

5 2 1 6 4 3 7

NECKLACE.SOL:

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

Решения задач - файлы с текстами программ, должны быть записаны на диск под именами 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.

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