Ruby每周一测 - 找零钱 - I am sailing, I am sailing

Ruby每周一测 - 液晶屏数字 | 一个奇怪的JS导致Firefox Session Restore ...

2008-03-25

Ruby每周一测 - 找零钱

Ruby每周一测 - Ruby Quiz 是Ruby Talk邮件列表上的一个持续了很长时间活动，每周有一个小题目被提出来，然后大家进行解答讨论。Amazon上还有相关的书： Best of Ruby Quiz。我尝试挑选其中的一些题目进行翻译，做一个每周一测系列，欢迎大家参与讨论。

-----题目分割线-----

这周的题目是找零钱，假设我们需要找给别人39美分的零钱，那么结果将会是(美元的硬币有25,10,5,1这种)：

>> make_change(39)
=> [25, 10, 1, 1, 1, 1]

假设我们的硬币种类有10,7,1，那么找14美分的零钱结果将会是：

>> make_change(14, [10, 7, 1])
=> [7, 7]

这次的每周一测就是完成该方法：

def make_change(amount, coins = [25, 10, 5, 1])

end

这个方法应该返回最优化的结果，即总的零钱个数最少。
另外，为了编程方便，这里假设coins已经是排序完毕的，并且如果无解的话，返回nil： make_change(5, coins = [4,2]) => nil

-----解答分割线-----
原题和一些解法在这里：http://rubyquiz.com/quiz154.html
原文的解答说明简单翻译见：http://www.javaeye.com/post/501439

16:23
浏览 (535)
评论 (65)
分类: Ruby
进入论坛
相关推荐

struts 2008-05-30

seairy 写道

def make_change(amount, coins = [25, 10, 5, 1])
	change = []
	coins.each do |coin|
		(amount / coin).times do
			change << coin
			amount -= coin
		end
	end
	change if amount.zero?
end

p make_change(39) #[25, 10, 1, 1, 1, 1]
p make_change(14, [10, 7, 1]) #[10, 1, 1, 1, 1]
p make_change(14, [5, 3, 2]) #nil
p make_change(12, [22, 3, 2]) #[3, 3, 3, 3]

sandybuster 2008-05-30

没看大家的做了一个
做完之后再看大家的
自己想的很不全面啊
谢谢各位受教了

sandybuster 2008-05-30

这个应该用递归比较好吧，还有就是零钱中必须要有1，不然有时候会出错。

def make_change(money,change_array)
  alist=change_array.sort{|x,y| x <=> y }
  alength=change_array.length
  change=0
  for i in (0..alength-1)
    if money>=alist[i]
      change=alist[i]
    else 
      break
    end
  end
  
  if money>0
    puts change
    make_change(money-change,change_array)
  end
end
list=[25,10,5,1]
make_change(23,list)#10 10 1 1 1
make_change(55,list)#25 25 5
make_change(1,list)# 1
make_change(39,list)#25 10 1 1 1 1

1000copy 2008-05-07

class Array; def sum; inject( nil ) { |sum,x| sum ? sum+x : x }; end; end
def clonearray(arr)
	b = []
	for a in arr
	  b << a 
	end
	return b
end
def match(condidatesolution,avail,paymoney)
	@temp = 0
	for i in 0..avail.size-1
		@temp += condidatesolution[i] * avail[i]
	end
	return ( @temp ==paymoney)
end
def printarray(arr)
	print "["
	for a in arr
		print a.to_s + ","
	end
	print "]"
