Программист Андрей очень любит спорт. Больше всего ему нравится теннис. Как и все игроки, Андрей выигрывает и проигрывает матчи. Конечно же проигрыш его очень злит и мешает потом сосредоточиться на программировании. Однажды Андрей подумал: «тебя не будет злить проигрыш матча, если ты не будешь в таких матчах играть». Андрей хочет только выигрывать. Зная вероятность p1 выигрыша очка на своей подаче, а также вероятность p2 выигрыша очка на подаче соперника, можно с легкостью посчитать вероятность выигрыша всего матча. Андрею предстоит важная игра. Помогите ему подсчитать вероятность выигрыша следующего матча.
Правила игры.
Матч состоит из сетов. Сеты из геймов. В одном гейме подающий не меняется. Победителем в гейме считается тот, кто выиграл как минимум 4 очка, при условии, что соперник выиграл как минимум на два меньше. После каждого гейма подающий меняется. Сет играется до 6 геймов. Если у соперника в этот момент 5 геймов, то есть счет 6-5, то играется дополнительный гейм. После этого либо сет заканчивается счетом 7-5, либо играется тай-брэйк, если счёт стал 6-6.
Правила тай-брэйка.
Подаёт тот, кто принимал в предыдущем гейме. После первого разыгранного очка подающий меняется и далее подающий меняется каждые два очка. Выигрывает тот, кто выиграл как минимум 7 очков при условии, что соперник выиграл как минимум на два меньше. Победитель тай-брэйка выигрывает сет.
Матч играется до трёх побед в сетах. После тай-брэйка в новом сете подает тот, кто принимал первую подачу на тай-брэйке предыдущего сета, либо же, если тай-брэйка не было, подает тот, кто принимал подачу в последнем гейме предыдущего сета.
Два вещественных числа p1 и p2 (0 ≤ p1, p2 ≤ 1) — вероятности выигрыша очка на своей подаче и на подаче соперника соответственно. Числа даны максимум с 4 знаками после запятой.
В единственной строке выведите одно число, вероятность выигрыша полного матча Ответ будет считаться правильным, если абсолютная или относительная погрешность не превысит 10 - 9.
0.5 0.5
0.500000000000000
0.7 0.3
0.500000000000000
В первом гейме первого сета всегда подаёт Андрей.
В настоящее время британские ученые занялись проблемой повышения производительности традиционных компьютеров. Недавнее исследование показало, что если заменить логический нуль на операцию побитового сдвига в право (x = x / 2), а логическую единицу операцию отрицания (x = 1 - x), то новая архитектура позволит решать задачи, которые в настоящее время считаются NP трудными. Назовем базовые операции новым нулем и новой единицей, соответственно.
Например, известная задача коммивояжера в предложенной архитектуре эквивалентна получению числа (дроби) 
из единицы с помощью новых нулей и единиц. Таким образом, требуется лишь написать программу (последовательность нулей и единиц), которая является решением задачи коммивояжера для чисел a и b.
Единственная строка содержит два целых числа a и b.
1 ≤ b ≤ 60,
1 ≤ a < 2b,
a – нечетно.
В единственную строку необходимо вывести последовательность из новых нулей и единиц, которая является решением задачи о коммивояжере в новой архитектуре. Если решений несколько, то необходимо вывести программу наименьшей длины.
1 1
0
3 3
0010
Как известно, послание Майя о конце света 21 декабря 2012 года не сбылось. Возможно, проблема была в том, что его неправильно расшифровали. Календарь Майя достаточно сложен для понимания, но несмотря на это исследователи смогли вычислить не точную дату, но количество дней, которое человечество еще сможет прожить.
К сожалению, не все цифры числа из послания Майя сохранились, т.е. некоторые из них отчетливо видны на каменной плите, а остальные слишком размыты. У народности Майя во времена создания послания был известен культ числа k, поэтому достоверно известно, что число из послания кратно k. Поскольку правительство всерьез восприняло послание предков, необходимо найти минимально возможное число, которое могло быть упомянуто Майя.
Первая строка содержит два целых числа n и k — длина числа послания и культовое число соответственно.
Вторая строка содержит послание, состоящее из n цифр и знаков "?", которые обозначают отчетливые и размытые символы соответственно.
1 ≤ n, k ≤ 1000.
В единственной строке необходимо вывести минимально возможное число, состоящее из n цифр, которое могло быть упомянуто в послании Майя. Заметим, что древние Майя также не любили лидирующие нули и поэтому их в послании быть не могло.
Если по сохранившемуся посланию и заданным ограничениях число восстановить невозможно, то необходимо вывести -1.
2 14
4?
42
2 17
4?
-1
Виктория очень часто обижается на Лёшу. Обижалась она и в этот раз. Известно, что Лёша и Виктория гуляли n минут. И в каждую из этих минут Виктория была либо обижена, либо не обижена на Лёшу. Так как все мы программисты, то будем обозначать эти n минут состояния Виктории как n-битную строку. Более формально i-й бит строки будет равен единице, если она обижалась в i-ю минуту, иначе этот бит будет равен нулю.
Лёша утверждает Виктории, что она слишком часто на него обижается. Он любит всё доказывать. Поэтому Лёша хочет посчитать количество таких отрезков времени, на которых её обида была строго больше, чем число X. За отрезок может отвечать пара чисел (l, r), где 1 ≤ l ≤ r ≤ n. Обида Виктории на отрезке — это отношение количества минут, которые она обижалась, к общему количеству минут на отрезке. Более формально обида Виктории на отрезке (l, r) равна 
, где cnt1 — количество единиц на отрезке (l, r) битовой строки, а cntall — общее количество символов с позиции l по r в битовой строке.
Помогите Лёше доказать Виктории, что обид слишком много!
Первая строка входных данных содержит описание числа X в виде двух целых чисел P и Q разделенных пробелом (0 ≤ P ≤ 1000, 1 ≤ Q ≤ 1000, P ≤ Q), то есть X равно 
.
Следующая строка входных данных содержит строку s состоящую из символов '0' и '1'. Длина строки положительная и не превышает 200 000.
Выведите единственное целое число — количество отрезков (l, r), на которых обида Виктории строго больше, чем X.
3 10
10110
13
9 10
010100101101
7
Легенды для задач бывают разные. Бывают длинные или короткие. Бывают скучные или веселые. Бывают понятные или нет. Вам решать какая эта. Дано дерево из n вершин. Также дано q запросов. Один запрос представляет собой пару чисел v и k. Подвесим дерево за вершину v и выпишем размеры поддеревьев каждой вершины дерева в порядке неубывания. Ответом на запрос является k-е число в этом списке.
Первая строка входных данных содержит два числа – n и q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105). Каждая из следующих n - 1 строк содержит описание ребра дерева – его концы ui и vi (1 ≤ ui, vi ≤ n) Каждая из следующих q строк содержит описание очередного запроса – числа vi и ki (1 ≤ vi, ki ≤ n)
Выведите ответ на каждый из запросов на отдельной строке.
5 5
1 2
1 3
1 4
4 5
2 5
1 3
4 4
2 3
2 2
5
1
3
2
1
Андрей(как и все Андреи) очень любит играть с числами и складывать в столбик. У него есть два числа X и Y в десятичной системе счисления, изначально равные нулю. Разряды чисел нумеруются слева в 1-индексации. Андрей выполняет над ними следующие типы операций:
- 1 k a b - вставить цифру a (0 ≤ a ≤ 9) после k-го разряда числа X (если k равно 0, то цифра вставляется в начало числа). Аналогично вставить цифру b в число Y. Гарантируется, что на момент выполнения операции числа содержат не менее k разрядов.
- 2 k - удалить из чисел X и Y разряды с номером k. Гарантируется, что на момент выполнения операции числа содержат не менее k разрядов.
- 3 k - вывести k-й разряд числа Z, равного сумме X и Y. Обратите внимание, что для данной операции не гарантируется, что в числе Z будет присутствовать k-й разряд. В случае его отсутствия выведите - 1.
Гарантируется, что после выполнения каждой из операций числа X и Y не будут иметь ведущих нулей.
Первая строка входных данных содержит единственное число n (1 ≤ n ≤ 3 × 105) - количество выполняемых операций. Следующие n строк содержат описание операций в описанном выше формате. Для всех операций значения параметра k удовлетворяет неравенству 0 ≤ k ≤ n.
Для каждой операции третьего типа выведите ее результат на отдельной строке.
12
1 0 8 1
3 1
3 2
2 1
1 0 8 3
3 1
3 2
1 0 4 5
3 1
3 2
3 3
3 5
9
0
1
1
1
0
1
-1
Андрей (как и все Андреи) очень любит играть в различные игры. Однажды он совершенно случайно первый раз в жизни оказался в казино. Крупье предложил сыграть в одну привлекательную игру. Вам дают кубик с k гранями, на каждой из которой написаны уникальные числа от 1 до k. У вас есть возможность подбросить кубик n раз и остановиться после любого броска, ваш выигрыш — это число, написанное на верхней грани кубика после последнего броска. Выпадение каждой из граней равновероятно. Андрей довольно неплохо разбирается в математике и поэтому знает оптимальную стратегию игры, максимизирующую его выигрыш. Вам же предлагается найти матожидание выигрыша, если вы будете играть как Андрей.
Два целых числа n и k.
1 ≤ n, 1 ≤ k, n × k ≤ 1012
Единственная строка должна содержать вещественное число — матожидание выигрыша при оптимальной стратегии. Абсолютная или относительная погрешность не должна превышать 10 - 9.
1 6
3.500000000000000
2 6
4.250000000000000
Андрей (как и все Андреи) любит массивчики. А еще он любит играть с ними и считать разные циферки. Однажды у него появился массивчик целых чисел A длины n. И решил Андрей выбрать три (возможно одинаковых) индекса i, j, k, а потом взять и посчитать побитовое исключающее или чисел A[i], A[j] и A[k]. Андрей даже придумал название своей операции — 3XOR. После того, как эйфория прошла, он задумался, а что будет, если взять все возможные неупорядоченные комбинации индексов i, j, k, применить новую операцию, а потом сложить результаты. Должно получиться какое-то чиселко. Помогите Андрею решить эту задачку.
В первой строке записано число n. Во второй строке вам дан массивчик A.
3 ≤ n ≤ 104
0 ≤ A[i] ≤ 106
В единственной строке выведите ответ на задачу.
3
1 2 3
42
5
42 4 42 2 42
2868