題目描述
莉莎剛拿到一個數學作業。作業是一個有個很多練習題的作業簿,並區分許多章節。
作業簿理有n個章節,章節號碼用數字標示為1到n。
第i個章節裡有ti個題目,題號用數字標示為1到ti。
每個頁面可以容的下k個題目。沒有任何頁面是空白的,所以只有每個章節的最後一頁的題目不到k個。
每個新章節都從新的一頁開始,所以同一頁裡絕對不會包含兩個章節以上的內容。
頁數的號碼從1開始。
第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 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);
}
}