問題一覧 > 通常問題

No.2684 折々の色

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : AyunaAyuna / テスター : 👑 tute7627tute7627 👑 SPD_9X2SPD_9X2 👑 rin204rin204 だれだれ aradarad kyawakyawa ma_twma_tw kjqwkjqw kosuke-norikosuke-nori
0 ProblemId : 10406 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-19 23:15:50

問題文

この世界の生命体は視細胞を $M$ 個持っているため、色を $M$ 個の値 $(C_1, C_2, \dots C_M)$ で表現します。
この世界の生命体であるあなたは、$N$枚の色とりどりなカードのうち異なる2枚を重ね合わせて色 $(X_1, X_2, \dots X_M)$ をつくろうとしています。
カード $i$ の色は $(C_{i,1}, C_{i,2}, \dots C_{i,M})$ で、不透明度は $T_i$ %です。
2枚のカード $i,$ $j$ を、カード $i$ が上になるように重ねたときの色 $(Y_1, Y_2, \ldots, Y_M)$ は次の式で求められます。

  • $Y_1=\frac{T_i}{100}C_{i,1}+(1-\frac{T_i}{100})\frac{T_j}{100}C_{j,1}$
  • $Y_2=\frac{T_i}{100}C_{i,2}+(1-\frac{T_i}{100})\frac{T_j}{100}C_{j,2}$
  • $\vdots$
  • $Y_M=\frac{T_i}{100}C_{i,M}+(1-\frac{T_i}{100})\frac{T_j}{100}C_{j,M}$
ある2つの色 $(Y_1, Y_2, \ldots, Y_M)$ と $(Y_1', Y_2'\ldots, Y_M')$ について各要素がすべて等しいとき、またこのときに限り2つの色は同じであるといいます。 $N$ 枚のカードのうち異なる2枚のカードを選び適切に重ね合わせることで求めている色と同じ色 $(X_1, X_2, \dots X_M)$ をつくれるかどうか教えてください。

入力

$N\ M$
$X_1$ $X_2$ $\dots$ $X_M$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,M}$ $T_1$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,M}$ $T_2$
$\dots$
$C_{N,1}$ $C_{N,2}$ $\dots$ $C_{N,M}$ $T_N$

  • $2 \le N \le 2 \times 10^5$
  • $1 \le M \le 10$
  • $0 \le X_i \lt 2^{16}(1 \le i \le M)$
  • $0 \le C_{j, i} \lt 2^{16}(1 \le i \le M, 1 \le j \le N)$
  • $0 \lt T_i \le 100(1 \le i \le N)$
  • $i \neq j $であれば$(C_{i,1}, C_{i,2}, \dots C_{i,M}) \neq (C_{j,1}, C_{j,2}, \dots C_{j,M})$
  • 入力はすべて整数

出力

2枚のカード$i,$ $j$を重ねたときに求めている色をつくれる場合、Yes と出力してください。 どのように2枚のカードを重ね合わせても求めている色をつくれない場合はNo と出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 3
100 120 140
80 100 160 75
320 360 160 50
0 5 10 30
出力
Yes

カード1とカード2を、カード1が上となるように重ね合わせたとき、求めていた色をつくることができます。

サンプル2
入力
2 4
0 0 0 0
0 10 20 30 40
50 60 70 80 90
出力
No

どのようにカードを重ね合わせても求めている色はつくれません。

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