1-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Марсианский волейбол
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Волейбольный матч на Марсе играется двумя командами до k очков, при этом для победы отрыв должен быть хотя бы на 2 очка. За каждый розыгрыш мяча одна из команд получает ровно 1 очко.

На текущий момент матча счет первой команды равен x, а счет второй команды равен y. Какое минимальное количество мячей будут разыграны до окончания матча?

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 5000).

Каждый тестовый пример описывается одной строкой, содержащей три целых числа, разделенных пробелами: k, x и y (1 ≤ k ≤ 100; 0 ≤ x, y ≤ 100).

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

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

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

Примеры
Входные данные
3
2 1 0
3 4 3
5 0 0
Выходные данные
1
1
5
"B" Раскраска стены
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

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

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

Маша просит вас придумать, как ей покрасить стену.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t.

Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, m, k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ max(n, m)) — размеры стены и количество различных красок у Маши.

В следующих n строках содержатся по m чисел aij:

  • aij = 0, если на позиции (i, j) находится лампа;
  • aij = 1, если на позиции (i, j) находится плитка.

Суммарное количество плиток и ламп по всем тестам не превосходит 105.

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

Для каждого теста в отдельной строке сначала выведите ответ на него:

  • NO, если не существует ни одного способа покрасить стену так, как хочет Маша.
  • YES, если способ перекрасить есть. В этом случае в следующих n строках выведите по m чисел bij — цвет плитки на позиции (i, j) или 0, если на этой позиции лампа. Если подходящих раскрасок несколько, выведите любую из них.

Примеры
Входные данные
2
4 3 2
0 1 0
1 0 1
1 0 1
0 1 0
3 4 2
0 1 0 1
1 0 1 1
1 1 1 0
Выходные данные
YES
0 2 0 
2 0 2 
1 0 1 
0 1 0 
NO
"C" Магический артефакт
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Максим играет в компьютерную игру. Она состоит из n уровней, которые пронумерованы от 1 до n. Их можно проходить в любом порядке, на i-й уровень Максим тратит ai секунд.

Кроме того, Максим может найти магический артефакт, который усилит его персонажа. Артефакт в игре ровно один, и его местонахождение точно неизвестно — на i-м уровне он находится с вероятностью pi. После получения артефакта играть становится существенно проще — с ним Максим проходит i-й уровень за bi секунд (bi ≤ ai). Обратите внимание, что артефакт не действует на том уровне, на котором Максим его нашёл.

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

Математическим ожиданием случайной величины называется сумма по всем возможным исходам произведения вероятности этого исхода на значение величины. В данном случае исходы соответствуют тому, на каком уровне окажется артефакт, а значение величины — время прохождения, если артефакт оказался на этом уровне, а Максим проходит уровни в выбранном порядке.

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

Входные данные содержат несколько тестовых примеров. В первой строке задано одно число t — количество тестов (1 ≤ t ≤ 1000).

Каждый из тестов описывается следующим образом: в первой строке задано число n — количество уровней (1 ≤ n ≤ 105).

В следующих n строках описаны уровни. Каждый из них задаётся тремя целыми числами: ai, bi, xi — время прохождения уровня до и после нахождения артефакта и значение, которое помогает вычислить вероятность найти артефакт на этом уровне. Вероятность вычисляется по формуле pi = xi / 107 (1 ≤ bi ≤ ai ≤ 105; 0 ≤ xi ≤ 107; сумма всех xi равна 107).

Сумма n по всем тестам не превосходит 5·105.

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

Для каждого теста выведите одно число — математическое ожидание времени игры при оптимальном выборе порядка прохождения уровней. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10 - 6.

Примеры
Входные данные
2
3
10 5 10000000
5 3 0
7 3 0
4
3 1 2500000
4 1 2500000
10 1 2500000
2 1 2500000
Выходные данные
16
10.25
"D" Менеджер памяти
Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

Петя активно ведет разработку своего собственного менеджера памяти MEM 2.0 для хранилища на базе магнитных 7D блоков. Однако он столкнулся с проблемой оптимальной выдачи данных из хранилища пользователям.

Всего в менеджере Пети хранится n блоков с данными, пронумерованных от 1 до n, и имеется q запросов о выдаче данных с одного или нескольких из них. Запросы необходимо обработать в том порядке, в котором они поступили.

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

