DMPG '16 B6 - Counting Money

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

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 to count. However, Bob's computer needs to handle negative numbers as well, so instead, it uses base -2. Base -2 is very similar to base 2, except the digits represent increasing powers of -2 instead of 2. This means that the digits (from right to left) represent 1, -2, 4, -8, and so on, instead of 1, 2, 4, 8. However, there is still a problem: his computer can't convert between base -2 and base 10 yet. Can you help Bob write a program to do this?

There are two operations that will be needed:

  • A x Change x, a number in base -2, into base 10.
  • B y Change y, a number in base 10, into base -2.
Base -2 Conversion Base 10
11011 (-2)^4 + (-2)^3 + (-2)^1 + (-2)^0 7
11010 (-2)^4 + (-2)^3 + (-2)^1 6

Input Specification

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

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

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

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

Output Specification

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

Sample Input

A 11011
B 6

Sample Output



  • 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.