Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2391
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2391
Progressões Aritméticas
Por OBI - Olimpíada Brasileira de Informática 2011 
Brazil
Timelimit: 1
Bob é um aluno do ensino médio que gosta muito de matemática. Na última aula ele aprendeu o que são Progressões Aritméticas (PAs) e ficou fascinado por elas. Pelo que Bob entendeu, Progressões Aritméticas são sequências de números nas quais a diferença entre dois elementos consecutivos é sempre igual a uma constante r, chamada de razão da PA.
Um exemplo de Progressão Aritmética de razão 2 é −1, 1, 3, 5. Além disso, toda sequência com um ou dois elementos é sempre uma Progressão Aritmética. Por outro lado, 5, 6, 8, 9, 10 não é uma PA porque a diferença entre elementos consecutivos não é constante: a diferença entre os dois primeiros elementos é 6−5 = 1, enquanto a diferença entre o terceiro e o segundo elementos é 8−6 = 2.
Bob percebeu que qualquer sequência, mesmo que a mesma não seja uma Progressão Aritmética, pode ser quebrada em sequências menores que são PAs. Por exemplo, vimos que a sequência 5, 6, 8, 9, 10 não é uma PA, mas podemos quebrar ela entre o 6 e o 8 para obtermos as sequências 5, 6 e 8, 9, 10, que são PAs. Note que não existe como quebrar a sequência em menos partes se quisermos ter apenas PAs no fim do procedimento.
Bob é fascinado por programação mas ainda não sabe programar muito bem, e por isso pediu sua ajuda: ele não está conseguindo descobrir como quebrar sequências muito grandes de um jeito eficiente; por isso, pediu que você escrevesse um programa para, dada uma sequência qualquer, imprimir o número mínimo de partes em que precisamos quebrar a sequência para termos apenas Progressões Aritméticas no término do processo. Caso a sequência original já seja uma PA, podemos terminar o processo com uma única parte, e portanto a resposta para esse caso é 1.
É fácil verificar que a sequência −2, 0, 2, 3, 3, 4, 6 (do segundo caso de teste abaixo) não é uma PA, pois 2−0 ≠ 3−2. Verificando manualmente, você pode constatar que não é possível particionar a sequência em duas de tal forma que ambas as partes sejam PAs. Entretanto, existe uma maneira de particionar a sequência em 3 PAs: [−2, 0, 2] [3, 3] [4, 6]. Portanto, temos que a resposta para este exemplo é 3.
No terceiro caso de teste abaixo, a sequência −2, 0, 3, 6 pode ser particionada de várias formas. As únicas maneiras que resultam em PAs são as seguintes:
- Com 4 partes temos 1 possibilidade:
[−2] [0] [3] [6]
- Com 3 partes temos 3 possibilidades:
[−2, 0] [3] [6]
[−2] [0, 3] [6]
[−2] [0] [3, 6]
- Com 2 partes temos 2 possibilidades:
[−2, 0] [3, 6]
[−2] [0, 3, 6]
Entrada
A primeira linha da entrada é composta por um inteiro N(1 ≤ N ≤ 105), o número de elementos da sequência. Na segunda linha existem N inteiros ai (-105 ≤ ai ≤ 105), os elementos da sequência.
Saída
A saída deve conter uma única linha, indicando o número mínimo de partes em que Bob precisa quebrar a sequência original para que ele termine apenas com PAs.
| Exemplos de Entrada | Exemplos de Saída |
|
5 1 2 3 4 5 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 100100
int main() {
int vetor[MAXN], diferenca[MAXN];
int n, resposta = 1;
scanf("%d", &n);
if (n == 1 || n == 2) {
printf("1\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &vetor[i]);
for (int i = 1; i < n; i++) diferenca[i] = vetor[i] - vetor[i - 1];
diferenca[0] = diferenca[1];
for (int i = 1; i < n; i++)
if (diferenca[i] != diferenca[i - 1]) {
resposta++;
diferenca[i] = diferenca[i + 1];
}
printf("%d\n", resposta);
return 0;
}
Input
1 2 3 4 5
Output