Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 56 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников
    6-9 классы(30 задач)
    7-9 классы(25 задач)
    10-11 классы(114 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#494
Игра
  

Поле для детской игры представляет собой последовательность кружков, первый из которых является стартом, а последний – финишем. На некоторых из кружков указано действие, которое нужно совершить фишке, попавшей на этот кружок: передвинуть фишку на несколько кружков вперед или назад, или сделать еще один ход. Изначально фишки всехK игроков ставятся на старт. Затем они по очереди делают ходы, которые заключаются в следующем. Игрок получает очередное "случайное" число, используя генератор псевдослучайных чисел, описанный ниже, и передвигает свою фишку на столько кружков вперед, какое число он получил (если это число больше количества кружков до финиша, то игрок останавливается на финише). Если на кружке, куда он попал в результате своего хода, написано, что требуется совершить некоторое действие, то игрок совершает это действие. После этого он совершает действие, указанное на кружке, куда он попал в результате предыдущего действия и т. д. до тех пор, пока он не попадет на кружок, на котором не указано никакого действия.

Игра заканчивается, как только фишка одного из игроков достигнет финиша. Этот игрок и считается победителем. Требуется написать программу, которая по описанию поля и по данным параметрам генератора псевдослучайных чисел определит, кто выиграет в данной игре.

Генератор псевдослучайных чисел устроен следующим образом. Его параметрами являются натуральные числа a, b, c и x0. Генератор порождает последовательность натуральных чисел x1, x2, x3, … по следующему правилу: xn+1 равно остатку от деления (axn+ b) на c (при n = 0, 1, 2, …). Для игры используются числа x1, x2, x3, … именно в этом порядке (число x0 не используется). Все игроки используют общий датчик, то есть, если, например, первый игрок использовал число x1 и передал ход второму, то тот будет использовать число x2, а если ему потребуется повторить ход, то x3 и т. д.

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

В первой строке входных данных содержатся числа a, b, c, x0, описывающие генератор псевдослучайных чисел. Все числа целые неотрицательные и не превосходят 1000; c > 0. В следующей строке записаны числа K – количество игроков и L – количество кружков поля, включая старт и финиш (1 ≤ K, L ≤ 1000). В следующих L–2 строках записаны команды во втором, третьем, …, L–1-м кружке (в кружках старта и финиша никаких команд нет и при попадании туда ничего делать не нужно). Каждая команда записывается парой чисел.

Если первое число равно единице, то это означает, что нужно сделать дополнительный ход. При этом, если второе число равно T и T > 0, то нужно сделать ход на T кружков вперед, если T < 0 – то на |T| кружков назад, а если T = 0, то нужно снова воспользоваться датчиком псевдослучайных чисел и сделать указанное им количество шагов вперед.

Если первое число равно нулю, то ничего делать не нужно. (Если первое число равно нулю, то второе число также равно нулю.)

Другие значения первое число принимать не может.

Число T целое, и всегда таково, что при соответствующем ходе фишка не окажется за пределами доски (но может оказаться на клетке Старт или Финиш). Если же T = 0 и очередное "случайное" число больше, чем количество кружков до финиша, то фишка останавливается на финише.

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

Выведите одно число – номер игрока-победителя. Гарантируется, что одна из фишек обязательно достигнет финиша, причем за время игры будет совершено не более миллиона перемещений (на "случайное" число или число, указанное в кружке).

Примеры
Входные данные
1 1 100 1
2 5
0 0
0 0
1 1
Выходные данные
2
3
Входные данные
1 1 100 1
2 5
0 0
1 0
1 1
Выходные данные
1
2
#496
Точки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.

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

В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа xi, yi – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 106. Некоторые точки могут совпадать.

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

Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.

Примеры
Входные данные
1
0 0
Выходные данные
5.6568542495
Входные данные
2
1 1
1 2
Выходные данные
7.6568542495
#497
Автобусы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

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

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

В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

Во второй строке задаются через пробел M чисел – номера автобусных остановок, рядом с которыми есть станции метро (каждая – не более одного раза).

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

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

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

Подзадачи и система оценки

Данная задача содержит две подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 1 (40 баллов)

В этой подзадаче \(N \leq 2000\)

Подзадача 2 (60 баллов)

Дополнительные ограничения отсутствуют.

Примеры
Входные данные
8 2
1 2
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
1
6
Входные данные
8 2
5 3
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
2
6
#508
Кинотеатр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

\(X\) мальчиков и \(Y\) девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Напишите программу, которая выдаст, как нужно сесть мальчикам и девочкам, чтобы рядом с каждым мальчиком сидела хотя бы одна девочка, а рядом с каждой девочкой — хотя бы один мальчик.

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

Вводятся два числа — \(X\) и \(Y\) (оба числа натуральные, не превосходящие 100).

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

Выведите какую-нибудь строку, в которой будет ровно \(X\) символов B (обозначающих мальчиков) и \(Y\) символов \(G\) (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры
Входные данные
5 5
Выходные данные
BGBGBGBGBG
Входные данные
5 3
Выходные данные
BGBGBBGB
Входные данные
100 1
Выходные данные
NO SOLUTION
#510
Метро
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задано описание метрополитена в виде описания веток. Каждая ветка содержит номера станций, которые на ней находятся. Станция, присутствующая на нескольких ветках - пересадочная. Требуется определить маршрут от станции до станции с минимальным количеством пересадок.

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до \(N\). На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции \(A\) на станцию \(B\). Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции \(A\) на станцию \(B\) добраться невозможно, в этом случае ваша программа должна это определить.

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

Сначала вводится число \(N\) — количество станций метро в городе (2≤\(N\)≤100). Далее следует число \(M\) — количество линий метро (1≤\(M\)≤20). Далее идет описание \(M\) линий. Описание каждой линии состоит из числа \(P_i\) — количество станций на этой линии (2≤\(P_i\)≤50) и \(P_i\) чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: \(A\) — номер начальной станции, и \(B\) — номер станции, на которую нам нужно попасть. При этом если через станцию \(A\) проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию \(B\) проходит несколько линий, то нам не важно, по какой линии мы приедем.

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

Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции \(A\) на станцию \(B\) невозможно, программа должна вывести одно число –1 (минус один).

Примеры
Входные данные
5
2
4 1 2 3 4
2 5 3
3 1
Выходные данные
0
Входные данные
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
Выходные данные
2
Входные данные
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
Выходные данные
1
Входные данные
4
2
2 1 2
2 3 4
1 3
Выходные данные
-1
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест