# Pairs of Integers

### From Progteam

(Difference between revisions)

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

+ | |||

+ | <pre> | ||

+ | 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 | ||

+ | |||

+ | </pre> | ||

[[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 |
---|---|

Source: | Unknown |

Link: | 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