# Pairs of Integers

(Difference between revisions)
 Revision as of 22:48, 22 April 2008 (view source)Mlc413 (Talk | contribs)← Older edit Revision as of 20:20, 2 April 2009 (view source)Hjfreyer (Talk | contribs) Newer edit → Line 9: Line 9: '''Pairs of Integers''' is problem number 1117 on the Peking University ACM '''Pairs of Integers''' is problem number 1117 on the Peking University ACM site. 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. + +
+                                                                                         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
+
+
[[Category:Number Theory]] [[Category:Number Theory]] [[Category:Arithmetic and Algebra]] [[Category:Arithmetic and Algebra]] {{problem-stub}} {{problem-stub}}

## Revision as of 20:20, 2 April 2009

 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.

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