GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Friday 15 July 2022

[Solution] Mark the Dust Sweeper Codeforces Solution



B. Mark the Dust Sweeper
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mark is cleaning a row of n rooms. The i-th room has a nonnegative dust level ai. He has a magical cleaning machine that can do the following three-step operation.

  • Select two indices i<j such that the dust levels aiai+1aj1 are all strictly greater than 0.
  • Set ai to ai1.
  • Set aj to aj+1.
Mark's goal is to make a1=a2==an1=0 so that he

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

can nicely sweep the n-th room. Determine the minimum number of operations needed to reach his goal.
Input

The first line contains a single integer t (1t104) — the number of test cases.

The first line of each test case contains a single integer n (2n2105) — the number of rooms.

Mark and the Online Exam Codeforces Solution

Mark and Professor Koro Codeforces Solution

Mark and Lightbulbs Codeforces Solution

Mark and His Unfinished Essay Codeforces Solution

Mark the Dust Sweeper Codeforces Solution

Mark the Photographer Codeforces Solution

The second line of each test case contains n integers a1a2, ..., an (0ai109) — the dust level of each room.

It is guaranteed that the sum of n across all test cases does not exceed 2105.

Output

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

No comments:

Post a Comment