3131번 - 크리스마스 선물 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 177 | 48 | 41 | 33.065% |
문제
상근이는 두 손자에게 크리스마스 선물을 주려고 한다. 오늘 상근이는 선물 N개를 구매했고, 손자들이 스스로 나누어 가지게 하려고 한다. 아이들은 번갈아가면서 선물을 하나씩 가져가고, 나이가 많은 손자(형) 먼저 시작한다. 상근이의 손자들은 순수함을 잃었기 때문에, 항상 남아있는 선물 중에서 가장 비싼 선물을 가져갈 것이다.
형이 가져간 선물 가격의 총 합이 동생의 합보다 적어도 A만큼 높지 않으면 형은 행복하지 않을 것이다. 또, 동생이 가져간 선물 가격의 총 합이 형의 합보다 많아야 B만큼 낮지 않으면 동생은 행복하지 않을 것이다. 즉, 두 손자를 행복하게 하기 위해서는 가져간 선물 가격의 총 합의 차이가 A와 B 안에 있어아 한다.
선물의 가격은 모두 양의 정수이다. 각 선물의 가격은 포장지에 붙여져 있다. 상근이는 쇼핑을 마치고 선물을 나누어 주기 전에 선물 하나에 가짜 가격을 붙이려고 한다. 이 가짜 가격도 자연수이어야 한다.
N개의 선물 중 가격이 붙어있는 선물 N-1개의 가격이 주어진다. 이때, 두 손자를 행복하게 할 수 있는 가짜 가격의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 109, 1 ≤ N ≤ 100,000)
다음 N-1개 줄에는 선물의 가격이 한 줄에 하나씩 주어진다. 모든 가격은 109보다 작은 자연수이고, 내림차순으로 정렬되어져 있다. 가격이 붙어져 있지 않은 선물의 가격은 입력으로 주어지지 않는다.
출력
두 손자를 행복하게 만들 수 있는 가짜 가격의 수를 출력한다.
예제 입력 1
3 3 4 5 5 5
예제 출력 1
2
예제 입력 2
50 60 3 100 20
예제 출력 2
22
예제 입력 3
6 15 7 17 13 10 10 6 2
예제 출력 3
23
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2008 > National Competition #2 - Seniors 1번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호