Atcoder arc079 D Decrease (Contestant ver.) （逆推）

阅读量：6230 次

发布时间：2019-06-21

本文共 3207 字，大约阅读时间需要 10 分钟。

D - Decrease (Contestant ver.)

Time limit : 2sec / Memory limit : 256MB

Score : 600 points

Problem Statement

We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N−1 or smaller.

Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.

It can be proved that the largest element in the sequence becomes N−1 or smaller after a finite number of operations.

You are given an integer K. Find an integer sequence ai such that the number of times we will perform the above operation is exactly K. It can be shown that there is always such a sequence under the constraints on input and output in this problem.

Constraints

0≤K≤50×1016

Input

Input is given from Standard Input in the following format:

Output

Print a solution in the following format:

Na1 a2 ... aN

Here, 2≤N≤50 and 0≤ai≤1016+1000 must hold.

Sample Input 1

Copy

Sample Output 1

Copy

43 3 3 3

Sample Input 2

Copy

Sample Output 2

Copy

31 0 3

Sample Input 3

Copy

Sample Output 3

Copy

22 2

The operation will be performed twice: [2, 2] -> [0, 3] -> [1, 1].

Sample Input 4

Copy

Sample Output 4

Copy

727 0 0 0 0 0 0

Sample Input 5

Copy

1234567894848

Sample Output 5

Copy

101000 193 256 777 0 1 1192 1234567891011 48 425

题意：

　　要你输出一个长度为N数组，满足k次操作。每一次操作选择数组里面最大的一个，将这个数减去N，其他的数全部加1。当执行完k次操作后，数组里面的最大一个数要小于等于N-1。这k次操作中全部数都要大于等于0.(k <= 50* 10¹⁶ , N<=50)

题解：

　　我们知道在最后的时候最大的是N-1。那么我们可以构造一个[0, 49] 的N为50 的数组。

　　你每次选择一个最小的数加50，其他是数减1。很明显这个[0, 49] 的数组是符合的。

　　当你执行了50次操作的时候，你会发现数组变成了[1, 50]。

　　我们就可以在[0, 49] 的数组上直接加上循环次数 ((k-1/50)+1) - 1。

　　我们还剩下 k%N 次操作

　　如果当k%N > 0 的时候，直接暴力这些操作，选择一个最小的数+N，其他数--。

　　如果k%N == 0。因为是N的倍数，因为循环次数是算的向下完整的循环，k%N==0，会使全部数+1.

　　(k = 50) 　　[0, 49] 上加上了 49/50+1-1 = 0；但是第50次就变成了[1, 50]。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 typedef unsigned long long uLL;15 #define ms(a, b) memset(a, b, sizeof(a))16 #define pb push_back17 #define mp make_pair18 #define eps 0.000000000119 #define IOS ios::sync_with_stdio(0);cin.tie(0);20 const LL INF = 0x3f3f3f3f3f3f3f3f;21 const int inf = 0x3f3f3f3f;22 const int mod = 1e9+7;23 const int maxn = 50000+10;24 LL a[60];25 int main() {26 #ifdef LOCAL27 freopen("input.txt", "r", stdin);28 // freopen("output.txt", "w", stdout);29 #endif30 // IOS31 LL k;scanf("%lld", &k);32 if(k==0) cout << "2\n1 1\n";33 else{34 int N = 50;35 LL t = (k-1)/N + 1;36 for(int i = 1;i<=N;i++) a[i] = i-1;37 for(int i = 1;i<=N;i++) a[i] += (t-1);38 int hh = k%N;39 if(hh==0){40 for(int i = 1;i<=N;i++) a[i]++;41 }42 for(int i = 1;i<=hh;i++){43 for(int j = 1;j<=N;j++){44 if(i==j) a[i] += N;45 else a[j]--;46 }47 }48 printf("%d\n", N);49 for(int i = 1;i<=N;i++)50 printf("%lld ", a[i]);51 printf("\n");52 }53 return 0;54 }