fork(2) download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. class CLDROP{
  4.     static int[][] dp;
  5.     public static void main(String args[])throws Exception{
  6.         precal(14,5000);
  7.         Reader re = new Reader(System.in);
  8.         int T = re.nextInt();
  9.         for(; T>0; T--){
  10.             int n = re.nextInt();
  11.             int h = re.nextInt();
  12.             if(n<10)
  13.                 System.err.println(n+" "+h);
  14.             int v;
  15.             if(n>=14)
  16.                 v = lg(h);
  17.             else{
  18.                 v = dp[h][n];
  19.                 if(v==0)
  20.                     v = lg(h);
  21.             }
  22.             System.out.println(v);
  23.         }
  24.     }
  25.  
  26.     static int lg(int x){
  27.         return 1+(int)(Math.log(x)/Math.log(2));
  28.     }
  29.  
  30.     static void precal(int n, int h){
  31.         dp = new int[h+1][n+1];
  32.         for(int i=1; i<=h; i++)
  33.             dp[i][1] = i;
  34.         for(int i=1; i<=n; i++)
  35.             dp[1][i] = 1;
  36.         for(int i=2; i<=h; i++){
  37.             for(int j=2; j<=n; j++){
  38.                 dp[i][j] = Integer.MAX_VALUE;
  39.                 for(int k=1; k<=i; k++){
  40.                     int a = dp[k-1][j-1];
  41.                     if(a==0 && k-1!=0)
  42.                         a = lg(k-1);
  43.                     int b = dp[i-k][j];
  44.                     if(b==0 && i-k!=0)
  45.                         b = lg(i-k);
  46.                     int m = 1 + Math.max(a, b);
  47.                     if(m<dp[i][j])
  48.                         dp[i][j] = m;
  49.                 }
  50.                 if(dp[i][j]==lg(i))
  51.                    break;
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. class Reader{
  58.     BufferedReader br;
  59.     StringTokenizer st;
  60.     Reader(InputStream in) throws Exception{
  61.         br = new BufferedReader(new InputStreamReader(in));
  62.         st = new StringTokenizer("");
  63.     }
  64.  
  65.     String next() throws Exception{
  66.         while(!st.hasMoreTokens())
  67.             st = new StringTokenizer(br.readLine());
  68.         return st.nextToken();
  69.     }
  70.  
  71.     int nextInt() throws Exception{
  72.         return Integer.parseInt(next());
  73.     }
  74. }
  75.  
Success #stdin #stdout #stderr 3.3s 320576KB
comments (?)
stdin
copy 
1
1 10
stdout
copy 
10
stderr
copy 
1 10
https://ideone.com/tnmRsK
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!