| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
ACM_0222 - MORE OR LESS ACCURATE |
A number N written in the system with a positive base R will always appear as a string of digits between 0 and R − 1, inclusive. A digit at the position P (positions are counted from right to left and starting with zero) represents a value of RP . This means the value of the digit is multiplied by RP and values of all positions are summed together. For example, if we use the octal system (radix R = 8), a number written as 17024 has the following value:
1 · 84 + 7 · 83 + 0 · 82 + 2 · 81 + 4 · 80 = 1 · 4096 + 7 · 512 + 2 · 8 + 4 · 1 = 7700
8
8
8
With a negative radix −R, the principle remains the same: each digit will have a value of (−R)P . For example, a negaoctal (radix −R = −8) number 17024 counts as:)
)
)
One big advantage of systems with a negative base is that we do not need a minus sign to express negative numbers. A couple of examples for the negabinary system (−R = −2):
|
decimal |
negabinary |
decimal |
negabinary |
decimal |
negabinary |
|
-10 |
1010 |
-3 |
1101 |
4 |
100 |
|
-9 |
1011 |
-2 |
10 |
5 |
101 |
|
-8 |
1000 |
-1 |
11 |
6 |
11010 |
|
-7 |
1001 |
0 |
0 |
7 |
11011 |
|
-6 |
1110 |
1 |
1 |
8 |
11000 |
|
-5 |
1111 |
2 |
110 |
9 |
11001 |
|
-4 |
1100 |
3 |
111 |
10 |
11110 |
You may notice that the negabinary representation of any integer number is unique, if no “leading zeros” are allowed. The only number that can start with the digit “0” is the zero itself.
Today, we are interested whether there were any contestants’ answers in 2007 that were almost correct, i.e., their program output was different from the correct answer only by one. Will you help us to find out?
Input
The input contains several test cases. Each test case is given on a single line containing number X written in the negabinary notation. The line contains N (1 ≤ N ≤ 106) characters “0” or “1” representing the negabinary bits aN −1...a1a0 respectively. Numbers will be given to you without leading zeros, i.e., for each input where X ƒ= 0 it holds that aN −1 = 1.
Output
For each test case, print a single line with number (X + 1) written in the negabinary notation. Output the number without any leading zeros.
Examples
|
№ |
stdin |
stdout |
|
1 |
1 |
110 |
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2014-10-08 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | CTU Open 2014.G |
RSS