問題一覧 > 通常問題

No.1341 真ん中を入れ替えて門松列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : nmnmnmnmnmnmnm / テスター : 37zigen
3 ProblemId : 3651 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-12-24 23:22:45

問題文

門松列とは3つの整数が左からABCと並んでいる時に、
全ての値が異なりABCのうち2番目に大きな整数がACである場合をいう。

また、門松ポイントとは3つの整数が門松列であるとき、3つの整数のうちの最大値である。

3つの正の整数ABCが左からこの順番でN組与えられる。
任意の2つの組の間で真ん中の正の整数Bのみ入れ替える操作がN回まで可能である。
操作によってすべての組を門松列にできるか判定せよ。
できる場合にはすべての組の門松ポイントの総和をMポイント以上にできるかを判定せよ。

入力

N M
A1 B1 C1
A2 B2 C2
 
AN BN CN

Nは与えられる3つの正の整数ABCの組の数。1N3000
Mは問題文中の判定に用いるポイント数。0M3000000000000=3×1012
AiBiCiは与えられるi番目の組の正の整数ABCAiCi1Ai,Bi,Ci1000000000=109

出力

すべて門松列にできない場合は、1行のみで"NO"と出力せよ。
すべて門松列にできる場合は1行目に"YES"と出力せよ。
すべて門松列にできる場合で、門松ポイントの総和をMポイント以上にできる場合は2行目に"KADOMATSU!"と出力せよ。
すべて門松列にできる場合で、門松ポイントの総和をMポイント以上にできない場合は2行目に"NO"と出力せよ。

サンプル

サンプル1
入力
2 5
2 3 4
1 1 2
出力
YES
KADOMATSU!

1番目の組の真ん中の数の3と2番目の組の真ん中の数の1を入れ替えます。
すると1回の入れ替えで2組とも門松列になるので"YES"を出力します。
1番目の組の門松ポイントは「2,1,4」の最大値なので4です。
2番目の組の門松ポイントは「1,3,2」の最大値なので3です。
よって、門松ポイントの総和は4+3=7ポイントです。
これは判定ポイントの5ポイント以上なので"KADOMATSU!"と出力します。

サンプル2
入力
3 20
7 5 5
2 8 1
4 3 5
出力
YES
KADOMATSU!

2回の操作でできます。

サンプル3
入力
1 100
2 1 3
出力
YES
NO

最初から門松列なので0回の操作ですべて門松列にすることは可能です。
しかし、門松ポイントの総和を判定ポイント以上にすることはできません。

サンプル4
入力
2 0
1 2 3
4 1 3
出力
NO

すべて門松列にすることができません。

サンプル5
入力
5 2021
5 10 1
3 3 16
7 8 8
11 1979 15
6 8 9
出力
YES
KADOMATSU!

2021年あけましておめでとうございます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。