#730

Binary periodical fraction to decimal

Темы: [Двоичная система счисления]

Преобразуйте двоичное число.

Входные данные

Дана запись целого двоичного числа или двоичной периодической дроби, которая включает в себя:

1. Необязательную целую часть.
2. Необязательный символ точки, отделяющий целую часть от дробной.

3. Необязательную дробную непериодическую часть.

4. Необязательную периодическую дробную часть, записываемую в круглых скобках.

Выходные данные

Необходимо определить значение этой дроби, сохранить его в переменной типа double и вывести на экран с точностью не менее 12 знаков. Общая длина входной строки не превосходит 30 символов.

Примеры

Входные данные

0.1

Выходные данные

0.5

Входные данные

0.01

Выходные данные

0.25

#731

Rational number to binary periodical

Темы: [Двоичная система счисления]

Дано рациональное число. Запишите его в виде двоичной периодической дроби.

Входные данные

На вход программа получает два натуральных числа n и m, каждое из которых не превосходит 1000.

Выходные данные

Программа должна вывести значение n/m, записанное в виде двоичной периодической дроби, при этом длина непериодической дробной части и длина периода должны быть минимально возможными. Если данное число является конечной двоичной дробью, периодическую часть выводить не надо.

Примеры

Входные данные

1 2

Выходные данные

0.1

Входные данные

1 3

Выходные данные

0.(01)

#732

Binary periodical fraction to rational number

Темы: [Двоичная система счисления]

Преобразуйте дробь.

Входные данные

Дана запись двоичной дроби, как в задаче "Binary periodical fraction to decimal", но в целых числах точки может не быть. Необходимо представить ее в виде несократимой рациональной дроби n/m.

Выходные данные

Программа должна вывести значения n и m .

Примеры

Входные данные

0.1

Выходные данные

1 2

Входные данные

0.01

Выходные данные

1 4

#1282

Тапкодёр

Темы: [Двоичная система счисления] [Бинарный поиск в массиве] [Сортировка слиянием]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2008, 2 день, Задача B ]

Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2^k зарегистрировавшихся участников, которым присвоены номера от 1 до 2^k.

Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.

Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме n договорных, возможен любой исход.

Некоторые m участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.

Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.

Входные данные

В первой строке заданы три целых числа k (1 ≤ k ≤ 60), n (0 ≤ n ≤ 100 000) и m (1 ≤ m ≤ 100 000). В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ≠ y. В последней строке перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.

Выходные данные

Выходные данные должны содержать m целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.

Комментарии к примерам тестов.

1. У каждого из участников есть возможность выйти в финал, так как договорных матчей нет.

2. Если четвертый участник выиграет у третьего, то договорная встреча первого и третьего не состоится, что благоприятно для первого.

3. Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал.

Система оценки

Тесты к этой задаче состоят из четырех групп, баллы начисляются только при прохождении всех тестов группы и всех тестов предыдущих групп.

0. Тесты 1–10. k <= 5. Эта группа оценивается в 30 баллов.

1. Тесты 11–14. k <= 20. Эта группа оценивается в 20 баллов.

2. Тесты 15–18. k <= 30. Эта группа оценивается в 20 баллов.

3. Тесты 19–23. Дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов.

Примеры

Входные данные

2 0 3
1 3 4

Выходные данные

2 2 2

Входные данные

3 1 1
3 1
1

Выходные данные

Входные данные

Выходные данные

3 1 2 3

#1339

Цифры и числа

Темы: [Двоичная система счисления] [Простые задачи на перебор]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2009, Задача C ]

Как много открытий можно сделать, исследуя числа и составляющие их цифры!

Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.

Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 1110₂ (в десятичной системе — 14) можно получить из числа 1100₂ (в десятичной системе — 12), прибавив к последнему сумму его цифр:

1100₂ + 10₂ = 1110₂.

Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 1₂, 4 = 100₂, 6 = 110₂, 13 = 1101₂, 15 = 1111₂. Продолжить работу он собирается с помощью компьютера.

Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.

Входные данные

В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 10¹⁸).

Выходные данные

В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.

Примечание

Решения, корректно работающие при n ≤ 10⁶, будут оцениваться из 40 баллов.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

Страница: << 1 2 3 4 >> Отображать по: