Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1823-cf71007e
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #51 A問題 - Flea travel (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 A問題
Problem description
Beta Round #51の自分の参加記録

問題概要

n個 (1000以下) のセルが円周上に並んでいる.
あるセルから,1個右に移動,次はそこから2個右に移動,次はそこから3個右に移動,…
と無限に移動したとき,最終的に全てのセルに到達するかどうかを調べる問題.

解法

適当にループを回してシミュレーションすれば良い.
2n回移動すると,初期値に戻り,ジャンプの幅もmod nで最初に等しくなるので2n回ループを回せば十分.
解析的に考えると,nが2のべき乗であるときのみYESが答えになる.
nは10^9以下のバージョンはPKU 3372 (http://poj.org/problem?id=3372) にある.
以下のコードは,場所とジャンプ幅を状態として同じ状態になるまでループを回すプログラム.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int reach[1010][1010];

int main(){
  int i,j,k,l,m,n,now,s;

  while(scanf("%d",&n)==1){
    rep(i,n) rep(j,n) reach[i][j] = 0;
    now=0; s=1;

    while(!reach[now][s]){
      reach[now][s]=1;
      now = (now+s)%n;
      s = (s+1)%n;
    }

    rep(i,n){
      rep(j,n) if(reach[i][j]) break;
      if(j==n) break;
    }

    if(i<n) puts("NO"); else puts("YES");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1823-cf71007e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。