630 . Panda Land 7: Casino Island

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description


There's a special island in Panda Land called Casino Island where all gambling activities are legalized. Here, a well known betting game called Tipu-Tipu is held every month.


Each gambler could place only one bet. Each bet should consists of m
distinct numbers from 1 to L

(m
is chosen by the gambler). Each month, the game owner will announce a sequence of L
distinct numbers (the `master') and each bet will be matched to this sequence for a prize. The prize will be given if and only if the bet match perfectly to the master's prefix. In other word, a bet of m
numbers, should match the first m
numbers of the master. And yes, a higher m

will gives you a higher prize but also a higher risk of not gaining anything.




For example:


The prizes for m
from 1 to L
respectively are: 10, 20, 30, 40, 50 and 60.


The master is: 1 2 3 4 5 6












1-st bet : 1 		m = 1
, match!, 		prize = 10

2-nd bet : 1 2 		m = 2
, match!, 		prize = 20

3-rd bet : 1 2 3 4 		m = 4

, match!,

prize = 40

4-th bet : 1 2 4 3 		m = 4
, not match, 		prize = 0

5-th bet : 3 1 		m = 2

, not match,

prize = 0


Total prize = 10 + 20 + 40 + 0 + 0 = 70.




Of course the owner of the game wants to minimize the total of prize. So he asked you to write a program to find a master sequence which gives the minimum possible total of prize. If there are several of them, find the one which comes first lexicographically.

Input Format


The first line of input contains an integer T
, the number of test cases to follow. Each case begins with two integers L
<!-- MATH
$(3 \le L \le 30)$
-->
(3 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">L WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">30)
and N

<!-- MATH
$(1 \le N \le 100000)$
-->
(1 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">N WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">100000)
. The next line contains L
numbers representing the prizes for <!-- MATH
$m = 1, 2, \ldots, L$
-->
m = 1, 2,..., L

respectively. Each prize will be between 1 and 100, inclusive. The next N
lines describe all the N
bets. Each bet is stated in a line, beginning with an integer m
<!-- MATH
$(1 \le m \le L)$
-->
(1 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">m WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/630.png"
ALT="$ \le$">L)

-- the length of the bet, and followed by m
distinct numbers describing the bet. Each number in the bet will be between 1 and L
, inclusive.

Output Format


For each case, print in a single line the master sequence which gives the minimum possible total prize. If there's more than one such sequence, output the one that comes first lexicographically. Each number in the sequence should be separated by a single space.

Sample Input 1



2 

4 3 

1 2 3 4 

2 1 2 

4 2 1 3 4

4 2 1 4 3

4 13 

1 2 3 4 

2 2 1 

4 1 2 3 4

4 1 2 4 3

2 1 3 

2 1 4 

2 2 3 

2 2 4 

2 3 1 

2 3 2 

2 3 4 

2 4 1 

2 4 2 

2 4 3



Sample Output 1



1 3 2 4 

1 3 2 4



Hints

Problem Source

Migrated from old NTUJ.

ACM ICPC regional Jakarta site 2008

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 2000
Submit
Back to Top