Sorting Pancakes Codeforces Solution | Codeforces Problem Solution 2022

Sorting Pancakes Codeforces Solution | Codeforces Problem Solution 2022

G. Sorting Pancakes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Nastya baked 𝑚$m$ pancakes and spread them on 𝑛$n$ dishes. The dishes are in a row and numbered from left to right. She put 𝑎𝑖$a_i$ pancakes on the dish with the index 𝑖$i$.

Solution Click Below:- CLICK HERE

Seeing the dishes, Vlad decided to bring order to the stacks and move some pancakes. In one move, he can shift one pancake from any dish to the closest one, that is, select the dish 𝑖$i$ (𝑎𝑖>0$a_i>0$) and do one of the following:

• if 𝑖>1$i>1$, put the pancake on a dish with the previous index, after this move 𝑎𝑖=𝑎𝑖−1$a_i=a_i-1$ and 𝑎𝑖−1=𝑎𝑖−1+1$a_{i-1}=a_{i-1}+1$;
• if 𝑖<𝑛$i<n$, put the pancake on a dish with the following index, after this move 𝑎𝑖=𝑎𝑖−1$a_i=a_i-1$ and 𝑎𝑖+1=𝑎𝑖+1+1$a_{i+1}=a_{i+1}+1$.

Vlad wants to make the array 𝑎$a$non-increasing, after moving as few pancakes as possible. Help him find the minimum number of moves needed for this.

Food for Animals Codeforces Solution | Codeforces Problem Solution 2022 

Make It Increasing Codeforces Solution | Codeforces Problem Solution 2022 

Detective Task Codeforces Solution | Codeforces Problem Solution 2022 

Vertical Paths Codeforces Solution | Codeforces Problem Solution 2022 

Replace With the Previous, Minimize Codeforces Solution 

Vlad and Unfinished Business Codeforces Solution 

Sorting Pancakes Codeforces Solution 

The array 𝑎=[𝑎1,𝑎2,…,𝑎𝑛]$a=[a_1,a_2,\dots ,a_n]$ is called non-increasing if 𝑎𝑖≥𝑎𝑖+1$a_i\ge a_{i+1}$ for all 𝑖$i$ from 1$1$ to 𝑛−1$n-1$.

Input

The first line of the input contains two numbers 𝑛$n$ and 𝑚$m$ (1≤𝑛,𝑚≤250$1\le n,m\le 250$) — the number of dishes and the number of pancakes, respectively.

The second line contains 𝑛$n$ numbers 𝑎𝑖$a_i$ (0≤𝑎𝑖≤𝑚$0\le a_i\le m$), the sum of all 𝑎𝑖$a_i$ is equal to 𝑚$m$.

Output

Print a single number: the minimum number of moves required to make the array 𝑎$a$ non-increasing.

 

Join Now for Solution:-