Задачи муниципального этапа олимпиады школьников по информатике 2010

При просмотре телепередачи "Форт Байан" Петя заметил, что ведущий делает какие-то вычисления, перед тем как открыть дверь и пустить участников игры на очередное испытание. Петя заметил в блокноте ведущего формулу `sum_{i=1}^N\ sqrt(i)` и понял, что кодом для замка на двери комнаты `N` является результат вычислений по этой формуле.

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100`).

Вывести одно вещественное число с точностью не менее `10^{-5}` – результат вычислений.

5

8.38233

Допускается вывод результата с большей точностью и в экспоненциальной форме, например, таким образом: 8.3823323474417620E+0000

Из города Китеж в форт Байан почти каждый час с `7^00` до `17^00` отправляются автобусы с туристами. К сожалению, в расписании указано только время отправления, но не указано время прибытия. Петя узнал, что время поездки до форта без остановок равно `K` часов. Но согласно постановлению главного врача Беловодья водители во время поездки должны делать остановки с `8^00` до `9^00` на завтрак, с `13^00` до `14^00` на обед и с `18^00` до `19^00` на ужин.

Напишите программу, которая поможет Пете узнать время прибытия автобуса.

Первая строка ввода содержит два целых числа – время отправления автобуса `T` (`7\ ≤\ T\ ≤\ 17`, `T≠8`, `T≠13`) и длительность поездки без остановок `K` (`2\ ≤\ K\ ≤\ 10`).

Вывести одно целое число – время прибытия автобуса с учетом остановок на еду. Входные данные таковы, что автобусы прибывают в форт не позднее `23^00`.

11 3

15

Если бы автобус ехал без остановок, то он приехал бы в форт в `14^00`, но водитель должен сделать остановку на обед с `13^00` до `14^00`, поэтому автобус приедет в форт в `15^00`.

Во дворе форта Байан проходят соревнования по игре в "бинго". Игра проходит на поле размером 5x5 клеток, каждые 5 секунд компьютер случайно выбирает одну из пустых клеток и подсвечивает ее, тогда один из игроков команды должен встать на эту клетку или положить в нее пушечное ядро. Если команда не успевает выполнить ход за отведенное время, то ход пропускается. Если ряд из 5 клеток по горизонтали или по вертикали будет полностью заполнен, команда кричит "бинго" и клетки этого ряда освобождаются от игроков и ядер. Может получиться так, что ядро (или игрок) ставится на пересечении двух рядов, в каждом из которых было по 4 заполненных клетки, таким образом два ряда (по вертикали и по горизонтали) будут заполнены одновременно, в этом случае команда кричит "бинго" дважды, и оба этих ряда освобождаются от игроков и ядер.

Напишите программу, определяющую, сколько раз за время игры команда сможет сказать "бинго", если успеет выполнить все ходы.

Первая строка ввода содержит одно целое число `N` (`5\ ≤\ N\ ≤\ 100`) – количество ходов. Далее следует `N` строк, содержащих по два целых числа от 1 до 5 – номер строки и номер столбца подсвечиваемой клетки. Подсвечиваются только пустые к этому моменту клетки.

Вывести одно целое число – сколько раз у команды получится "бинго".

8
1 2
3 5
3 2
4 5
3 1
3 4
3 3
5 5

1

После игры в "бинго" пушечные ядра нужно сложить в две непустые пирамиды. При этом одна пирамида должна иметь квадратное основание, а другая – треугольное. В самом верхнем слое первой пирамиды 1 ядро, во 2-м слое – 4 ядра, в 3-м слое – 9 ядер, в `i`-м слое – `i^2` ядер. Таким образом, первая пирамида в зависимости от числа слоев будет содержать 1, 5, 14, 30, 55, 91 и т. д. ядер. В самом верхнем слое второй пирамиды 1 ядро, во 2-м слое – 3 ядра, в 3-м слое – 6 ядер, в `i`-м слое – на `i` ядер больше, чем в предыдущем. Вторая пирамида в зависимости от числа слоев будет содержать 1, 4, 10, 20, 35, 56, 84 и т. д. ядер.

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

Ввод содержит от 1 до `100\ 000` строк, каждая из которых содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^8`) – количество ядер, которые нужно собрать в пирамиды. Последняя строка ввода, содержащая число 0, сигнализирует о завершении ввода и не должна обрабатываться.

Для каждого числа из ввода, кроме 0, вывести строку, содержащую два числа – количество слоев в первой пирамиде и количество слоев во второй пирамиде, при котором количество ядер, оставшихся лишними, минимально. Если существует несколько минимальных вариантов, вывести тот из них, в котором количество слоев в первой пирамиде меньше.

2
100
0

1 1
3 7

В первом случае все ядра будут собраны в пирамиды, во втором случае вне пирамид останется лежать 2 ядра.

Оценка для решения, правильно работающего для 11 строк, `N\ ≤\ 100` – 40 баллов; для 11 строк, `N\ ≤\ 10^8` – 60 баллов; для 1001 строки, `N\ ≤\ 10^8` – 80 баллов.

Для получения дополнительного времени в сокровищнице команда должна сыграть с Мастерами Игры. Пете предстоит сыграть в следующую игру. В начале игры игроку выдаются шесть карточек с цифрами от 0 до 9. Игрок должен выбрать из них две пары карточек таким образом, чтобы сумма двузначных чисел, которые образует каждая из пар карточек, была как можно ближе к 100. Чем больше сумма чисел отличается от 100 (в большую или меньшую сторону), тем больше дополнительных секунд в сокровищнице потеряет команда. После каждого хода игрок получает четыре новые карточки к двум оставшимся от предыдущего хода, и снова должен сделать свой ход. Игра продолжается `N` ходов. Пете удалось узнать порядок карточек в стопке, из которой карточки выдаются игроку.

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

Первая строка ввода содержит одно целое число - количество ходов `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, первая из которых содержит шесть целых чисел от 0 до 9, а остальные строки содержат четыре целых числа от 0 до 9 – цифры на карточках, которые получает игрок перед каждым ходом.

Вывести `N` строк, в каждой строке вывести две пары по две цифры – ход игрока. Если существует несколько решений, минимизирующих общую сумму отличий от 100, вывести одно из них (любое).

2
2 0 2 3 7 5
9 2 2 8

23 75
02 98

На первом ходе игрок получает из своих карточек сумму `23+75=98`, а на втором ходе – `02+98=100`. Общая сумма отличий от 100 равна `|100-98|+|100-100|=2`.

Решение, правильно работающее для `N\ =\ 1`, получит не менее 25 баллов.