# Pairs of Integers

(Difference between revisions)
 Revision as of 20:20, 2 April 2009 (view source)Hjfreyer (Talk | contribs)← Older edit Revision as of 04:40, 3 April 2009 (view source)Hjfreyer (Talk | contribs) (solv'd!)Newer edit → 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 == + +
+                                                                                                   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 pairs = not_chopped(N);
+
+                                                                                                   SortedSet all = new TreeSet(new Comparator() {
+                                                                                                   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 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.emptyList();
+                                                                                                   }
+                                                                                                   }
+
+                                                                                                   public static List not_chopped(int N) {
+                                                                                                   if (N == 0) {
+                                                                                                   return Collections.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 results = new LinkedList();
+
+                                                                                                   // 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;
+                                                                                                   }
+
+                                                                                                   static List digitsAddingTo(int N) {
+                                                                                                   List res = new LinkedList();
+                                                                                                   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 listOf(int i, int j) {
+                                                                                                   List l = new LinkedList();
+                                                                                                   return l;
+                                                                                                   }
+                                                                                                   }
+
+ + == 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.

## Revision as of 04:40, 3 April 2009

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

 This problem has been solved by hjfreyer.

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

```