プログラムの実行結果は以下の通り。
39回進み，5歩目，25歩目で逆向きに進む。詳細は以下の通り。 1 sum:1 2 sum:3 3 sum:6 4 sum:10 * 5 sum:5 6 sum:11 7 sum:18 8 sum:26 9 sum:35 10 sum:45 11 sum:56 12 sum:68 13 sum:81 14 sum:95 15 sum:110 16 sum:126 17 sum:143 18 sum:161 19 sum:180 180 OK 20 sum:200 21 sum:221 22 sum:243 23 sum:266 24 sum:290 * 25 sum:265 26 sum:291 27 sum:318 28 sum:346 29 sum:375 30 sum:405 31 sum:436 32 sum:468 33 sum:501 34 sum:535 35 sum:570 36 sum:606 37 sum:643 38 sum:681 39 sum:720 360 OK
プログラムのソースは以下の通り。
#include "puzutl.h"
const int N = 100; // まあこれくらいの数字の中に見つかるでしょ。
int sum[1+N] = {0}; // 事前に歩数の合計値は計算しておく
YesNo check180( int n, int i, int j) // ちょうど180度で止まるか?
// n :I:1歩,2歩,…,n歩進む
// i :I:この歩数の時逆方向に進む
// j :I:この歩数の時逆方向に進む
{
int sum = 0; // 進んだ歩数
for( int k=1; k<= n; k++) { // 1歩からn歩進む
if( k == i || k == j) sum -= k; // i,jで逆向きに進む
else sum += k; // i,j以外は時計回りに進む
if( (sum+180) % 360 == 0) { // sum%180にしてしまうと360度の場合も含まれてしまうので
return YES; // ちょうど180度で停止した
}
}
return NO; // 180度で停止することはなかった。
}
int main( int argc, cstring argv[])
{
int minn = 0; // 最低360度回転しなければならないので必ず進む歩数があるはず
for( int i=1; i<= N; i++) { // 最初にトータルの歩数を求めておく
sum[i] += i+sum[i-1]; // トータルの歩数は前の歩数に次の歩数を足したもの
if( minn == 0 && sum[i] > 360) { // 最低1周する所から調べ始める
minn = i; // minnを使わないで1から調べた方がバグが少ないプログラムになる
}
}
for( int n=minn; n< N; n++) { // 合計数字が針の動く回数だから小さい数字から調べていく
for( i=1; i< n; i++) { // その中から2つの数字を選択して調べる(一つめの数字)
for( int j=i+1; j< n; j++) { // もう一つの数字(一つめより必ず大きな数字)
int back = i+j; // ２つの数字の合計
if( ((sum[n]-back-back)%360) == 0) { // 2回引き算するのは，回ったと仮定してある分を取り消し，更にその分元に戻る
if( check180( n, i, j)) { // その中にちょうど180で止まっているものがあるか?
ps( "%d回進み，%d歩目，%d歩目で逆向きに進む。詳細は以下の通り。\n", n, i, j);
int sum = 0; // 以下詳細の出力
for( int p=1; p<= n; p++) {
if( p == i || p == j) sum -= p;
else sum += p;
ps( "%s %d sum:%d", (p==i||p==j)?"*":" ", p, sum);
if( (sum+180)%360 == 0) ps( " 180 OK"); // sum%180にしてしまうと360度の場合も含まれてしまうので
if( sum%360 == 0) ps( " 360 OK");
ps( "\n");
}
return 0; // 答えが見つかったので終了
}
}
}
}
}
pe( "答えが見つからない\n");
return 0;
}