Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM481 DIV1 EASY/DIV2 MEDIUM - ChickenOracle (この記事を編集する[管理者用])

Source

TopCoder SRM481 DIV1 EASY (250pt)
TopCoder SRM481 DIV2 MEDIUM (500pt)
Problem Statement
SRM481 DIV1 自分の参加記録

問題概要

神様しか答えの知らない2択問題がある.答えはAかB.
n人の人が神様に答えを聞いた.
そのn人の人から神様から聞いた答えを聞いた.その結果が与えられる.
神様が嘘を付いた人数と,n人の人が嘘を言った人数が与えられる.
答えはAかBか判断できないか,両方矛盾してるかを求める問題.
nは100万以下.

解法

神様から本当の話を聞いたけど,嘘を付いている人数でループして,それぞれ達成できるパターンがあるかどうか判定する.
解析的に解くと,O(1)で解けるが,偶奇性や正値性などを忘れてハマる可能性がある.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

class ChickenOracle {
public:
string theTruth(int n, int egg, int A, int B) {
  int i,j,k;
  int X, Y, ok1, ok2;
  string res;

  X = n-A; Y = A;
  ok1 = ok2 = 0;

  REP(i,0,B+1){
    j = X - i + (B-i);
    k = Y + i - (B-i);
    if(X < i) continue;
    if(Y < B-i) continue;
    if(j==egg) ok1=1;
    if(k==egg) ok2=1;
  }

  if( ok1 &&  ok2) res = "Ambiguous";
  if( ok1 && !ok2) res = "The egg";
  if(!ok1 &&  ok2) res = "The chicken";
  if(!ok1 && !ok2) res = "The oracle is a lie";

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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