Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 18 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: << 1 2 3 4 >> Отображать по:
#1745
Ездящий город
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».

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

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

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

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

Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).

Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.

Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.

Будем считать, что времени на то, чтобы отметиться на контрольном пункте и на то, чтобы пересесть с автобуса на автобус, участнику не требуется. Т.е. если, например, в момент 10 он прибывает на какой-то контрольный пункт, то дальше он может уехать любым автобусом, отправляющимся от этого контрольного пункта в момент времени 10 или позднее.

Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).

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

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

Примеры
Входные данные
2 2
2 1 3 1
1 2 5 4
3
1 2 1
Выходные данные
7
Входные данные
3 4
2 1 30 10
1 2 50 40
2 3 45 10
3 1 55 10
3
1 2 1
Выходные данные
65
Входные данные
2 2
1 2 3 1
1 2 5 4
3
1 2 1
Выходные данные
-1
#1750
Подпалиндромы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

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

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

Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.

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

Выведите одно число — количество подстрок данной строки, являющихся палиндромами

Примеры
Входные данные
aaa
Выходные данные
6
Входные данные
aba
Выходные данные
4
#3204
Отрезки на прямой возвращаются
  

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

  • он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
  • среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
Выходные данные
3 4 0 0
#3205
Отрезки на прямой возвращаются--2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

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

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

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

Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

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

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

Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
Выходные данные
OK
WA
WA
OK
#3331
Мелодия
  

Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.

Мелодия состоит из \(M\) нот \(b_1, b_2, \dots, b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\), \(L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i\) (\(i = 1, 2, \dots N\)) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i\) (\(i = 1, 2, \dots M\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.

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

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

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--3, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 100\), \(1 \le M \le 100\), \(0 \le a_i \le 1\,000\), \(0 \le b_i \le 1\,000\), \(0 \le L \le 10^6\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le N \le 1\,000\), \(1 \le M \le 1\,000\), \(0 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\), \(0 \le L \le 10^9\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 10^5\), \(1 \le M \le 10^5\), \(0 \le a_i \le 10^6\), \(0 \le b_i \le 10^6\), \(0 \le L \le 10^9\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Некоторые тесты этой группы объединяются в подгруппы, тесты за каждую подгруппу ставятся только при прохождении всех тестов подгруппы.
Примеры
Входные данные
6 8 179
4 9 23 15 43 7
3 10 14 7 3 8 7 3
Выходные данные
0
Входные данные
5 8 5
5 3 8 14 1
10 7 3 7 12 3 3 6
Выходные данные
4
Входные данные
2 2 4
6 13
8 10
Выходные данные
1
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест