Q3: Interplanetary Spaceflight Milan Tusk is the richest person in the universe. After devoting decades of his life to further our space exploration technologies, he’s finally ready to retire. Being a space enthusiast, the first thing he wants to do is visit n planets p1, p2, …, pn, in this order. He’s currently on planet p0. Milan knows that the distance between planets pi and pi + 1 (for 0 ≤ i < n) is d[i]light years. His spaceship uses 1 tonne of fossil fuels per light year. He starts with a full tank and can fill up his tank at any of the n planets (but he must not run out in between two planets). There’s a huge cost to set up the spaceship for refuelling. Due to financial constraints (he’s not THAT rich), he can fill up his tank at most ktimes. In order to save money and make his spaceship lighter, Milan is looking for the smallest possible fuel tank that enables him to complete his space travel and reach planet pn. What is the smallest tank capacity that enables him to do so? Filename Your filename for this question must be q3.py. Input The input consists of two lines: The first line contains n integers separated by single spaces. These numbers specify the list d. The second line contains a single integer, k. Output Output a single integer: the minimum possible fuel tank capacity (in tonnes) for Milan’s spaceship. Constraints 1 ≤ n ≤ 100 0 ≤ k ≤ 100 1 ≤ d[i] ≤ 100 Time Limit Your program has to finish running within 1 second on any valid input. Sample Input 1 2 1 1 3 Sample Output 1 2 Sample 1 Explanation The capacity should be at least 2; Otherwise, Milan can’t travel from p0 to p1. If the capacity is 2, Milan can simply fill up his tank once on p1. Note that right before he fills up there, his tank is empty, but that’s fine because he’s already on p1. Sample Input 2 1 1 1 1 1 1 1 2 Sample Output 2 3 Sample Input 3 5 5 5 5 4 Sample Output 3 5 USE PYTHON

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Q3: Interplanetary Spaceflight

Milan Tusk is the richest person in the universe. After devoting decades of his life to further our space exploration technologies, he’s finally ready to retire. Being a space enthusiast, the first thing he wants to do is visit n planets p₁, p₂, …, p_n, in this order. He’s currently on planet p₀.

Milan knows that the distance between planets p_i and p_i + 1 (for 0 ≤ i < n) is d[i]light years. His spaceship uses 1 tonne of fossil fuels per light year. He starts with a full tank and can fill up his tank at any of the n planets (but he must not run out in between two planets). There’s a huge cost to set up the spaceship for refuelling. Due to financial constraints (he’s not THAT rich), he can fill up his tank at most ktimes.

In order to save money and make his spaceship lighter, Milan is looking for the smallest possible fuel tank that enables him to complete his space travel and reach planet p_n. What is the smallest tank capacity that enables him to do so?

Filename

Your filename for this question must be q3.py.

Input

The input consists of two lines:

The first line contains n integers separated by single spaces. These numbers specify the list d.
The second line contains a single integer, k.

Output

Output a single integer: the minimum possible fuel tank capacity (in tonnes) for Milan’s spaceship.

Constraints

1 ≤ n ≤ 100
0 ≤ k ≤ 100
1 ≤ d[i] ≤ 100

Time Limit

Your program has to finish running within 1 second on any valid input.

Sample Input 1

2 1 1 3

Sample Output 1

Sample 1 Explanation

The capacity should be at least 2; Otherwise, Milan can’t travel from p₀ to p₁.
If the capacity is 2, Milan can simply fill up his tank once on p₁. Note that right before he fills up there, his tank is empty, but that’s fine because he’s already on p₁.

Sample Input 2

1 1 1 1 1 1 1 2

Sample Output 2

Sample Input 3

5 5 5 5 4

Sample Output 3

USE PYTHON

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions