# Pairs of Integers

 Sorter: mlc413 Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1117

Pairs of Integers is problem number 1117 on the Peking University ACM site.

## Python Solution

I have a program which I believe works, (it works on the test input) that I quickly wrote up in python. I'll soon translate this to java and test it.

```def already_chopped(N, last_digit):
rest = (N - last_digit)/11.0
if rest == int(rest):
return [(int(rest)*10 + last_digit, int(rest))]
else:
return []

def not_chopped(N):
if N < 10:
return [(N, 0)]

strval = str(N)
unit_digit = int(strval[-1])
rest = int(strval[0:-1])

results = []

# First, try keeping the unit digits the same
if unit_digit % 2 == 0:
half = unit_digit / 2
results += [(a * 10 + half, b * 10 + half)
for a, b in not_chopped(rest)]

# This time half+5, don't forget the carry
results += [(a * 10 + half + 5, b * 10 + half + 5)
for a, b in not_chopped(rest - 1)]

# now try all the other combos of digits
possible_digits = [(a, (unit_digit - a) % 10) for a in range(10)]

for (a, b) in possible_digits:
carry = a + b >= 10
results += [(big * 10 + a, small * 10 + b)
for big, small in
already_chopped(rest - (carry and 1 or 0), b)]

return results

```