Максим вырос, разочаровался в большой науке и теперь работает авиадиспетчером. Каждый день он делает очень важное и ответственное дело: сажает самолеты.
Этот процесс не такой уж сложный, как может показаться на первый взгляд. В аэропорту, в котором работает Максим, всего одна посадочная полоса, поэтому самолеты должны садиться по очереди. Посадка занимает \)b\( минут. Если самолет прилетел, а посадочная полоса занята, его отправляют совершать дополнительные круги над городом до тех пор, пока он не прилетит к аэропорту со свободной взлётно-посадочной полосой. Один круг занимает \)f\( минут. Если посадочная полоса свободна, самолёт немедленно начинает посадку. Если несколько самолётов подлетают к аэропорту со свободной посадочной полосой одновременно, то один из них идёт на посадку, а другие отправляются совершать дополнительные круги.
Сегодня в аэропорт должны прилететь \)n\( самолетов, известно время прилета каждого из них. За какое время все самолёты совершат посадку?
В первой строке даны три целых числа \)n\(, \)b\(, \)f\( — количество самолетов (\)1 \le n \le 1000\(), время, которое занимает посадка и время, которое занимает один круг над аэропортом (\)1 \le b, \ f \le 10^9\( ). В следующей строке дано \)n\( целых чисел \)t_i\( — времена прибытия самолетов, перечисленные в произвольном порядке (\)0 \le t_i \le 10^9$ ).
Выведите одно число: время, за которое все самолёты совершат посадку.
10 5 12 13 0 1 10 20 20 2 1 10 20
79
Витя безумно любит статистику. Ещё бы — у них со старшим братом день рождения приходится на один и тот же день года! Теперь каждый год в свой день рождения он записывает, сколько лет ему и его брату, и пытается найти в этих записях что-нибудь интересное.
Сегодня у Вити день рождения, и он показал свои записи Алёне. Витя знает, что она тоже любит исследовать всякие наборы чисел и находить в них закономерности. Алёна тут же заметила интересный момент: когда в один из прошлых дней рождения Вите было 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