end
def makechange2(paymoney,avail)
	# 相当于解方程 aW+bX+cY+dZ = paymoney
	# 要求：
	# 这里W,X,Y,Z = 10,7,5,1
	# 要求找到所有的[a,b,c,d]的集合中
	#  a+b+c+d 是最小的作为解。
	#
	# 最大范围的数组 [3,5,7,39]
	
	# 获得最大数组 coinmax
	@coinmax = []
	@coincurr = []
	for coinavail in avail
	  @coinmax << paymoney/coinavail
	  @coincurr << 0
	end
	#printarray @coinmax
	#printarray @coincurr
	@size = @coincurr.size()
	# 循环遍历可能解空间，升位，直到 @coincurr[@size-1] > @coinmax[@size-1] 
	@i =0 
	@mincoincount = 99999 

	while @coincurr[@size-1] <= @coinmax[@size-1] 
	    if match(@coincurr,avail,paymoney)
		  print "a solution:"
		  printarray @coincurr
		  puts
		  @coincount = 	@coincurr.sum
		  if @coincount < @mincoincount 
		    @mincoincount = @coincount
		    @finalsolution = clonearray(@coincurr)		    
		  end 
		end	
		@first = @coincurr.shift
		@coincurr.insert(0,@first+1)
		#print "--"
		#printarray @coincurr
		for i in 0..(@size -2)
		  if @coincurr[i] > @coinmax[i] 
		    @coincurr[i+1] = @coincurr[i+1] + @coincurr[i] / (@coinmax[i]+1)
		    @coincurr[i] = @coincurr[i] % (@coinmax[i]+1)
		  end
		end  
	end
	print "finalsolution:"
	printarray @finalsolution
end
makechange2( 39,[10,7,5,1])

kdekid 2008-05-03

def make_change(amount, coins=[25, 10, 5, 1])
begin
  plan = []
  for am in coins.min..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in coins.min..am/2 do
        if plan[a] and plan[am-a] then
          s = plan[a].length + plan[am-a].length
          if s < size then
            size = s
            plan[am] = plan[a] + plan[am-a]
          end
        end
      end
    end
  end
  plan[amount]
rescue StandardError => bang
  nil
end
end

这个方法和QuakeWang翻译的第二种方法类似。其实动态规划一般不考虑用递归。递归用到桟，桟一般较小，当递归层次很深的时候有可能桟溢出。第二种方法是递推，简单来说，就是从最基本的情况出发。例如这里，递归函数是

M(k) = min{M(1)+M(k-1), M(2)+M(k-2), ..., M(k/2, n-k/2)}

递归的方法是从 k = amount 的情况开始考虑。而递推的方法是从 k = 1 开始考虑。所以递推是先计算 k = 1 时，M(k) = ?，然后 k = 2 时，M(k) = ?，一直到 k = amount，M(k) = ?。

递推法因为没有用桟，而是用堆作为储存空间，所以递推法一般较递归要好。递推法也更好理解。

lianion 2008-04-09

Java版,对11个测试分别循环1000次,总共需要15ms.

public class Test {

	public static int[] change(int change, int[] coins) {

		// 初始化 硬币种类
		if (coins == null) {
			int[] cs = { 25, 10, 5, 1 };
			coins = cs;
		}

		// 硬币种类的个数
		int count = coins.length - 1;

		// 优化 忽略用不到的大面额硬币
		int start = 0;
		for (; start <= count; start++) {
			if (change >= coins[start]) {
				break;
			}
		}
		if (start != 0) {
			count -= start;
			int[] cs = new int[count + 1];
			System.arraycopy(coins, start, cs, 0, count + 1);
			coins = cs;
		}

		// 得到结果
		int[] ns = change(change, coins, count);

		// 将用不到的大面额的硬币的个数设置为0
		if (start != 0) {
			count += start;
			int[] cs = new int[count + 1];
			System.arraycopy(ns, 0, cs, start, ns.length);
			ns = cs;
		}
		return ns;
	}

