Advertisement
Guest User

pokemongo.cpp

a guest
Sep 18th, 2016
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. int gN,K,*M[21],*N[21];
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <algorithm>
  5.  
  6. bool attack(int);
  7. bool lancia(int a){return(attack(a-1));}
  8. bool resiste(int a){return(attack(a));}
  9.  
  10. bool put(int *dst,int src)
  11. {
  12.   if(*dst>=src){*dst=src;return(true);}
  13.   return(false);
  14. }
  15.  
  16. void init(int n, int k)
  17. {
  18.   gN=n;
  19.   K=k;
  20.   if((1<<k)>=n)return;
  21.   if(k==1)return;
  22.   int NP=n,NE=k;
  23.   for(int z=1;z<=NE;z++)M[z]=new int [NP+1];
  24.   for(int z=1;z<=NE;z++)N[z]=new int [NP+1];
  25.   for(int e=1;e<=NE;e++){M[e][1]=1;N[e][1]=1;}
  26.   for(int k=1;k<=NP;k++){M[1][k]=k;N[1][k]=1;}
  27.   for(int e=2;e<=NE;e++)for(int k=2;k<=NP;k++)
  28.   {
  29.     int wrs=2000000000;
  30.     for(int n=N[e][k-1];n<=k;n++)if(put(&wrs,std::max(M[e-1][n-1],M[e][k-n])))N[e][k]=n;
  31.     else break;
  32.     M[e][k]=1+wrs;
  33.   }
  34.   //printf("al peggio %d lanci\nparti lanciando dal %d piano\n",M[NE][NP],N[NE][NP]);
  35. }
  36.  
  37. int dico(int K,int N)
  38. {
  39.   int l=0,r=N;
  40.   while(l<r)
  41.   {
  42.     int m=(l+r)/2;
  43.     if(attack(m))l=m+1;
  44.     else r=m;
  45.   }
  46.   return(l);
  47. }
  48.  
  49. int thr(int b,int egg,int k)
  50. {
  51.   //printf("%d %d %d\n",b,egg,k);
  52.   if(k==0)return(0);
  53.   if(egg==1)
  54.   {
  55.     int l=0;
  56.     while((l<k)&&(attack(b+l)))l++;
  57.     return(l);
  58.   }
  59.   int m=N[egg][k];
  60.   //printf("[%d]\n",b+m);
  61.   if(lancia(b+m))return(m+thr(b+m,egg,k-m));
  62.   else return(thr(b,egg-1,m-1));
  63. }
  64.  
  65. int new_pokemon()
  66. {
  67.   if((1<<K)>=gN)return(dico(K,gN));
  68.   return(thr(0,K,gN));
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement