| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1010 STAMPS 总么一直runtime error ,求高手解答import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
private int kinds = 0;
private final int size = 1000;
private int[] values = new int[size];
private int[] currPath = new int[size];
private int[] path = new int[size];
private int level;
private int numOfKinds = 0;
private int num = 0;
private int maxValue = 0;
private int numOfSame = 0;
private int remainValue = 0;
private int remainNum = 0;
public static void main(String[] args) {
Main m = new Main();
m.start();
}
public void start() {
Scanner scanner = new Scanner(System.in);
String line = null;
while ((line = scanner.nextLine()) != null) {
kinds = 0;
int count = 1;
StringTokenizer st = new StringTokenizer(line);
while (st.hasMoreTokens()) {
int v = Integer.parseInt(st.nextToken());
if (v == 0)
break;
values[count++] = v;
kinds++;
}
st = new StringTokenizer(scanner.nextLine());
while (st.hasMoreTokens()) {
int value = Integer.parseInt(st.nextToken());
if (value == 0)
break;
numOfKinds = 0;
num = 0;
maxValue = 0;
numOfSame = 0;
remainNum = 4;
remainValue = value;
level = kinds;
des(1);
if (numOfSame == 0) {
System.out.println(value + " ---- none");
} else if (numOfSame > 1) {
System.out.println(value + " (" + numOfSame + "): tie");
} else {
System.out.print(value + " (" + numOfKinds + "): ");
for (int i = 1; i <= path[0]; i++) {
int tmpCount = path[i];
while (tmpCount > 0) {
System.out.print(values[i] + " ");
tmpCount--;
}
}
System.out.println();
}
}
}
}
public int[] check(int[] a) {
int num = 0;
int kind = 0;
int maxValue = 0;
for (int i = 1; i <= a[0]; i++) {
if (a[i] != 0) {
num += a[i];
kind++;
if (values[i] > maxValue)
maxValue = values[i];
}
}
return new int[] { kind, num, maxValue };
}
public void update(int[] result) {
numOfKinds = result[0];
num = result[1];
maxValue = result[2];
}
public void copy(int[] src, int[] dest) {
int n = src[0];
for (int i = 0; i <= n; i++) {
dest[i] = src[i];
}
}
public void des(int currLevel) {
if (currLevel > level)
return;
if (remainNum <= 0)
return;
for (int i = 0; i <= remainNum; i++) {
currPath[0] = currLevel;
if (remainValue - i * values[currLevel] < 0)
break;
currPath[currLevel] = i;
remainNum -= i;
remainValue -= i * values[currLevel];
if (remainValue == 0) {
int[] result = check(currPath);
if (numOfSame == 0) {
numOfSame = 1;
update(result);
copy(currPath, path);
} else {
if (result[0] > numOfKinds) {
numOfSame = 1;
update(result);
copy(currPath, path);
} else if (result[0] == numOfKinds && result[1] < num) {
numOfSame = 1;
update(result);
copy(currPath, path);
} else if (result[0] == numOfKinds && result[1] == num
&& result[2] > maxValue) {
numOfSame = 1;
update(result);
copy(currPath, path);
} else if (result[0] == numOfKinds && result[1] == num
&& result[2] == maxValue) {
numOfSame++;
}
}
} else if (remainValue > 0 && currLevel < level) {
des(currLevel + 1);
}
remainNum += i;
remainValue += i * values[currLevel];
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator