The most challenging exam for the students of the Recreational Mathematics Department is the exam in numeric shifts. Every year problems in this subject become more and more difficult. For the latest exam Professor Numberski has prepared something unbelievable.
The decimal notation of a certain number begins from a group of digits which will be denoted as B. In other words, the initial number is BX. If we multiply this number by A, the result of multiplication will be a number obtained by rewriting the group of digits B from the beginning to the end of the initial number, which means the final result of multiplication is XB.
The task of students is to find the minimal possible initial number BX based on given A and B.
The only line contains two integers A and B (2 ≤ A ≤ 9, 1 ≤ B ≤ 106).
The only number — solution of the task, or -1 if there is no solution.
5 1
-1
3 1
142857
Alice and Bob are playing the next game. Both have same matrix N × M filled with digits from 0 to 9.
Alice cuts the matrix vertically, choose order of the columns, then links all the columns to each other to have the cyclic sequence of N × M digits. Note that she cannot rotate the columns, i.e. end of some column must be linked to beginning of the other column. Then she cuts a sequence and reads the decimal representation of integer A upside down.
Bob cuts the matrix horizontally, choose order of the rows, then link all the rows to each other to have the cyclic sequence of N × M digits. Note that he cannot rotate the rows, i.e. end of some row must be linked to beginning of the other row. Then he cuts a sequence and reads the decimal representation of integer B from left to right.
Player who obtained the biggest integer wins. If both integers are are equal, then game is tied. You are given the matrix, find the number obtained by winner (or by both players in case of tie), if both Alice and Bob are playing optimally.
First line contains integers N and M (1 ≤ M, N ≤ 100).
Each of next N lines contains string of M digits (without the spaces or other delimiters inside) — the given matrix. You may assuma that atleast one digit in the matrix is not equal to 0.
Print answer to the problem. Note that number must be printed without leading zeroes.
2 2
28
27
8722
Synonymous Words Number System (SWNS) uses the lines of N characters consisting of '0' and '1' (2 ≤ N ≤ 10000). There is only one operation with words within the number system – it's called synonymization. Synonymization is reversing the character order in any substring containing even number of '1' symbols.
If we can create one word from the another one, by carrying out not more than 16·N synonymization, then such words are called synonyms.
It is necessary to determine whether the given words are synonymous, and, if so, find out the right sequence of synonymizations.
Different words with a length of N characters are written in two lines, one per line.
If the given words are not synonymous, output 'NO' in a single line.
Otherwise, output 'YES' in the first line. The second line contains an integer K (K ≤ 16·N) – a number of synonymization required for the conversion. The following K lines contain pairs of numbers that describe conversion of the first word into the second one. The first integer specifies a number of the first character participating in synonymization, and the second integer (always greater than the first one) – a number of the last character.
110001111
111100011
YES
1
3 7
110
010
NO
Это интерактивная задача.
Окутанный фантасмагоричными предзнаменованиями Вася взирает на безлунное небо. «Если бы я мог стать столь же чрезвычайно сияющим» — подумал Вася вглядевшись в звезду, и тут же получил зловещее предупреждение из древних глубин космоса. И тогда он понял, что сосредоточив свое невежественное сознание на некоторых звездах, можно услышать кошмарный зов неизвестного Древнего Бога.
Вспомнив знания, полученные из Некрономикона, Вася установил, что каждый из Древних имеет свой радиус влияния, и звезды находящиеся внутри радиуса отвечают зовом тому, кто в них вглядывается. Три Бога отравляют реальность своим противоестественным существованием: Азазот, с радиусом влияния 30 световых лет, Йог-Сотот с радиусом 20 и Шаб-Ниггурат с радиусом 10. Небо представляет собой координатную плоскость 100 на 100 световых лет, и на каждой целочисленной координате находится звезда. Вася может всматриваться в звезду с определенными координатами и понимать, находится ли она в радиусе влияния Древнего.
В данный момент пробудился только один Древний, то есть только вокруг него звезды отвечают на взор. Вася должен понять, какой из Древних пробудился и сказать его радиус, но сделать все это не более чем за N действий, иначе Вася сойдет с ума от переполняющего чудовищного познания.
Выведите строку вида «! R», где R — радиус влияния пробужденного Древнего.
Чтобы узнать находится ли звезда (X, Y) внутри зоны влияния Древнего, выведите в стандартный поток строку вида «? X Y», где X, Y — целые числа (0 ≤ X, Y ≤ 100). После этого выведите перевод строки и выполните операцию flush.
В ответ на запрос придет одно целое число: единица, если звезда находится внутри зоны влияния Древнего и ноль, если нет.
Чтобы вывести ответ на задачу, выведите строку вида «! R», где R — радиус влияния пробужденного Древнего.
Если вы сделаете более N запросов вида «? X Y» или сделаете некорректный запрос, решение получит вердикт «Неправильный ответ».
Если в какой-то момент ваша программа ничего не будет выводить или вы забудете выполнить операцию flush после вывода вопроса или ответа, решение получит вердикт «Решение зависло».
Чтобы выполнить операцию flush, можно использовать (сразу после вывода запроса и перевода строки):
- fflush(stdout) в C++;
- System.out.flush() в Java;
- stdout.flush() в Python;
- flush(output) в Pascal;
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| [0.5ex] 1 | 25 | N = 10202 | полная | |
| 2 | 25 | 103 ≤ N ≤ 5·103 | 1 | полная |
| 3 | 25 | 300 ≤ N ≤ 500 | 1,2 | полная |
| 4 | 25 | N = 101 | 1,2,3 | полная |
1
0
? 8 12
? 95 87
! 10