問題一覧 > 通常問題

No.2684 Colors of the Seasons

レベル : / AI推定難易度 : 1125 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 75
作問者 : Ayuna / テスター : 👑 tute7627 SPD_9X2 👑 rin204 だれ arad kyawa ma_tw kjqw kosuke-nori
お気に入りにしたユーザー ProblemId : 10406 / 自分の提出
問題文最終更新日: 2024-03-19 23:15:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 422 (第1回 競技プログラミング講習会作問企画コンテスト) (順位表) の他の問題:

Problem Statement

Life forms in this world have $M$ photoreceptor cells, so a color is represented by $M$ values $(C_1, C_2, \dots C_M)$.
You, a life form of this world, are trying to create the color $(X_1, X_2, \dots X_M)$ by overlaying 2 distinct cards out of $N$ colorful cards.
Card $i$ has color $(C_{i,1}, C_{i,2}, \dots C_{i,M})$ and opacity $T_i$ %.
When 2 cards $i,$ $j$ are overlaid so that card $i$ is on top, the resulting color $(Y_1, Y_2, \ldots, Y_M)$ is given by the following formulas.

  • $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}$
Two colors $(Y_1, Y_2, \ldots, Y_M)$ and $(Y_1', Y_2'\ldots, Y_M')$ are said to be the same if and only if all of their corresponding elements are equal. Determine whether you can create a color identical to the desired color $(X_1, X_2, \dots X_M)$ by choosing 2 distinct cards out of the $N$ cards and overlaying them appropriately.

Input

$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)$
  • If $i \neq j $, then $(C_{i,1}, C_{i,2}, \dots C_{i,M}) \neq (C_{j,1}, C_{j,2}, \dots C_{j,M})$
  • All inputs are integers

Output

If the desired color can be created by overlaying 2 cards $i,$ $j$, print Yes. If the desired color cannot be created no matter how 2 cards are overlaid, print No. Print a newline at the end.

Sample

Sample 1
Input
3 3
100 120 140
80 100 160 75
320 360 160 50
0 5 10 30
Output
Yes

Overlaying card 1 and card 2 so that card 1 is on top creates the desired color.

Sample 2
Input
2 4
0 0 0 0
0 10 20 30 40
50 60 70 80 90
Output
No

The desired color cannot be created no matter how the cards are overlaid.

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