시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB45615612031.662%

문제

길이 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}

W3sicHJvYmxlbV9pZCI6IjU0ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYzlcdWFkZTBcdWFjMTIgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzQgbisxXHVjNzU4IFx1YmU0NFx1YWMxMFx1YzE4YyBcdWMyMThcdWM1ZjQgczxzdWI+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj4gKHM8c3ViPmk8XC9zdWI+ICZsZTsgczxzdWI+aSsxPFwvc3ViPiBmb3IgMSAmbGU7IGkgJmxlOyBuKSBcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzU4ICZxdW90O1x1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjQmcXVvdDtcdWM3NDQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQgOiAxICZsZTsgaSAmbGU7IG5cdWM1ZDBcdWMxMWMgbTxzdWI+aTxcL3N1Yj4gPSAoczxzdWI+aTxcL3N1Yj4gKyBzPHN1Yj5pKzE8XC9zdWI+KVwvMi48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUyA9IHsxLDIsMiw0fSBcdWM3N2MgXHViNTRjIE0gPSB7M1wvMiwyLDN9XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWI0ZWYgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YzIxOFx1YWMwMCBcdWIwOThcdWM2MmMgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWQzYzlcdWFkZTBcdWFjMTIgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWM4MTVcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHViOWNjIFx1YWNlMFx1YjgyNFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzOFx1Yzc3NCBuXHVjNzU4IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNCBtPHN1Yj4xPFwvc3ViPiwuLi4sbTxzdWI+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4XHViNTRjLCBcdWQ1NzRcdWIyZjkgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjRcdWI4NWMgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzIxOFx1YzVmNCBzPHN1Yj4xPFwvc3ViPiwuLi4sczxzdWI+bisxPFwvc3ViPlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHVjNWI0XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkM2M5XHVhZGUwXHVhYzEyIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgbiAmbGU7IDUsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjQgbTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBtPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQzYzlcdWFkZTBcdWFjMTIgXHVjMjE4XHVjNWY0XHViODVjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCA0XHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YjljY1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQgOiB7MiwyLDgsMTB9IFwvIHsxLDMsNywxMX0gXC8gezAsNCw2LDEyfSBcLyB7LTEsNSw1LDEzfTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTQ4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1lYW4gU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIGEgbm9uZGVjcmVhc2luZyBzZXF1ZW5jZSBvZiBpbnRlZ2VycyBzPHN1Yj4xPFwvc3ViPiwuLi4sczxzdWI+bisxPFwvc3ViPiAoczxzdWI+aTxcL3N1Yj4gJmxlOyBzPHN1Yj5pKzE8XC9zdWI+IGZvciAxICZsZTsgaSAmbGU7IG4pLiBUaGUgc2VxdWVuY2UgbTxzdWI+MTxcL3N1Yj4sLi4uLG08c3ViPm48XC9zdWI+IGRlZmluZWQgYnkgbTxzdWI+aTxcL3N1Yj4gPSAxXC8yKHM8c3ViPmk8XC9zdWI+ICsgczxzdWI+aSsxPFwvc3ViPiksIGZvciAxICZsZTsgaSAmbGU7IG4sIGlzIGNhbGxlZCB0aGUgbWVhbiBzZXF1ZW5jZSBvZiBzZXF1ZW5jZSBzPHN1Yj4xPFwvc3ViPiwuLi4sczxzdWI+bisxPFwvc3ViPi4gRm9yIGV4YW1wbGUsIHRoZSBtZWFuIHNlcXVlbmNlIG9mIHNlcXVlbmNlIDEsIDIsIDIsIDQgaXMgdGhlIHNlcXVlbmNlIDEuNSwgMiwgMy4gTm90ZSB0aGF0IGVsZW1lbnRzIG9mIHRoZSBtZWFuIHNlcXVlbmNlIGNhbiBiZSBmcmFjdGlvbnMuIEhvd2V2ZXIsIHRoaXMgdGFzayBkZWFscyB3aXRoIG1lYW4gc2VxdWVuY2VzIHdob3NlIGVsZW1lbnRzIGFyZSBpbnRlZ2VycyBvbmx5LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIG5vbmRlY3JlYXNpbmcgc2VxdWVuY2Ugb2YgbiBpbnRlZ2VycyBtPHN1Yj4xPFwvc3ViPiwuLi4sbTxzdWI+bjxcL3N1Yj4sIGNvbXB1dGUgdGhlIG51bWJlciBvZiBub25kZWNyZWFzaW5nIHNlcXVlbmNlcyBvZiBuICsgMSBpbnRlZ2VycyBzPHN1Yj4xPFwvc3ViPiwuLi4sczxzdWI+bisxPFwvc3ViPiB0aGF0IGhhdmUgdGhlIGdpdmVuIHNlcXVlbmNlIG08c3ViPjE8XC9zdWI+LC4uLixtPHN1Yj5uPFwvc3ViPiBhcyBtZWFuIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBhIG5vbmRlY3JlYXNpbmcgc2VxdWVuY2Ugb2YgaW50ZWdlcnMsPFwvbGk+XHJcblx0PGxpPmNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBub25kZWNyZWFzaW5nIHNlcXVlbmNlcywgZm9yIHdoaWNoIHRoZSBnaXZlbiBzZXF1ZW5jZSBpcyBtZWFuIHNlcXVlbmNlLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIGFuc3dlciB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMiAmbGU7IG4gJmxlOyA1IDAwMCAwMDAgKS4gVGhlIHJlbWFpbmluZyBuIGxpbmVzIGNvbnRhaW4gdGhlIHNlcXVlbmNlIG08c3ViPjE8XC9zdWI+LC4uLixtPHN1Yj5uPFwvc3ViPi4gTGluZSBpICsgMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIG08c3ViPmk8XC9zdWI+ICgwICZsZTsgbTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwICkuIFlvdSBjYW4gYXNzdW1lIHRoYXQgaW4gNTAlIG9mIHRoZSB0ZXN0IGNhc2VzIG4gJmxlOyAxIDAwMCBhbmQgMCAmbGU7IG08c3ViPmk8XC9zdWI+ICZsZTsgMjAgMDAwIC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIHdyaXRlIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQgZXhhY3RseSBvbmUgaW50ZWdlciAmbWRhc2g7IHRoZSBudW1iZXIgb2Ygbm9uZGVjcmVhc2luZyBpbnRlZ2VyIHNlcXVlbmNlcywgdGhhdCBoYXZlIHRoZSBpbnB1dCBzZXF1ZW5jZSBhcyB0aGUgbWVhbiBzZXF1ZW5jZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW5kZWVkLCB0aGVyZSBhcmUgZm91ciBub25kZWNyZWFzaW5nIGludGVnZXIgc2VxdWVuY2VzIGZvciB3aGljaCAyLCA1LCA5IGlzIHRoZSBtZWFuIHNlcXVlbmNlLiBUaGVzZSBzZXF1ZW5jZXMgYXJlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjIsIDIsIDgsIDEwLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4xLCAzLCA3LCAxMSwmbmJzcDs8XC9saT5cclxuXHQ8bGk+MCwgNCwgNiwgMTIsJm5ic3A7PFwvbGk+XHJcblx0PGxpPiZtaW51czsxLCA1LCA1LCAxMy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2005 > Day 1 2번

  • 문제를 번역한 사람: koosaga