Pairs of Integers

From Progteam

(Difference between revisions)
Jump to: navigation, search
(solv'd!)
Line 7: Line 7:
|source
|source
}}
}}
 +
 +
{{solved|hjfreyer}}
 +
'''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 ==
+
== 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 ==
 +
 
 +
<pre>
 +
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;
 +
    }
 +
}
 +
</pre>
 +
 
 +
== Original 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.
+
I first used this algorithm, which has a couple formatting related bugs, but in essence gets the right answer is a lot cleaner than the java.  I pretty much wrote the Java from this line by line.
<pre>
<pre>

Revision as of 04:40, 3 April 2009


Pairs of Integers
Problem Number 1117
Sorter: mlc413
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1117




Checkmark.jpg This problem has been solved by hjfreyer.


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