testededobra.cpp

#include<bits/stdc++.h>
using namespace std;

const int maxp = 55, maxm = 1010;
const int INF = 1e9 + 7;

int dp[maxm][maxp]; //Matriz que irá guardar os valores da programação dinâmica


int main(){
	//inicializamos a DP com "infinito" para todos os valores
	for(int i = 1; i <= maxp; i++){
		for(int j = 0; j <= maxm; j++){
			dp[j][i] = INF;
		}
	}
	//montamos a base da DP
	for(int i = 0; i <= maxm; i++) dp[i][1] = i;
	for(int i = 1; i <= maxp; i++) dp[1][i] = 1, dp[0][i] = 0;

	//calculamos os valores da DP, antes dos casos de teste
	for(int k = 2; k <= maxp; k++){
		for(int x = 2; x <= maxm; x++){
			for(int i = 1; i < x; i++){
				dp[x][k] = min(dp[x][k], max(dp[i - 1][k - 1], dp[x - i][k]) + 1);
			}
		}
	}

	int t;
	int cont = 0; //contador para o caso de teste

	scanf("%d", &t);
	while(t--){
		int n, m;
		scanf("%d %d", &n, &m);
		printf("Case %d: %d\n", ++cont, dp[m][n]);

	}


}