	public static int[] change(int change, int[] coins, int count) {

		// 最少的硬币个数据
		int min = change / coins[0];
		if (min * coins[0] == change) {
			int[] ns = new int[count + 1];
			ns[0] = min;
			return ns;
		} else {
			min++;
		}
		// 最多的硬币个数据
		int max = change / coins[count] + 1;

		for (int current = min; current <= max; current++) {
			int[] r = new int[count + 1];

			// 初始值
			r[0] = current;

			do {
				// 进位
				if (r[0] == 0) {
					int i = 1;
					for (; i < count; i++) {
						if (r[i] != 0) {
							break;
						}
					}
					r[i + 1]++;
					r[i - 1] = r[i] - 1;
					r[i] = 0;
				} else {
					r[0]--;
					r[1]++;
				}
				// 比较
				int sum = 0;
				for (int i = 0; i <= count; i++) {
					sum += r[i] * coins[i];
				}
				if (sum == change) {
					return r;
				}

			} while (r[count] != current); // 循环结束

		}
		return null;
	}

	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		for (int i = 0; i < 1000; i++) {
			eq(change(25, new int[] { 25 }), new int[] { 1 });
			eq(change(10, new int[] { 10 }), new int[] { 1 });
			eq(change(1, new int[] { 1 }), new int[] { 1 });
			eq(change(5, new int[] { 3, 2 }), new int[] { 1, 1 });
			eq(change(5, new int[] { 4, 3, 2 }), new int[] { 0, 1, 1 });
			eq(change(39, new int[] { 25, 10 }), null);
			eq(change(14, new int[] { 10, 7, 1 }), new int[] { 0, 2, 0 });
			eq(change(14, new int[] { 5, 3, 2 }), new int[] { 1, 3, 0 });
			eq(change(12, new int[] { 22, 3, 2 }), new int[] { 0, 4, 0 });
			eq(change(40, new int[] { 20, 19, 1 }), new int[] { 2, 0, 0 });

			eq(change(427, new int[] { 10000, 1000, 10, 1 }), new int[] { 0, 0,
					42, 7 });
		}
		long end = System.currentTimeMillis();
		System.out.println((end - start) + "ms");
	}

	public static boolean eq(int[] a, int[] b) {
		boolean r;
		if (a == null) {
			r = b == null;
		} else {
			r = true;
			int m = a.length - 1;
			for (int i = 0; i <= m; i++) {
				if (a[i] != b[i]) {
					r = false;
				}
			}
		}
		return r;
	}

}

javasweet 2008-04-03

我贴一个用java写的，输出结果与要求的稍有不同。使用最小公倍数求最优解。

　Java代码
public static void main(String[] args) {
int[] coins = new int[] { 11, 10, 5, 2 };
int[] change = make_change(127, coins);
print(change, coins);
}

public static int[] make_change(int amount, int[] coins) {
return change(amount, coins, 0);
}

private static int[] change(int amount, int[] coins, int start) {

int[] result = null;

if (coins.length == 0) {
return null;
}

result = new int[coins.length];

int balance = amount;
int gcd = 0;
int i = 0;

if (start == coins.length - 1) {
gcd = coins[start];
} else {
gcd = gcd(coins[start], coins[start + 1]);
}

balance = amount;
if (amount >= gcd) {
result[start] = (amount / gcd) * (gcd / coins[start]);
balance = amount - coins[start] * result[start];
}

if (balance == 0) {
return result;
} else if (start == coins.length - 1) {
return null;
}

int[] firstChange = new int[coins.length];
int pMaxCoin = -1;
int[] minChange = null;

amount = balance;
i = start;

while (i < coins.length && amount != 0) {
firstChange[i] = amount / coins[i];
if (pMaxCoin == -1) {
pMaxCoin = i;
}
amount = amount - firstChange[i] * coins[i];
i++;
}

if (amount > 0) {
minChange = null;
} else {
minChange = firstChange;
}

int other[] = new int[coins.length];

for (i = 1; i <= firstChange[pMaxCoin]; i++) {
amount = balance - (firstChange[pMaxCoin] - i) * coins[pMaxCoin];
other = change(amount, coins, start + 1);
if (other != null) {
other[pMaxCoin] = (firstChange[pMaxCoin] - i) + other[pMaxCoin];
if (sum(other) < sum(minChange)) {
minChange = other;
}
}
}
if (minChange == null || result == null) {
return null;
}
for (i = 0; i < result.length; i++) {
result[i] = result[i] + minChange[i];
}
return result;
}

