Pairs of Integers

From Progteam

Revision as of 20:20, 2 April 2009 by Hjfreyer (Talk | contribs)
Jump to: navigation, search


Pairs of Integers
Problem Number 1117
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

Personal tools