USACO 2013 Dec Bronze Problem- 도약 > 문제은행 : 정보올림피아드&알고리즘




2788 : 도약

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
8 회   
시도횟수
12 회   

문제

개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연잎 들을 이용해서 이리저리 뛰어놀고 있다.

 

개구리가 뛰는 장면을 보던 강빈이는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다.

 

1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다.

2. 개구리는 오른쪽으로만 뛴다.

3. 개구리는 두 번만 뛴다.

4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다.

 

허나, 연잎들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 강빈이는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 강빈이를 위해 프로그램을 짜주자.


입력형식

첫 번째 줄에는 연잎의 수 N(3 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 각 연잎의 좌표가 주어진다. 모든 좌표는 0 이상 108 이하이다.

출력형식

개구리가 오른쪽으로 도약하는 경우의 수를 출력한다.

입력 예

5
3
1
10
7
4

출력 예

4

Hint!

개구리가 오른쪽으로 도약하는 경우는 다음 4가지뿐이다. (1, 3, 7), (1, 4, 7), (4, 7, 10), (1, 4, 10)



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP