fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. inline long long round_up_div(long long a,long long b){
  8.        return (a-1)/b + 1 ;
  9. }
  10.  
  11. class CandyAddict{
  12.       #define RETURN(x) {\
  13.               res[i] = x;\
  14.               goto END;\
  15.               }
  16.       public: vector<long long> solve(vector<int> X, vector<int> Y,vector<int> Z){
  17.               int n = X.size();
  18.               vector<long long> res,x,y,z;
  19.               for(int i=0;i<n;++i){
  20.                       x.push_back(X[i]);
  21.                       y.push_back(Y[i]);
  22.                       z.push_back(Z[i]);
  23.               }
  24.               res.resize(n);
  25.               for (int i=0;i<n;++i){
  26.                   if (x[i]==y[i]) RETURN(0)
  27.                   //else if (z[i]==1) res[i] = x[i]%y[i];
  28.                   else{
  29.                            int day = 1;
  30.                            long long rem = x[i] % y[i];
  31.                            long long cur = x[i] / y[i];
  32.                            long long diff = cur * (x[i]-y[i]);
  33.                            while(1){
  34.                                     if (day == z[i]) RETURN(rem)                                   
  35.                                     if (rem + diff < y[i]){
  36.                                         long long period = round_up_div(y[i] - rem, diff);
  37.                                         if (day + period * cur > z[i]) RETURN(rem + (z[i]-day) / cur * diff + (z[i]-day) % cur * x[i])
  38.                                         else{
  39.                                              day += period * cur;
  40.                                              rem = (rem + period * diff) % y[i];
  41.                                              cur++;
  42.                                         }
  43.                                     }
  44.                                     else{
  45.                                          if (day + cur > z[i]) RETURN(rem + (z[i]-day) * x[i])
  46.                                          else{
  47.                                              day += cur;
  48.                                              rem += diff;
  49.                                              cur += (rem / y[i]);
  50.                                              rem %= y[i];
  51.                                              }
  52.                                     }
  53.                                     diff = cur * (x[i]-y[i]);
  54.                            }
  55.                   }
  56.  
  57.                   END:;
  58.               }
  59.               return res;
  60.       }
  61. };
  62.  
  63. // local test entry
  64. int main()
  65. {
  66.     vector<int> a,b,c;
  67.     int n;
  68.     cin>>n;
  69.     a.resize(n);
  70.     b.resize(n);
  71.     c.resize(n);
  72.     for(int i=0;i<n;++i) cin>>a[i]>>b[i]>>c[i];
  73.     vector<long long> result = CandyAddict().solve(a,b,c);
  74.     for(int i=0;i<n;++i) cout<<result[i]<<endl;
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
5
1000000000 1 342568368
1000000000 2 560496730
1000000000 3 586947396
1000000000 999999998 386937583
1000000000 999999999 609483745
stdout 
342568367000000000
60496729000000000
253614062000000001
773875166
609483745
https://ideone.com/oUYtR5
language:
C++14 (gcc 8.3)
created:
10 years 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!