pokemongo.cpp

int gN,K,*M[21],*N[21];
#include <stdio.h>
#include <math.h>
#include <algorithm>

bool attack(int);
bool lancia(int a){return(attack(a-1));}
bool resiste(int a){return(attack(a));}

bool put(int *dst,int src)
{
  if(*dst>=src){*dst=src;return(true);}
  return(false);
}

void init(int n, int k)
{
  gN=n;
  K=k;
  if((1<<k)>=n)return;
  if(k==1)return;
  int NP=n,NE=k;
  for(int z=1;z<=NE;z++)M[z]=new int [NP+1];
  for(int z=1;z<=NE;z++)N[z]=new int [NP+1];
  for(int e=1;e<=NE;e++){M[e][1]=1;N[e][1]=1;}
  for(int k=1;k<=NP;k++){M[1][k]=k;N[1][k]=1;}
  for(int e=2;e<=NE;e++)for(int k=2;k<=NP;k++)
  {
    int wrs=2000000000;
    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;
    else break;
    M[e][k]=1+wrs;
  }
  //printf("al peggio %d lanci\nparti lanciando dal %d piano\n",M[NE][NP],N[NE][NP]);
}

int dico(int K,int N)
{
  int l=0,r=N;
  while(l<r)
  {
    int m=(l+r)/2;
    if(attack(m))l=m+1;
    else r=m;
  }
  return(l);
}

int thr(int b,int egg,int k)
{
  //printf("%d %d %d\n",b,egg,k);
  if(k==0)return(0);
  if(egg==1)
  {
    int l=0;
    while((l<k)&&(attack(b+l)))l++;
    return(l);
  }
  int m=N[egg][k];
  //printf("[%d]\n",b+m);
  if(lancia(b+m))return(m+thr(b+m,egg,k-m));
  else return(thr(b,egg-1,m-1));
}

int new_pokemon()
{
  if((1<<K)>=gN)return(dico(K,gN));
  return(thr(0,K,gN));
}