e579: 10050 - Hartals

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=e579

內容

一個社會研究組織採用了一組簡單的參數來模擬我們國家政黨運作的行為。
參數之一是一個正整數h，h稱為罷會(hartal)參數，它表示同一個政黨連續兩次連續罷會的間隔天數。
儘管該參數有點過於簡單，但還是能用於預測政黨罷會造成的影響。

以下範例為您說明：
考慮現在有三個政黨。假設h1 = 3，h2 = 4，h3 = 8，其中hi是第i方的罷會參數。
現在，我們將模擬這三個方在N = 14天的罷會行為。
模擬的起始天一定是星期天，並假設在每週的假日(星期五和星期六)不會有任何罷會情形。

Days 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
Party 1 x x x x
Party 2 x x x
Party 3 x
Hartals 1 2 3 4 5

上面的模擬顯示，在14天內將會罷會5天(分別在第3、4、8、9和12天)。
第6天沒有罷會，因為它屬於假日(星期五)。由此可知我們在2週內損失了5個工作天。

在這個問題中，考慮到多個政黨的罷會參數和天數N，您的工作是計算出這N天內我們因為罷會損失多少工作天。

輸入第一列 T 代表測資數，每組測資第一列包含一個整數 N (7 <= N <= 3650)代表模擬天數，下一列包含一個整數P (1 ≤ P ≤ 100)表示政黨數，接下來的P行，第i行包含一個正整數hi(永遠不會是7的倍數)，代表第i個政黨的罷會參數。

範例輸入

2
14
3
3
4
8
100
4
12
15
25
40

範例輸出

5
15

想法

一天一天的模擬，若該天為假日( i+1 或 i 整除 6)則跳過，若否，則判斷是否有參數可使其整除。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int T, N, P, mp[101], lose;
    cin >> T;
    while(T--){
        cin >> N >> P;
        lose = 0;
        for(int i = 0; i < P; ++i) cin >> mp[i];
        for(int i = 1; i <= N; ++i){
            if((i + 1) % 7 == 0 || i % 7 == 0) continue;
            for(int j = 0; j < P; ++j){
                if(i >= mp[j] && i % mp[j] == 0){
                    ++lose;
                    break;
                }
            }
        }
        cout << lose << "\n";
    }
}