시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 16 MB 170 52 43 28.477%

문제

길이 n+1의 비감소 수열 s1,...,sn+1 (si ≤ si+1 for 1 ≤ i ≤ n) 을 생각해보자.

이러한 수열의 "평균값 수열"을 다음과 같이 정의한다 : 1 ≤ i ≤ n에서 mi = 1/2(si + si+1).

예를 들어, 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}

W3sicHJvYmxlbV9pZCI6IjU0ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYzlcdWFkZTBcdWFjMTIgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzQgbisxXHVjNzU4IFx1YmU0NFx1YWMxMFx1YzE4YyBcdWMyMThcdWM1ZjQgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj4gKHM8c3ViPmk8XC9zdWI+ICZsZTsgczxzdWI+aSsxPFwvc3ViPiBmb3IgMSAmbGU7IGkgJmxlOyBuKSBcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzU4ICZxdW90O1x1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjQmcXVvdDtcdWM3NDQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQgOiAxICZsZTsgaSAmbGU7IG5cdWM1ZDBcdWMxMWMgbTxzdWI+aTxcL3N1Yj4gPSAxXC8yKHM8c3ViPmk8XC9zdWI+ICsgczxzdWI+aSsxPFwvc3ViPikuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFMgPSB7MSwyLDIsNH0gXHVjNzdjIFx1YjU0YyBNID0gezNcLzIsMiwzfVx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViODA3XHViNGVmIFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjRcdWM3NDAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWMyMThcdWFjMDAgXHViMDk4XHVjNjJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjODE1XHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzhcdWM3NzQgblx1Yzc1OCBcdWFjMTBcdWMxOGNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjQgbTxzdWI+MTxcL3N1Yj4sLi4uLG08c3ViPm48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOFx1YjU0YywgXHVkNTc0XHViMmY5IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQzYzlcdWFkZTBcdWFjMTIgXHVjMjE4XHVjNWY0XHViODVjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWMyMThcdWM1ZjQgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj5cdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YzViNFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsdDs9IG4gJmx0Oz0gNSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNCBtPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7PSBtPHN1Yj5pPFwvc3ViPiAmbHQ7PSAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgNFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWI5Y2NcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0IDogezIsMiw4LDEwfSBcLyB7MSwzLDcsMTF9IFwvIHswLDQsNiwxMn0gXC8gey0xLDUsNSwxM308XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNZWFuIFNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIG5vbmRlY3JlYXNpbmcgc2VxdWVuY2Ugb2YgaW50ZWdlcnMgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj4gKHM8c3ViPmk8XC9zdWI+ICZsZTsgczxzdWI+aSsxPFwvc3ViPiBmb3IgMSAmbGU7IGkgJmxlOyBuKS4gVGhlIHNlcXVlbmNlIG08c3ViPjE8XC9zdWI+LC4uLixtPHN1Yj5uPFwvc3ViPiBkZWZpbmVkIGJ5IG08c3ViPmk8XC9zdWI+ID0gMVwvMihzPHN1Yj5pPFwvc3ViPiArIHM8c3ViPmkrMTxcL3N1Yj4pLCBmb3IgMSAmbGU7IGkgJmxlOyBuLCBpcyBjYWxsZWQgdGhlIG1lYW4gc2VxdWVuY2Ugb2Ygc2VxdWVuY2UgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj4uIEZvciBleGFtcGxlLCB0aGUgbWVhbiBzZXF1ZW5jZSBvZiBzZXF1ZW5jZSAxLCAyLCAyLCA0IGlzIHRoZSBzZXF1ZW5jZSAxLjUsIDIsIDMuIE5vdGUgdGhhdCBlbGVtZW50cyBvZiB0aGUgbWVhbiBzZXF1ZW5jZSBjYW4gYmUgZnJhY3Rpb25zLiBIb3dldmVyLCB0aGlzIHRhc2sgZGVhbHMgd2l0aCBtZWFuIHNlcXVlbmNlcyB3aG9zZSBlbGVtZW50cyBhcmUgaW50ZWdlcnMgb25seS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBub25kZWNyZWFzaW5nIHNlcXVlbmNlIG9mIG4gaW50ZWdlcnMgbTxzdWI+MTxcL3N1Yj4sLi4uLG08c3ViPm48XC9zdWI+LCBjb21wdXRlIHRoZSBudW1iZXIgb2Ygbm9uZGVjcmVhc2luZyBzZXF1ZW5jZXMgb2YgbiArIDEgaW50ZWdlcnMgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj4gdGhhdCBoYXZlIHRoZSBnaXZlbiBzZXF1ZW5jZSBtPHN1Yj4xPFwvc3ViPiwuLi4sbTxzdWI+bjxcL3N1Yj4gYXMgbWVhbiBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgYSBub25kZWNyZWFzaW5nIHNlcXVlbmNlIG9mIGludGVnZXJzLDxcL2xpPlxyXG5cdDxsaT5jYWxjdWxhdGVzIHRoZSBudW1iZXIgb2Ygbm9uZGVjcmVhc2luZyBzZXF1ZW5jZXMsIGZvciB3aGljaCB0aGUgZ2l2ZW4gc2VxdWVuY2UgaXMgbWVhbiBzZXF1ZW5jZSw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBhbnN3ZXIgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4gKDIgJmxlOyBuICZsZTsgNSAwMDAgMDAwICkuIFRoZSByZW1haW5pbmcgbiBsaW5lcyBjb250YWluIHRoZSBzZXF1ZW5jZSBtPHN1Yj4xPFwvc3ViPiwuLi4sbTxzdWI+bjxcL3N1Yj4uIExpbmUgaSArIDEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBtPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IG08c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMCApLiBZb3UgY2FuIGFzc3VtZSB0aGF0IGluIDUwJSBvZiB0aGUgdGVzdCBjYXNlcyBuICZsZTsgMSAwMDAgYW5kIDAgJmxlOyBtPHN1Yj5pPFwvc3ViPiAmbGU7IDIwIDAwMCAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IGV4YWN0bHkgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIG5vbmRlY3JlYXNpbmcgaW50ZWdlciBzZXF1ZW5jZXMsIHRoYXQgaGF2ZSB0aGUgaW5wdXQgc2VxdWVuY2UgYXMgdGhlIG1lYW4gc2VxdWVuY2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkluZGVlZCwgdGhlcmUgYXJlIGZvdXIgbm9uZGVjcmVhc2luZyBpbnRlZ2VyIHNlcXVlbmNlcyBmb3Igd2hpY2ggMiwgNSwgOSBpcyB0aGUgbWVhbiBzZXF1ZW5jZS4gVGhlc2Ugc2VxdWVuY2VzIGFyZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4yLCAyLCA4LCAxMCwmbmJzcDs8XC9saT5cclxuXHQ8bGk+MSwgMywgNywgMTEsJm5ic3A7PFwvbGk+XHJcblx0PGxpPjAsIDQsIDYsIDEyLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4mbWludXM7MSwgNSwgNSwgMTMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2005 2번

  • 문제를 번역한 사람: koosaga