시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Первое правило вещественных чисел --- не используйте вещественные числа
Подслушано в Заколково
Петя работает в наукограде Заколково. Он занимается разработкой нового микропроцессора Чебур. Поскольку ведущий архитектор микропроцессора очень не любит числа с плавающей точкой, вещественные числа в микропроцессоре Чебур хранятся в формате с фиксированной точкой.
Внутренние регистры процессора хранят вещественные числа в виде двоичной дроби ровно с $n$ двоичными знаками после точки. Число знаков до точки не ограничено. В таком формате представимы числа, равные $p/2^n$ для некоторого целого $p$. Число $x$, полученное в результате выполнения арифметических операций над вещественными числами, при сохранении в регистр процессора заменяется на ближайшее представимое число, а если $x$ находится ровно посередине между двумя представимыми числами, то на большее из них.
Для хранения чисел в памяти используется формат, при котором вещественное число представляется в виде двоичной дроби ровно с $k$ двоичными знаками после точки ($k \le n$, число знаков до точки, так же как и у регистров, не ограничено). В таком формате представимы в точности числа, равные $p/2^k$ для некоторого целого $p$. При загрузке числа из памяти в регистр процессора число дополняется нулями до $n$ двоичных знаков после точки. При сохранении числа $y$ в память из регистра оно заменяется на ближайшее представимое число, а если $y$ находится ровно посередине между двумя представимыми числами, то на большее их них.
Например, пусть $n = 10$, $k = 5$. Число 1 хранится в памяти в виде $1.00000_2$, число 3 хранится в памяти как $11.00000_2$. При загрузке в регистры числа дополняются нулями до $1.0000000000_2$ и $11.0000000000_2$, соответственно. Пусть было выполнено деление 1 на 3. Если результат деления $1/3$ записать в двоичной системе, получится $0.(01)_2$ --- здесь, как и в случае десятичных дробей, часть в скобках означает период бесконечной двоичной дроби. При сохранении в регистре процессора эта дробь будет приближена значением $0.0101010101_2$. Умножим теперь это число на 3. Получится число $0.1111111111_2$, в таком же виде оно хранится в регистре процессора. При сохранении в память оно приближается числом $1.00000_2$, как ближайшей двоичной дробью с 5 знаками после точки.
Петя заметил, что если загрузить в регистры единицу и целое число $v$, поделить 1 на $v$, затем умножить результат деления на $v$ и сохранить результат умножения в память, то итоговое сохраненное значение не всегда равно 1. Например, если $v = 40$, то после деления в регистре оказывается значение $0.0000011010_2$, после умножения на $v$ значение $1.0000010000_2$, после сохранения в память оно преобразуется в $1.00001_2$. Петя называет такие числа неудачными.
Петю заинтересовал вопрос, какие целые числа от 1 до $r$ являются неудачными. Помогите ему выяснить это.
Первая строка входного файла содержит три целых числа $n$, $k$ и $r$ ($1 \le k \le n \le 100$, $1 \le r \le 1000$).
В первой строке выходного файла выведите число $t$ --- количество неудачных чисел, лежащих в диапазоне от 1 до $r$. Во второй строке выходного файла через пробел выведите в возрастающем порядке все неудачные числа, лежащие в диапазоне от 1 до $r$.
10 5 60
7 40 50 52 53 55 58 59