1439 . FairlyLife

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

16.7% (2/12)

Tags

Ural

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 1

10 3

Sample Output 1

4
12 12
17 18
29 30
87 94

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 11
2 1 11
3 2 11
4 3 11
5 4 11
6 5 11
7 6 11
8 7 11
9 8 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
Submit
Back to Top