Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM526.5 DIV1 EASY/DIV2 MEDIUM - MagicCandy (この記事を編集する[管理者用])

Source

TopCoder SRM526.5 DIV1 EASY (250pt)
TopCoder SRM526.5 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

最初,1~Nまでの整数が順番に書いてある.(Nは1000000000以下)
以下の操作を繰り返すとき,一番最後に削除される整数を求める問題.
 平方数番目を同時に消す.つまり,1番目,4番目,9番目,…,を消す.
 消されて空白になった場所を詰める.

解法

色々解法はある.
以下のコードの方法は,
 N - 一番最後が削除される回数
が答えで,一番最後が消されるかどうかだけチェックしながらシミュレーションした.
証明は可能だけど自明じゃない.
他には,答えには規則性があるので,Nが小さい時に愚直にシミュレーションして規則を探す,とか,
時間的に最後の削除から順番にgreedyにシミュレーションする方法などがある.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

class MagicCandy {
public:
int whichOne(int n) {
  int i,j,k;
  int res = n;

  while(n > 1){
    k = (int)sqrt(n)-1;
    while(k<=0) k++;
    while((k+1)*(k+1) <= n) k++;

    if(k*k==n) res--;
    n -= k;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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