これは私がプログラムを作った私の問題です
アリババは40人の泥棒をだまし、野生のオオカミの家である大きな洞窟の中に彼らを閉じ込めることができました。泥棒は武器を持っておらず、泥棒の首長だけがナイフを持っています。武器がないとオオカミと戦うことができないので、生きたまま食べられるのではなく自殺することにします。
彼らは皆、輪になって立ち、3人に1人が自殺することを決心しますが、泥棒の首長はこの考えを嫌い、自殺するつもりはありません。彼は彼が最後に残っている人になるように彼がどこに立つべきかを計算します。
HackerManはこのストーリーに基づいてゲームを作成したいと考えていますが、殺す代わりに、参加者がゲームを離れることを決定し、3番目ごとの位置ではなく、2番目ごとの位置になります。もちろん、このゲームの参加者数は40人をはるかに超えます。
入力
入力の最初の行は、テストケースの数を指定する整数N（1 <= N <= 1000）です。その後、すべての行に、ゲームの参加者数である整数X（5 <= X <= 100000000）が含まれます。
出力
テストケースごとに、生き残った参加者の位置を含む行を生成します。参加者のシリアル番号が1からnであり、カウントが人1から始まると仮定します。つまり、最初に離れる人は番号2の人です。
サンプル入力
3 5 11 45
サンプル出力
3 7 27
これが私のソリューションプログラムです
class SurvivalStrategy {
public int next;
public int value;
public boolean alive;
SurvivalStrategy(int n, int v)
{
this.next = n;
this.value = v;
this.alive = true;
}
public int getNext(){
return this.next;
}
public void kill(){
this.alive = false;
}
public void changeNext(int n){
this.next = n;
}
public static void main(String[] args) throws IOException {
System.out.println("Enter the number of cases");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int N = Integer.parseInt(line);
int[] array = new int[N];
for(int a = 0; a < N; a++)
{
System.out.println("Enter No. of theives in case " + (a + 1));
array[a] = Integer.parseInt(br.readLine());
}
for(int b = 0; b < N; b++)
{
try{
int theives = 0;
theives = array[b];
SurvivalStrategy[] people = new SurvivalStrategy[theives];
int i = 0;
int nextctr = 2;
for(i = 0; i < people.length; i++)
{
people[i] = new SurvivalStrategy(nextctr, i + 1);
if(nextctr > people.length)
{
people[i] = new SurvivalStrategy(1, i + 1);
}
nextctr++;
}
int k = 0;
int nextguy = 0;
int survivers = people.length;
boolean CarryOnJatta = true;
int lastSurviver = 0;
while(CarryOnJatta)
{
if(k >= people.length)
{
k = 0;
k = k + 2;
}
if(people[k].alive)
{
//System.out.println(people[k].value + " is Alive");
nextguy = people[k].getNext();
if(people[nextguy - 1].alive)
{
people[nextguy - 1].kill();
people[k].changeNext(people[nextguy - 1].next);
lastSurviver = people[k].value;
survivers--;
}else{
k = k + 2;
}
k = k + 2;
}else{
k = k + 2;
}
if (survivers == 1)
{
CarryOnJatta = false;
System.out.println("" + lastSurviver);
}
}
} catch(Exception e)
{
e.printStackTrace();
}
}
}
}
私のプログラムは小さな値の出力を提供していますが、大きな値の出力は提供していません。input（23987443）で試してみると、Javaヒープサイズ超過エラーが発生します。このプログラムのスペースと時間の複雑さを改善できる方法はありますか？他のアルゴリズムが目的の出力を生成している場合も、他のアルゴリズムを利用できます。