問題一覧 > 通常問題

No.1780 [Cherry Anniversary] 26 Cherry Trees Blooming in Midwinter

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 37
作問者 : 👑 Kazun / テスター : eSeF
お気に入りにしたユーザー ProblemId : 7271 / 自分の提出
問題文最終更新日: 2022-06-30 23:05:43
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
Advent Calendar Contest 2021 (順位表) の他の問題:

This problem is the Day 9 problem (Problem I) of Advent Calendar Contest 2021.

This problem was created based on information as of December 9, 2021. The information has since been updated, so it may no longer match (the input of the sample cases).

Problem Statement

There are 26 cherry trees, named cherry tree A, cherry tree B, $\cdots$, cherry tree Z.

Initially, cherry tree $\alpha$ is blooming with flowers of color $C_\alpha$.

An investigation of these 26 cherry trees has revealed that they have the following $N$ properties.

  • The $i$-th ability is called $S_i$. A cherry tree $\alpha$ can perform the action if and only if $\alpha$ is contained in the string $S_i$.
    • If cherry tree $\alpha$ is blooming with flowers of color $A_i$ at that moment, it gains energy $E_i$ and changes its flower color to $B_i$.
    • If cherry tree $\alpha$ is blooming with flowers of color $B_i$ at that moment, it gains energy $E_i$ and changes its flower color to $A_i$.
Note that the energy gained may be negative.

Cherry tree $\alpha$ can use the abilities available to it up to $K_\alpha$ times in total (the same ability may be used multiple times, and some abilities may not be used even 1 time).

Is it possible for the flowers blooming on the 26 cherry trees to all be the same color? If it is possible, find the maximum total energy gained among the ways of using abilities such that the flowers blooming on the 26 cherry trees are all the same color.

Constraints

  • $1 \leq C_\alpha \leq 16$
  • $0 \leq K_\alpha \leq 10^7$
  • $0 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i, B_i \leq 16$
  • $A_i \neq B_i$
  • $-10^7 \leq E_i \leq 10^7$
  • $S_i$ is a string consisting of uppercase English letters
  • $|S_i| \leq 30$
  • All numbers in the input are integers

Input

$C_{{\rm {A}}}$ $C_{{\rm {B}}}$ $C_{{\rm {C}}}$ $C_{{\rm {D}}}$ $C_{{\rm {E}}}$ $C_{{\rm {F}}}$ $C_{{\rm {G}}}$ $C_{{\rm {H}}}$ $C_{{\rm {I}}}$ $C_{{\rm {J}}}$ $C_{{\rm {K}}}$ $C_{{\rm {L}}}$ $C_{{\rm {M}}}$ $C_{{\rm {N}}}$ $C_{{\rm {O}}}$ $C_{{\rm {P}}}$ $C_{{\rm {Q}}}$ $C_{{\rm {R}}}$ $C_{{\rm {S}}}$ $C_{{\rm {T}}}$ $C_{{\rm {U}}}$ $C_{{\rm {V}}}$ $C_{{\rm {W}}}$ $C_{{\rm {X}}}$ $C_{{\rm {Y}}}$ $C_{{\rm {Z}}}$
$K_{{\rm {A}}}$ $K_{{\rm {B}}}$ $K_{{\rm {C}}}$ $K_{{\rm {D}}}$ $K_{{\rm {E}}}$ $K_{{\rm {F}}}$ $K_{{\rm {G}}}$ $K_{{\rm {H}}}$ $K_{{\rm {I}}}$ $K_{{\rm {J}}}$ $K_{{\rm {K}}}$ $K_{{\rm {L}}}$ $K_{{\rm {M}}}$ $K_{{\rm {N}}}$ $K_{{\rm {O}}}$ $K_{{\rm {P}}}$ $K_{{\rm {Q}}}$ $K_{{\rm {R}}}$ $K_{{\rm {S}}}$ $K_{{\rm {T}}}$ $K_{{\rm {U}}}$ $K_{{\rm {V}}}$ $K_{{\rm {W}}}$ $K_{{\rm {X}}}$ $K_{{\rm {Y}}}$ $K_{{\rm {Z}}}$
$N$
$S_1$ $A_1$ $B_1$ $E_1$
$\vdots$
$S_N$ $A_N$ $B_N$ $E_N$
(Note): The subscript "N" in $C_{{\rm {N}}}, K_{{\rm {N}}}$ and the one in $S_N$ represent different things ($C_{{\rm {N}}}, K_{{\rm {N}}}$ refer to the cherry tree named N, while $S_N$ refers to the number of abilities $N$ given on line 3).

Output

If it is impossible for the flowers blooming on the 26 cherry trees to all be the same color, output Impossible; if it is possible, find the maximum total energy gained.

Sample

Sample 1
Input
1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4
ABE 1 2 -1
ABC 2 3 -1
ABD 1 3 -10
CD 2 3 100
Output
88

