Advertisement
Guest User

Untitled

a guest
Apr 27th, 2015
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.83 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ii long long int
  3.  
  4. using namespace std;
  5.  
  6. int coin[110];
  7.  
  8. ii dp[10500];
  9.  
  10. int main()
  11. {
  12. int test;
  13. scanf("%d",&test);
  14. while(test--)
  15. {
  16. int k,n;
  17. scanf("%d %d",&k,&n);
  18. dp[0]=0;
  19. for(int i=0;i<n;i++)
  20. {
  21. scanf("%d",&coin[i]);
  22. }
  23. for(int i=1;i<=10500;i++)
  24. {
  25. dp[i]=9999999;
  26. }
  27. for(int i=0;i<n;i++)
  28. {
  29. for(int j=coin[i];j<=10500;j++)
  30. {
  31. dp[j]=min(dp[j],dp[j-coin[i]]+1);
  32. }
  33. }
  34. for(int i=k;i<=10500;i++)
  35. {
  36. if(dp[i]!=9999999)
  37. {
  38. printf("%d %d\n",i,dp[i]);
  39. break;
  40. }
  41. }
  42. memset(dp,0,sizeof dp);
  43. }
  44. return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement