# Pairs of Integers

(Difference between revisions)
 Revision as of 16:51, 3 April 2009 (view source)Hjfreyer (Talk | contribs)← Older edit Latest revision as of 16:52, 3 April 2009 (view source)Hjfreyer (Talk | contribs) (→Original Python "Solution") Line 1: Line 1: - {{solved|hjfreyer}} {{solved|hjfreyer}} Line 136: Line 135: == Original Python "Solution" == == 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. + 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.

## Latest revision as of 16:52, 3 April 2009

 This problem has been solved by hjfreyer.

 Sorter: mlc413 Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1117

Pairs of Integers is problem number 1117 on the Peking University ACM site.

## 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;
}
});

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

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

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

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

```