Luigi, le pizzaiolo rigolo, vend des pizzas au metre ( ou plutot par tranche de 10 centimètres ). Il a acheté une chainette de 4 mètres pour mesurer les parts
qu'il vend, et l'a découpé en quatre petites chainettes. Quelles sont les tailles de ces quatres chainette ?
Analyse
Avec 4 metres, on obtient 40 parts de 10 centimètres. Donc il faut trouver a,b,c,d, tel que a+b+c+d=40 et que quelque soit i dans 1..40, on puisse trouver un n-uplet (x ou x,y ou x,y,z ou xyzw ) dans (a,b,c,d), tel que une combinaison du type x+y = i+z existe. Une petite astuce : si on peut trouver n et n+2, alors on peut déduire n+1.
Le code reprend le principe du compte est bon. On va prendre toute les combinaisons de 4-uplets tel que leur somme soit 40, et pour chaque combinaison on va essayer de trouver toutes les valeurs de 1 à 40. Si une valeur N n'est pas trouvée mais que N-1 et N+1 sont possibles, on continue.
Petite optimisation ( ca coute pas cher mais quand meme ) : on classe les 4 valeurs par ordre croissant, donc la 1ere est forcement inférieur à 10, la deuxième à 13 ...
La valeur max pour la longueur est 53, ensuite il faut plus de 4 morceaux !
Programme
#define GAP(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))
#define NBCH 4
#define longueur 40
int plus (int *a, int b) { return (*a += b); }
int moins(int *a, int b) { return (*a = GAP(*a,b)); }
#define NBOP 2
int (*f[])(int *,int) = { plus , moins };
char s[] = "+-";
int lcb(int *tab, int nb, int tot)
{
int i,j,k,t[NBCH];
for ( i=0 ; i<nb-1 ; i++ )
for ( j=i+1 ; j<nb ; j++)
for ( k=0; k<NBOP; k++) {
memcpy(t,tab,sizeof(int)*NBCH);
if ( t[i] == tot ) return 1;
if ( (*f[k])(&t[i],t[j]) ) {
if ( t[i] == tot ) return 1;
t[j]=t[nb-1];
if (lcb(t,nb-1,tot)) return 1;
}
}
return 0;
}
int main(void)
{
int i,j,k, t;
int tab[4] ;
int prev =1;
for ( i=1 ; i< longueur/4 ; i++ )
for ( j=i; (3*j) < ( longueur-i ) ; j++ )
for ( k=j; (2*k) < (longueur-i-j) ; k++ ) {
tab[0]=i; tab[1]=j; tab[2]=k;
tab[3]=longueur-i-j-k;
for ( t=1; t<longueur; t++) {
if ( lcb(tab,4,t) ) prev=1;
else {
if ( ! prev ) break;
prev = 0;
}
}
if ( t == longueur ) printf("%d %d %d %d\n",tab[0],tab[1],tab[2],tab[3]);
}
}
Conclusion
Si votre pizzaiolo
a un problème rigolo
pensez à coder
un peu de C.
Problème
Analyse
Programme
Conclusion