SRM 503 Div1 easy ToastXToast

topcoder

問題概要

生焼けしたパンの数と焦げたパンの数、
それぞれ、どれだけ焼いたかの時間が与えられる。
最低何種類のパンが存在したと考えられるか。
ただし、同じ種類のパンは同じ時間を境に生焼けになったり、こげすぎたりする。
また、その境を絞り込めないようなパンが存在する場合、-1を返す

解法

答えは、2, 1, -1しかない。

  • A = 生焼けで一番焼かなかったものの時間
  • B = 生焼けで一番焼いたものの時間
  • C = 焦げたもので一番焼かなかったものの時間
  • D = こげたもので一番焼いたものの時間

とする。
そうすると、

  • -1 (C < A || D < B)
  • 1 (B < C)
  • 2 (A < C && B < D)
2の場合

焦げたパンのうち、一番焼いたものと、生焼けのパンのうち、一番焼かなかったもの以外を
一種類のパンと考える。
つまり、Dと、Bの間に、その種類の境の時間があると考える。
同様に、生焼けのパンのうち、一番焼かなかったものと、焦げたパンのうち一番焼いたもの以外を
一種類のパンと考える。
つまり、AとCの間にその種類の境があると考える。

1の場合

すべてのパンを同じ種類と考える。
つまり、B とCの間に境があったと考える。

-1の場合

焦げたパンで一番焼かなかったもののパンの種類の境が絞り込めないか、
または、
生焼けのパンで一番焼いたもののパンの種類の境が絞り込めないため
解なし。

ソース

#include<algorithm>
#include<vector>
#define ALL(C)     (C).begin(),(C).end()
using namespace std;

class ToastXToast {
public:
  int bake(vector <int> U, vector <int> O) {
    sort(ALL(U));
    sort(ALL(O));
    if(U.back() < O.front()){
      return 1;
    }
    if(U.front() < O.front() && U.back() < O.back()){
      return 2;
    }
    else return -1;
  }
};