A9193. Dima and To-do List
编程题
普及/提高-
知识点
题目描述
The first line of the input contains two integers $n,k (1<=k<=n<=10^{5})$ . The second line contains $n$ integers $a_{1},a_{2},...,a_{n} (1<=a_{i}<=10^{3})$ , where $a_{i}$ is the power Inna tells Dima off with if she is present in the room while he is doing the $i$ -th task.
It is guaranteed that $n$ is divisible by $k$ .
It is guaranteed that $n$ is divisible by $k$ .
输入格式
In a single line print the number of the task Dima should start with to get told off with as little power as possible. If there are multiple solutions, print the one with the minimum number of the first task to do.
输出格式
Explanation of the first example.
If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as $k$ = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12.
Explanation of the second example.
In the second example $k$ = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.
If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as $k$ = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12.
Explanation of the second example.
In the second example $k$ = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.
输入输出样例
输入 #1
6 2 3 2 1 6 5 4
输出 #1
1
输入 #2
10 5 1 3 5 7 9 9 4 1 8 5
输出 #2
3
说明/提示
Explanation of the first example.
If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as $k$ = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12.
Explanation of the second example.
In the second example $k$ = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.
If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as $k$ = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12.
Explanation of the second example.
In the second example $k$ = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.