Петин менеджер умеет мгновенно выдавать данные из любого числа блоков, если на каждый из них указывает хотя бы один указатель. Если же это не так, менеджер сначала переставляет указатели, чтобы условие выполнялось, а затем выдает данные — время выполнения этой операции для i-го запроса составляет si миллисекунд, можно переставить любое число указателей.

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

Рассмотрим приведенные в примере тесты.

В первом тесте Петя изначально может поставить указатели на блоки 1, 2 и 4 — после этого первые два запроса выполнятся мгновенно. Перед третьим запросом за s3 = 1 миллисекунду он может поставить указатели на блоки 2, 3 и 5, а перед четвертым запросом за s4 = 1 миллисекунду он может поставить указатели на блоки 1, 3 и 5. Суммарное время на все запросы будет равно s3 + s4 = 2 миллисекунды.

Во втором тесте Пете невыгодно выполнять первые два запроса мгновенно (ставя изначально указатели на блоки 1, 2 и 4), потому что потом ему придется потратить 10 миллисекунд, чтобы поставить указатели на другие блоки. Поэтому оптимальная стратегия для Пети — изначально поставить указатели на блоки 1, 2 и 3, перед вторым запросом на блоки 1, 3, 4 за s2 = 1 миллисекунду, а перед последним запросом поставить указатели на блоки 1, 3 и 5 за s4 = 3 миллисекунды. Итого суммарное время ответа на запросы s2 + s4 = 4 миллисекунды.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, k, q — количество блоков в менеджере, количество указателей и количество пользовательских запросов соответственно (1 ≤ k ≤ n ≤ 105, 1 ≤ q ≤ 106).

В следующей строке содержится q целых чисел si — время, требуемое для перестановки указателей при ответе на i-й запрос (1 ≤ si ≤ 104).

В следующих q строках содержится описание запросов пользователей, i-й запрос описывается одной строкой, где первое число ci описывает количество блоков данных, которое пользователь хочет получить (1 ≤ ci ≤ k), а следующие ci чисел описывают номера этих блоков bi, j в возрастающем порядке (1 ≤ bi, j ≤ n).

Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105, а также сумма ci во всех тестах одних входных данных не превосходит 106.

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

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

Примеры
Входные данные
2
5 3 4
1 1 1 1
1 2
2 1 4
2 2 3
3 1 3 5
5 3 4
1 1 10 3
1 2
2 1 4
2 1 3
3 1 3 5
Выходные данные
2
4
"E" ЛИСА
Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

Илья работает в Лаборатории Изучения Строковых Алгоритмов (ЛИСА). Сейчас он пытается решить такую задачу.

Задан массив строк s1, s2, ..., sn и q запросов. Каждый запрос характеризуется двумя целыми числами li и ri (1 ≤ li ≤ ri ≤ n). Для ответа на запрос необходимо сделать следующее. Назовем строку представимой, если ее можно получить следующим образом: выберем две строки sx и sy, где li ≤ x, y ≤ ri, выберем непустой префикс строки sx и непустой суффикс строки sy, возьмем их конкатенацию. Ответом на запрос является количество различных представимых строк для заданных li и ri.

Например, пусть s = [abc, ab, ac, bcac], выберем li = 2, ri = 3. Представимыми будут строки:

x = 2, y = 2: ab = a + b, aab = a + ab, abb = ab + b, abab = ab + ab.

x = 2, y = 3: ac = a + c, aac = a + ac, abc = ab + c, abac = ab + ac.

x = 3, y = 2: ab = a + b, aab = a + ab, acb = ac + b, acab = ac + ab.

x = 3, y = 3: ac = a + c, aac = a + ac, acc = ac + c, acac = ac + ac.

Всего получилось 12 различных представимых строк.

Помогите Илье решить задачу достаточно быстро.

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

В первой строке заданы два целых числа n и q — количество слов и запросов соответственно (1 ≤ n, q ≤ 105).

Каждая из следующих n строк содержит непустые слова si, состоящие из строчных латинских букв. Суммарная длина всех слов не превосходит 105.

Следующие q строк содержат пары чисел li, ri (1 ≤ li ≤ ri ≤ n) — левая и правая граница i-го запроса соответственно.

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

Выведите q строк, i-я из них должна содержать единственное целое число — ответ на i-й запрос.

Примеры
Входные данные
4 3
abc
ab
ac
bcac
3 4
1 3
2 3
Выходные данные
20
23
12

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.