HDU 1276兵士隊列訓練問題【シミュレーション】
1886 ワード
兵士隊列訓練問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4475 Accepted Submission(s): 2100
Problem Description
ある部隊は新兵の隊列訓練を行い、新兵を最初から順番に番号をつけ、横隊に並べた.訓練のルールは以下の通りである.最初から1から2のカウントを続けます...あとは1から2、1から3の順番で残りの人数が3人を超えないまで行います.
Input
本題には複数のテストデータグループがあり、第一行為グループ数N、次いでN行新兵数であり、新兵数は5000を超えない.
Output
全部でN行あり、それぞれ入力した新兵数に対応し、各行に残りの新兵の最初の番号を出力し、番号の間にスペースがある.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4475 Accepted Submission(s): 2100
Problem Description
ある部隊は新兵の隊列訓練を行い、新兵を最初から順番に番号をつけ、横隊に並べた.訓練のルールは以下の通りである.最初から1から2のカウントを続けます...あとは1から2、1から3の順番で残りの人数が3人を超えないまで行います.
Input
本題には複数のテストデータグループがあり、第一行為グループ数N、次いでN行新兵数であり、新兵数は5000を超えない.
Output
全部でN行あり、それぞれ入力した新兵数に対応し、各行に残りの新兵の最初の番号を出力し、番号の間にスペースがある.
Sample Input
2
20
40
Sample Output
1 7 19
1 19 37
#include <cstdio>
#include <cstring>
bool vis[5500];
int main (){
int T;
scanf("%d", &T);
while(T--){
int N;
scanf("%d", &N);
int k = N;
for(int i = 1; i <= N; ++i)
vis[i] = 1;
if(N <= 3)
{
printf("1");
for(int i = 2; i <= N; ++i)
if(vis[i]) printf(" %d",i);
printf("
");
continue;
}
while(1){
int temp2 = 0;
for(int i = 1; i <= N; ++i){
if(vis[i])
temp2++;
if(temp2 == 2){
vis[i] = 0;
k--;
temp2 = 0;
}
}
if(k <= 3)
break;
int temp3 = 0;
for(int i = 1; i <= N; ++i){
if(vis[i])
temp3++;
if(temp3 == 3){
vis[i] = 0;
k--;
temp3 = 0;
}
}
if(k <= 3)
break;
}
printf("1");
k--;
for(int i = 2; k > 0; i++){
if(vis[i]){
printf(" %d",i);
k--;
}
}
printf("
");
}
return 0;
}