Solución ejercicio B : Facebook Hacker Cup New Year's Resolution

Bueno, les traigo la solución de los ejercicios de la hacker cup de facebook. Empiezo por el segundo ejercicio por que muchos fallaron en el primero (A pesar de ser el más sencillo) y aún quiero que lo vayan pensando. 

El enunciado del ejercicio está disponible en : 

https://www.facebook.com/hackercup/problems.php?pid=1036037553088752&round=742632349177460

Ahora, lo que ofrecí, la solución, en realidad este ejercicio es un típico de programación que se tiende a resolver con programación dinámica, pero, debido a los límites de los datos de entrada, bastó con recursividad.

El algoritmo

Imaginemos que tenemos un array con 6 enteros y queremos saber si es posible sumar 32, lo que haremos es: 

consultaremos por cada número si es posible que restando llegue a 0, en ese caso retornaremos verdadero. Para optimizar y usar DP podemos guardar para cada resultado su valor, así cuando toque volver a ser consultado se evitará mucho procesamiento. ¿Se animan a programarlo así?

Para los que ya entendieron el algoritmo les dejo el código, la única diferencia es que tenemos para restar tres valores:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <sstream>
#include <string>
#include <cmath>

typedef long long ll;
using namespace std;
int n,t;
int m[25][3];

bool solve(int i,int x,int y,int z){
if(i>n)return false;
if(x==0&&y==0&&z==0)return true;
if(x<0||y<0||z<0)return false;
return solve(i+1,x-m[i][0],y-m[i][1],z-m[i][2])||solve(i+1,x,y,z);
}

int main(){
//freopen("new_years_resolution.txt","r",stdin);
//freopen("new_years_resolution_out.txt","w",stdout);
cin>>t;
//cout<<t<<endl;
for(int z=1;z<=t;z++){
    int p,c,f;
    cin>>p>>c>>f>>n;
    for(int i=0;i<n;i++){
       cin>>m[i][0]>>m[i][1]>>m[i][2];
    }
    bool res=solve(0,p,c,f);
    string out;
    if(res)out="yes";else out="no";
    cout<<"Case #"<<z<<": "<<out<<endl;
}
return 0;
}

Ahora, ¿se animan a calcular la complejidad del algoritmo? ¿SI ESTÁ BASTANTE GLOTÓN VERDAD?

¿Alguna mejor solución?  DÉJALA EN LOS COMENTARIOS, LA IDEA ES COMPARTIR CONOCIMIENTO

COMPARTE PARA SUBIR LA SOLUCIÓN A OTROS EJERCICIOS