By using the abilities as follows, the flowers blooming on all cherry trees can be made color $3$. Here, using the ability called $S$ to change the flower color from $A$ to $B$ is denoted by $A \xrightarrow{[S]} B$.

  • Cherry tree A: $1 \xrightarrow{[{\rm ABD}]} 3$
  • Cherry tree B: $1 \xrightarrow{[{\rm ABE}]} 2 \xrightarrow{[{\rm ABC}]} 3$
  • Cherry tree C: $2 \xrightarrow{[{\rm CD}]} 3$
  • Cherry tree D, $\dots$, cherry tree Z: do nothing
In this case, the energy gained is $\underbrace{(-10)}_{{\rm A}}+\underbrace{(-1-1)}_{{\rm B}}+\underbrace{(100)}_{{\rm C}}+\underbrace{(0)}_{{\rm D}}+\dots+\underbrace{(0)}_{{\rm Z}}=88$. Moreover, among the ways of making the flowers blooming on all cherry trees the same color, the energy gained cannot be made greater than $88$. Therefore, $88$ is the answer.

Note that the following ways of using energy are not possible.

  • $\times$ Cherry tree A first uses $[{\rm ABC}]$ $\cdots$ This cannot be used, since cherry tree A is initially neither color $2$ nor color $3$.
  • $\times$ Cherry tree D uses $[{\rm ABE}]$ $\cdots$ This cannot be used, since ABE does not contain D.
  • $\times$ Cherry tree A uses abilities as $1 \xrightarrow{[{\rm ABE}]} 2 \xrightarrow{[{\rm ABC}]} 3$ $\cdots$ Since $K_{{\rm A}}=1$, abilities cannot be used $2$ times.

Sample 2
Input
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0
Output
Impossible

The colors of the flowers blooming on the 26 cherry trees do not all match, yet no abilities can be used, so the colors of the blooming flowers cannot be made the same.

Sample 3
Input
2 1 1 4 4 4 2 1 5 6 1 15 7 9 4 2 1 13 13 1 9 3 11 16 2 1
24 24 23 22 23 26 24 21 24 26 23 20 22 21 22 18 23 19 23 20 19 22 23 20 21 16
37
FAULT 1 2 -10
FALLINLOVE 2 3 -3
DOUBT 3 4 -8
PLASTIC 4 5 100
SUBWAY 5 6 -85
BUDDY 6 7 12
BLUEMOON 7 8 0
BAN 8 9 -1
ANSWER 9 10 77
LOVE 10 11 4
LAUNDRY 11 12 5
MICROSCOPE 12 13 74
NOTLONELY 13 14 -4
ANTHEM 14 15 6
STRAYBULLET 1 15 9
DEADEND 4 6 46
SONIA 3 7 35
JAMAICA 8 10 -3
ONWAY 4 13 -4
SILENT 5 10 -4
NERVOUS 9 11 1
ABCDEFGHIJKLMNOPQRSTUVWXYZ 1 2 4
ABCDEFGHIJKLMNOPQRSTUVWXYZ 2 3 7
ABCDEFGHIJKLMNOPQRSTUVWXYZ 3 4 -4
ABCDEFGHIJKLMNOPQRSTUVWXYZ 4 5 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ 5 6 10
ABCDEFGHIJKLMNOPQRSTUVWXYZ 6 7 53
ABCDEFGHIJKLMNOPQRSTUVWXYZ 7 8 31
ABCDEFGHIJKLMNOPQRSTUVWXYZ 8 9 10
ABCDEFGHIJKLMNOPQRSTUVWXYZ 9 10 -46
ABCDEFGHIJKLMNOPQRSTUVWXYZ 10 11 46
ABCDEFGHIJKLMNOPQRSTUVWXYZ 11 12 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ 12 13 13
ABCDEFGHIJKLMNOPQRSTUVWXYZ 13 14 64
ABCDEFGHIJKLMNOPQRSTUVWXYZ 14 15 19
ABCDEFGHIJKLMNOPQRSTUVWXYZ 15 16 0
ABCDEFGHIJKLMNOPQRSTUVWXYZ 16 1 31
Output
35282
Sample 4
Input
2 4 2 15 4 11 6 1 5 6 15 15 7 11 6 12 14 15 13 11 9 4 13 16 4 3
104 1007 1114 1023 215 1129 707 507 1112 516 727 129 417 418 1012 1219 629 323 1021 829 112 1013 505 710 102 928
26
A 2 10 1
B 4 10 1
C 2 10 1
D 15 10 1
E 4 10 1
F 11 10 1
G 6 10 1
H 1 10 1
I 5 10 1
J 6 10 1
K 15 10 1
L 15 10 1
M 7 10 1
N 11 10 1
O 6 10 1
P 12 10 1
Q 14 10 1
R 15 10 1
S 13 10 1
T 11 10 1
U 9 10 1
V 4 10 1
W 13 10 1
X 16 10 1
Y 4 10 1
Z 3 10 1
Output
17518

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