Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1107

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1107

Laser Sculpture

 

Maratona de Programação da SBC Brazil

Timelimit: 1

Since its invention, in 1958, the laser has been used in a huge variety of applications, like electronic equipment, cirurgical instruments, weapons, and much more.

The image above shows a diagram of an equipment to sculpt, with a laser, a block of some solid material. In the figure we can see a laser emitter that moves horizontally to the right and left with a constant speed. When the emitter is turned on when moving, a specific width layer is removed from the block, being vaporized by the laser.

The image below illustrates the process of sculpting with a laser, showing an example of (a) a block, with a height of 5 mm and a length of 8 mm, at the start of the process, (b) the format that we want the sculpted block to be, and (c) the sequence of layer removals during the process, considering that in each step, a layer with 1 mm of width is removed. In the first step, the piece numbered 1 is removed; in the second, the one numbered with 2; and so it goes on. During the process of sculpting, the laser was turned on 7 times, in total, once for each removed piece of the block.


Write a program that, given the height and the length of the block, and its final format, find out the total number of times the laser must be turned on.

 

Input

 

The input contains several test cases. Each test case is composed by two lines. The first line of a test case contains two integers A and C, separated by a blank space, indicating, respectively, the height (1 ≤ A ≤ 104) and the length (1 ≤ C ≤ 104) of the block to be sculpted, in milimeters. The second line contains C integers Xi, each one indicating the final height, in milimeters of the block between the positions i and i + 1 through the length (0 ≤ Xi ≤ A, for 0 ≤ i ≤ C - 1). Consider that on each step, a layer of width 1 mm is removed on the parts of the block where the laser is turned on.

The end of the input is indicated by a line that contains only two zeros, separated by a blank space.

 

Output

 

For each test case, your program must print a single line, containing an integer, indicating the number of times that the laser must be turned on to sculpt the block in the indicated format.

 

 

 

Input Sample Output Sample

5 8
1 2 3 2 0 3 4 5
3 3
1 0 2
4 3
4 4 1
0 0

7
3
3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;

int main(){
	int i,j,l,m,n;

	while(cin >> n >> m && n && m){
     int ar[m];
		long long k =0;
     for(i = 0; i  <  m; i++){
       cin >> ar[i];
       	if(i){
       		if(ar[i-1] > ar[i])
       		  k += ar[i-1] - ar[i] ;
       	    }else
       		 k +=  n - ar[i] ;
	}
	cout << k << endl;
}
  return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5 8
1 2 3 2 0 3 4 5
3 3
1 0 2
4 3
4 4 1
0 0

Output

x
+
cmd
7
3
3

#2 Code Example with Java Programming

Code - Java Programming


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) throws Exception {
      String l;
        boolean f;
        int ans, A, tmp, w;
        int[] X;
        while (!(l = read()).equals("0 0")) {
            A = toInt(l.split("\\s")[0]);
            X = readArray();
            tmp = A;
            w = A;
            ans = 0;
            f = false;
            for (int Xi : X) {
                if (Xi  < = tmp) {
                    f = false;
                } else {
                    if (!f) {
                        ans += w - tmp;
                    }
                    w = Xi;
                    f = true;
                }

                tmp = Xi;
            }
            out.println(f ? ans : ans + w - tmp);
        }
        out.close();
    }

    private static String read() throws IOException {
        return in.readLine();
    }

    private static int[] readArray() throws IOException {
        String[] line = in.readLine().split("\\s");
        int l = line.length;
        int[] a = new int[l];
        for (int i = 0; i  <  l; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        return a;
    }

    private static int toInt(String s) {
        return Integer.parseInt(s);
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5 8
1 2 3 2 0 3 4 5
3 3
1 0 2
4 3
4 4 1
0 0

Output

x
+
cmd
7
3
3

#3 Code Example with Python Programming

Code - Python Programming


while True:
    altura, comprimento = map(int, input().split())
    if altura == comprimento == 0:
        break
    x = list(map(int, input().split()))
    quant = 0
    xant = 0
    for i in range(len(x)):
        if i == 0:
            quant += altura - x[i]
        elif x[i] < xant:
            quant += xant - x[i]
        xant = x[i]
    print(quant)

Copy The Code & Try With Live Editor

Input

x
+
cmd
5 8
1 2 3 2 0 3 4 5
3 3
1 0 2
4 3
4 4 1
0 0

Output

x
+
cmd
7
3
3
Advertisements

Demonstration


Previous
#1105 Beecrowd Online Judge Solution 1105 Sub-prime Solution in C, C++, Java, Js and Python
Next
#1113 Beecrowd Online Judge Solution 1113 Ascending and Descending Solution in C++, Java, Js and Python