# [Gold II] 평균값 수열 [문제 링크](https://www.acmicpc.net/problem/5485) ## 문제 설명 <p>길이 n+1의 비감소 수열 s₁,...,s_n+1 (s_i ≤ s_i+1 for 1 ≤ i ≤ n) 을 생각해보자.</p> <p>이러한 수열의 "평균값 수열"을 다음과 같이 정의한다 : 1 ≤ i ≤ n에서 m_i = (s_i + s_i+1)/2.</p> <p>예를 들어, S = {1,2,2,4} 일 때 M = {3/2,2,3}이다. 이렇듯 평균값 수열은 정수가 아닌 수가 나올 수도 있지만, 이 문제에서는 평균값 수열의 원소가 정수인 경우만 고려하기로 한다.</p> <p>길이 n의 감소하지 않는 평균값 수열 m₁,...,m_n이 주어질때, 해당 수열을 평균값 수열로 가지는 수열 s₁,...,s_n+1의 개수를 세어라.</p> ## 입력 <p>첫 번째 줄에 평균값 수열의 길이 n이 주어진다. (2 ≤ n ≤ 5,000,000)</p> <p>이후 n개의 줄에 평균값 수열 m_i가 순서대로 주어진다. (0 ≤ m_i ≤ 1,000,000,000)</p> ## 출력 <p>주어진 수열을 평균값 수열로 가지는 수열의 개수를 출력하라.</p> ## 풀이 각 m마다 올 수 있는 s의 범위를 기억하다가 만약 left>right가 되는 구간이 등장한다면 수열을 못만들어 0을 출력하면 됩니다. $s_{i-1}$의 범위가 left ~ right이었다면 $s_i$의 범위는 $2m_{i-1}$-right ~ min($m_i$, $2m_{i-1}$-left)의 구간을 가진다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int last, left=-1e9, right=1e9; for(int i=0;i<n;i++) { int cur; cin >> cur; if(i) { int nextL = last*2-right; int nextR = last*2-left; left = nextL; right = nextR; } right = min(right, cur); if(left>right) { cout << 0; return 0; } last = cur; } cout << right-left+1; } ```