private static int lcm(int a, int b) {

int max = a;
int min = b;
int c = 0;

if (a < b) {
max = b;
min = a;
}
c = max % min;
if (c == 0) {
return min;
} else {
return lcm(min, c);
}
}

private static int gcd(int a, int b) {
int lcm = lcm(a, b);
return a * b / lcm;

}

public static void print(int[] change, int[] coins) {
if (change == null) {
System.out.println("can'nt change");
return;
}
for (int i = 0; i < change.length; i++) {
if (change[i] > 0) {
System.out.println(coins[i] + "×" + change[i]);
}
}
}

private static int sum(int[] a) {
if (a == null) {
return Integer.MAX_VALUE;
}
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
return sum;
}

这个有bug：
int[] coins = new int[] { 40,34,17,12,11,10,3,2 };
int[] change = make_change(30, coins);
print(change, coins);
得出的结论是 can'nt change,但是是有结果的：[17,1][11,1][2,1]或者[10,3]

kiol 2008-03-31

第二个算法好像是按步走的，就是每一次都用所有的硬币情况试一遍，并记录累积。
直到第一次累积到a，这就是所用步骤最少也就是硬币最少的解法。
但是我怀疑他的效率。

blcakcat 2008-03-31

我贴一个用java写的，输出结果与要求的稍有不同。使用最小公倍数求最优解。

　

public static void main(String[] args) {
        int[] coins = new int[] { 11, 10, 5, 2 };
        int[] change = make_change(127, coins);
        print(change, coins);
    }

    public static int[] make_change(int amount, int[] coins) {
        return change(amount, coins, 0);
    }

    private static int[] change(int amount, int[] coins, int start) {

        int[] result = null;

        if (coins.length == 0) {
            return null;
        }

        result = new int[coins.length];

        int balance = amount;
        int gcd = 0;
        int i = 0;

        if (start == coins.length - 1) {
            gcd = coins[start];
        } else {
            gcd = gcd(coins[start], coins[start + 1]);
        }

        balance = amount;
        if (amount >= gcd) {
            result[start] = (amount / gcd) * (gcd / coins[start]);
            balance = amount - coins[start] * result[start];
        }

        if (balance == 0) {
            return result;
        } else if (start == coins.length - 1) {
            return null;
        }

        int[] firstChange = new int[coins.length];
        int pMaxCoin = -1;
        int[] minChange = null;

        amount = balance;
        i = start;

        while (i < coins.length && amount != 0) {
            firstChange[i] = amount / coins[i];
            if (pMaxCoin == -1) {
                pMaxCoin = i;
            }
            amount = amount - firstChange[i] * coins[i];
            i++;
        }

        if (amount > 0) {
            minChange = null;
        } else {
            minChange = firstChange;
        }

        int other[] = new int[coins.length];

        for (i = 1; i <= firstChange[pMaxCoin]; i++) {
            amount = balance - (firstChange[pMaxCoin] - i) * coins[pMaxCoin];
            other = change(amount, coins, start + 1);
            if (other != null) {
                other[pMaxCoin] = (firstChange[pMaxCoin] - i) + other[pMaxCoin];
                if (sum(other) < sum(minChange)) {
                    minChange = other;
                }
            }
        }
        if (minChange == null || result == null) {
            return null;
        }
        for (i = 0; i < result.length; i++) {
            result[i] = result[i] + minChange[i];
        }
        return result;
    }

    private static int lcm(int a, int b) {

        int max = a;
        int min = b;
        int c = 0;

        if (a < b) {
            max = b;
            min = a;
        }
        c = max % min;
        if (c == 0) {
            return min;
        } else {
            return lcm(min, c);
        }
    }

    private static int gcd(int a, int b) {
        int lcm = lcm(a, b);
        return a * b / lcm;

    }

    public static void print(int[] change, int[] coins) {
        if (change == null) {
            System.out.println("can'nt change");
            return;
        }
        for (int i = 0; i < change.length; i++) {
            if (change[i] > 0) {
                System.out.println(coins[i] + "×" + change[i]);
            }
        }
    }

    private static int sum(int[] a) {
        if (a == null) {
            return Integer.MAX_VALUE;
        }
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
        return sum;
    }

