Pairs of Integers

From Progteam

Revision as of 16:52, 3 April 2009 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.



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.

Contents

Intuition

We started with the notion that you can significantly lower the search space by noting that based on the units digit, you can determine what the units digits must be down to about 12 pairs (down from 100). Then, having guessed values for the units digit, recursively guess for the rest of the digits.

Pot holes

A couple issues I ran into:

  • Double counting. 11 + 1 = 12 might get counted twice, because you can get "1" from "11" two different ways.
  • Formatting issues. I made a silly assumption that the bigger number will always be the length of N. Not so! Take 100 for example.

Java Solution

import java.util.*;

public class Main{

    public static Scanner in;
 
    public static void main(String[] args){
        in=new Scanner(System.in);

        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();


	List<Pair> pairs = not_chopped(N);
	
	SortedSet<Pair> all = new TreeSet<Pair>(new Comparator<Pair>() {
		public int compare(Pair a, Pair b) {
		    return a.i - b.i;
		}
	    });
	
	all.addAll(pairs);

	System.out.println(all.size());

	for (Pair p: all) {
	    int len = Integer.toString(p.i).length();
	    System.out.printf("%d + %0"+(len-1)+"d = %d\n", p.i, p.j, N);
	}
    }


    public static List<Pair> already_chopped(int N, int last_digit) {
	if ( (N - last_digit) % 11 == 0) {
	    int rest = (N - last_digit) / 11;
	    return listOf(rest * 10 + last_digit, rest);
	} else {
	    return Collections.<Pair>emptyList();
	}
    }
    
    public static List<Pair> not_chopped(int N) {
	if (N == 0) {
	    return Collections.<Pair>emptyList();
	}
	if (N < 10) {
	    return listOf(N, 0);
	}

	String strval = "" + N;
	int unit_digit = 
	    Integer.parseInt("" + strval.charAt(strval.length() - 1));
	int rest = Integer.parseInt(strval.substring(0, strval.length() - 1));
	//System.out.println(unit_digit);

	List<Pair> results = new LinkedList<Pair>();
	
	// First, try keeping the unit digits the same
	if (unit_digit % 2 == 0) {
	    int half = unit_digit / 2;
	    for (Pair p : not_chopped(rest)) {
		results.add(new Pair(p.i * 10 + half, p.j * 10 + half));
	    }
	    // This time half + 5, don't forget the carry
	    for (Pair p : not_chopped(rest - 1)) {
		results.add(new Pair(p.i * 10 + half + 5, p.j * 10 + half + 5));
	    }
	}
	
	// now try all the other combos of digits
	List<Pair> possible_digits = digitsAddingTo(unit_digit);
	
	for (Pair p : possible_digits) {
	    int a = p.i;
	    int b = p.j;
	    
	    boolean carry = a + b >= 10;
	    for (Pair q : already_chopped(rest - (carry ? 1 : 0), b)) {
		results.add(new Pair(q.i * 10 + a, q.j * 10 + b));
	    }
	}
	return results;
    }

    static List<Pair> digitsAddingTo(int N) {
	List<Pair> res = new LinkedList<Pair>();
	for (int i = 0; i < 10; i++) {
	    res.add(new Pair(i, (N - i + 10) % 10));
	}
	return res;
    }

    static class Pair {
	int i, j = 0;
	Pair(int i, int j) {this.i=i; this.j=j;}
	public String toString(){return i+", "+j;}
    }

    static List<Pair> listOf(int i, int j) {
	List<Pair> l = new LinkedList<Pair>();
	l.add(new Pair(i, j));
	return l;
    }
}

Original Python "Solution"

I first used this algorithm, which has a couple formatting related bugs, but in essence gets the right answer and is a lot cleaner than the java. I pretty much wrote the Java from this line by line.

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