В непроходимом лесу имеется N полянок и M тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.
На двух разных полянках живут Красная Шапочка и ее бабушка. Домик Красной Шапочки находится на полянке с номером 1, а домик бабушки - на полянке с номером N. Красная Шапочка хорошо ориентируется в лесу и знает, какое минимальное время ей потребуется для прохождения каждой тропинки. Когда Красная Шапочка идет по лесу, она переходит с тропинки на тропинку только на полянках. На каждой полянке есть укрытие, в котором Красная Шапочка может спрятаться на некоторое время.
В этом же лесу живет Волк. Время, за которое Волк пробегает какую-либо тропинку, может отличаться от времени, за которое по ней проходит Красная Шапочка. Кроме того, если Волк пробегает по одной и той же тропинке несколько раз, то каждый раз он может тратить на это разное время.
С края полянки, где живет Красная Шапочка, Волк увидел, что она собирается нести пирожки бабушке и побежал по тропинкам привычного ему пути от дома Красной Шапочки к дому бабушки. Волк начинает бежать от домика Красной Шапочки в тот момент, когда она решила выйти из дома, его путь заканчивается как только он окажется на полянке с домиком бабушки. Ни на одной полянке Волк не задерживается.
Чтобы застать бабушку в целости и сохранности, Красной Шапочке необходимо обогнать Волка. При этом ей нельзя оказаться с Волком на одной тропинке, даже если Волк уже покидает ее, а она только появляется на ней, или наоборот. Чтобы избежать встречи с Волком на полянке, Красная Шапочка использует имеющееся там укрытие. Красной Шапочке нельзя появляться на полянке одновременно с Волком или покидать укрытие на полянке в тот момент, когда на ней появляется Волк. При необходимости Красная Шапочка может идти по тропинке дольше минимально возможного времени, а также выйти из дома позже, чем она исходно решила.
Необходимо написать программу, которая поможет Красной Шапочке добраться к бабушке раньше Волка, если известна последовательность тропинок, по которым побежал Волк.
Первая строка входного файла содержит числа N, M и K (2 ≤ N ≤ 2000, 1 ≤ M ≤ 100000, 1 ≤ K ≤ 100000). Следующие M строк содержат по три числа: Bi, Ei - номера полянок, которые соединяет i-я тропинка, и Ti - минимальное время, за которое Красная Шапочка может по ней пройти (1 ≤ Ti ≤ 10000). В следующих K строках находится последовательное описание пути Волка, по два числа в строке: Pi - номер тропинки, по которой он побежит, и Vi - время, которое он на это затратит (1 ≤ Vi ≤ 10000). Путь волка всегда начинается на полянке 1 и заканчивается на полянке N. Все числа во входном файле целые и в пределах одной строки разделены пробелами.
В том случае, если Красная Шапочка не может добраться до домика бабушки быстрее Волка, выходной файл должен содержать слово 'NO'.
Если Красная Шапочка сможет добраться до домика бабушки быстрее волка, в первой строке выходного файла должно быть слово 'YES'. Во второй строке в этом случае должно содержаться число тропинок в пути Красной Шапочки. В третью строку следует вывести номера тропинок в том порядке, в котором Красная Шапочка должна по ним пройти. Числа должны быть разделены пробелами.
Информацию о времени прохождения по тропинкам и остановках на полянках в выходной файл выводить не нужно.
\(2 \leq N \leq 200\) Решение оценивается в \(30\) баллов.
\(NK \leq 6 \cdot 10^6\) Решение оценивается в \(40\) баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в \(30\) баллов.
3 2 3 1 2 13 1 3 9 1 5 1 5 2 5
YES 1 2
В школу бальных танцев профессора Падеграса записались n учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора?
В первой строке задано число n (1 ≤ n ≤ 106). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику).
В единственной строке должно содержаться единственное число — количество вариантов выбора требуемой группы.
Тесты в этой задаче разбиты на группы. Баллы начисляются только за группу целиком в том случае, когда пройдены все тесты группы, а также все тесты предыдущих групп.
8 aabbaabb
10
В известном городе Санкт-Тверь решили построить новый микрорайон, представляющий в плане прямоугольную область. Границы микрорайона и его улицы по проекту ориентированы строго по сторонам света, причем улицы разбивают микрорайон на кварталы размером 1 км × 1 км.
Во время привязки исходного проекта к местности выяснилось, что некоторые кварталы по проекту микрорайона оказываются полностью или частично расположенными на топком болоте. Область, занимаемая болотом, связна и со всех сторон окружена подлежащими застройке кварталами микрорайона (область связна, если из любой ее точки можно добраться в любую другую, не выходя за пределы области).
Для сохранения экологии местности и обеспечения безопасности жителей занятую болотом область решили оградить стеклянным забором. Забор должен проходить только по границам кварталов проектируемого микрорайона, отделяя болото, и, возможно, некоторые кварталы проекта, не занятые болотом, от остальной части микрорайона.
Для экономии строительных материалов забор должен иметь минимальную длину. Среди всех заборов минимальной длины нужно выбрать тот, для которого площадь части микрорайона, попадающей внутрь забора, минимальна.
Требуется написать программу, которая спроектирует забор с заданными выше свойствами.
Входные данные содержат описание многоугольника — границы области, состоящей только из кварталов c заболоченными участками. Стороны многоугольника параллельны осям координат.
В первой строке задано целое число n — количество вершин в многоугольнике (4 ≤ n ≤ 100 000, n четное). В каждой из следующих n строк заданы два целых числа — координаты очередной вершины при обходе этого многоугольника против часовой стрелки. Все числа не превосходят 109 по абсолютной величине. Никакие три последовательные вершины границы не лежат на одной прямой. Граница многоугольника не содержит самопересечений и самокасаний.
Вывод программы на стандартный поток должен содержать описание многоугольника, определяющего искомый забор. Формат описания многоугольника тот же, что и для входных данных. Никакие три последовательные вершины этого многоугольника не должны лежать на одной прямой.
8 0 0 9 0 9 9 6 9 6 3 3 3 3 6 0 6
6 0 0 9 0 9 9 6 9 6 6 0 6
Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета. Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5 + 1 + 4 + 3 = 6 + 7.
Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера ☺. Для этого он расширил свое определение счастливого номера на n-значные номера лицевых счетов и других документов, состоящих из цифр от 0 до k (1 ≤ k ≤ 9). Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...
Вам предлагается определить количество несчастливых n-значных номеров, которые можно составить, используя цифры от 0 до k. В номерах допускается любое количество ведущих нулей.
Входной файл unlucky.in содержит описание нескольких видов номеров. Каждый вид номеров определяется значениями n и k. Для данного входного файла вы должны создать соответствующий ему выходной файл и отправить его на проверку жюри.
Входной файл содержит несколько пар значений n и k, каждая пара записана в отдельной строке.
Для каждой пары значений n и k входного файла выведите в соответствующей строке выходного файла искомое количество несчастливых билетов или 0, если такое число вам получить не удалось. Количество строк во входном и выходном файлах должно совпадать.
За правильное решение задачи для каждого вида номеров вы получите 5 баллов. Так, представленный в примере выходной файл соответствует 15 баллам.
При сдаче на проверку выходного файла во время тура вы будете получать одно из двух сообщений:
4 1 7 1 3 2 6 2 22 2 7 9 8 7 9 6 8 8 12 9 20 9 20 3 17 5 16 7 15 9 19 5 26 9 100 3 99 4 50 5
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ≥ 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.
Требуется написать программу, которая по заданным числам n и k найдет такое d, чтобы число n в системе счисления с основанием d заканчивалось как можно большим количеством цифр k.
Вводятся два целых десятичных числа n и k (1 ≤ n ≤ 1011; 0 ≤ k ≤ 9).
Выведите два числа: d — искомое основание системы счисления и l — количество цифр k, которым заканчивается запись числа n в этой системе счисления. Если искомых d несколько, выведите любое из них, не превосходящее 1012 (такое всегда существует).
Примеры
|
|
| комментарий |
| 49 1 | 3 2 | 4910 = 12113 |
| 7 5 | 3 0 | Ни в одной системе счисления 7 не заканчивается на цифру 5 |
4 4
5 1
9 9
10 1