lllyq 2008-03-31

要解释还挺麻烦的，这个面对面画个图就好解释了，尽量不用术语
要找的零钱为m, 假设解为Dk, Dk-1,..., D1
先做第k次决策Dk，尝试所有的零钱C(1..i)，则Dk-1=m-Dk(Ci)，他这里的解法就是用数组保存状态，整个数组长度就是m，Dk就是下标到起点的距离（默认是0，因为就是求m），然后再从m-Dk的下标开始作为起点，如果改点已被标记，根据最优解原理，就忽略
简单的例子如找7对[3, 2, 1]，Dk决策就是3, 2, 1，此时状态就是3剩4， 2剩5，1剩6，再分别对4, 5, 6重复尝试，可以举出一个重复的例子，其中5-1=4(也就是7-2-1)，与7-3=4就表示重复了，那就忽略, 一直重复没有零钱为止，重复的次数就是零钱的最优个数，然后根据保存的状态找到最优解

hongkong 2008-03-30

不知有没有哪个测试驱动高手，能小步骤用测试驱动方法寻出方案
期待啊

Quake Wang 2008-03-29

是一个意思，不过原文提供的解法优化了一下，把能够整除的小值硬币移除掉，不参与计算：

inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}

庄表伟 2008-03-29

def make_change(amount, coins = [25, 10, 5, 1],list={})
  return list[amount] if list.include?(amount)
  return [amount] if coins.include?(amount)
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin},list)
    if other_coins && min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  list[amount]=return_array=min_one_coin ? [min_one_coin]+min_coins : nil
end

p make_change(14,[10,7,1],{})
p make_change(380,[20,19,1],{})
p make_change(30,[21,10,1],{})

to:Quake Wang

我这个，是不是跟你那个解法，是一个意思？

Quake Wang 2008-03-29

让我们来看一个简单解法：

def make_change(amount, coins = [25,10,5,1])
  coins.map{|coin| f = amount/coin; amount %= coin; Array.new(f){coin} }.flatten
end

这里采用贪心算法，每次总是用最大的硬币去整除，然后将余下的钱用下一个硬币进行同样运算。这种算法在美元硬币体系以及其他很多国家（如人民币)下就是最优解法了(如何证明？)，但是在前面第2个例子make_change(14, [10, 7, 1])，就得不到最优解。

复杂的部分开始了：如果要得到最优解法，就要列出所有的可能组合，但是考虑到穷举法的效率问题，我们需要用更"聪明"的算法检查各种组合。这个问题实际上和计算机科学中著名的背包问题(Knapsack Problem)是等价的，用于解决这个问题常见的算法是动态规划(Dynamic programming algorithm)。

动态规划通常有2种方式:
1. 自顶向下 (Top-down)，将问题分解为多个小问题，然后用递归和备忘录(memoization)的方式进行计算，避免相同的小问题重复计算，下面这个解答就是采用这个方式：

class Array
  def sum
    inject {|total, i| total + i}
  end
end

def make_change(amount, coins = [25, 10, 5, 1])
  # memoize solutions
  optimal_change = Hash.new do |hash, key|
    hash[key] = if key < coins.min
      []
    elsif coins.include?(key)
      [key]
    else
      coins.
        # prune unhelpful coins
      reject { |coin| coin > key }.

        # prune coins that are factors of larger coins
      inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}.

        # recurse
      map { |coin| [coin] + hash[key - coin] }.

        # prune unhelpful solutions
      reject { |change| change.sum != key }.

        # pick the smallest, empty if none
      min { |a, b| a.size <=> b.size } || []
    end
  end

  optimal_change[amount]
