fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int M=1e6+5;
  4. const int inf=1e8+5;
  5. int dp[910][8100],p[910][8100];
  6. void pre()
  7. {
  8. 	for(int i=0;i<=900;i++)
  9. 	{
  10. 		for(int j=0;j<=8100;j++)
  11. 		{
  12. 			dp[i][j]=inf;
  13. 			p[i][j]=10;
  14. 		}
  15. 	}
  16. 	dp[0][0]=1; //minimum number of digit having sum=0 and squared sum=0
  17. 	for(int i=0;i<=900;i++)
  18. 	{
  19. 		for(int j=0;j<=8100;j++)
  20. 		{
  21. 			for(int k=1;k<=9;k++)
  22. 			{
  23. 				if(i+k>900 || j+k*k>8100) continue;
  24. 				if(dp[i+k][j+k*k]>=1+dp[i][j])
  25. 				{
  26. 					dp[i+k][j+k*k]=1+dp[i][j];
  27. 					p[i+k][j+k*k]=min(p[i+k][j+k*k],k);
  28. 				}
  29. 			}
  30. 		}
  31. 	}
  32. }
  33. int main()
  34. {
  35. 	pre();
  36. 	int t;
  37. 	cin>>t;
  38. 	while(t--)
  39. 	{
  40. 		string ans="";
  41. 		int n,m;
  42. 		cin>>n>>m;
  43. 		if(n>900 || m>8100 || dp[n][m]>100)
  44. 		{
  45. 			cout<<"No solution"<<endl;
  46. 			continue;
  47. 		}
  48. 		while(n && m)
  49. 		{
  50. 			int x=p[n][m];
  51. 			ans+=x+'0';
  52. 			n-=x;
  53. 			m-=x*x;
  54. 		}
  55. 		sort(ans.begin(),ans.end());
  56. 		cout<<ans<<endl;
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0.18s 60076KB
comments (?)
stdin 
1
6 8
stdout 
11112
https://ideone.com/AKSZX6
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!