Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

何種類かパンがある.
各種類ごとに閾値があって,それより長く焼くと焦げ,それより短いと焼けない.
焼けなかったパン (50個以下) の焼いた時間と,焦げたパン (50個以下) の焼いた時間が与えられる.
どの種類のパンも,最低1枚は焼けず,最低1枚は焦げた.
最小で何種類のパンがあったかを求める問題.ありえないならそれを指摘する.
同じ時間だけ焼いたパンは存在しないとする.

解法

最小時間のパンが焦げてたら,それに対応する焼けないパンが存在しないからありえない.
同様に,最大時間のパンが焼けてなかっても,ありえない.
後は,任意の焼けなかったパンの時間が,任意の焦げたパンの時間より短ければ1種類で可能.
そうでなければ,
 最小時間のパン と 最大時間以外のすべての焦げたパン
 最大時間のパン と 最小時間以外のすべての焼けなかったパン
を対応させれば2種類で可能.

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

class ToastXToast {
public:
int bake(vector <int> a, vector <int> b) {
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  if(a[a.size()-1] < b[0]) return 1;

  if(a[0] > b[0]) return -1;
  if(a[a.size()-1] > b[b.size()-1]) return -1;

  return 2;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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