MWC '15 #3 P2: Mechanical Pencils

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

lim495062 has recently become obsessed with mechanical pencils. He has N (1 \le N \le 1\,000\,000) mechanical pencils (numbered 1 to N) and M (1 \le M \le 1000) packs of graphite lead (numbered 1 to 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 (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 (1 \le L \le 100) and the lead may have different lengths S (1 \le S \le 100).

Now lim495062 wants to know which pencil and lead pack combination give him the longest 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 and M, the number of mechanical pencils and the number of lead packs respectively.

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

The next M lines initiate with integer L_m denoting the number of lead this pack has, followed by L_m integers denoting the size, S_{l_m}, of the 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

2 2
4 1 2 2 1
1 4

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.


  • 0
    fed80  commented on April 4, 2016, 2: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, 10:42 a.m.
    2 2
    2 20 10
    1 1

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

      The output should be 2 2

  • 1
    kushanzaveri  commented on April 4, 2016, 8:07 a.m.


    • 2
      atarw  commented on April 4, 2016, 4:43 p.m.