eolymp
bolt
Try our new interface for solving problems
Məsələlər

Подсчет 1-иц

Подсчет 1-иц

Пусть \textbf{b_i(x)} - \textbf{i}-ый наименее значимый бит \textbf{x}, то есть \textbf{i}-ая наименее значимая цифра \textbf{x }в системе счисления \textbf{2 }(\textbf{i }≥ \textbf{1}). Например, поскольку \textbf{6} = \textbf{(110)_2}, то \textbf{b_1(6)} = \textbf{0}, \textbf{b_2(6)} = \textbf{1}, \textbf{b_3(6)} = \textbf{1}, \textbf{b_4(6)} = \textbf{0}, \textbf{b_5(6)} = \textbf{0}, и так далее. Пусть \textbf{A }и \textbf{B }(\textbf{1 }≤ \textbf{A }≤ \textbf{B }≤ \textbf{10^18}) - целые числа, \textbf{k_i} - количество таких целых \textbf{x }что \textbf{A }≤ \textbf{x }≤ \textbf{B }и \textbf{b_i(x)} = \textbf{1}. Напишите программу, которая определит \textbf{A }и \textbf{B }по заданным \{\textbf{k_i}\}. \InputFile Состоит из нескольких тестов. Количество тестов не более \textbf{100000}. Каждый тест имеет следующий формат: \textbf{n} \textbf{k_1} \textbf{k_2} \textbf{...} \textbf{k_n} Первая строка каждого теста содержит целое число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{64}). Далее следуют \textbf{n }строк, каждая из которых содержит \textbf{k_i} (\textbf{0 }≤ \textbf{k_i} ≤ \textbf{2^63 - 1}). Для всех \textbf{i }> \textbf{n}, \textbf{k_i} = \textbf{0}. Последняя строка содержит \textbf{n} = \textbf{0} и не обрабатывается. \OutputFile Для каждого теста вывести в одной строке: \begin{itemize} \item Если \textbf{A} и \textbf{B} могут быть определены однозначно, то вывести \textbf{A} и \textbf{B}. Разделяйте числа одним пробелом. \item Если существует более одной пары \textbf{A} и \textbf{B}, выведите "\textbf{Many}" (без кавычек). \item Иначе, то есть если не существует ни одной искомой пары, выведите "\textbf{None}" (без кавычек). \end{itemize}
Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
2
2
1
4
1
1
1
1
0
Çıxış verilənləri #1
1 4
Many
Mənbə 2012 JAG Practice Contest for ACM-ICPC Asia Regional 2012, AtCoder, November 4; 2013 Petrozavodsk Winter Training Camp, January 26, Problem B