Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 311 312 313 314 315 316 317 >> Отображать по:
#113529
Arkady's Game
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Аркадий и Алексей придумали новую игру. Листок клетчатой бумаги размером 2 N ×2 M клеток заполняется цифрами (по одной цифре в каждую клетку). Затем начинается собственно игра: тот, чья очередь ходить, разрезает листок пополам вдоль короткой стороны (или любой стороны, если листок квадратный), выбирает любую из половин и выбрасывает ее; оставшаяся половина передается другому игроку. При этом игрок получает очки за каждую пару клеток, бывших соседними до разрезания:

• если в соседних клетках были одинаковые цифры, то игрок получает 3 очка;

• если в соседних клетках были цифры одинаковой четности, то игрок получает 1 очко;

• если в соседних клетках были цифры разной четности, то игрок получает 0 очков.

Резать листок можно только по линиям, разделяющим клетки. Игра завершается, когда от листка остается одна клетка — ее разрезать нельзя. Побеждает тот, кто наберет больше очков. Аркадий ходит первым и его интересует, какую максимальную разницу между его очками и очками Алексея он может получить, если оба они будут играть оптимально. Аркадию и Алексею доступны только такие листки, у которых N и M отличаются не более чем на 1.

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

В первой строке записаны два целых числа N и M ( 0 ≤ N , M ≤ 10 , | N − M | ≤ 1 ). Данный листок имеет размеры 2 N ×2 M клеток. В следующих 2 N строках записано содержимое листка. В каждой строке записано 2 M десятичных цифр без пробелов. Каждая цифра соответствует одной клетке исходного листка.

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

Выведите единственное число — максимально возможную разницу между количествами очков Аркадия и Алексея.

Примечание

В первом примере Аркадий может разрезать квадрат по горизонтали, получив 2 очка (за пары 1, 3 и 2, 4). Оставив Алексею половинку с цифрами 1, 2, Аркадий не даст ему шанса заработать ни одного очка. Если же Аркадий разрежет исходный квадрат по вертикали, то он не получит ни одного очка, зато при разрезании любой из оставшихся половин ( или Во втором примере Алексей наберет больше очков, как бы не играл Аркадий. Первым ходом Аркадий может только разрезать листок по вертикали, не получив очков. Если отдать Алексею левую половину, то это позволит ему получить 6 очков, разрезав ее по вертикали (за пары 2, 2 и 1, 1). При этом Аркадию достанется листок , разрезание которого не принесет очков. Если же отдать Алексею правую половину исходного листка, то он сможет получить 1 очко, разрезав листок любым способом. Но для максимизации своего выигрыша Алексей разрежет листок по вертикали и отдаст Аркадию половинку , разрезание которой не принесет последнему очков. Итоговый счет 0:1 в пользу Алексея.

Примеры
Входные данные
1 1
12
34
Выходные данные
2
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

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

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113539
Продажа картин
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Продажа картин ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
32 megabytes

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).

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

Выведите Q строк, где в q -й строке записано единственное число - количество вариантов продать картины клиентам, чтобы хотя бы C человек купили цветные картины, по модулю 10007 после первых q изменений требований.

Разбалловка для личной олимпиады

Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.

Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.

Примеры
Входные данные
2 2
1 1
1 1
1
1 1 1
Выходные данные
1
Входные данные
2 2
1 2
2 3
2
1 2 2
2 2 2
Выходные данные
4
4
Входные данные
4 2
1 2 3 4
1 2 3 4
1
4 1 1
Выходные данные
66
#113541
Шарики
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Шарики ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Есть N шариков, висящих в воздухе вдоль одной линии слева направо. Девочка Перика хочет поиграть со стрелами и проверить свои навыки охотника. Она стреляет в линию шариков слева, запуская стрелу на некоторой высот. Стрела летит вдоль линии слева направо до тех пор, пока не попадет в шарик. В тот момент, когда она его касается, шарик лопается, а стрела летит дальше на высоте, уменьшенной на 1. То есть, если стрела летела на высоте H , то после столкновения она будет лететь на высоте H - 1 . Цель нашего героя - сбить все шарики, использовав минимальное количество стрел.

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

