rust 0.6 (incoming branch) solution to google code jam practice problem "Store Credit" http://code.google.com/codejam/contest/351101/dashboard

credit.rs

fn main() {
  let mut input = get_lines();
    let num_cases_str = vec::remove(&mut input, 0);
    let num_cases = int::from_str(num_cases_str).get();
    let mut i = 1;
    while i <= num_cases {
        let credit = int::from_str(vec::remove(&mut input, 0)).get();
        let _num_items = int::from_str(vec::remove(&mut input, 0)).get();
        let items = vec::map(str::split_char(vec::remove(&mut input, 0), ' '), |&s| int::from_str(s).get());
        let (a, b) = best_buy(credit, items);
        io::println(fmt!("Case #%d: %u %u", i, a, b));
        i += 1;
    }
}

fn best_buy(credit: int, items: &[int]) -> (uint, uint) {
    let buyable = vec::filtered(items, |&itm| itm <= credit);
    let mut best_pair = (0, 1);
    let mut best_total = 0;
    let mut i = 0;
    let mut j: uint;
    while i < buyable.len() - 1 {
        j = i + 1;
        while j < buyable.len() {
            let tmp_total = items[i] + items[j];
            if tmp_total <= credit && tmp_total > best_total {
                best_pair = (i+1, j+1);
                best_total = tmp_total;
            }
            j += 1;
        }
        i += 1;
    }
    best_pair
}

fn get_lines() -> ~[~str] {
    let mut result = ~[];
    let reader = io::stdin();
    let util = @reader as @io::ReaderUtil;
    while !reader.eof() {
        result.push(util.read_line());
    }
    result
}

In this problem you must grab 2 unique items (no more or less). So what looks like a dynamic programming problem at first is actually solved by simply searching all unique pairs. After eliminating unusable items, even google's large input file takes under a second.