TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

66.7% (2/3)

Tags

Description

山南 (みなみ)寫了一段這樣的程式碼:

int find(int n,int p) {
  int l,r,m,c;
  l=c=0;
  r=n-1;
  while(l<=r) {
    m=(l+r)/2;
    c++;
    if(p<m){r=m-1;}
    else if(p>m){l=m+1;}
    else break;
  }
  return c;
}

(因為akira只有教她C語言,只會Pascal的就抱歉啦。)(?!)

相信各位都看的出來,
這段程式是用來計算利用二分搜尋法找一個數要探測幾次的。

不過由於最近重力無限大的關係,
南突然想要知道在 p 固定的時候,什麼樣的 n 會導致 find() 傳回的值為 q(必須滿足n>p),
你能夠幫她解決這個問題嗎?

Input Format

兩個整數 p 跟 q。
0<=p<=9999
1<=q<=14

Output Format

輸出所有會讓 find(n,p)=q 的 n 值。
由於這樣的答案可能會有非常多個,
請將答案分成一組一組的連續區間來輸出,
組數要盡量少,而且要依照數字大小由小到大輸出。
第一行輸出一個整數 m 代表答案被分成幾個區間,
接下來每行輸出一個區間的起點跟終點。

Sample Input

10 3

Sample Output

4
12 12
17 18
29 30
87 94

Hints

Problem Source

原TIOJ1439 / Problem Setter:akira(Adapted From Ural 1064)

Subtasks

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536