Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PAS11 - Progressões aritméticas

 

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.

Entrada

A primeira linha da entrada é composta por um inteiro N, o número de elementos da sequência. Na segunda linha existem N inteiros ai, 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.

Restrições

  • 1 ≤ N ≤ 105
  • −105ai ≤ 105

Exemplos

Entrada
5
1 2 3 4 5

Saída
1

Entrada
7
-2 0 2 3 3 4 6

Saída
3

É fácil verificar que a sequência −2, 0, 2, 3, 3, 4, 6 (do exemplo acima) 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.

Entrada
4
-2 0 3 6

Saída
2

A sequência −2, 0, 3, 6 (do exemplo acima) 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]


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 1 nível 1

hide comments
2015-04-04 04:36:36 cargold2
3

Last edit: 2015-04-04 04:36:57
2014-04-03 14:10:03 Gabriel Alcântara[IFCE]
A condiçăo de existęncia de uma PA é ter dois ou mais termos e onde posiçăo[i+1] - posiçăo[i] é uma constante. Entăo sendo assim o 1< N ≤(10^5).
2012-03-18 00:27:58 Severino Mizael da silva
as entradas usadas para testar os nossos programas săo iguais ?
pois tem questőes que eu submeto e da acepted com um tempo X depois de fazer melhorias no codigo(garantido que săo melhorias) fica outro tempo Y onde Y > X
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.