Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Восьмая командная олимпиада"

Задача A. Последовательность - 4

(Время: 1 сек. Память: 16 Мб)

Бесконечная числовая последовательность задана с помощью формулы ее k-го члена:

        Ak = k!*2k, где k = 1, 2, 3,...

Найти сумму N первых членов этой последовательности. Так как найденная сумма может быть очень большой, выведите ее по модулю M.

Входные данные

Входной файл INPUT.TXT содержит два целых числа N - количество членов последовательности (1 ≤ N ≤ 104) и M - модуль (2 ≤ M ≤ 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите сумму N первых членов последовательности по модулю M.

Примеры

INPUT.TXTOUTPUT.TXT
15 102
210000 20
3100 1000000000909349562

Задача B. Пирамида

(Время: 1 сек. Память: 16 Мб)

Иннокентий очень любит строить пирамиды. А так как он еще маленький, то свои пирамиды он строит из кубиков. Сначала он выкладывает в ряд N кубиков – основание пирамиды, затем выкладывает остальные уровни так, что каждый последующий уровень на два кубика меньше предыдущего. Все уровни выровнены по центру относительно основания.

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

Входные данные

Входной файл INPUT.TXT содержит нечетное натуральное число N (N < 1000) – основание пирамиды.

Выходные данные

В выходной файл OUTPUT.TXT выведите пирамиду с основанием N. Вместо кубиков используйте символ 'A' (заглавная английская буква). В начале строки для форматирования выведите необходимое количество символов '.' (точка).

Пример

INPUT.TXTOUTPUT.TXT
15..A
.AAA
AAAAA

Задача C. Интеграл

(Время: 1 сек. Память: 16 Мб)

На плоскости задана функция:

Найдите площадь фигуры, ограниченной сверху графиком функции f(x), снизу – осью ОХ, а слева и справа – заданными границами L и R. Абсолютная погрешность (т.е. разница между вычисленным приближенным значением и точным значением) для площади должна быть менее 10−6.

Входные данные

Входной файл INPUT.TXT содержит два вещественных числа L и R (L < R, −108 ≤ L, R ≤ 108).

Выходные данные

В выходной файл OUTPUT.TXT выведите значение площади фигуры с точностью до шести знаков после запятой.

Примеры

INPUT.TXTOUTPUT.TXT
1-10 0.51.994271
20.25 101.169255
3-10 102.915947

Задача D. Золотоискатели

(Время: 1 сек. Память: 16 Мб)

Артель золотоискателей, состоящая из трех человек, добыла N самородков. Один из золотоискателей решил уехать, не ожидая конца вахты, так как у него на Большой земле родился сын.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N - количество добытых самородков (1 ≤ N ≤ 100). Во второй строке записано N целых чисел m1, m2, …, mn (1 ≤ mi ≤ 100), разделенные пробелами - веса добытых самородков.

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
18
1 3 4 1 2 5 1 1
3
1 3 4
23
1 3 6
0

Задача E. Купол

(Время: 1 сек. Память: 16 Мб)

3141-й год. Люди уже давно колонизировали Луну. Однако иногда возникают небольшие трудности. Например, недавно на поверхность Луны упало два метеорита. В результате их падения образовалось два кратера, имеющих форму окружностей (поверхность Луны в этой задаче можно считать плоской). Центр первого кратера находится в точке (x1, y1), центр второго в точке (x2, y2). Их радиусы равны r1 и r2 соответственно.

Кратеры оказались достаточно глубокими, поэтому было решено их неким образом закрыть. Для этого было решено возвести полусферический купол, на поверхности которого разместить солнечные батареи (нельзя же допустить, чтобы пропадало так много свободного места). Разумеется, чем больше радиус основания купола, тем больше требуется ресурсов и времени на его возведение. Поэтому требуется построить купол с минимальным радиусом основания.

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

Входные данные

Входной файл INPUT.TXT содержит шесть чисел: x1, y1, r1 и x2, y2, r2. Все числа во входном файле целые и не превосходят 10000 по абсолютному значению. Радиусы кратеров положительны.

Выходные данные

В выходной файл OUTPUT.TXT выведите три числа: R, X, Y – соответственно минимальный радиус основания купола и координаты центра основания купола. Все числа следует выводить с точностью не хуже 10−4.

Пример

INPUT.TXTOUTPUT.TXT
10 0 1
2 0 1
2 1 0

Задача F. Сыграем?

(Время: 1 сек. Память: 16 Мб)

– Что имеем?

– Всего лишь два предмета:

  1. Шахматная доска размера N на M, в каждой клетке которой записана цифра ноль;
  2. Кубик, на каждой грани которого записана одна цифра, причём никакие две грани не содержат одинаковых цифр. Также известно, что грань кубика идеально совпадает с клеткой доски.

– А где кубик?

– Изначально кубик находится в верхнем левом углу доски.

– Что можем делать? И сколько раз?

– Всего лишь одно действие: перекатывать кубик на соседнюю клетку по горизонтали и вертикали с той, на которой кубик стоит нижней гранью. Перекатывать кубик можно бесконечное число раз!

– А цифры? При чем тут цифры?

– Когда кубик стоит на какой-то клетке, цифра с нижней грани кубика переписывается на клетку доски.

– А как победить?

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

– Число на шахматной доске?

– Цифры с шахматной доски переписываются в следующем порядке: сначала выписываются друг за другом слева направо цифры с первой строки доски, затем в продолжение этой же строки выписываются цифры из второй строки в том же порядке, затем из третьей и так далее. Выведите максимальное число, которое можно получить вышеописанным способом.

Входные данные

Входной файл INPUT.TXT содержит В первой строке содержатся два целых положительных числа N и M (1 ≤ N•M ≤ 106, N ≤ M) - количество строк и столбцов шахматной доски соответственно.

Вторая строка содержит шесть цифр от '0' до '9', которые написаны на гранях кубика, гарантируется, что никакая цифра не встречается два раза. Порядок перечисления граней следующий: нижняя, передняя, верхняя, задняя, левая и правая.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число без ведущих нулей – ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
11 5
9 3 2 0 4 7
97249
22 2
5 4 7 0 3 6
6650

Задача G. Взвешивание

(Время: 1 сек. Память: 16 Мб)

Имеется N монет, не различимых на первый взгляд. Однако, одна из них фальшивая. Фальшивая монета чуть тяжелее, чем настоящая, но во всем остальном полностью идентична настоящим. Кроме того, есть чашечные весы без гирь и шкалы (по таким весам, можно определить, какая чаша тяжелее или легче, но нельзя сказать на сколько). Найти минимальное количество взвешиваний, за которое можно гарантированно определить фальшивку.

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число N – количество монет (2 ≤ N ≤ 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество взвешиваний.

Примеры

INPUT.TXTOUTPUT.TXT
121
231

Задача H. Формула 001

(Время: 2 сек. Память: 32 Мб)

Мальчик Миша собирается участвовать в школьных соревнованиях по гонкам с препятствиями по версии «Формула 001». Но к любым соревнованиям необходимо готовиться. Младший брат Миши, Ральф, не так силен в гонках с препятствиями, как его старший брат, но зато он обладает незаурядной фантазией. Он решил помочь брату и придумал игру, играя в которую, можно существенно увеличить свой опыт в вождении гоночного автомобиля.

Игра состоит в следующем. Пусть у нас есть бесконечное игровое поле, покрытое бесконечной квадратной сеткой. Некоторое множество узлов этой сетки отмечено. Назовем это множество S. В игре участвуют несколько игроков. У каждого игрока есть машина – фигура, которая может находиться только в узлах из множества S. В начале игры все машины находятся в различных начальных узлах. Ход каждого игрока состоит в перемещении машины в некоторый узел из множества S, возможно, тот же самый. Цель игры – добраться до определенного, финишного узла первым.

Ход происходит по следующим правилам. Пусть на предыдущем шаге машина была перемещена на вектор (X, Y) (если это первый шаг, то X=0 и Y=0). Тогда за один текущий ход машину можно передвинуть на один из следующих векторов: (X−1, Y−1), (X−1, Y), (X−1, Y+1), (X, Y−1), (X, Y), (X, Y+1), (X+1, Y−1), (X+1, Y) и (X+1, Y+1).

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

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

Входные данные

В первой строке входного файла INPUT.TXT находится N – число элементов множества S. 2 ≤ N ≤ 1000. В последующих N строках находятся координаты узлов из этого множества – целые числа Xi, Yi (−109 ≤ Xi, Yi ≤ 109).

Никакие два узла во входном файле не совпадают. Занумеруем эти узлы, начиная с 1, в порядке их описания во входном файле. Стартовым узлом будет являться узел с номером 1, финишным узел с номером N .

Выходные данные

В выходной файл OUTPUT.TXT выведите -1, если добраться до финишного узла невозможно. Иначе, в первой строке выведите минимальное требуемое число ходов K . Во второй выведите K+1 число – номера посещенных узлов в порядке посещения. Первым узлом должен быть узел с номером 1, последним – узел с номером N .

Примеры

INPUT.TXTOUTPUT.TXT
13
0 0
0 1
0 2
2
1 2 3
23
0 0
0 2
0 3
-1


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483