2011年2月20日日曜日

Codeforces Beta Round #56

初参加してきました。CodeForces
。。。なんですが。

開始後
コンテストページどこ?
というところで詰まる。

お約束ですね。

では本題へ。今回は問題Aしか見ていないため、Aのみ書く。

問題A

ルームメイトが、主人公のシリアルを、N個の箱のいずれかに隠してしまった。
箱は左から順に0.1.2.3、、、という順番に並んでおり、シリアルの場所についてヒントが与えられる。
ヒントは"To the left of i"或いは"To the right of i"という文面。
要するに、「シリアルは i 番目より左の箱にある。」或いは「シリアルは i 番目より右の箱にある」というヒント。
このヒントを元に、シリアルが入っている可能性のある箱を絞り、最終的に幾つ残っているかを出力する。
ヒントは矛盾している場合があり、箱が残らない場合がある。その場合は-1を出力する。

解き方

Start, End で範囲を指定。その中に幾つの箱が存在しているのかを算出する。

コード

#include
#include
#include

using namespace std;

#define REP(X, Y) for(int i = X;i < Y;i++)
#define rep(X) REP(0, X)

void main(int argc, char* argv[]){
string str[4];
int number_of_box, number_of_hints, start, end;
int number;

while( cin >> number_of_box >> number_of_hints){
start = 0;
end = number_of_box + 1;
rep(number_of_hints){
cin >> str[0] >> str[1] >> str[2] >> str[3] >> number;
if(str[2] == "right"){
start = max(start, number);
}else{
end = min(end,number);

}
}
if( (end - start) < 2)
{
cout << -1 << endl;
}else{
cout << (end - start - 1) << endl;
}

}

}

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。