Algorithm
Problem Name: beecrowd | 2782
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2782
Stepladder
By OBI 
Brasil
Timelimit: 1
We say that a sequence of numbers is a stepladder, if the difference between consecutive numbers is always the same. For example, "2, 3, 4, 5" and "10, 7, 4" are stepladder. Note that any sequence with only one or two numbers is also a stepladder! In this problem we are looking for stepladder in a larger sequence of numbers. Given a sequence of numbers, we want to determine how many ladders there are. But we're only interested in stepladder as long as possible. Therefore, if one stepladder is a piece of another, we consider only the largest. For example, in the sequence "1, 1, 3, 5, 4, 8, 12" we have 4 different steps: "1, 1, 1", "1, 3, 5", "5, 4" 4, 8, 12 ".
Input
The first line of the grid contains an integer (1 ≤ N ≤ 1000) that defines the size of the sequence of numbers. The second line contains N integers defining the sequence. The value of the sequence numbers is between -106 and 106 inclusive.
Output
Print a line containing an integer representing how many stepladders there are in the sequence.
| Input Samples | Output Samples |
|
8 1 1 1 3 5 4 8 12 |
4 |
|
1 112 |
1 |
|
5 11 -106 -223 -340 -457 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, x, c=0;
cin >> n;
vector<int>v(n);
vector<int>s;
for (int i = 0; i < n; ++i)
{
cin >> v[i];
if (i > 0)
{
x=v[i-1]-v[i];
s.push_back(x);
}
}
if (n < 3)
cout << 1 << endl;
else
{
for (int i = 0; i < s.size(); ++i)
{
if (i==s.size()-1)
c++;
else
{
if (s[i]!=s[i+1])
c++;
}
}
cout << c << endl;
}
return 0;
}
#2 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
var prompt = function(texto) { return lines.shift();};
const size = parseInt(prompt());
const sequence = prompt().split(" ").map(Number);
var steps = 0;
var difference;
for (let i = 1; i < size; i++) {
if (sequence[i] - sequence[i - 1] != difference) {
difference = sequence[i] - sequence[i - 1];
steps++;
}
}
if (size == 1) {
steps = 1;
}
console.log(steps);