end

这里比较有意思的是利用了Ruby Hash构建器，给Hash传递了一个hash/key的block，这样传递同样的Key就不会重复计算了，配合递归就得到了结果：

      map { |coin| [coin] + hash[key - coin] }

2. 自底向上 (Bottom-up) (这种方式我不是很明白，有谁可以解释一下？)

def make_change(a, list = [25, 10, 5, 1])
  return nil if a < 0
  return nil if a != a.floor

  parents = Array.new(a + 1)
  parents[0] = 0
  worklist = [[0, 0]]
  while parents[a].nil? && !worklist.empty? do
    base, starting_index = worklist.shift
    starting_index.upto(list.size - 1) do |index|
      coin = list[index]
      tot = base + coin
      if tot <= a && parents[tot].nil?
        parents[tot] = base
        worklist << [tot, index]
      end
    end
  end

  return nil if parents[a].nil?
  result = []
  while a > 0 do
    parent = parents[a]
    result << a - parent
    a = parent
  end
  result.sort!.reverse!
end

-----备注分割线-----
以上是简单的翻译原文解答说明，从这个每周一测可以学到Ruby Array多种方法(map, reject, inject, min ...)，Hash构建器的妙用，以及动态规划算法入门。
可惜我不是学计算机科学的，算法是我的弱项，大家对于这2个解法的详细说明有兴趣的话，还是看原文吧： http://rubyquiz.com/quiz154.html
后续的每周一测我会挑选那些更有趣，或者能够体现Ruby语言妙用的题目，尽量少偏向算法的题目。

hax 2008-03-29

我前面写的那个代码有bug。改后的：

function makeChange1(amount, coins) {
	if (coins == null) coins = [25, 10, 5, 1];
	if (coins.cache == null) coins.cache = {};
	for (var i = 0; i < coins.length; i++) {
		var c = coins[i];
		var o = coins.cache[c] = {length:1};
		o[c] = 1;
	}
	return mapToArray(_makeChange1(amount, coins, 0, Number.POSITIVE_INFINITY));
}

// convert Map<int, int> to List<int>
// {1:2,2:0,3:1} => [1,1,3]
function mapToArray(map) {
	if (map == null) return [];
	var a = [];
	for (var k in map) {
		k = parseInt(k, 10);
		if (isNaN(k)) continue;
		var v = map[k];
		for (var i = 0; i < v; i++) a.push(k);
	}
	return a.sort(compare);
}

function compare(a, b) {
	return b - a;
}

function _makeChange1(amount, coins, offset, max) {
	var x = coins.cache[amount];
	if (x != null) return x.length <= max ? x : null;
	
	var best = null;
	
	for (var i = offset; i < coins.length; i++) {
		var c = coins[i];
		if (c * max < amount) break;
		var m = amount % c;
		if (m == 0) {
			var n = amount / c;
			max = n - 1;
			best = {length:n}; best[c] = n;
		} else if (m == amount) {
			continue;
		} else {
			var n = (amount - m) / c;
			while (n > 0) {
				var x = _makeChange1(m, coins, i + 1, max - n);
				if (x != null) {
					x[c] = x[c] ? x[c] + n : n;
					x.length += n;
					max = x.length - 1;
					best = x;
				}
				n--; m += c;
			}
		}
	}
	coins.cache[amount] = best;
	return best;
}

function eq(a, b) {
	if (a === b) return true;
	if (a instanceof Array && b instanceof Array && a.length == b.length) {
		for (var i = 0, n = a.length; i < n; i++) {
			if (a[i] != b[i]) return false;
		}
		return true;
	}
	return false;
}

function assertEq(a, b) {
	if (!eq(a, b)) throw Error(a + ' != ' + b);
}

var makeChange = makeChange1;

