Условие:http://acm.timus.ru/problem.aspx?space=1&num=1658
Очень интересная задачка ))
Я написал какую-то дикую динамику с очередями. (BFS с меморизацией)
Интересный момент - в этой задаче очень хорошо проявляется разница
между STL очередью и самописной.
STL очередь: Accepted, 0.203 с, 7 453 КБ
Самописная очередь: Accepted, 0.125 c, 13 597 КБ 11 строчка рейтинга "лучшие попытки" 
Код:
Код:
#include <iostream>
#include <queue>
using namespace std;
char sq[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
char l[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
char d[901][8101];
queue <short int> q1;
queue <short int> q2;
int qps=0;
char vec[10000];
int vp=0;
void ans(int &a, int &b){ // Сбор ответа по родителям
vp=0;
while(d[a][b]){
vec[vp]=d[a][b];
vp++;
qps=d[a][b]-48;
a-=qps;
b-=sq[qps];
}
if(vp>100){
printf("No solution\n");
}else {
while(vp){
vp--;
printf("%c",vec[vp]);
}
printf("\n");
}
}
int main(){
short int a,b,o,p;
q1.push(0);
q2.push(0);
while(!q1.empty()){ //Собственно BFS, рассчитывает ответы сразу для всех возможных случаев
a=q1.front();
b=q2.front();
q1.pop();
q2.pop();
for(int i=1;i<10;i++){ //По идее, в этом месте i++ делается ~15 000 000 раз. Замена на ++i замедляет (!!!!!!) на 0.02 с.
o=a+i;
p=b+sq[i];
if(o<901 && p<8101 && !d[o][p]){
d[o][p]=l[i];
q1.push(o);
q2.push(p);
}
}
}
int t;
int e,f;
scanf("%d",&t);
for(int test=0;test<t;test++){a
scanf("%d%d",&e, &f);
if(e == 0 && f == 0){
printf("0\n");
}else if(e == 0 || f ==0){
printf("No solution\n");
}else if(e > 900 || f > 8100 || !d[e][f]){
printf("No solution\n");
}else ans(e,f);
}
return 0;
}