В первой строке записано одно натуральное число N ( 1 ≤ N ≤ 1000000 ). Во второй строке записано N натуральных чисел H i . Каждое число H i ( 1 ≤ H i ≤ 1000000 ) обозначает высоту, на которой висит i-й шарик в порядке слева направо.

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

В единственной строке выведите одно целое число - минимальное количество выстрелов, необходимое Перике для того чтобы сбить все шарики.

Примеры
Входные данные
5
2 1 5 4 3
Выходные данные
2
Входные данные
5
1 2 3 4 5
Выходные данные
5
Входные данные
5
4 5 2 1 4
Выходные данные
3
#113546
Тигры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

В заповеднике живут q тигров. Чтобы следить за положением тигров на территории заповедника, используются ошейники с радиомаяком. Ошейник у каждого тигра имеет радиомаяк с уникальным сигналом. Система обнаружения настраивается на приём сигнала радиомаяка от i-го тигра последовательно для i от 1 до q.

Для приёма сигнала на территории заповедника установлено n приёмников в точках с координатами (x1, y1), ..., (xn, yn). Система обнаружения позволяет сотруднику заповедника за один запрос выбрать любые m (3 ≤ m ≤ n) приёмников. Выбранные приёмники должны являться вершинами выпуклого многоугольника. Система определяет, находится ли радиомаяк i-го тигра внутри этого многоугольника.

Сотрудник заповедника должен локализовать положение каждого тигра. Положение i-го тигра считается локализованным, если удалось определить такое множество приёмников, являющихся вершинами выпуклого многоугольника, что внутри этого многоугольника находится тигр, но нет других приёмников.

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

После того как положение i-го тигра локализовано, система автоматически переходит к приёму сигналов от следующего тигра, пока положение всех q тигров не будет локализовано.

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

Требуется написать программу, которая взаимодействует с программой жюри и локализует положение каждого тигра.

Протокол взаимодействия

Это интерактивная задача.

Сначала на вход подаётся информация об установленных в заповеднике приёмниках и количестве тигров.

Первая строка входных данных содержит целое число n — количество приёмников (3 ≤ n ≤ 5 000). Последующие n строк описывают координаты приёмников, j-я из этих строк содержит два целых числа xj и yj — координаты j-го приёмника ( - 109 ≤ xj, yj ≤ 109). Следующая строка содержит число целое число q — количество тигров (1 ≤ q ≤ 2000).

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

Для каждого теста зафиксировано число k — максимальное количество запросов к системе обнаружения для локализации положения одного тигра. Гарантируется, что k запросов достаточно, чтобы решить задачу для соответствующих данных. Это число не сообщается программе-решению, но ограничения на него в различных подзадачах приведены в таблице системы оценивания. Если программа-решение делает более k запросов для определения местоположения одного из тигров, на этом тесте она получает в качестве результата тестирования «Неверный ответ».

Запрос к системе обнаружения начинается с символа «?», за которым следует целое число m — количество выбранных в запросе приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n).

В ответ программа получает строку «Yes», если тигр находится внутри многоугольника, образованного приёмниками с номерами p1, ..., pm, и строку «No» в противном случае.

После того, как положение тигра локализовано, программа-решение должна вывести строку, начинающуюся с символа «!», за которым следует целое число m — количество выбранных приёмников (3 ≤ m ≤ n), и m различных целых чисел pi — номера приёмников, перечисленные в порядке обхода многоугольника по или против часовой стрелки (1 ≤ pi ≤ n). Эта строка означает, что внутри выпуклого многоугольника, образованного приёмниками с номерами p1, ..., pm, находится тигр и нет других приёмников.

Ответное сообщение от программы жюри отсутствует, и программа-решение должна немедленно приступать к поиску следующего тигра. Локализовав положение тигра с номером q, программа-решение должна завершить работу.

Тигры не перемещаются во время работы системы обнаружения. Координаты тигров в каждом тесте фиксированы и не меняются в процессе тестирования.

Если существует несколько правильных многоугольников, локализующих положение тигра, можно вывести любой из них.

На рисунке продемонстрирована процедура локализации положения каждого из тигров из приведенного ниже примера.

Примечание

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

Страница: << 311 312 313 314 315 316 317 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест