# Pairs of Integers

### From Progteam

(Difference between revisions)

(→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. |

<pre> | <pre> |

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

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