После конца соревнования, если вы
захотите, решить какие-либо задачи, не сданные на соревновании, то можете
перейти по данной ссылке (http://codeforces.com/blog/entry/47622) и получить
алгоритм, как это сделать.
Задача A. Контур-кампус
Ограничение по времени: 1
секунда
Ограничение по памяти: 64
мегабайта
Олег — настоящий спортивный программист. Сегодня он увидел
объявление на стене. Он сразу же понял, что речь идёт о промышленной
разработке. А пока он не съездит на чемпионат мира по программированию, он в
промышленное программирование ни ногой. Но раз уж он увидел это объявление,
ему стало интересно, чему равна полезность этого текста.
Олег определяет полезность как информативность
минус экспрессивность. Информативность
текста — это количество цифр и английских букв в нём. Экспрессивность
текста — это количество знаков препинания в нём. Знаками препинания
считаются точка, запятая, дефис (тире), двоеточие, восклицательный знак.
Олег мгновенно смог посчитать полезность объявления. Теперь
ваша очередь!
В данной задаче всего один тест. Он содержит текст
объявления в кодировке Win-1251. Программа, которую вы напишете, может считать текст и
обработать его, либо ничего не читать из входных данных, а сразу выдать
правильный ответ.
Выведите единственное
целое число — полезность объявления.
тест
Подавай заявку и
приезжай на Контур.Кампус - школу промышленной разработки СКБ Контур, которая
проходит за городом в атмосфере настоящего стартапа.
В 2016 году Кампус проходит с 3 по 6
ноября, заявки принимаем до 14 октября.
Ты научишься писать код для программных продуктов и узнаешь
особенности работы над боевыми проектами. Все это под руководством опытных
разработчиков, которые расскажут, как стать хорошим программистом и не
совершить распространенных ошибок, разберут интересные кейсы и примеры. Кампус
- это много новых, полезных и приятных знакомств!
Основной язык Кампуса
- C#. Язык довольно прост в освоении, и мы не требуем виртуозного
им владения. Главное - не бояться.
Подробности можно прочитать тут: kontur.ru/kampus.
ответ
100
Ответ в примере неверный и приводится лишь для иллюстрации
формата вывода.
Зато объявление самое настоящее! Если вы не пройдёте сегодня в основной тур
четвертьфинала, прочитайте его внимательней после соревнования :)Разбор задачи А. Контур-кампус
В этом тексте 23 знака препинания, 15 латинских букв, 8
цифр.
Ответ:
15 + 8 - 23 = 0
Задача B. Сильный программист
Ограничение по
времени: 1 секунда
Ограничение по памяти: 64 мегабайта
Миша хочет стать очень сильным
программистом. Поэтому он качает пальцы, вися на турнике. Миша выполняет N подходов
к турнику. При каждом подходе он висит на турнике T секунд.
Между подходами Миша отдыхает P секунд. Тренировка считается оконченной
после последнего подхода.
Чтобы чётко следовать плану
тренировки, Миша использует приложение на телефоне, которое пищит, когда Мише
нужно залезть на турник или слезть с турника.
Однако Мише
не хватает ещё одного приложения, которое сможет до начала тренировки сказать,
сколько секунд составит её длительность. Приложение должно принимать на вход
числа N, P и
T, после чего
выдавать общее время тренировки. Ваша задача — реализовать такое приложение.
Входные данные содержат целые числа T, P, N (1
^ T,P ^
10; 2 ^ ^ 10). Каждое число
записано с новой строки.
Выведите целое число — общее время
тренировки в секундах.
|
тест
|
ответ
|
|
2
|
22
|
|
3
|
|
|
5
|
|
|
|
Разбор задачи B. Сильный программист
Общее время на подходы: N * T
Общее
время на перерывы (N - 1) * P, т.к.
перерывов меньше на единицу, чем подходов Ответ: сумма этих двух величин
Задача C. Волчок
Ограничение по времени: 1 секунда
Ограничение по памяти: 64
мегабайта
Папа сделал маленькому Вите
игрушку-волчок. Волчок — это жестяной круг, через центр которого продета ось
вращения. Если такой волчок хорошо раскрутить, он может долгое время вращаться,
не падая.
Волчок получился не очень красивым, тогда папа разделил его верхнюю поверхность
на четыре одинаковых сектора и решил покрасить каждый сектор в один из цветов:
красный, зелёный, белый, синий. Все четыре сектора должны быть покрашены в
разные цвета. Подумав, папа понял, что существует шесть способов раскрасить
волчок:
Папа не смог
выбрать лучший способ и спросил у Вити, какой волчок тот хочет. Витя назвал
порядок цветов по часовой стрелке, который ему нравится больше всего. Какой из
шести способов раскраски, приведённых на рисунке, выбрал Витя?
В
единственной строке записаны четыре латинские буквы, обозначающие порядок
цветов, названный Витей. Буква «г» обозначает красный цвет, буква «g» — зелёный, буква «w» — белый,
буква «b» — синий. Все четыре буквы различны.
Выведите
целое число от 1 до 6 — способ раскраски волчка, который нравится Вите больше
всего.
|
тест
|
ответ
|
|
grbw
|
3
|
|
rgbw
|
5
|
|
|
Разбор задачи C. Волчок
Есть
всего 24 перестановки из четырёх цветов. Для каждой из них вы заранее можете
глазами на картинке найти ответ и записать отдельным if'ом в программе.
Задача D. Судоку
Ограничение по
времени: 1 секунда
Ограничение по памяти: 64 мегабайта
Помогите Васе решить такой судоку.
|
|
4
|
|
2
|
|
6
|
8
|
|
9
|
|
|
|
|
7
|
9
|
8
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
|
7
|
9
|
|
|
1
|
|
|
6
|
|
3
|
|
1
|
4
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
7
|
|
4
|
|
9
|
1
|
|
|
5
|
|
6
|
|
3
|
|
2
|
|
|
6
|
|
|
|
|
8
|
|
|
Чтобы решить
судоку, нужно заполнить все свободные клетки квадрата цифрами от 1 до 9 так,
чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3 х 3 каждая
цифра встречалась бы ровно один раз.
Гарантируется,
что существует единственный способ решения данного судоку.
В единственной строке даны целые
числа i и
j —
координаты клетки (1 ^ i,j ^
9). Первая координата клетки — номер строки (сверху вниз), вторая — номер
столбца (слева направо). Клетка судоку (i,j) изначально пуста.
В этой задаче 53 теста, по одному
тесту на каждую пустую клетку судоку. Порядок тестов известен и приведён ниже.
|
1)
|
5
|
5
|
10)
|
2
|
8
|
19)
|
3
|
8
|
28)
|
5
|
9
|
37)
|
6
|
9
|
46)
|
8
|
6
|
|
2)
|
1
|
1
|
11)
|
2
|
9
|
20)
|
3
|
9
|
29)
|
6
|
1
|
38)
|
7
|
2
|
47)
|
8
|
8
|
|
3)
|
1
|
3
|
12)
|
3
|
1
|
21)
|
4
|
1
|
30)
|
6
|
2
|
39)
|
7
|
3
|
48)
|
9
|
2
|
|
4)
|
1
|
5
|
13)
|
3
|
2
|
22)
|
4
|
2
|
31)
|
6
|
3
|
40)
|
7
|
4
|
49)
|
9
|
3
|
|
5)
|
1
|
8
|
14)
|
3
|
3
|
23)
|
4
|
3
|
32)
|
6
|
4
|
41)
|
7
|
5
|
50)
|
9
|
5
|
|
6)
|
2
|
1
|
15)
|
3
|
4
|
24)
|
4
|
7
|
33)
|
6
|
5
|
42)
|
7
|
6
|
51)
|
9
|
6
|
|
7)
|
2
|
2
|
16)
|
3
|
5
|
25)
|
4
|
8
|
34)
|
6
|
6
|
43)
|
7
|
8
|
52)
|
9
|
7
|
|
8)
|
2
|
3
|
17)
|
3
|
6
|
26)
|
5
|
1
|
35)
|
6
|
7
|
44)
|
8
|
3
|
53)
|
9
|
8
|
|
9)
|
2
|
7
|
18)
|
3
|
7
|
27)
|
5
|
3
|
36)
|
6
|
8
|
45)
|
8
|
4
|
|
|
|
|
|
|
Формат выходных
данных
Выведите число, которое находится в клетке (i, j) в решённом судоку.
Пример
|
Разбор задачи D. Судоку
Мы
специально выбрали судоку попроще. Вы могли написать программу или заранее
решить судоку на бумаге. Если вы не решили эту задачу и не знаете, как это
сделать, вбейте в поисковик "как решать судоку” и найдёте множество
различных алгоритмов.
Задача E. Конфеты
Ограничение по времени: 1 секунда
Ограничение по памяти: 64
мегабайта
У Маши p конфет,
а у Паши q конфет.
Известно, что числа p и
q не
меньше двух и не имеют общих делителей, кроме единицы. Мы скажем вам, чему
равняется сумма p и
q. Скажите нам, чему могут равняться эти числа.
Единственная
строка содержит целое число n — общее количество конфет у Маши и Паши (4
< n <
109).
Выведите через пробел целые числа p и q такие, что:
1. p > 2; q > 2;
2. p + q = n;
3. p и
q не
имеют общих делителей, кроме единицы.
Если задача
имеет несколько решений, вы можете вывести любое из них. Если задача не имеет
решения, выведите —1.
|
тест
|
ответ
|
|
12
|
5 7
|
|
4
|
-1
|
|
|
Разбор задачи E. Конфеты
Пустим
цикл по i от 1 до n. На каждом шаге будем находить НОДО, n - i) за линейное время (простым перебором всех делителей). Такой
алгоритм даст решение задачи за O(n * n). Однако если остановить программу после первого найденного
подходящего i, то алгоритм будет работать за O(log n * log n). Дело в том, что если некоторое простое i не подошло под ответ, то n делится на i. Поэтому когда вы дойдёте до 30го простого, ваше n должно будет делится уже на произведение всех простых от 1
до 30, что больше 1e9, а значит невозможно.
Задача F. Влад в армии
Ограничение по
времени: 1 секунда
Ограничение по памяти: 64 мегабайта
Влад служит в армии всего месяц.
Сегодня у его батальона первый выезд в поля. Сразу же после приезда подошёл
офицер и сказал прокопать ров из точки (0, 0) в точку (п + 1, 0). Ров должен
представлять из себя ломаную, которую офицер нарисовал на схеме и передал
Владу. Влад обладает талантом организатора, поэтому тут же выбрал несколько
сослуживцев-рядовых и отправил их копать ров по выданной ему схеме.
Но вот проблема — через минуту
пришёл другой офицер и сказал, что ров из точки (0, 0) в точку (п + 1, 0)
нужно прокопать по другой схеме. Влад подумал и решил выкопать оба рва, чтобы
оба офицера остались довольны.
За день оба
рва были выкопаны, а ночью прошёл дождь и наполнил их водой. Найдите общую
площадь образовавшихся при этом островов.
Первая схема рва представляет
собой ломаную (0, 0)-(1,yi)-(2,y2)-...-(n,yn)-(n + 1, 0). Вторая схема рва представляет собой
ломаную (0,0)-(1, Y\)-(2,
Y2)-...-(n, Yn)-(n + 1,0).
Первая
строка содержит целое число п (2 ^ п ^ 1000). Вторая строка содержит целые
числа yi, y2, ..., yn. Третья
строка содержит целые числа Yi, Y2, ..., Yn. Гарантируется,
что -1000 ^ yi, Yi ^
1000 и yi = Yi.
Выведите
общую площадь островов, образовавшихся после дождя. Ответ должен быть выведен с
абсолютной или относительной точностью не менее 10_4.
|
тест
|
ответ
|
|
5
|
4.0000000000
|
|
2 2 2 2 1
|
|
|
13 3 10
|
|
|
|
В примере после дождя образовалось три
острова с площадью 0.75, 1.5 и 1.75 соответственно.
Разбор задачи F. Влад в армии
Проведём
n + 2 вертикальные прямые с х от 0 до n + 1. Они разобьют данные схемы на n + 1 полосу. Решим задачу для каждой полосы независимо, а
после просуммируем. В каждой полосе будет ровно по одному отрезку от каждой
схемы. Если они не пересекаются, то нам нужно найти площадь четырёхугольника
(или треугольника в случае крайней левой или крайней правой полосы). Если они
пересекаются, то мы получаем два треугольника с общей вершиной и параллельными
сторонами, не содержащими эту вершину. Такие треугольники подобны и из подобия
можно найти их высоты, а значит и площади.
Задача G. Открытый Кубок
Ограничение по времени: 2 секунды
Ограничение по памяти: 256
мегабайт
Эндрю — тренер по спортивному программированию.
Прямо сейчас идёт этап Открытого Кубка по программированию, и Эндрю интересны
результаты тех команд, которые он тренирует.
В его любимом браузере есть
функция поиска текста на странице: Эндрю вводит некоторую строку, и браузер
показывает все её вхождения. Эндрю хочет воспользоваться этим функционалом,
чтобы смотреть результаты своих команд. Для этого ему нужно выбрать строку,
которая входит во все названия его команд и не входит в название ни одной
другой команды.
Но таблица текущих результатов
Открытого Кубка устроена так, что команда начинает отображаться в ней только в
тот момент, когда впервые отправляет решение на проверку. Изначально таблица
пуста. Это означает, что при появлении в таблице результатов каждой новой
команды Эндрю, возможно, потребуется обновить строку поиска. Среди всех команд
Эндрю есть одна любимая, которая, к счастью для него, сделала первую попытку на
соревновании. Так что даже в таблице результатов из одной команды Эндрю есть,
за кого болеть.
Найдите
строку, по которой должен искать Эндрю после каждой появляющейся в таблице команды.
В первой
строке записано целое число n — общее число команд, которые отправляли свои
решения на проверку (1<= n <= 10). Далее в n строках
перечислены названия этих команд в том порядке, в котором они появлялись в
таблице результатов. Названия команд попарно различны и состоят только из
строчных латинских букв и символов подчёркивания «_». После названия тех
команд, которые тренирует Эндрю, добавлен символ «+». Длины всех названий не
превосходят 10.
После
появления в таблице результатов каждой из команд выведите наименьшую (по длине)
общую подстроку названий команд Эндрю, не содержащуюся в названиях других
команд (учитываются лишь те команды, который в этот момент присутствуют в
таблице результатов). Если подходящих строк несколько, выведите любую из них.
Если подходящей строки не существует, нужно выдать «-1».
|
тест
|
ответ
|
|
6
|
m
|
|
mit_kotiki+
|
t
|
|
sjtu_koty+
|
k
|
|
itmo_first
|
ot
|
|
msu_koshki
|
kot
|
|
mipt_alot
|
-1
|
|
spsu_kot
|
|
|
|
Разбор задачи G. Открытый Кубок
Будем
решать задачу n раз: отдельно для каждого нового
запроса. Переберём все подстроки первой строки за время O(L * L), для каждой
из них проверим подходит ли она. Для этого: пробежимся по всем остальным
строкам и найдём, входит ли она в них. Общая сложность такого решения: O(n * n * LM), что не превосходит нескольких миллионов действий и требует
меньше 0.1 секунды
Задача H. Пасьянс
Ограничение по времени: 1 секунда
Ограничение по памяти: 128
мегабайт
Рубина по вечерам любит
раскладывать пасьянс. Для этого она использует фамильную колоду карт. В колоде
Рубины m * n карт,
каждая из которых имеет одну из m мастей и достоинство от 1 до n. В колоде нет двух карт одной масти с
одинаковым достоинством.
Разложить пасьянс — это значит
разложить все карты на m стопок
так, чтобы в каждой стопке все карты были одной масти и следовали снизу вверх в
порядке возрастания достоинства. Пасьянс начинается с того, что Рубина тасует
карты и раскладывает их рубашкой вниз в к горизонтальных рядов, i-й ряд состоит
из ai
карт. За один ход разрешается взять самую правую карту из какого- нибудь ряда и
переместить её в стопку, соответствующую масти этой карты. Ход возможен лишь в
том случае, если верхняя карта в этой стопке на единицу меньше достоинством,
чем перемещаемая карта, либо если стопка пуста, а перемещаемая карта имеет
достоинство 1.
Рубина уже
перетасовала карты и разложила их в ряды. Выясните, получится ли у неё разложить
пасьянс.
В первой
строке записаны целые числа m, n и
к —
количество мастей, количество карт в масти и количество рядов соответственно (1
<= n*m <= 105; 1 <= к <= 105). Каждая из следующих к строк содержит описание очередного
ряда карт. Описание ряда начинается с целого положительного числа а —
количества карт в i-м ряду. Далее в строке с описанием ряда перечислено аi пар чисел bij, Cij —
масть и достоинство карты, лежащей в i-м ряду на позиции j слева
направо (1 <= bij <= m; 1 <= Cij <= n). Гарантируется,
что все карты на входе различны и вместе образуют колоду Рубины.
Если пасьянс
разложить не удастся, выведите «N0». Иначе в первой строке выведите «YES», а в следующих n * m строках
выведите описания карт в порядке их перекладывания в стопки. Описание карты
должно представлять из себя два числа через пробел — её масть и достоинство.
Если существует несколько различных порядков, удовлетворяющих условию задачи,
можно вывести любой из них.
|
тест
|
ответ
|
|
2 3 2
|
YES
|
|
3 1 3 2 3 1 1
|
11
|
|
3 1 2 2 2 2 1
|
21
|
|
|
2 2
|
|
|
23
|
|
|
12
|
|
|
13
|
|
2 3 2
|
N0
|
|
3 1 3 2 2 1 2
|
|
|
3 1 1 2 3 2 1
|
|
|
|
Разбор задачи H. Пасьянс
Построим
ориентированный граф, вершинами которого будут все карты из колоды. Из вершины A в вершину B проведём ребро, если карту,
соответствующую A, нужно переложить в стопку раньше, чем карту,
соответствующую вершине B (каждую из карт в свою стопку). Соответственно,
ребра между вершинами возникают в двух ситуациях: карты одной масти, и ребро
ведет из карты с меньшим достоинством в карту с большим; карта лежит в ряду
правее другой карты. Заметим, что топологическая сортировка вершин данного
графа, которую можно получить с помощью поиска в глубину, непосредственно
задает требуемый порядок карт. А если в графе будут циклы, то разложить пасьянс
не получится. Кроме того, можно заметить, что для целей топологической
сортировки достаточно оставить только ребра между соседними по достоинству и
соседними в рядах картами. В свете последнего замечания в графе будет O(nm) ребер, и ответ будет найден за O(nm).
Задача I. Сумма степеней
Ограничение по
времени: 5 секунд
Ограничение по памяти: 128 мегабайт
Даны целые числа n,
к, l. Нужно найти
количество способов представить число n в виде l слагаемых,
каждое из которых является степенью числа к с целым неотрицательным показателем.
Слагаемые в сумме должны следовать в порядке неубывания.
В первой
строке записано целое число t — количество тестов (1 <= t <= 100).
Каждая из следующих t строк
содержит целые числа n, k, l (1 <= n <= 1018; 2 <= к <= 1018; 1 <= l <= 100).
Выведите количество способов по модулю 109
+ 7.
|
тест
|
ответ
|
|
3
|
2
|
|
12 3 4
|
1
|
|
7 2 5
|
0
|
|
7 2 2
|
|
|
|
В первом примере число 12 можно представить как 1 + 1 + 1 + 9 или 3 + 3 + 3
+ 3. Во втором примере число 7 можно представить только как 1 + 1 + 1 + 2 + 2. В
третьем примере ни одного представления не существует, т.к. в любом разложении
числа 7 на степени двойки присутствует не менее трёх слагаемых.
Разбор задачи I. Сумма степеней
Давайте рассматривать разбиения на суммы, в которых все
слагаемые упорядочены по невозрастанию. Тогда мы можем действовать следующим
образом: в каждый момент у нас есть какая-то текущая степень, сумма которую
осталось добить, и мы знаем сколько слагаемых осталось поставить. Мы можем либо
взять ещё одно слагаемое текущей степени, либо перейти на степень на одну
меньшую.
Наивный способ оформить данное решение в виде динамического
программирования: dp(sum, deg, count) = dp(sum, deg - 1, count) + dp(sum - k^deg, deg, count - 1)
И база: dp(0, 0,
0) = 1.
Ответ лежит в dp(n, log_k(n) + 1, l ).
Проблема такой наивной динамики: sum до 10^18. Но это не проблема на самом деле: мы
знаем что sum % ^deg = n % ^deg, так как sum получена из n вычитанием степеней k больше либо равных deg. А также мы
знаем что если sum / ^deg больше count, то ответ для такой dp равен 0. Это потому что нам надо использовать count слагаемых каждое из которых не больше ^deg и набрать sum, и при этом ^deg * count < sum. Таким образом вместо sum можно хранить sum / ^deg, и этот
параметр не превосходит I .
Тогда модифицированная dp выглядит так:
dp(s, deg, count) = dp(s * k + n_k[deg - 1], deg - 1, count) + dp(sum - 1,
deg, count - 1),
Где n_k[deg - 1] = n / k^(deg - 2) % k. (то есть (deg - 1)-ый разряд
в k-ичной записи числа n).
База остаётся прежней: dp(0, 0, 0) = 1.
Ответ лежит в dp(0, I og_k(n) + 1, I ).
Состояний в dp - I * I og_k (n) * I , каждое
вычисляется за O(1).
Таким образом общая сложность - 0(I^2 log(n) ).
Задача J. Динамическая сложность строки
Ограничение по
времени: 5 секунд
Ограничение по памяти: 64 мегабайта
Подстрока — это несколько подряд
идущих символов в строке. Префикс строки — это подстрока, включающая первый
символ строки. Суффикс строки — это подстрока, включающая последний символ
строки.
Рассмотрим строку «квалификация».
Строки «валик» или «акация» не являются её подстроками, т.к. буквы этих строк
не идут в ней подряд. «валиф» и «каци» являются подстроками, при этом они обе
не являются ни префиксом, ни суффиксом. «квал» является префиксом, а «кация»
суффиксом строки. Сама строка «квалификация» является собственным суффиксом и
префиксом.
В данной задаче мы считаем, что
номера символов в строке индексируются с нуля.
Периодом строки s назовём
минимальное положительное целое число T, для которого для любого 0 ^ i < |s| верно, что s[i] = s[i mod T], где i mod T — остаток от
деления i на
T.
Грань строки — это её непустой
префикс, который не является всей строкой и при этом равен её суффиксу.
Сложностью строки назовём число различных периодов её граней. Динамической
сложностью строки назовём сумму сложностей всех её префиксов.
Для данного
числа п
требуется найти бинарную строку (над алфавитом {., X}) длины п, имеющую
максимальную динамическую сложность.
Единственная строка содержит целое число п (1 <= п <= 25).
В первой
строке выведите искомую строку длины n, во второй строке выведите её динамическую
сложность. Если существует несколько строк с максимальной динамической
сложностью, можно вывести любую из них.
|
тест
|
ответ
|
|
1
|
0
|
|
2
|
1
|
|
10
|
.X..X..X..
14
|
|
|
Рассмотрим третий пример.
Рассмотрим все префиксы строки и посчитаем их сложность:
«.» — граней нет ^ сложность = 0
«.X»
— граней нет ^ сложность = 0
«.X.»
— грань «.» (период 1) ^ сложность = 1
«.X..»
— грань «.» (период 1) ^ сложность = 1
«.X..X» — грань «.X» (период 2) ^
сложность = 1
« .X..X. » — грани « . » (период 1) и « .X. » (период 2) ^ сложность = 2
« .X..X.. » — грани « . » (период 1) и « .X.. » (период 3) ^ сложность = 2
«.X..X..X» — грани «.X» (период 2) и «.X..X» (период 3) ^
сложность = 2
«.X..X..X.» — грани «.»
(период 1), «.X.»
(период 2) и «.X..X.» (период 3) ^
сложность = 3
«.X..X..X..» — грани «.»
(период 1), «.X..»
(период 3) и «.X..X..» (период 3) ^
сложность = 2
Получаем, что строка «.X..X..X.. » имеет динамическую
сложность 14.
Разбор задачи J. Динамическая сложность строки
Давайте за 2^n переберём все бинарные строки
длины n. После этого за O(n * n) посчитаем их динамическую сложность. Это делается следующим
образом:
1)
Для каждого префикса
посчитаем его период за линейное время с помощью префикс-функции или z-функции. Это
суммарно делается за O(n * n)
2)
Теперь переберём все
префиксы строки. Для каждого префикса будем за время O(n) находить его сложность: все грани строки можно перечислить
за линейное время с помощью алгоритма префикс-функции, после чего взять его
заранее посчитанный период и добавить в словарь. Сложностью данной строки будет
размер словаря. Такой словарь можно реализовать за константное время, храня его
в одном integer’e и добавлять элементы, добавляя бит в нужную позицию.
Общая
сложность решения: O(n * n * 2^n). Оно отработает несколько
минут, после чего вы можете создать новое решение, в котором занести ответы на
все 25 тестов в массив констант.
Этого
уже достаточно, чтоб сдать задачу, однако, у жюри также есть решения за O(n * 2^n) и 0(2^n), но мы их не будем приводить здесь, т.к. их описание
требует гораздо больший объём текста.
Задача K. Открытый Кубок - 2
Ограничение по времени: 2 секунды
Ограничение по памяти: 256
мегабайт
Эндрю — тренер по спортивному
программированию. Прямо сейчас идёт этап Открытого Кубка по программированию, и
Эндрю интересны результаты тех команд, которые он тренирует.
В его любимом браузере есть
функция поиска текста на странице: Эндрю вводит некоторую строку, и браузер
показывает все её вхождения. Эндрю хочет воспользоваться этим функционалом,
чтобы смотреть результаты своих команд. Для этого ему нужно выбрать строку,
которая входит во все названия его команд и не входит в название ни одной
другой команды.
Но таблица текущих результатов
Открытого Кубка устроена так, что команда начинает отображаться в ней только в
тот момент, когда впервые отправляет решение на проверку. Изначально таблица
пуста. Это означает, что при появлении в таблице результатов каждой новой
команды Эндрю, возможно, потребуется обновить строку поиска. Среди всех команд
Эндрю есть одна любимая, которая, к счастью для него, сделала первую попытку на
соревновании. Так что даже в таблице результатов из одной команды Эндрю есть,
за кого болеть.
Найдите
строку, по которой должен искать Эндрю после каждой появляющейся в таблице команды.
В первой
строке записано целое число n — общее число команд, которые отправляли свои
решения на проверку. Далее в n строках перечислены названия этих команд
в том порядке, в котором они появлялись в таблице результатов. Названия команд
попарно различны и состоят только из строчных латинских букв и символов
подчёркивания «_».
После названия тех команд, которые тренирует Эндрю, добавлен символ «+».
Суммарная длина всех названий не превосходит 2 • 105.
После
появления в таблице результатов каждой из команд найдите общую подстроку
названий команд Эндрю, не содержащуюся в названиях других команд (учитываются
лишь те команды, который в этот момент присутствуют в таблице результатов).
Если подходящей строки не существует, нужно выдать «-1 -1». В противном случае
нужно вывести целые числа l и r такие, что искомая строка входит в
название любимой команды Эндрю с позиции l по позицию r (считая
позиции с нуля). Если подходящих строк несколько, выведите самую короткую из
них, а если и таких несколько, то ту, для которой минимально значение l.
|
тест
|
ответ
|
|
6
|
0 0
|
|
mit_kotiki+
|
2 2
|
|
sjtu_koty+
|
4 4
|
|
itmo_first
|
5 6
|
|
msu_koshki
|
46
|
|
mipt_alot
|
-1 -1
|
|
spsu_kot
|
|
|
|
Разбор задачи K. Открытый Кубок - 2
Построим
общее суффиксное дерево для всех строк из входа, при этом при построении
отметим в каждой вершине, каким строкам она принадлежала. Далее используем
классический приём объединения множеств вдоль дерева -- обходим суффиксное
дерево в глубину и поддерживаем множество, содержащее все номера строк, которые
могут быть встречены в поддереве, сливая эти множества снизу. При этом при
объединении множеств будем добавлять элементы меньшего множества к большему,
что в сумме отработает за nlog^2n.
Далее,
имея такое множество, мы должны узнать наименьший номер строки из второго типа,
в котором встречается ребро (logn) и наименьший номер строки из первого типа, в котором оно не
встречается. Второй запрос также может быть сделан за logn, но в
авторском решении он реализован с помощью бинарного поиска и сравнения номера
элемента с количеством элементов, меньших него за log^2 n.
Итоговая асимптотика: O(n log^2 n).
Комментариев нет:
Отправить комментарий