Informatica Online Judge

  KJB Sequence [1071 / 042F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 73   Total Tried : 94


The Champion of this Problem (C++) : gs17085 - ms / 208byte
My Best Submission (C++) : N/A

[koistudy.net (31st Yoon Ji Hak)]

Background

종범이는 칠판에 수열을 적고 있다. 그 방법은 다음과 같다.

1. 먼저 종범이는 칠판에 1을 하나 적는다.
2. 종범이는 다음과 같은 행동을 N번 반복한다.
1) 현재까지 적힌 수열을 두 배로 만든다.
2) 정가운데에 (현재까지 적힌 수들 중 가장 작은 수-1)을 적는다.

예를 들면
N=0일 경우 만들어진 수열은 {1},
N=1일 경우 만들어진 수열은 {1,0,1},
N=2일 경우 만들어진 수열은 {1,0,1,-1,1,0,1},
N=3일 경우 만들어진 수열은 {1,0,1,-1,1,0,1,-2,1,0,1,-1,1,0,1}이 될 것이다.

종범이는 문득, 이렇게 만든 수열의 L번째 항부터 R번째 항까지의 합을 구하고 싶어졌다.

종범이를 대신해서 합을 구해주자.

Input

한 줄에 N,L,R이 공백을 사이에 두고 주어진다. 수열에 L번째 항과 R번째 항이 존재한다는 것은 보장된다.

[Sub-Task Info]
- 20%에 해당하는 서브태스크에 대해서 0<=N<=10, 1<=L<=R<=10^3
- 40%에 해당하는 서브태스크에 대해서 0<=N<=10^5, 1<=L<=R<=10^6
- 40%에 해당하는 서브태스크에 대해서 0<=N<=10^9, 1<=L<=R<=10^9

Output

한 줄에 L번째 항부터 R번째 항까지의 합을 출력한다.

IO Example

입력1
2 3 5

출력1
1

입력2
3 2 11

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]