題目描述

莉莎剛拿到一個數學作業。作業是一個有個很多練習題的作業簿,並區分許多章節。



作業簿理有n個章節,章節號碼用數字標示為1到n。
第i個章節裡有ti個題目,題號用數字標示為1到ti
每個頁面可以容的下k個題目。沒有任何頁面是空白的,所以只有每個章節的最後一頁的題目不到k個。
每個新章節都從新的一頁開始,所以同一頁裡絕對不會包含兩個章節以上的內容。
頁數的號碼從1開始。

莉莎相信當題目的題號和它所在的頁碼剛好相同的時候,這個題目是特別的。給定莉莎的作業簿詳細的資訊,您可以算出有多少個特別的題目嗎?

原題網址

輸入格式

第一行包含兩個整數n和k,範圍是1到100(包含1和100)。分別是章節的數量,和一個頁面可以容納的題目數量上限。

第二行包含n個整數t1、t2、t3、...、tn,ti表示為第i個章節所包含的題目數量,範圍是1到100(包含1和100)。

輸出格式

輸出莉莎的作業簿中,特別題目的數量。

範例輸入

5 3
4 2 6 1 10

範例輸出

4

額外解釋

第1頁(章節1):1 2 3。
第2頁(章節1):4。
第3頁(章節2):1 2。
第4頁(章節3):1 2 3。
第5頁(章節3):4 5 6。
第6頁(章節4):1。
第7頁(章節5):1 2 3。
第8頁(章節5):4 5 6。
第9頁(章節5):7 8 9
第10頁(章節5):10

特別的題目為第1章的第1題、第3章的第5題、第5章的第9題和第5章的第10題,一共4題。

解題概念

掃過一遍所有的章節中所有的題目,並且在過程中紀錄目前的頁數和特殊題目的數量。

頁數一開始為1,當題號可以整除以k或是題號等於該章節的題數時,就要翻到下一頁(頁數加1)。

當題號剛好等於目前頁數的時候,將特殊題目的數量加1。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final int k = sc.nextInt();
        int page = 1;
        int special = 0;
        for (int i = 0; i < n; ++i) {
            final int t = sc.nextInt();
            for (int j = 1; j <= t; ++j) {
                if (j == page) {
                    ++special;
                }
                if (j % k == 0 || j == t) {
                    ++page;
                }
            }
        }
        System.out.println(special);
    }
}