fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll ex(ll a,ll b,ll &x,ll &y){
  5.     if(b==0){
  6.         x=1,y=0;
  7.         return a;
  8.     }
  9.     ll x1,y1;
  10.     ll d=ex(b,a%b,x1,y1);
  11.     x=y1;
  12.     y=x1-y1*(a/b);
  13.     return d;
  14.  
  15. }
  16. int main()
  17. {
  18.  
  19.  ll n;
  20.  while (cin>>n&&n!=0) {
  21. ll c1,n1,c2,n2;
  22. cin>>c1>>n1>>c2>>n2;
  23.  ll x,y;
  24.  ll d=ex(n1,n2,x,y);
  25.  if(n%d!=0){
  26.      cout<<"failed\n";
  27.    continue; 
  28.  }
  29. //  cout<<x<<" "<<y<<"\n";
  30.  x*=(n/d);
  31.  y*=(n/d);
  32. //  cout<<x<<" "<<y<<"\n";
  33.         ll k1 = n2 / d;
  34.         ll k2 = n1 / d;
  35.  
  36.        ll k = ceil((double)-x / k1);
  37.         x += k * k1;
  38.         y -= k * k2;
  39.         if (x < 0 || y < 0) {
  40.             cout << "failed\n";
  41.             continue;
  42.         }
  43.  
  44.         ll ans_x= x, ans_y = y;
  45.         ll bc = x * c1 + y * c2;
  46.  
  47.         for (int i = -1000; i <=1000; i++) {
  48.             ll xx = x + i * k1;
  49.             ll yy = y - i * k2;
  50.             if (xx >= 0 && yy >= 0) {
  51.                 ll c = xx * c1 + yy * c2;
  52.                 if (c < bc) {
  53.                     bc = c;
  54.                     ans_x= xx;
  55.                     ans_y = yy;
  56.                 }
  57.             }
  58.         }
  59.  
  60.         cout << ans_x<< " " << ans_y << "\n";
  61.     }
  62.     return 0;
  63. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4f8ZTx
language:
C++ (gcc 8.3)
created:
8 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!