RiseOJ – 크림빵

설명

KOI 빵집에서는 크림을 넣은 빵을 판다. KOI 빵집은 총 $N \times K$ 개의 빵을 만들었다. KOI 빵집은 일렬로 놓여 있는 빵을 앞에서부터 순서대로 $$K$$ 개씩 묶어서 한 묶음으로 판매할 것이다. 즉, 총 $$N$$ 개의 빵 묶음이 있다.

하지만 빵을 급하게 만드는 바람에, 빵 중 일부에는 크림이 들어있지 않다. 만약 크림이 없는 빵이 한 묶음에 $$P$$ 개 이상 있다면 그 묶음은 팔 수 없다. 다시 말해, 빵 묶음은 $$K$$ 개의 빵 중 크림이 없는 빵이 $$P$$ 개 미만이어야 팔 수 있다.

각 빵에 크림이 들어 있는지에 대한 정보가 주어진다. 이 때 팔 수 있는 빵 묶음의 수를 출력하여라.

제약

입력 형식

첫 번째 줄에 $$N$$ , $$K$$ , $$P$$ 가 공백을 하나 사이에 두고 주어진다.

두 번째 줄에는 앞쪽에 놓여있는 빵부터 순서대로 빵에 크림이 들어 있는지를 나타내는 정수가 공백을 사이에 두고 주어진다.

만약 $$0$$ 이 주어진다면 빵에 크림이 없는 것이고, $$1$$ 이 주어진다면 빵에 크림이 있는 것이다.

출력 형식

첫 번째 줄에 팔 수 있는 빵 묶음의 수를 출력한다.

서브태스크

서브태스크	점수	설명
1	5점	$$N = 1$$ .
2	5점	$$K = 1$$ .
3	5점	모든 빵에 크림이 들어있거나, 모든 빵에 크림이 들어있지 않다.
4	10점	같은 묶음에 속하는 빵들은 모두 크림이 들어있거나, 모두 크림이 들어있지 않다.
5	10점	$$P = 1$$ .
6	65점	추가 제한 없음.

예제 1

입력

2 3 2
1 1 0 1 0 0

출력

예제 2

입력

3 2 1
1 1 0 0 1 1

출력

힌트

막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.

힌트 1 로그인하고 잠금 해제 · 5 🪙

힌트 2 로그인하고 잠금 해제 · 10 🪙

문제 정보

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 1차 대회 > 초등부 1번

태그

#구현 JudgeKOI

크림빵

서브태스크	점수	설명
1	5점	$\(N = 1\)$ .
2	5점	$\(K = 1\)$ .
3	5점	모든 빵에 크림이 들어있거나, 모든 빵에 크림이 들어있지 않다.
4	10점	같은 묶음에 속하는 빵들은 모두 크림이 들어있거나, 모두 크림이 들어있지 않다.
5	10점	$\(P = 1\)$ .
6	65점	추가 제한 없음.