1012 - ヨゼフ？時間超過
2011/09/24
java
pku
poj
時間超過
1012 -- Joseph
Javaです。
なんとかそれっぽい答えがでるようになって、submitすると時間超過....
グーグルさんに尋ねて調べると、あらかじめ計算させてその値をつかっていたりしてるようでした。
とりあえずkが10よりうえのものは計算済みのものを使っています。
package p1012;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static class P {
boolean dead = false;
boolean goodP = false;
public P(boolean goodP) {
this.goodP = goodP;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
int k = scanner.nextInt();
if (k == 0)
break;
List<P> list = new ArrayList<Main.P>();
for (int i = 0; i < k; i++) {
list.add(new P(true));
}
for (int i = k; i < k * 2; i++) {
list.add(new P(false));
}
int[] is = { 0, 0, 0, 0, 0, 0, 0, 0, 1740, 93313, 459901, 1358657,
2504881 };
if (10 <= k) {
System.out.println(is[k - 1]);
continue;
}
int m = 0;
A: for (m = 2; m < 100000000; m += 1) {
int pos = 0;
List<P> list2 = new ArrayList<Main.P>(list);
int deadcount = k * 2;
while (deadcount != k) {
pos += m - 1;
if (list2.size() <= pos) {
pos = pos % list2.size();
}
if (pos < k)
continue A;
list2.remove(pos);
deadcount--;
}
break A;
}
System.out.println(m);
}
}
}
: