fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int dp[105][8105];
  6.  
  7. int Find(int a, int b){
  8.     if(a > 100 || b > 8100 || a > b || a < 0 || b < 0){
  9.     	return -1;
  10. 	}
  11.     if(!a && !b){
  12.     	return 0;
  13. 	}
  14.     if(dp[a][b] != -1){
  15.     	return dp[a][b];
  16. 	}
  17.     int res = 105, i = 9;
  18.     while(i > 0){
  19.         int tmp = Find(a - i, b - i * i);
  20.         if(tmp != -1){
  21.         	res = min(res, tmp + 1);
  22. 		}
  23.         i--;
  24.     }
  25.     dp[a][b] = res;
  26.     return res;
  27. }
  28.  
  29. int main(){
  30.     int t, a, b;
  31.     cin >> t;
  32.     while(t--){
  33.         memset(dp, -1, sizeof(dp));
  34.         dp[0][0] = 0;
  35.         cin >> a >> b;
  36.         int MIN = Find(a, b);
  37.  
  38.         if(MIN == -1 || MIN > 100){
  39.         	 cout << -1;
  40. 		}
  41.         else {
  42.             int i;
  43.             while(a > 0 && b > 0){
  44.                 i = 1;
  45.                 while(i < 10){
  46.                     if(a >= i && b >= i * i && dp[a - i][b - i * i] + 1 == dp[a][b]){
  47.                         cout << i;
  48.                         a -= i;
  49.                         b -= i * i;
  50.                         break;
  51.                     }
  52.                     i++;
  53.                 }
  54.             }
  55.         }
  56.         cout << endl;
  57.     }
  58.     return 0;
  59. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gJK8qg
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!