CF Round #656 A - Three Pairwise Maximums


Tags:cpcodeforcesdiv3math

問題

https://codeforces.com/contest/1385/problem/A

問題文

正の整数 x,y,zx,y,z に対して、 x=max(a,b),y=max(a,c),z=max(b,c)x = \max(a, b), y = \max(a, c), z = \max(b, c) となるような a,b,ca,b,c は存在する?

制約

  • 1t2×1041 \le t \le 2 \times 10^4
  • 1x,y,z1091 \le x,y,z \le 10^9

サンプル

5
3 2 3
100 100 100
50 49 49
10 30 20
1 1000000000 1000000000
YES
3 2 1
YES
100 100 100
NO
NO
YES
1 1 1000000000

考察

実験

全 6 パターンを考えてみる。まあ順番は適当に入れ替えてるんですけど

  1. bcax=a,y=a,z=cb \le c \le a \Rightarrow x = a, y = a, z = c
  2. cbax=a,y=a,z=bc \le b \le a \Rightarrow x = a, y = a, z = b
  3. acbx=b,y=c,z=ba \le c \le b \Rightarrow x = b, y = c, z = b
  4. cabx=b,y=a,z=bc \le a \le b \Rightarrow x = b, y = a, z = b
  5. abcx=b,y=c,z=ca \le b \le c \Rightarrow x = b, y = c, z = c
  6. bacx=a,y=c,z=cb \le a \le c \Rightarrow x = a, y = c, z = c

こうしてみると、以下の関係が成り立ってそう。定義を見れば明らかだけど

  • max=ax=y>z\max = a \Rightarrow x = y > z
  • max=bx=z>y\max = b \Rightarrow x = z > y
  • max=cy=z>x\max = c \Rightarrow y = z > x

解作成

max=ax=y>z\max = a \Rightarrow x = y > z について考えてみる。
こうしたとき、 aa は決まるけど、 b,cb, c はどうする?

z=max(b,c)z = \max(b, c) で、「条件を満たすものなら何を出力してもいいよ」なので、 b=c=zb = c = z にしちゃえばいい。

他も同様。

コード

https://codeforces.com/contest/1385/submission/126229275

void solve() {
  int x, y, z;
  cin >> x >> y >> z;
  if (x == y && y == z) {
    cout << "YES" << endl;
    cout << x << " " << y << " " << z << endl;
  }
  else if (x == y && x > z) {
    cout << "YES" << endl;
    cout << x << " " << z << " " << z << endl;
  }
  else if (y == z && z > x) {
    cout << "YES" << endl;
    cout << x << " " << x << " " << y << endl;
  }
  else if (z == x && x > y) {
    cout << "YES" << endl;
    cout << y << " " << x << " " << y << endl;
  }
  else {
    cout << "NO" << endl;
  }
}