No.2684 Colors of the Seasons
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}$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Ayuna
tute7627
SPD_9X2
だれ
arad
kyawa