Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
Всего в игре есть $$$n$$$ различных ресурсов: пшеница, сыр, вино, пряжа, шелк и т. д. За все время игры Игорь смог собрать множество различных ресурсов, каждый свой ресурс он собрал в столбики по $$$a_i$$$ штук. В игре каждый собранный ресурс, оставшийся до конца игры, имеет свою ценность в победных очках равный числу $$$b_i$$$.
Партия затянулась до поздней ночи, Игорю тяжело сосредоточиться и посчитать победные очки. Помогите Игорю посчитать количество очков, которое он получил за свои собранные ресурсы.
В первой строке записано целое число $$$n$$$ $$$(1\leq n\leq 10^5)$$$ — количество различных типов ресурсов в игре.
Далее в каждой $$$n$$$ строк записано по два числа $$$a_i,b_i$$$ $$$(0\leq a_i,b_i\leq 10^5)$$$ — количество ресурсов $$$i$$$ типа у Игоря и цена одного ресурса $$$i$$$ типа.
Выведите одно целое число, количество очков, которое смог заработать Игорь с ресурсов.
5 1 3 2 6 3 1 4 5 5 10
88
5 0 1 0 3 4 4 2 7 1 1
31
Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
Перед началом игры, каждому игроку раздаются фишки, монетки, ресурсы, а также игроки определяют порядок ходов между собой, для этого каждый игрок тянет жребий, это номер, под которым игрок будет выполнять свои действия в первый кон игры. Далее каждый следующий кон игроки меняются своими жребиями по кругу, первый игрок становится последним, второй становится первым, третий становится вторым, четвертый становится третьим. Игорю достался жребий с номером $$$k$$$.
В игре «Орлеан» одними из ключевых фишек в игре являются фишки рыцарей, всего их $$$n$$$ штук. Каждый игрок хочет получить как можно больше этих фишек, поэтому на каждом кону игры игроки будут брать по одной фишке рыцарей из пула. Игра «Орлеан» настолько долгая, что все фишки рыцарей разберут игроки до конца игры.
Помогите Игорю посчитать количество фишек рыцарей, которое Игорь сможет получить за время игры.
В единственной строке задано два целых числа $$$n$$$, $$$k$$$ $$$(1\leq n\leq 100, 1\leq k\leq 4)$$$ — количество фишек рыцарей в пуле, жребий который получил Игорь.
Выведите одно целое число — количество фишек рыцарей, которых возьмет Игорь.
9 3
3
11 2
2
12 3
3
Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
В этот раз Игорь решил играть через моряков. Для его суперстратегии требуется огромное количество моряков, для этого он каждый ход планирует забирать по одной фишке моряка, всего в игре есть $$$n$$$ фишек моряков, и игра будет длиться $$$k$$$ ходов. Поскольку в обычной игре никто не берет моряков, то можно считать, что только Игорь будет их получать.
Фишка моряка ничем не примечательна, при ее получении игрок получает некоторое количество монет, первый моряк дает $$$m$$$ монет, а каждый $$$i$$$ моряк, дает на одну монету больше чем $$$i-1$$$ моряк.
Помогите Игорю сосчитать, сколько он получит монет, забирая каждый ход по одному моряку из оставшихся.
В строке задано три целых числа $$$n$$$, $$$k$$$, $$$m$$$ $$$(1\leq n\leq 10^5, 0\leq k\leq 10^5,1\leq m\leq 10^5)$$$ — количество фишек моряков в игре, количество раундов в игре, количество денег которое приносит первый моряк.
Выведите одно целое число – количество монет, которое принесут суммарно все моряки за время игры.
12 18 2
90
5 4 10
46
75 40 96
4620
Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
В игре особенно важной фишкой являются рыцари, они помогают игроку ходить по дорогам, обеспечивая его безопасность, а также создают гильдии в новых городах, через которые игрок может торговать с местными жителями. Игорь хочет построить свою гильдию в городе Орлеан прямо сейчас. На данный момент у него есть $$$n$$$ фишек в мешке, а также среди них есть целых $$$k$$$ рыцарей. По правилам игры в начале хода игроки вытаскивают на свое поле некоторое количество фишек случайным образом из своего мешка. Все игроки играют честно, никто не подсматривает в мешок и не мухлюет при вытаскивании фишек. Игорь может вытащить из своего мешка $$$m$$$ фишек.
Помогите Игорю определить, какова вероятность события, что Игорь сможет вытащить из мешка хотя бы одного рыцаря для постройки гильдии.
В строке задано три целых числа $$$n$$$, $$$k$$$, $$$m$$$ $$$(1\leq n\leq 20, 0\leq k\leq n,1\leq m\leq 20)$$$ — количество фишек в мешке Игоря, количество фишек рыцарей и то, сколько Игорь сможет вытащить фишек из мешка.
Выведите одно вещественное число — вероятность события, что Игорь сможет вытащить хотя бы один жетон рыцаря из мешка. Ответ считается верным, если совпадает с ответом жюри с точностью 4 знака после запятой.
5 2 2
0.70000000
8 2 4
0.78571429
5 1 6
1.00000000
5 4 1
0.80000000
Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
В игре «Орлеан» игроки могут передвигаться из одного города в другой город по дорогам. По каждой дороге каждый игрок может ходить по нескольку раз.
По легенде игры "Орлеан" перед началом игры на каждой дороге было оставлено по одному мешку с ресурсом от торговца. Каждый ресурс имеет свою ценность в победных очках, например, стог сена стоит 1 победное очко, а шелковая ткань целых 5 очков. Игрок, проходя по дороге, может забрать ресурс, если он еще лежит в мешке.
Под конец игры Игорь находится в городе под номером 1 и планирует сделать ровно $$$k$$$ ходов по дорогам, собирая как можно больше победных очков. Достоверно известно, что Ира, Саша и Леша не планируют тратить последние свои действия в игре на передвижения по дорогам, а также известна карта дорог со всеми оставшимися ресурсами и их ценностью.
Помогите Игорю посчитать, какое максимальное количество очков Игорь сможет собрать, бегая по дорогам.
В первой строке задано три целых числа $$$n$$$, $$$m$$$, $$$k$$$ $$$(1\leq n\leq 10^4,1\leq m\leq 10^4,1 \leq k \leq 6)$$$ — количество городов на карте, количество дорог соединяющих города, количество ходов, которое планирует сделать Игорь.
Далее в $$$m$$$ строках записаны три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1\leq a_i\leq n,1\leq b_i \leq n,0 \leq c_i \leq 10)$$$ — номера городов, между которыми проходит дорога, и ценность ресурса лежащего в мешке, если $$$c_i$$$ равняется нулю это означает, что кто-то уже взял данный ресурс в мешке и мешок пуст.
Гарантируется, что у каждого города есть не более чем 10 присоединенных дорог.
Выведите одно целое число — максимальное количество очков, которое может получить Игорь, собирая ресурсы на дорогах.
5 4 3 1 2 1 2 3 2 3 4 3 4 5 1
6
6 6 6 1 2 3 2 3 3 3 4 5 4 5 1 5 6 7 6 1 3
22
Профессор Ш. занимается фундаментальными исследованиями в области изучения строк. Так, недавно на научной конференции в Бырниксе профессор ошеломил научное сообщество открытием нового вида строк – хороших строк. Непустую строку $$$S$$$, состоящую из строчных латинских букв, называют хорошей, если в ней нет $$$k$$$ подряд идущих гласных или $$$k$$$ подряд идущих согласных букв. Теперь Профессор хочет в каждой строке искать её наидлиннейшую хорошую подстроку. Однако профессор хорош в теоретических построениях, а написание программ – его слабое место.
Профессор нуждается в вашей помощи. Напишите программу, которая для заданной строки будет искать её наидлиннейшую хорошую подстроку.
Следует считать, что гласными буквами в латинском алфавите являются буквы $$$a$$$, $$$e$$$, $$$i$$$, $$$o$$$, $$$u$$$.
В первой строке содержится непустая строка $$$S$$$, состоящая из строчных латинских букв, длина которой не менее $$$2$$$ и не превосходит $$$100 000$$$.
Во второй строке содержится число $$$k$$$ $$$(1 \lt k \le |S|)$$$.
В единственной строке выведите число – размер наидлиннейшей хорошей подстроки $$$S$$$.
abacaba 2
7
aaabbb 2
2
aeoui 3
2
Даны три точки на плоскости, не лежащие на одной прямой. Провести через эти три точки окружность и вывести радиус этой окружности.
В первой строке записаны координаты первой точки. Во второй строке записаны координаты второй точки. В третьей строке записаны координаты третей точки. Все числа целые и не превосходят по абсолютной величине 1000.
Вывести радиус окружности, которая проведена через данные три точки, не менее чем с 4 знаками после запятой.
0 0 2 1 -2 1
2.5
0 10 0 0 12 4
7.07107
Вот и прошел 2113-й год, и Эдурд решил в очередной 113-й раз пересмотреть все фотографии за прошедший год на своём телефоне. Но злой хакер Довлентий знает, что Эдурд любит порядок и, взломав его телефон по незащищенной сети Famikon, перемешал все фотографии за последний год. Эдурд хочет навести порядок, но ему надоело видеть фотографии отсортированными по дате, и он хочет, чтобы теперь фотографии в его телефоне были отсортированы по месту, где было сделано фото, в лексикографическом порядке, а затем уже по дате и времени. Каждая фотография имеет несколько параметров: место, где сделано фото – представляет собой непустую строку символов латинского алфавита и символ точка; день, месяц, часы и минуты, когда была сделана фотография. Эдурд только устроился на работу программистом, и он работает над NekitOS-310, и хочет реализовать такую функцию, так как Эдурд последние дни слишком долго работал в PUBG-2, ему нужна ваша помощь.
Входные данные содержат информацию о фотографиях, их количество заранее не известно. Гарантируется, что их не более, чем 105. Каждая строка входных данных описывает одну фотографию в следующем формате:
place DD MM HH MM, где place - непустая строка состоящая из заглавных и строчных букв латинского алфавита и символа точка ('.') описывает локацию в которой сделана фотография; DD MM HH MM - день (от 01 до 31), месяц(от 01 до 12), час (от 00 до 23), и минута (от 00 до 59) соответственно, когда было сделано фото (каждая представляет собой ровно 2 цифры, например 01 03 00 32).
Ваша задача отсортировать входные данные в следующих приоритетах: сначала в лексикографическом порядке локации, далее в порядке даты и времени (по неубыванию). Обратите внимание что строка adidas лексикографически больше строки Abibas (т.к. символ'a' идет позже чем 'A' в таблице ASCII).
Вывод должен быть произведен в следующем формате: N place DD.MM.2113 HH: MM, где N - номер фотографии в порядке следования во входных данных, place DD MM HH MM - параметры фотографии из входных данных.
Если у двух фотографий совпадают все параметры, то выведите раньше ту, которая шла раньше в порядке следования во входных данных (то есть в порядке следования N).
Moscow 15 01 13 24
Maykop 17 05 00 13
Adler 21 11 04 20
St.Petersburg 30 01 17 59
Moscow 01 04 00 00
Kekland 04 12 01 43
Moscow 15 01 02 43
3 Adler 21.11.2113 04:20
6 Kekland 04.12.2113 01:43
2 Maykop 17.05.2113 00:13
7 Moscow 15.01.2113 02:43
1 Moscow 15.01.2113 13:24
5 Moscow 01.04.2113 00:00
4 St.Petersburg 30.01.2113 17:59
Moscow 15 01 13 24
Maykop 17 05 00 13
Adler 21 11 04 20
Moscow 15 01 13 24
st.Petersburg 30 01 17 59
Moscow 15 01 13 24
Moscow 01 04 00 00
Kekland 04 12 01 43
Moscow 15 01 02 43
3 Adler 21.11.2113 04:20
8 Kekland 04.12.2113 01:43
2 Maykop 17.05.2113 00:13
9 Moscow 15.01.2113 02:43
1 Moscow 15.01.2113 13:24
4 Moscow 15.01.2113 13:24
6 Moscow 15.01.2113 13:24
7 Moscow 01.04.2113 00:00
5 st.Petersburg 30.01.2113 17:59
Бывают случаи, когда в наборе задач есть очень простая. Эта – одна из них.
Всё, что от вас требуется – вывести сумму всех попарных произведений всех частичных сумм подряд идущих элементов массива длины N по модулю M.
Более понятным языком, если записать все частичные суммы в ряд, то нужно посчитать остаток от деления суммы попарных произведений чисел в этом ряду на M.
Первая строка содержит числа N и M (1 ≤ N ≤ 3·104, 1 ≤ M ≤ 230, M – степень двойки) – количество элементов и модуль.
Во второй строке содержатся N чисел ai (0 ≤ ai ≤ 104) – элементы массива.
В единственной строке выведите число – значение суммы попарных произведений, взятую по модулю M.
2 1024
2 4
44
2 4
2 4
0
3 16
1 2 3
14
В первом примере ответ 44 получается следующим образом: всего имеются 3 частичные суммы – 2, 4, 6 = 2 + 4. 2 * 4 + 4 * 6 + 2 * 6 = 8 + 24 + 12 = 44. Остаток от деления 44 на 1024 равен 44.
Островное государство М. состоит из $$$N$$$ островов, между некоторыми островами имеется паромное сообщение. Каждый остров государства пронумерован числом от $$$1$$$ до $$$N$$$. Известно, что с каждого острова можно добраться на любой другой, возможно, с пересадками. Всего в стране есть $$$N$$$ рейсов. Так как государство находится в плачевном финансовом положении, властями М. было решено закрыть ровно один рейс между двумя островами, но с условием, чтобы всё ещё можно было добраться от каждого острова до любого другого. Так как вы – министр цифрового развития, эта задача поставлена вам. Напишите программу, которая найдёт все рейсы, после удаления которых с каждого острова М. всё ещё можно будет добраться до любого другого.
В первой строке содержится число $$$N$$$ $$$(3 \le N \le 10^5)$$$ – количество островов и паромных переправ. В следующих $$$N$$$ строках содержатся числа $$$u_i$$$ и $$$v_i$$$ $$$(1 \le u_i, v_i \le N, u_i \ne v_i)$$$ – номера островов, соединенных друг с другом паромной переправой. Гарантируется, что между двумя островами действует не более одного рейса. Переправа действует в любом из двух направлений. Гарантируется, что с каждого острова можно попасть на любой.
В первой строке выведите число $$$k$$$ – количество переправ, после удаления которых от каждого острова можно будет добраться до любого другого.
Выведите все такие паромные переправы $$$(u_i, v_i)$$$, что после их отмены всё ещё можно будет добраться от каждого острова до любого другого. Переправы можно выводить в любом порядке, порядок перечисления островов рейса также может быть любым. Каждую переправу выводите в отдельной строке, разделяя номера островов пробелами.
4 2 1 2 3 2 4 1 3
3 1 2 2 3 3 1
В этом году в России проходит большой математически конгресс, одно из самых главных математических событий во всем мире. По всей России проводились сателлитные конференции приуроченные конгрессу. Конечно же, как настоящий математик, Игорь не мог пропустить данное событие и поучаствует в Московской конференции.
Перед конференцией Игорю необходимо напечатать текст своего выступления, чтобы как можно лучше выступить на конференции. Конечно же, Игорь готовил свое выступление прямо в поезде, как всегда в самый последний момент. Около места проведения конференции Игорь нашел копи центр, где могут напечатать текст.
Игорь обратил внимание на странное ценообразование за печать, копи центр для посетителей выставил $$$n$$$ диапазонов печати. Печать от $$$a_i$$$ до $$$b_i$$$ за один лист бумаги, копи центр возьмет $$$c_i$$$ денег. Если нет диапазона в который помещается текст Игоря, то копи центр отказывает в услуге.
Игорь быстро смекнул, что он может добавить сколько угодно пустых листов бумаги в свой заготовленный текст, чтобы заплатить меньше, но времени до начала конференции осталось совсем немного. Помогите, Игорю определить, сколько он должен будет заплатить денег.
В первой строке задано два целых числа $$$n$$$, $$$k$$$ $$$(1\leq n\leq 10^5, 1\leq k\leq 10^9)$$$ — количество диапазонов печати в печатном центре, количество страниц текста выступления Игоря.
Далее в каждой строке задано три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1\leq a_i \leq b_i\leq 10^9, 1\leq c_i\leq 10^5)$$$ — диапазон печати бумаги, цена за один лист бумаги.
Гарантируется, что $$$a_i=b_{i-1}+1$$$ при $$$2\leq i\leq n$$$.
Гарантируется, что $$$a_{1}=1$$$.
Выведите минимальное количество денег, которое потребуется Игорю потратить для печати своего текста. Выведите «-1» без кавычек, если Игорь не сможет напечатать текст и подготовиться к конференции.
4 15 1 5 20 6 10 15 11 20 10 21 30 5
105
11 16 1 1 7 2 2 14 3 4 17 5 7 1 8 8 18 9 10 19 11 12 18 13 14 9 15 18 5 19 19 2 20 20 8
38
В этом году в России проходит большой математический конгресс – одно из самых главных математических событий во всем мире. По всей России проводились сателлитные конференции, приуроченные конгрессу. Конечно же, как настоящий математик, Игорь не мог пропустить данное событие и поучаствует в Московской конференции.
Организаторы заранее разослали всем участникам программу конференции. Оценив ее, Игорь решил купить билеты на поезд из Ярославля в Москву и обратно. Организаторы конференции строго определили время проведения мероприятий. Сбор участников на вокзале зафиксировали днем $$$d1$$$ и временем $$$hh1:mm1$$$, а отъезд гостей с вокзала днем $$$d2$$$ и временем $$$hh2:mm2$$$. Вся конференция продлится меньше одной недели.
На сайте РЖД указано полное расписание поездов, а также сказано, что они повторяют свои рейсы еженедельно. Для каждого поезда указан день недели отбытия $$$d1_i$$$, время отбытия $$$hh1_i:mm1_i$$$, день недели прибытия $$$d2_i$$$, время прибытия $$$hh2_i:mm2_i$$$. Все поезда всегда ездят по своему графику и не опаздывают, а также выполняют свой рейс меньше одной недели.
Игорь может приехать ровно ко времени сборов участников или приехать заранее на конференцию и дождаться её начала в Москве. После окончания конференции Игорь может выехать с вокзала ровно в ту же минуту, которая указана организаторами временем отъезда, или может подождать свой поезд в Ярославль на вокзале.
Игорь хочет провести как можно меньше времени вне дома. Помогите Игорю определить, какое минимальное количество времени в минутах ему придётся провести в пути и в Москве суммарно.
В первой строке задано время, в которое Организаторы запланировали сбор участников на вокзале.
Во второй строке записано время отъезда участников, в которое Организаторы привозят участников конференции на вокзал.
В следующей строке записано два целых числа $$$n$$$, $$$m$$$ $$$(1\leq n,m\leq 100)$$$ — количество поездов, которые едут из Ярославля в Москву, и количество поездов, которые едут из Москвы в Ярославль.
В следующих $$$n$$$ строках записаны через пробел время отбытия и прибытия поездов из Ярославля в Москву.
В следующих $$$m$$$ строках записаны через пробел время отбытия и прибытия поездов из Москвы в Ярославль.
Каждое время задается в виде «d hh:mm» — строки из маленьких латинских букв описывающей день недели: monday, tuesday, wednesday, thursday, friday, saturday, sunday, часы от 0 до 23 и минуты от 0 до 59.
Гарантируется, что время сбора и отъезда участников не совпадает.
Гарантируется, что время отбытия с вокзала и прибытия на вокзал любого поезда не совпадает.
Выведите одно целое число — минимальное количество времени в минутах, которое потратит Игорь.
friday 10:00 friday 14:00 1 1 friday 09:00 friday 10:00 friday 15:00 friday 21:00
720
friday 10:00 sunday 20:00 2 3 sunday 23:00 monday 05:00 friday 09:00 friday 11:00 monday 02:00 monday 05:00 monday 01:00 monday 04:30 sunday 20:00 monday 03:00
10320