5485번 - 평균값 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 256 MB | 736 | 257 | 170 | 30.303% |
문제
길이 n+1의 비감소 수열 s1,...,sn+1 (si ≤ si+1 for 1 ≤ i ≤ n) 을 생각해보자.
이러한 수열의 "평균값 수열"을 다음과 같이 정의한다 : 1 ≤ i ≤ n에서 mi = (si + si+1)/2.
예를 들어, S = {1,2,2,4} 일 때 M = {3/2,2,3}이다. 이렇듯 평균값 수열은 정수가 아닌 수가 나올 수도 있지만, 이 문제에서는 평균값 수열의 원소가 정수인 경우만 고려하기로 한다.
길이 n의 감소하지 않는 평균값 수열 m1,...,mn이 주어질때, 해당 수열을 평균값 수열로 가지는 수열 s1,...,sn+1의 개수를 세어라.
입력
첫 번째 줄에 평균값 수열의 길이 n이 주어진다. (2 ≤ n ≤ 5,000,000)
이후 n개의 줄에 평균값 수열 mi가 순서대로 주어진다. (0 ≤ mi ≤ 1,000,000,000)
출력
주어진 수열을 평균값 수열로 가지는 수열의 개수를 출력하라.
예제 입력 1
3 2 5 9
예제 출력 1
4
힌트
다음과 같은 4가지 경우만이 존재한다 : {2,2,8,10} / {1,3,7,11} / {0,4,6,12} / {-1,5,5,13}
출처
Olympiad > International Olympiad in Informatics > IOI 2005 > Day 1 2번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호