Advertisement
aimon1337

Untitled

Feb 26th, 2020
370
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. using namespace std;
  5. int N, V[1000];
  6. long M[1000], Max[1000], S;
  7. ofstream G("iesire.txt");
  8. void Citeste ()
  9. {
  10.     cin>> N>> S;
  11.     for (int i=1; i<= N; i++)
  12.     {
  13.         cin>>M[i];
  14.         Max[i]  = S / M[i];
  15.     }
  16. //    F.close();
  17. }
  18. int Solutie (int k)
  19. {
  20.     long S=0;
  21.     for (int i=1; i<= k; i++)
  22.         S += V[i] * M[i];
  23.     return ( ::S == S );
  24. }
  25. void Tipar (int k)
  26. {
  27.     G << endl;
  28.     for (int i=1; i<= k-1; i++)
  29.         if (V[i])
  30.             G  << V[i] << "*"<<M[i]<< " + ";
  31.     if (V[k])
  32.         G << V[k] << "*"<<M[k];
  33. }
  34. int Valid (int k)
  35. {
  36.     long S=0;
  37.     for (int i=1; i<= k; i++)
  38.         S += V[i] * M[i];
  39.     return ( ::S >= S );
  40. }
  41. void Monede_Back ()
  42. {
  43.     int k;
  44.     for (k=1; k<=N; k++)
  45.         V[k]=-1;
  46.     k=1;
  47.     while (k>0)
  48.     {
  49.         while (V[k]<Max[k])
  50.         {
  51.             V[k] ++;
  52.             if (Valid(k))
  53.             {
  54.                 if (Solutie(k))
  55.                     Tipar (k);
  56.                 else if (k<N)   k++;
  57.             }
  58.             else
  59.                 V[k]=Max[k];
  60.         }
  61.         V[k--]=-1;
  62.     }
  63. }
  64. int main ()
  65. {
  66.     Citeste();
  67.     Monede_Back ();
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement