UCC Coding Competition '20 P2 - Optimal Skiing

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 64M

Problem type

You finally arrive at your dream ski resort after saving up cash for decades. As this vacation was so expensive, you want to spend the maximum amount of time skiing, which means minimizing time on ski lifts.

The mountain is served by many ski lifts. You have studied the map extensively and wrote down your options for taking lifts to the summit of the mountain. Some of these options might involve riding multiple ski lifts. You have also done research on the time it takes to ride each ski lift, in minutes.

Please find the fastest possible time, in minutes, to ascend from the base of the mountain to the summit using one of these ski lift routes.

Input Specification

The first line will consist of an integer N (1 \le N \le 100), the number of ski lift routes you can take to get up the mountain.

The next N lines will each describe one of the ski lift routes. The first number in each line will be an integer M_i (1 \le M_i \le 100), indicating that this route involves taking M_i different lifts. This will be followed by M_i integers, representing the travel time for each of the ski lifts. None of the travel times for each ski lift will exceed 2020.

Output Specification

Please output one integer, the time required for the shortest ski lift route, in minutes, to get you to the summit.

Sample Input

1 10
3 3 5 3
2 1 8

Sample Output


Explanation for Sample Output

The input describes 3 ways to get up the mountain. The first uses one lift that takes 10 minutes. The second uses three lifts, taking 3, 5 and 3 minutes, for a total trip of 11 minutes. The third uses two lifts, taking 1 and 8 minutes, for a total trip of 9 minutes. 9 minutes is the shortest option.


  • -17
    Narcariel  commented on May 19, 2020, 4:56 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.

    • 4
      Plasmatic  commented on May 19, 2020, 6:32 p.m.

      10000 does not work either, as the max lift time is 2020 \times 100 = 202000

    • 6
      Kevy3030  commented on May 19, 2020, 5:17 p.m. edit 2

      The travel time for each individual lift does not exceed 2020, but the total time for the entire route might. The problem statement has been updated for clarity.

      • -2
        Narcariel  commented on May 20, 2020, 3:16 p.m.

        Ok thanks.