assertEq(makeChange(25), [25]);
assertEq(makeChange(10), [10]);
assertEq(makeChange(1), [1]);
assertEq(makeChange(5, [3, 2]), [3, 2]);
assertEq(makeChange(5, [4, 3, 2]), [3, 2]);
assertEq(makeChange(39), [25, 10, 1, 1, 1, 1]);
assertEq(makeChange(14, [10, 7, 1]), [7, 7]);
assertEq(makeChange(14, [5, 3, 2]), [5, 5, 2, 2]);
assertEq(makeChange(12, [22, 3, 2]), [3, 3, 3, 3]);
assertEq(makeChange(38, [20, 19, 1]), [19, 19]);

var t1 = new Date().getTime();
var test = makeChange(31415926, [10001, 1001, 101]);
var t2 = new Date().getTime();

out(test.length + ':[' + test + '] use time:' + (t2 - t1));

function out(s) {
	if (typeof alert != 'undefined') alert(s);
	if (typeof WScript != 'undefined') WScript.Echo(s);
}

执行结果：
D:\sjhe\js\test\change>cscript change.js
Microsoft (R) Windows Script Host Version 5.6
Copyright (C) Microsoft Corporation 1996-2001. All rights reserved.

3926:[10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,1001,1001,1001,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101] use time:4375

kiol 2008-03-28

有个bug，改了一下。

def make_change(amount, coins = [25, 10, 5, 1])
  return nil if amount == 0
  return [amount] if coins.include? amount
  coins_count = []
  valid_coins = coins.select{|coin| coin < amount}
  valid_coins.each do |coin| 
    counter = [amount]
    idx = 0
    while  counter[idx] >= coin do
      counter << counter[idx] - coin
      counter[idx] = coin
      idx = idx.next
    end
    tail = counter.delete_at(idx)
    counter.concat(make_change(tail, valid_coins)) if tail > 0
      
    coins_count << counter
  end
   
  min = 9999
  result = []
  coins_count.each do |counter|
    if counter.size < min
      min = counter.size
      result = counter
    end
  end
  
  return result
end

arr = make_change(380,[30, 20, 5, 1])
puts arr
tmp = 0
arr.each{|i| tmp += i}
puts tmp

kiol 2008-03-28

我也写了一个，不知道对不对
def make_change(amount, coins = [25, 10, 5, 1])
return nil if amount == 0
return [amount] if coins.include? amount
coins_count = []
valid_coins = coins.select{|coin| coin < amount}
valid_coins.each do |coin|
counter = [amount]
idx = 0
while counter[idx] >= coin do
counter << counter[idx] - coin
counter[idx] = coin
idx = idx.next
end
if counter[idx] > 0
counter << make_change(counter[idx], valid_coins)
else
counter.delete_at(idx)
end
coins_count << counter
end

min = 9999
result = []
coins_count.each do |counter|
if counter.size < min
min = counter.size
result = counter
end
end

return result
end

puts make_change(380,[20,19,1])

t0uch 2008-03-28

我也来贴一个

依据coins[i] = 1 + min{coins[i - d[j]]}

c语言风格，不要笑

def make_change(amount, coins = [25, 10, 5, 1])
  
  c = Array.new
  choice = Array.new
  result = Array.new
  minchoice = 0
  
  c[0] = 0
  
  for i in 1..amount
    min = 100000
    for j in 0..(coins.size() - 1)
      if coins[j] <= i and c[i - coins[j]] < min
        min = c[i - coins[j]]
        minchoice = j
      end
      c[i] = 1 + min
      choice[i] = minchoice
    end
  end

  if c[amount] == 100001
    return nil
  else
    while amount > 0
      result.push(coins[choice[amount]])
      amount = amount - coins[choice[amount]]
    end
    result
  end
  
end

#print make_change(50)
#puts make_change(1)
#puts make_change(9,[10,2,1])
#puts make_change(8,[10,4,2])
#puts make_change(19,[10,4,2,1])
#puts make_change(38, [20, 19, 1])
#puts make_change(11, [10, 1])

