問題
問題
1 から 2n の数が書かれた 2n 枚のカードがあり，上から 1, 2, 3, ... , 2n の順に積み重なっている．
このカードを，次の方法を何回か用いて並べ替える．
整数 k でカット
上から k 枚のカードの山 A と 残りのカードの山 B に分けた後， 山 A の上に山 B をのせる．リフルシャッフル
上から n 枚の山 A と残りの山 B に分け， 上から A の1枚目， B の1枚目， A の2枚目， B の2枚目， …， A の n枚目， B の n枚目， となるようにして， 1 つの山にする．入力ファイルの指示に従い，カードを並び替えたあとのカードの番号を，上から順番に出力するプログラムを作成せよ．
入力
- 1 行目には n （1 ≦ n ≦ 100）が書かれている． すなわちカードの枚数は 2n 枚である．
- 2 行目には操作の回数 m （1 ≦ m ≦ 1000）が書かれている．
- 3 行目から m + 2 行目までの m 行には， 0 から 2n-1 までのいずれか 1 つの整数 k が書かれており， カードを並べ替える方法を順に指定している．
- k = 0 の場合は， リフルシャッフルを行う．
- 1 ≦ k ≦ 2n-1 の場合は， k でカットを行う．
出力
2n 行からなる出力ファイルを提出せよ． 1 行目には並べ替え終了後の一番上のカードの番号， 2 行目には並べ替え終了後の上から 2 番目のカードの番号というように， i 行目には上から i 番目のカードの番号を出力せよ．
入出力例
入力例1
2
2
1
0
出力例1
2
4
3
1
入力例2
3
2
2
4
0
0
出力例2
1
5
4
3
2
6
解答例
C
#include <stdio.h>
#include <stdlib.h>
void main()
{
//つっちょが練習のため作ったものなのでときどき変かもしれません、ご了承下さい
int x = 0;
int xx;
int i;
int num = 0;
int count = 0;
int count2 = 0;
int card[200];
int cardd[200];
int t[2000];
freopen("output.txt","w",stdout);
freopen("input.txt","r",stdin);
scanf("%d \n",&x);
scanf("%d \n",&num);
xx = x;
x = x * 2;
for( ; count < num;){
scanf("%d \n",&t[count]);
count++;
}
count = 0;
for( ; count < x ;){
card[count] = count+1;
cardd[count] = count+1;
count++;
}
count = 0;
for( ; count < num;){
if(t[count] == 0){
for( ; count2 < xx ;){
i = count2 * 2;
card[i]=cardd[count2];
card[i+1]=cardd[count2+xx];
count2++;
}
}
else{
for( ; count2 < x ;){
i = t[count]+count2;
if(i >= x){
card[count2]=cardd[i-x ];
}
else {
card[count2]=cardd[i];
}
count2++;
}
}
count2 = 0;
for( ; count2 < x ; ){
cardd[count2]=card[count2];
count2++;
}
count++;
count2 = 0;
}
for (;count2 < x;){
printf("%d \n",card[count2]);
count2++;
}
}Java
import java.io.*;
import java.util.*;
public class Answer4 {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileInputStream("input.txt"));
PrintWriter out = new PrintWriter(new FileOutputStream("output.txt"));
int n = in.nextInt();
int n2 = n * 2;
int[] ans = new int[n2];
int[] work = new int[n2];
for(int i=0; i<n2; i++){
ans[i] = i;
}
int m = in.nextInt();
for(int i=0; i<m; i++){
int k = in.nextInt();
if(k == 0){
for(int j=0; j<n; j++){
work[j * 2] = ans[j];
work[j * 2 + 1] = ans[n + j];
}
System.arraycopy(work, 0, ans, 0, n2);
}
else{
int up = n2 - k;
for(int j=0; j<up; j++)
work[j] = ans[j + k];
for(int j=0; j<k; j++)
work[j + up] = ans[j];
System.arraycopy(work, 0, ans, 0, n2);
}
}
for(int i : ans)
out.println(i + 1);
in.close();
out.close();
}
}C#(参考)
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace joi2006_q4
{
class Program
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader("input.txt", Encoding.Default);
int n = int.Parse(sr.ReadLine());//カードの枚数
int m = int.Parse(sr.ReadLine());
int m2 = 0;
int[] card = new int[n * 2 + 1];
int[] aftercard = new int[n * 2 + 1];
string output = "";
for (int i = 1; i <= n * 2; i++)
{
//初期化
card[i] = i;
}
while (true)
{
int refull;
if (m2 == m)
{
sr.Close();
break;
}
else
{
refull = int.Parse(sr.ReadLine());
}
if (refull == 0)
{
for (int s = 1; s <= n; s++)
{
aftercard[s * 2 - 1] = card[s];
aftercard[s * 2] = card[s + n];
}
}
else
{
for (int i = 1; i <= n * 2; i++)
{
if (i + refull <= n * 2)
{
aftercard[i] = card[i + refull];
}
else
{
aftercard[i] = card[i + refull - n * 2];
}
}
}
for (int reset = 1; reset <= n * 2; reset++)
{
card[reset] = aftercard[reset];
}
m2++;
}
for (int i = 1; i <= n * 2; i++)
{
output += card[i].ToString() + Environment.NewLine;
}
StreamWriter sw = new StreamWriter("output.txt", false, Encoding.Default);
sw.Write(output);
sw.Close();
}
}
}考察
単に「正確にプログラムが書けるか」という問題であるが、いささか複雑ではある。
少しずつ作っていき、こまめにそれまで書いたコードが正常に動作しているかデバッグ出力を確認する作業が大切である。
問題では1..nという添字が用いられているが、全て0..n-1と読み替える。
出力時には+1する必要がある。
並べ替えの実装に関しては、図をよく見て添字の対応関係を
具体的な作業としては次の通りである。
- カードのデータを保存しておく配列ans[200]と並べ替えのときに用いる一時的な領域work[200]を宣言する(2<=2n<=200)。
- nを入力する(2nが頻繁に登場するので、ここで変数n2に2倍した値を代入しておくこととする)
- ans[i](0<=i<2n)をi+1で初期化する。
- mを入力し、以下の操作をm回行う。
- kを入力する。kが0の場合はリフルシャッフル、それ以外の場合はカットを行う。
- workにansから新たなカードの並び順を作成する。
- リフルシャッフル
- 図を参考にすると次のようになる(２枚ずつn回処理する)(0<=j<n)。
- work[j * 2] = ans[j];
- work[j * 2 + 1] = ans[n + j];
- カット
- 新しい並びの切れ目をcut = n2 - k;で得る。これは上のカードが何枚か、および下のカードの一番上のカードの添字となる(元の切れ目はもちろんk)。
- まず上のカードを下に配置する。上のカードはk枚なので(0<=j<k)
- work[j + cut] = ans[j];
- 次に下のカードを上に配置する。下のカードはcut枚なので(0<=j<cut)
- work[j] = ans[j + k];
- workをansにコピーする(ループで簡単にできるが、Cならmemcpy、JavaならSystem.arrayCopyがスマート)。
- 答えの並びがansに入っているので、それを出力する。