XІ Всеукраїнська комплексна олімпіада з математики, фізики та інформатики
"Турнір чемпіонів"
2004 р.
Завдання з математики
Задача Яблоки (APPLE)
Бабушка продавала яблоки на штуки, складывая их правильной пирамидкой, основанием которой является равносторонний треугольник. Сколько яблок было у бабушки, если все они образовали одну пирамидку, причем в ребре пирамидки N яблок. Напишите программу APPLE, которая читает длину стороны N с клавиатуры и выводит число яблок X на экран.
Ограничения:1<=N<=100000000
Формат ввода/вывода:
| ввод: N |
вывод: X |
Пример:
| ввод: 3 |
вывод: 10 |
Задача Удачное Вычитание (DIFF)
"Вундеркинд" Сережа на уроке математики придумал для соседа игру. Записав в ряд N целых чисел X1 ,X2 ,...,XN , он предложил заменить какую-нибудь пару рядом стоящих чисел XK ,XK+1 их разностью XK - XK+1 (всегда вычитаем из первого числа второе, но не наоборот). Затем он повторял это действие до тех пор, пока не останется одно число. Какое максимальное число M можно получить таким образом? Напишите программу DIFF, которая читает количество чисел N и числа X1 ,X2 ,...,XN из файла DIFF.DAT и записывает число M в файл DIFF.SOL.
Ограничения: 1<= N <=10000, -10000<= Xk <=10000 (k=1,2,...,N)
Формат ввода/вывода:
| DIFF.DAT: N X1 X2 ... XN |
DIFF.SOL: M |
Пример:
| DIFF.DAT: 3 1 2 3 |
DIFF.SOL: 2 |
Задача Торговые Агенты (AGENTS)
Отдел доставки фирмы "Рога и Копыта" обслуживает торговые точки. Каждый день товар завозится в одну из них. График завоза по дням составлен заранее, причем в этом графике точки могут повторяться.
Два агента с машинами распределили заказы между собой. Каждый день один из них завозит товар в очередную торговую точку и остается в ней, а другой никуда не перемещается. Работа агентов спланирована так, чтобы суммарный расход горючего был минимальным. Торговые точки заданы своими координатами. Из точки в точку агенты перемещаются по прямой. Перед началом работы агенты находятся в точке плоскости с координатами (0,0).
Напишите программу AGENTS, которая читает входные данные с клавиатуры : число торговых точек N и N пар вещественных чисел (X1 ,Y1 ), (X2 ,Y2 ), ... (XN ,YN ) - координаты 1-ой, 2-ой, …, N -ой торговых точек, затем число дней в графике M и M чисел K1 K2 ,... KM - номера точек, которые нужно посетить в 1-ый, 2-ой, …, M -ый день. Программа должна определить суммарный пробег машин S с точностью до ε =10 -5 и вывести его на эеран .
Ограничения:
1<= N <=10, -1000.0<= Xk Yk <=1000.0 (k = 1,2,...,N)
1<= M <=10000, -1000.0<= Kj <=N (j = 1,2,...,M)
Формат ввода/вывода:
| ввод: N X1 Y1 X2 Y2 ... XN YN M K1 K2 ... KM |
вывод: S |
Пример:
| ввод: 3 3.0 4. 0 1.0 4.0 4.0 1.0 5 2 3 1 3 2 |
вывод: 12.2462112512 |