Editorial for Bedao Regular Contest 06 - ICD


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask đầu tiên:

  • Ta chỉ cần duyệt hai for với ~x~ là số kẹo của từng học sinh khi học sinh ~i~ chia kẹo, ta có công thức ~ x =~ ~a[i]~ ~div~ ~(n - i)~.
  • Ta chỉ cần cộng ~x~ vào từng ~a[j]~ với ~j > i~ .

Subtask thứ hai:

  • Nhận thấy ~a[j]~ khi được cộng vào một khoảng là tổng cộng dồn các ~x~ của các ~i~ ~(i < j)~ nên ta chỉ cần lấy ~x~ từ công thức trên và cộng vào một biến duy nhất, gọi ~sum~ là tổng của các ~x~ trước đó, ta chỉ cần cho ~a[j] = a[j] + sum~ rồi lấy ~x~ bằng công thức trên với ~a[j]~ sau đó cộng tiếp ~x~ cho ~sum~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll GCD(ll a1 , ll b1){
   while(b1 != 0){
       a1 = a1 % b1;
       ll tmp = b1;
       b1 = a1;
       a1 = tmp;
   }
   return a1;
}

template <typename T> inline void read(T & x)
{
    char c; bool nega=0;
    while((!isdigit(c=getchar()))&&c!='-');
    if(c=='-')
    {
        c=getchar();
        nega=1;
    }
    x=c-48;
    while(isdigit(c=getchar()))
    {
        x=x*10+c-48;
    }
    if(nega) x=-x;
}
template <typename T> void Write(T x) {if (x > 9) Write(x/10); putchar(x%10+48);}
template <typename T> void write(T x) {if (x < 0) {putchar('-'); x = -x;} Write(x);}

long long pow_mod(long long a, long long b, long long m) {
     long long res = 1;
     while(b){
            res = res * (b & 1 ? a : 1) % m;
            a = a * a % m; b >>= 1;
     }
     return res;
}

const ll MAXN = 1e6 + 7;
ll a[MAXN] , n;
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin >> n;
   for(int i = 1 ; i <= n ; i ++){
       cin >> a[i];
   }
   if(n <= 3000){
       for(int i = 1 ; i < n ; i ++){
           {
                ll z = a[i] % (n - i - 1 + 1);
                ll base = (a[i] - z) / (n - (i + 1) + 1);
                for(int j = i + 1 ; j <= n ; j ++){
                           a[j] += base;
                }
                a[i] = z;
           }
       }
       for(int i = 1;  i <= n ; i ++){
            cout << a[i] << " " ;
       }
       return 0;
   }
   ll base = 0;
   for(int i = 1 ; i < n ; i ++){
              a[i] += base;
              ll z = a[i] % (n - i - 1 + 1);
              {
                base += (a[i] - z) / (n - (i + 1) + 1);
              }
              a[i] = z;
   }
   a[n] += base;
   for(int i = 1 ; i <= n ; i ++){
       cout << a[i] << " ";
   }
   return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.