Витя безумно любит статистику. Ещё бы — у них со старшим братом день рождения приходится на один и тот же день года! Теперь каждый год в свой день рождения он записывает, сколько лет ему и его брату, и пытается найти в этих записях что-нибудь интересное.
Сегодня у Вити день рождения, и он показал свои записи Алёне. Витя знает, что она тоже любит исследовать всякие наборы чисел и находить в них закономерности. Алёна тут же заметила интересный момент: когда в один из прошлых дней рождения Вите было n лет, его брату было m лет, а сегодня Витя младше своего брата ровно в k раз!
Вернувшись вечером домой, Алёна заинтересовалась вопросом: а достаточно ли этих данных, чтобы вычислить, сколько лет исполнилось Вите сегодня? Алёна быстро справилась, а сможете ли вы решить эту сложную задачу и выяснить по числам n , m и k , сколько лет Вите?
Ввод состоит из трех строк, которые содержат по одному натуральному числу: n , m и k — возраст Вити и его брата в былые времена, а также во сколько раз Витя сегодня младше своего брата ( 1 ≤ n < m ≤ 10 000 , 2 ≤ k ≤ 10 000 ).
Если описанная в условии ситуация могла произойти, выведите единственное число t — сколько лет сегодня исполнилось Вите.
Если Витя и Алёна ошиблись, и описанной ситуации быть не могло, выведите число - 1 .
4 15 2
11
4 15 3
-1
4 8 2
-1
Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.
Числами Фибоначчи называется числовая последовательность F 1 , F 2 , ..., F n , ... , которая устроена следующим образом: F 1 = 1 , F 2 = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то F i = F i - 1 + F i - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .
Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F 3 = 3 , F 4 = 5 , F 5 = 8 , F 6 = 13 и F 7 = 21 . Среди них на 3 делятся два числа: F 3 = 3 и F 7 = 21 .
Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 10 5 ).
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.
3 7
2
На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен k i .
Например, пусть k = 8 . Запись 357 8 означает число 3·8 2 + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 239 10 . А число 192 10 , в системе счисления с основанием 8 записывается как 300 8 .
Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.
Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 10 18 .
Все ограничения на числа в этой задаче заданы в десятичной системе счисления. Все числа во вводе также записаны в десятичной системе счисления.
Первая строка входных данных содержит число k — основание системы счисления, которую использует Ильдар ( 2 ≤ k ≤ 10 9 ).
Вторая строка входных данных содержит число n — минимальное количество нулей на конце достаточно круглого числа ( 0 ≤ n ≤ 100 ).
Третья строка входных данных содержит число i — порядковый номер достаточно круглого числа, которое интересует Ильдара ( 1 ≤ i ≤ 10 9 ).
Выведите одно число — запись в десятичной счистеме счисления i -го по порядку достаточно круглого в системе счисления с основанием k натурального числа. Гарантируется, что ответ не превышает 10 18 .
Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ». Если вы пишете на языке Python, то волноваться не надо, в Python встроенный целочисленный тип не имеет ограничений на величину числа.
8 2 3
192
Арсений — молодой перспективный спортсмен. Всё, что любит делать Арсений — это тренироваться и вкусно есть. Также он отличается пунктуальностью. Только что он составил расписание из n пунктов: для каждого из следующих n часов он решил, что будет делать в это время — тренироваться или есть.
Арсений показал расписание своему тренеру, но ему оно не до конца понравилось. Тренер объяснил, что тренироваться в следующий час после приёма пищи вредно для здоровья.
Теперь Арсений хочет изменить свое расписание так, чтобы он ни разу не тренировался непосредственно после еды. При этом он хочет изменить минимальное число пунктов своего расписания. Помогите Арсению!
В первой строке входных данных содержится число n — количество пунктов в расписании Арсения ( 1 ≤ n ≤ 10 5 ).
Во второй строке содержится исходное расписание Арсения. Это строка s длины n , состоящая только из латинских букв « t » и « e », при этом если на позиции i в строке s стоит буква « t », то это значит, что в i -м часу Арсений запланировал тренироваться, а если на этой позиции стоит буква « e », то это значит, что в i -м часу Арсений запланировал есть.
В первой строке выведите минимальное количество пунктов расписания, которые необходимо изменить.
Во второй строке выведите строку из n латинских букв « t » и « e » — изменённое расписание в том же формате, что и во входных данных. Если подходящих расписаний несколько, выведите любое из них.
6 tttete
1 ttteee
5 tttte
0 tttte
9 eeeeetttt
4 eeeeeeeee
Каждый год в одном из уголков нашей вселенной проходят Интеллектуальные Олимпийские Игры. В этом году честь проводить это масштабное мероприятие выпала планете Юпитер. Вам предстоит отобрать две команды на Игры из имеющихся n кандидатов в сборную.
Все кандидаты являются школьниками, каждый кандидат учится в определенном классе. Как и на Земле, на Юпитере 11 классов, пронумерованных от 1 до 11. На Игры отбирается две команды по результатам отборочных соревнований. На соревнованиях проводится пять отборочных туров. По итогам каждого тура каждый школьник может набрать от 0 до 300 баллов, чем больше, тем лучше.
В первую команду попадают четыре лучших школьника по сумме баллов, набранных на всех отборочных турах. Во вторую команду попадают четверо лучших по сумме баллов из тех, кто не попал в первую команду, и при этом не учится в 11 классе.
Все туры уже проведены, и получилось так, что любые два кандидата набрали в сумме различное количество баллов. Осталось лишь написать программу, которая по имеющимся данным о кандидатах и результатах туров определит тех восьмерых, которые защитят честь Юпитера на Интеллектуальных Олимпийских Играх и докажут, что Юпитер — суперпланета!
Первая строка входных данных содержит единственное число n — количество кандидатов в сборную Юпитера ( 8 ≤ n ≤ 500 ).
Следующие n строк содержат информацию о кандидатах. Каждая строка содержит 6 целых чисел — номер класса, в котором учится очередной кандидат, и его результаты на отборочных турах.
Номер класса является числом от 1 до 11, а результат на каждом туре — числом от 0 до 300.
Гарантируется, что все участники имеют различные суммарные баллы.
Гарантируется, что есть хотя бы 8 кандидатов, обучающихся не в 11 классе.
Выведите две строки.
Первая строка должна содержать четыре целых числа, разделенных пробелами — номера кандидатов, которые попадут в первую команду Юпитера. Кандидаты нумеруются с единицы в порядке их появления во вводе. Выводить номера следует в порядке возрастания.
Вторая строка должна описывать вторую команду Юпитера в аналогичном формате.
10 9 50 271 287 282 42 10 230 241 137 14 240 10 276 109 300 197 300 8 205 292 194 232 74 10 294 291 299 300 255 9 195 275 265 134 9 11 204 259 96 263 83 7 141 223 85 84 26 11 286 294 289 221 261 10 277 52 117 272 262
3 4 5 9 1 2 6 10