Страница: << 88 89 90 91 92 93 94 >> Отображать по:
#3304
Fish
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Как рассказывала Шахерезада, в одной далёкой стране, посреди пустыни, есть озеро. Вначале в том озере было \(F\) рыбок. Были выбраны \(K\) ценнейших видов драгоценных камней, и каждая рыбка проглотила один камень. Заметьте, что \(K\) может быть меньше \(F\), поэтому некоторым рыбкам достались камни одного вида.

Время шло, рыбки охотились друг на друга. Одна рыбка может съесть другую, если та хотя бы в два раза короче (рыбка \(A\) может съесть рыбку \(B\) тогда и только тогда, когда \(L_A \ge 2L_B\)). Рыбки выбирают своих жертв без каких-то особых правил. Одна рыбка может выбрать несколько меньших рыбок и съесть их одну за одной, а может и не съесть ни одной, даже если способна. Когда рыбка съедает другую, её длина не меняется, однако все камни из живота меньшей рыбки оказываются в животе большей.

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

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

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

В первой строке записано единственное целое число \(F\) — начальное количество рыбок в озере (\(1 \le F \le 500\,000\)). Во второй строке записано единственное целое число \(K\) (\(1 \le K \le F\)) — количество видов драгоценных камней (пронумерованных целыми числами от \(1\) до  \(K\)). В третьей строке записано единственное целое число \(M\) — модуль (\(2 \le M \le 30\,000\)). Каждая из следующих \(F\) строк содержит по два целых числа — длину соответствующей рыбки \(L_x\) и номер вида драгоценного камня \(G_x\), проглоченного ей (\(1 \le L_x \le 1\,000\,000\,000\), \(1 \le G_x \le K\)).

Гарантируется, что хотя бы один камень каждого вида от \(1\) до \(K\) проглочен хотя бы одной рыбкой.

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

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

Примечание к примеру тестов

Всего 11 возможных комбинаций, поэтому нужно вывести 11 по модулю 7, то есть 4.

Возможные комбинации: \([1]\), \([1,2]\), \([1,2,3]\), \([1,2,3,3]\), \([1,3]\), \([1,3,3]\), \([2]\), \([2,3]\), \([2,3,3]\), \([3]\), и \([3,3]\). (Для каждой комбинации перечислены камни, её составляющие. К примеру, \([2,3,3]\) — комбинация, состоящая из одного камня вида 2 и двух камней вида 3.)

Эти комбинации можно получить следующими способами:

  • \([1]\): Можно поймать вторую (или четвёртую) рыбку, пока она не съела какую-то ещё.
  • \([1,2]\): Если вторая рыбка съест первую рыбку, в ней будут камень вида \(1\) (который она изначально проглотила), а также камень вида 2 (из первой рыбки).
  • \([1,2,3]\): Один из возможных способов получения этой комбинации: четвёртая рыбка съедает первую, потом третья съедает четвёртую. Если теперь поймать третью рыбку, у неё в животе найдётся по одному камню всех видов.
  • \([1,2,3,3]\): Четвёртая ест первую, третья ест четвёртую, третья ест пятую, вы ловите третью.
  • \([1,3]\): Третья ест четвёртую, вы её ловите.
  • \([1,3,3]\): Третья ест пятую, третья ест четвёртую, вы её ловите.
  • \([2]\): Вы ловите первую рыбку.
  • \([2,3]\): Третья ест первую, вы её ловите.
  • \([2,3,3]\): Третья ест первую, третья ест пятую, вы её ловите.
  • \([3]\): Вы ловите третью рыбку.
  • \([3,3]\): Третья ест пятую, вы её ловите.

Примеры
Входные данные
5
3
7
2 2
5 1
8 3
4 1
2 3
Выходные данные
4
#3305
Linear Garden
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes
Рамзес Второй только что вернулся с победоносной битвы. Чтобы увековечить свою победу, он решил построить величественный сад. Сад будет содержать длинную линию из растений, которая будет тянуться вдоль всего пути от его дворца в Луксоре до Карнакского храма. Сад будет состоять только из лотосов и папирусов, поскольку они символизируют Верхний и Нижний Египет соответственно.
Сад должен содержать ровно \(N\) растений. Кроме того, он должен быть сбалансирован: на любом непрерывном отрезке сада количества лотосов и папирусов не должны отличаться более, чем на 2. Сад может быть представлен в виде строки букв ‘L’ (лотос) и ‘P’ (папирус).
Например, для \(N\) = \(5\) возможны \(14\) сбалансированных садов. В алфавитном порядке это сады: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP и PPLPL.
Возможные сбалансированные сады данной длины могут быть упорядочены в алфавитном порядке и пронумерованы, начиная с 1. Например, для \(N\) = 5 сад с номером 12 – это сад PLPPL.
Напишите программу, которая по заданным количеству растений \(N\) и строке, которая представляет сбалансированный сад, вычисляет номер, присвоенный этому саду, по модулю заданного целого числа \(M\). Следует заметить, что для решения задачи значение числа \(M\) не имеет никакого другого смысла, кроме как упрощения вычислений.

Ограничения

\(1 \le N \le 1000000\)
\(7 \le M \le 10000000\)

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

Ваша программа должна читать из стандартного ввода данные в следующем формате:
•Строка 1 содержит целое число \(N\) – количество растений в саду.
•Строка 2 содержит целое число \(M\).
•Строка 3 содержит строку из \(N\) символов ‘L’ (лотос) и ‘P’ (папирус), которая представляет сбалансированный сад.

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

Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число от 0 до \(M-1\) включительно – номер, присвоенный саду, описанному в стандартном вводе, вычисленный по модулю M.

