시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 198 64 50 28.409%

문제

길이 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+MTxcL3N1Yj4sLi4uLHM8c3ViPm4rMTxcL3N1Yj5cdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YzViNFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbHQ7PSBuICZsdDs9IDUsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjQgbTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmx0Oz0gbTxzdWI+aTxcL3N1Yj4gJmx0Oz0gMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDNjOVx1YWRlMFx1YWMxMiBcdWMyMThcdWM1ZjRcdWI4NWMgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIDRcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHViOWNjXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNCA6IHsyLDIsOCwxMH0gXC8gezEsMyw3LDExfSBcLyB7MCw0LDYsMTJ9IFwvIHstMSw1LDUsMTN9PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWVhbiBTZXF1ZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgYSBub25kZWNyZWFzaW5nIHNlcXVlbmNlIG9mIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LC4uLixzPHN1Yj5uKzE8XC9zdWI+IChzPHN1Yj5pPFwvc3ViPiAmbGU7IHM8c3ViPmkrMTxcL3N1Yj4gZm9yIDEgJmxlOyBpICZsZTsgbikuIFRoZSBzZXF1ZW5jZSBtPHN1Yj4xPFwvc3ViPiwuLi4sbTxzdWI+bjxcL3N1Yj4gZGVmaW5lZCBieSBtPHN1Yj5pPFwvc3ViPiA9IDFcLzIoczxzdWI+aTxcL3N1Yj4gKyBzPHN1Yj5pKzE8XC9zdWI+KSwgZm9yIDEgJmxlOyBpICZsZTsgbiwgaXMgY2FsbGVkIHRoZSBtZWFuIHNlcXVlbmNlIG9mIHNlcXVlbmNlIHM8c3ViPjE8XC9zdWI+LC4uLixzPHN1Yj5uKzE8XC9zdWI+LiBGb3IgZXhhbXBsZSwgdGhlIG1lYW4gc2VxdWVuY2Ugb2Ygc2VxdWVuY2UgMSwgMiwgMiwgNCBpcyB0aGUgc2VxdWVuY2UgMS41LCAyLCAzLiBOb3RlIHRoYXQgZWxlbWVudHMgb2YgdGhlIG1lYW4gc2VxdWVuY2UgY2FuIGJlIGZyYWN0aW9ucy4gSG93ZXZlciwgdGhpcyB0YXNrIGRlYWxzIHdpdGggbWVhbiBzZXF1ZW5jZXMgd2hvc2UgZWxlbWVudHMgYXJlIGludGVnZXJzIG9ubHkuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbm9uZGVjcmVhc2luZyBzZXF1ZW5jZSBvZiBuIGludGVnZXJzIG08c3ViPjE8XC9zdWI+LC4uLixtPHN1Yj5uPFwvc3ViPiwgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIG5vbmRlY3JlYXNpbmcgc2VxdWVuY2VzIG9mIG4gKyAxIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LC4uLixzPHN1Yj5uKzE8XC9zdWI+IHRoYXQgaGF2ZSB0aGUgZ2l2ZW4gc2VxdWVuY2UgbTxzdWI+MTxcL3N1Yj4sLi4uLG08c3ViPm48XC9zdWI+IGFzIG1lYW4gc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IGEgbm9uZGVjcmVhc2luZyBzZXF1ZW5jZSBvZiBpbnRlZ2Vycyw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIG5vbmRlY3JlYXNpbmcgc2VxdWVuY2VzLCBmb3Igd2hpY2ggdGhlIGdpdmVuIHNlcXVlbmNlIGlzIG1lYW4gc2VxdWVuY2UsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgYW5zd2VyIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgyICZsZTsgbiAmbGU7IDUgMDAwIDAwMCApLiBUaGUgcmVtYWluaW5nIG4gbGluZXMgY29udGFpbiB0aGUgc2VxdWVuY2UgbTxzdWI+MTxcL3N1Yj4sLi4uLG08c3ViPm48XC9zdWI+LiBMaW5lIGkgKyAxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbTxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBtPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDAgKS4gWW91IGNhbiBhc3N1bWUgdGhhdCBpbiA1MCUgb2YgdGhlIHRlc3QgY2FzZXMgbiAmbGU7IDEgMDAwIGFuZCAwICZsZTsgbTxzdWI+aTxcL3N1Yj4gJmxlOyAyMCAwMDAgLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgd3JpdGUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBleGFjdGx5IG9uZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG51bWJlciBvZiBub25kZWNyZWFzaW5nIGludGVnZXIgc2VxdWVuY2VzLCB0aGF0IGhhdmUgdGhlIGlucHV0IHNlcXVlbmNlIGFzIHRoZSBtZWFuIHNlcXVlbmNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbmRlZWQsIHRoZXJlIGFyZSBmb3VyIG5vbmRlY3JlYXNpbmcgaW50ZWdlciBzZXF1ZW5jZXMgZm9yIHdoaWNoIDIsIDUsIDkgaXMgdGhlIG1lYW4gc2VxdWVuY2UuIFRoZXNlIHNlcXVlbmNlcyBhcmU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MiwgMiwgOCwgMTAsJm5ic3A7PFwvbGk+XHJcblx0PGxpPjEsIDMsIDcsIDExLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4wLCA0LCA2LCAxMiwmbmJzcDs8XC9saT5cclxuXHQ8bGk+Jm1pbnVzOzEsIDUsIDUsIDEzLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2005 2번

  • 문제를 번역한 사람: koosaga