ps:怎么测试跑的速度？

hax 2008-03-28

function makeChange1(amount, coins) {
	if (coins == null) coins = [25, 10, 5, 1];
	if (coins.cache == null) coins.cache = {};
	for (var i = 0; i < coins.length; i++) {
		var c = coins[i];
		var o = coins.cache[c] = {length:1};
		o[c] = 1;
	}
	return mapToArray(_makeChange1(amount, coins, Number.POSITIVE_INFINITY));
}

// convert Map<int, int> to List<int>
// {1:2,2:0,3:1} => [1,1,3]
function mapToArray(map) {
	var a = [];
	for (var k in map) {
		k = parseInt(k, 10);
		if (isNaN(k)) continue;
		var v = map[k];
		for (var i = 0; i < v; i++) a.push(k);
	}
	return a.sort(compare);
}

function compare(a, b) {
	return b - a;
}

function _makeChange1(amount, coins, max) {
	var x = coins.cache[amount];
	if (x) return x.length < max ? x : null;
	
	var best = null;
	
	for (var i = 0; i < coins.length; i++) {
		var c = coins[i];
		if (c * max < amount) break;
		var m = amount % c;
		if (m == 0) {
			n = amount / c;
			max = n - 1;
			best = {length:n}; best[c] = n;
		} else if (m == amount) {
			continue;
		} else {
			var x = _makeChange1(amount - c, coins, max - 1);
			if (x == null) continue;
			max = x.length - 1;
			best = x; best[c] = best[c] ? best[c] + 1 : 1;
		}
	}
	coins.cache[amount] = best;
	return best;
}

function eq(a, b) {
	if (a === b) return true;
	if (a instanceof Array && b instanceof Array && a.length == b.length) {
		for (var i = 0, n = a.length; i < n; i++) {
			if (a[i] != b[i]) return false;
		}
		return true;
	}
	return false;
}

function assertEq(a, b) {
	if (!eq(a, b)) throw Error(a + ' != ' + b);
}

var makeChange = makeChange1;

assertEq(makeChange(25), [25]);
assertEq(makeChange(10), [10]);
assertEq(makeChange(1), [1]);
assertEq(makeChange(5, [3, 2]), [3, 2]);
assertEq(makeChange(5, [4, 3, 2]), [3, 2]);
assertEq(makeChange(39), [25, 10, 1, 1, 1, 1]);
assertEq(makeChange(14, [10, 7, 1]), [7, 7]);
assertEq(makeChange(14, [5, 3, 2]), [5, 5, 2, 2]);
assertEq(makeChange(12, [22, 3, 2]), [3, 3, 3, 3]);
assertEq(makeChange(38, [20, 19, 1]), [19, 19]);

var t1 = new Date().getTime();
var test = makeChange(31415926, [100000,1000,10,1]);
var t2 = new Date().getTime();
WScript.Echo(test.length, '[' + test + ']', ' use time:', t2 - t1);

输出结果：
D:\sjhe\js\test\change>cscript change.js
Microsoft (R) Windows Script Host Version 5.6
Copyright (C) Microsoft Corporation 1996-2001. All rights reserved.

427 [100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,1000,1000,1000,1000,1000,1000,1000,10
00,1000,1000,1000,1000,1000,1000,1000,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10
,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1
0,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,
1,1,1] use time: 16

用了16ms。

Trustno1 2008-03-28

如果只是想知道的答案的话,
可以去这里
http://acm.nankai.edu.cn
注册个号，找1132题.
题目稍微有差异,但是思路相同.

发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

Quake Wang

浏览: 27236 次
性别:
来自: 上海
详细资料

I am sailing, I am sailing

Ruby每周一测 - 找零钱

评论

发表评论

搜索本博客

博客分类

我的相册

其他分类

最近加入圈子

存档

最新评论

评论排行榜