Оценивание

Для некоторых тестов, в сумме оцениваемых в 40 баллов, \(N\) не будет превышать 40.

Примечание к первому примеру

Фактический номер, присвоенный PLPPL, это 12. Ответ равен 5, то есть, 12 по модулю 7.

Примеры
Входные данные
5
7
PLPPL
Выходные данные
5
Входные данные
12
10000
LPLLPLPPLPLL
Выходные данные
39
#3306
Pyramid Base
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes
Условие на английском языке (с картинками!)

Подстрочный перевод

Вас просят найти наибольшее подходящее пространство для постройки новой пирамиды. Вам предоставлена информация о доступной для застройки земли в виде квадратной сетки размера N на M. Основание пирамиды должно быть квадратом со сторонами, параллельными линиям этой сетки и с вершинами, лежащими в узлах этой сетки.

Исследование обнаружило множество из P возможно пересекающихся препятствий, каждое из которых описано прямоугольником на сетке. Для того, чтобы построить пирамиду, все клетки, содержащиеся в квадрате её основания, должны быть расчищены от препятствий. Удаление i-го препятствия стоит Ci, препятствия удаляются целиком. Удаление препятствия не оказывает влияния на другие препятствия, даже пересекающиеся.

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

Ограничения

Тесты к этой задаче разбиты на три группы. Для всех групп тестов выполняются следующие ограничения: 

Размеры сетки:
1 <= M, N <= 1,000,000
Стоимости удаления препятствий:
1 <= Ci <= 7,000
X-координаты самых левых и самых правых клеток препятствий:
1 <= Xi,1 <= Xi,2 <= M
Y-координаты самых верхних и самых нижний клеток препятствий:
1 <= Yi,1 <= Yi,2 <= N
1 группа (35 баллов) 
Количество денег:
B = 0
Количество препятствий:
1 <= P <= 1,000
2 группа (35 баллов) 
Количество денег:
0 < B < 2,000,000,000
Количество препятствий:
1 <= P <= 30,000
3 группа (30 баллов) 
Количество денег:
B = 0
Количество препятствий:
1 <= P <= 400,000

Формат входных данных

В первой строке два числа -- M и N соответственно.
Во второй строке одно число B.
В третьей строке одно число P.
Каждая из следующих P строк содержит в себе описание очередного препятствия -- пять чисел Xi,1, Yi,1, Xi,2, Yi,2, и Ci.

Формат выходных данных

Выведите одно число - максимально возможную длину стороны основания пирамиды. Если никакую пирамиду построить невозможно, то выведите число 0.

Примеры
Входные данные
6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20
Выходные данные
4
Входные данные
13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21
Выходные данные
3
#3307
Teleporters
  
#3330
Футболки
  
Array

Петя часто ездит на олимпиады, и потому у него накопилось много футболок. Все футболки он делит на три типа: белые, чёрные и цветные. Каждое утро он выбирает футболку и носит её весь день. Петя любит ходить только в свежих футболках, и поэтому, если он уже надевал одну, то следующий раз он наденет её только после стирки. Его мама не стирает вместе футболки разных типов (иначе они полиняют). Кроме того, мама соблюдает инструкции по оптимальной загрузке стиральной машинки, и для стирки ей требуется ровно \(K\) футболок. При этом, конечно, стирать уже чистые футболки она не будет. Подразумевается, что мама стирает футболки сразу же, как ее об этом попросит Петя, и на следующий день он уже может их надевать.

Один из типов футболок Петя любит больше остальных, отчасти из-за того, что количество футболок этого типа позволяет носить только их. Но однажды Пете сказали, что он одевается не “по моде”, на что Петя обиделся и поспорил, что он сможет \(N\) дней одеваться модно. По моде, принятой в их школе, нельзя ходить два дня подряд в однотипной футболке и нельзя прийти в футболке того же типа ровно через неделю, после того как ты ее надел (например, два понедельника подряд). Школьная мода распространяется и на те дни, когда в школу ходить не надо.

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

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

Во входном файле содержатся пять целых чисел \(N, W, B. C\) и \(K\), разделенных пробелами — число дней, которые Петя должен носить футболки “по моде”, количество белых, черных и цветных футболок, имеющихся у него соответственно, и количество грязных однотипных футболок, которое согласится стирать мама. Гарантируется, что хотя бы одно из чисел \(W, B, C\) не меньше \(K\). \(1 \le N \le 1000, 1 \le K \le 1000, 0 \le W \le 1000, 0 \le B \le 1000, 0 \le C \le 1000\).

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

В первой строке выходного файла выведите единственное слово YES или N0 — ответ на вопрос задачи. Если ответ YES, то во второй строке выведите \(N\) символов, где \(i\)-ый символ означает цвет футболки, которую Петя будет носить в \(i\)-ый день. Символ “W” означает белый цвет, “В” — черный, “С” — цветной.

Примечание

Система оценки

Тесты 1-3, из условия, оцениваются в 0 баллов.

1. В тестах этой группы среди чисел \(W, B\) и \(C\) хотя бы одно равно нулю. Эта группа оценивается в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).

2. Баллы за тесты этой группы начисляются только при прохождении всех тестов 1 группы. Некоторые тесты этой группы объединяются в подгруппы, баллы за каждую подгруппу ставятся только при прохождении всех тестов подгруппы

Примеры
Входные данные
2 5 0 4 1
Выходные данные
YES
WC
Входные данные
4 3 4 5 3
Выходные данные
YES
CWCW
Входные данные
10 3 2 1 3
Выходные данные
NO
Страница: << 88 89 90 91 92 93 94 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест