DMPG '16 B6 - Counting Money - Olympiads Online Judge

DMPG '16 B6 - Counting Money

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

WhiteTofuLord

Problem types

Bob is now so rich that he is no longer able to keep track of his own wealth. Instead, he now uses a computer to do it for him. Most computers use binary, or base $2$ $2$ to count. However, Bob's computer needs to handle negative numbers as well, so instead, it uses base $-2$ $- 2$ . Base $-2$ $- 2$ is very similar to base $2$ $2$ , except the digits represent increasing powers of $-2$ $- 2$ instead of $2$ $2$ . This means that the digits (from right to left) represent $1$ $1$ , $-2$ $- 2$ , $4$ $4$ , $-8$ $- 8$ , and so on, instead of $1$ $1$ , $2$ $2$ , $4$ $4$ , $8$ $8$ . However, there is still a problem: his computer can't convert between base $-2$ $- 2$ and base $10$ $10$ yet. Can you help Bob write a program to do this?

There are two operations that will be needed:

A x Change $x$ $x$ , a number in base $-2$ $- 2$ , into base $10$ $10$ .
B y Change $y$ $y$ , a number in base $10$ $10$ , into base $-2$ $- 2$ .

Base -2	Conversion	Base 10
$11011$ $11011$	$(-2)^4 + (-2)^3 + (-2)^1 + (-2)^0$ $(- 2)^{4} + (- 2)^{3} + (- 2)^{1} + (- 2)^{0}$	$7$ $7$
$11010$ $11010$	$(-2)^4 + (-2)^3 + (-2)^1$ $(- 2)^{4} + (- 2)^{3} + (- 2)^{1}$	$6$ $6$

Input Specification

The first line of input will contain $N$ $N$ $(1 \le N \le 1\,000)$ $(1 \leq N \leq 1 000)$ , the number of operations to be performed.

The next $N$ $N$ lines will each contain an operation in the format described above.

For at least $25\%$ $25 %$ of the marks, you will only need to convert from base $-2$ $- 2$ to base $10$ $10$ .

For at least another $25\%$ $25 %$ of the marks, $-10\,000 \le y \le 10\,000$ $- 10 000 \leq y \leq 10 000$ .

Output Specification

For each operation, print out the result of the operation on a single line.

Sample Input

Copy

2
A 11011
B 6

Sample Output

Copy

7
11010

Comments

0

DonMillsTeam10_16 commented on May 18, 2016, 3:06 p.m.

Is it guaranteed that converting to base -2 is always possible?

0

FatalEagle commented on May 18, 2016, 3:12 p.m.

You may assume there is always a valid solution.