MWC '15 #3 P2: Mechanical Pencils

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

aurpine

Problem type

lim495062 has recently become obsessed with mechanical pencils. He has $N$ ~N~ $(1 \le N \le 1\,000\,000)$ ~(1 \le N \le 1\,000\,000)~ mechanical pencils (numbered $1$ ~1~ to $N$ ~N~) and $M$ ~M~ $(1 \le M \le 1000)$ ~(1 \le M \le 1000)~ packs of graphite lead (numbered $1$ ~1~ to $M$ ~M~).

As you may know, a whole piece of lead can never be used up completely. It can be used up to a certain length, until the mechanical pencil loses grip of the lead, at which point the lead then must be discarded. The maximum length at which the lead may not be used by the mechanical pencil is $K$ ~K~ $(0 \le K \le 100)$ ~(0 \le K \le 100)~ and may vary from pencil to pencil.

lim495062 purchased his lead packs from very questionable sources. As a result, there may be different amounts of lead $L$ ~L~ ( $1 \le L \le 100$ ~1 \le L \le 100~) and the lead may have different lengths $S$ ~S~ $(1 \le S \le 100)$ ~(1 \le S \le 100)~.

Now lim495062 wants to know which pencil and lead pack pair permits the maximum writing time. Total usable lead positively correlates with writing time, meaning the more usable lead he has, the longer he can write for.

Input Specification

The first line contains two space separated integers $N$ ~N~ and $M$ ~M~, the number of mechanical pencils and the number of lead packs respectively.

The next $N$ ~N~ lines contain integers $K_n$ ~K_n~, the $K$ ~K~ value of pencil $n$ ~n~.

The next $M$ ~M~ lines initiate with integer $L_m$ ~L_m~ denoting the number of lead this pack has, followed by $L_m$ ~L_m~ integers denoting the size, $S_{l_m}$ ~S_{l_m}~, of the $l^\text{th}$ ~l^\text{th}~ piece of lead.

Output Specification

Two space separated integers, the pencil and lead pack pair that permits the maximum writing time.

If two pencils are tied, then take the one theoretically better pencil, meaning the one that would allow more lead use on average if used on all possible sets of lead packs. If still tied, take the first one (the one with the lower index). If two lead packs are tied, then take the one with fewer pieces of lead. If they have the same amount of lead, take the first one.

Sample Input

Sample Output

1 2

Explanation of Sample Output

It is optimal to use pencil 1 with lead pack 2 for a maximum lead use of 2. All other combinations permit 0 lead use.

Comments

0

maxcruickshanks commented on Dec. 5, 2024, 5:44 p.m. ← edited →

Since the original data were weak, an additional test case worth 10 marks was added, and all submissions were rejudged. Data were provided by grammer.

0

fed80 commented on April 4, 2016, 6:38 p.m.

Can we have a proper input/output specification, with an explanation, because currently it leaves a lot up to question.

1
d commented on April 4, 2016, 2:42 p.m.
2 2 40 30 2 20 10 1 1

0

atarw commented on April 4, 2016, 8:35 p.m.

The output should be 2 2