朝日新聞2005年7月22日のパズル横丁問題

問題

3本の街灯A,B,Cがある。

Aは3秒消灯,4秒点灯,Bは3秒消灯,6秒点灯,Cは3秒消灯,8秒点灯。

A,B,Cの3本とも22時ちょうどからの3秒間消えていたのが,再び3本とも消えるのはいつか?

解答への道(ヒント)

単に最小公倍数を求める問題なのであまりにも簡単。

とはいえプログラムを作って解答を求めるのが目標だし,プログラムも難しくはないので,プログラムを作成することにする。

1000秒分ほど配列を用意し,0で消灯,1で点灯を示す。最初にA,B,Cを条件を満たすように初期化して,後で同時に3秒間消灯になる場合を求める。

プログラムは以下のようになる。

  char          a[1000+100], b[1000+100], c[1000+100];
  int           p, i;
  for( p=0; p< 1000; ) {
    for( i=0; i< 3; i++) a[p++] = 0; // 3秒消灯
    for( i=0; i< 4; i++) a[p++] = 1; // 4秒点灯
  }
  for( p=0; p< 1000; ) {
    for( i=0; i< 3; i++) b[p++] = 0; // 3秒消灯
    for( i=0; i< 6; i++) b[p++] = 1; // 6秒点灯
  }
  for( p=0; p< 1000; ) {
    for( i=0; i< 3; i++) c[p++] = 0; // 3秒消灯
    for( i=0; i< 8; i++) c[p++] = 1; // 8秒点灯
  }
  for( p=3; p< 1000; p++) {     // 最初A,B,Cの3つとも消灯だったので3秒後から探す
    if( a[p+0] == 0 && b[p+0] == 0 && c[p+0] == 0 && // 同時に3秒消灯になるか?
        a[p+1] == 0 && b[p+1] == 0 && c[p+1] == 0 &&
        a[p+2] == 0 && b[p+2] == 0 && c[p+2] == 0 ) {
      // p秒後にA,B,Cが同時に3秒間消灯する
    }
  }

厳密に言うと最後のループには詰めの甘さが残る。気になる人は注意深い人でプログラマ向きかも知れない。

何故22時?と思ったけど,今日は22日だからか?

Win32APIのWaitForMultipleObjects()が64個のハンドルまでしか待てないのを昨日初めて知った。スレッドを100個生成して終了を待とうとしたら,いつもエラーが返ってきて延々悩んでしまった。

解速度