UTS Open '24 P1 - Watering the Plants

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

The year is 2060. Marcus has retired from computer science and has become a gardener. In his garden, he is growing N flowers along a number line, where the i^{th} flower is at position i (1 \le i \le N). Each flower needs 1 unit of water to survive the next day.

He also has a watering can that can hold up to K units of water, and it can be refilled by the hose at position 0. As Marcus walks along his garden, he will only be able to water the flowers that are at the same position as him.

Marcus begins at position 0 with an empty watering can. Since he is very lazy, he would like to know the minimum distance he must walk to water all of his plants, and return to position 0. Can you help him?

Constraints

For all subtasks,

1 \le N,K \le 10^5

Subtask 1 [50%]

K = 1

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line of input contains one integer, N, the number of flowers in Marcus' garden.

The second line of input contains one integer, K, the maximum capacity of his watering can.

Output Specification

Output one line containing one integer, the minimum distance Marcus has to walk to water all his plants and return to position 0.

Note that this value may not fit within a 32-bit integer type.

Sample Input 1

4
2

Sample Output 1

12

Explanation for Sample 1

One possible solution is as follows:

  • Marcus is at position 0 and fills his watering can. It now holds 2 units of water.
  • Marcus walks 1 unit right to flower 1, and waters it. His watering can now holds 1 unit of water.
  • Marcus walks 1 more unit right to flower 2, and waters it. His watering can is now empty.
  • Marcus walks 2 units left back to position 0 and refills his watering can. It now holds 2 units of water.
  • Marcus walks 3 units right to flower 3, and waters it. His watering can now holds 1 unit of water.
  • Marcus walks 1 more unit right to flower 4, and waters it. His watering can is now empty.
  • Marcus walks 4 units left to return to position 0.

Marcus walks a total of 1 + 1 + 2 + 3 + 1 + 4 = 12 units. It can be proven that this is minimal.

Sample Input 2

5
7

Sample Output 2

10

Explanation for Sample 2

Marcus' watering can holds more than enough water for all of the flowers in one trip! Thus, Marcus can simply fill his watering can once, walk right 5 units and water the flowers along the way, and finally walk 5 units left to return to position 0. He walks a total of 5 + 5 = 10 units, which is minimal.


Comments

There are no comments at the moment.