11683 – Laser Sculpture UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2730

Ad hoc, linear scan.

How I did it

• Read the number of rows and columns. If row == 0 and columns = 0 stop the program.
• Read the final heigth and insert this values inside a vector.
• Traverse the vector. If is the first time save the diference between the row and current vector position(set current equal to vector current position), otherwise if the current vector position  is less than current variable save the diference between current and the current vector position.
• Print the total.

Hints

•  Simulate the process will finish in TLE.
• To solve thism problem a linear scan is enough.

Code

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int row, col, val, current, tot;

while(scanf("%d %d", &row, &col))
{
    if(!row && !col)
       break;

    vector<int> vec;
    tot = 0;

    for(int x=0; x<col; x++)
    {
        scanf("%d", &val);
        vec.push_back(val);
    }

    for(int y=0; y<vec.size(); y++)
    {
        if(y == 0)
        {
            tot = row - vec[y];
            current = vec[y];
        }
        else
        {
            if(vec[y] < current)
               tot = tot + (current - vec[y]);
        }
        current = vec[y];
    }
    printf("%d\n", tot);
}

return 0;
}