Pairs of Integers

From Progteam

(Difference between revisions)
Jump to: navigation, search
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


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