Матч 387, Угадывание следующего элемента (GuessingNextElement)

Дивизион 2, Уровень 1

Арифметическая прогрессия определяется первым членом a₁ и разностью d:

a₁, a₁ + d, a₁ + 2d, a₁ + 3d, …

Геометрическая прогрессия определяется первым членом b₁ и знаменателем q:

b₁, b₁q, b₁q², b₁q³, …

Массив a содержит или арифметическую или геометрическую прогрессию. Известно, что по содержимому массива a однозначно определяется тип прогрессии. Необходимо найти следующий элемент последовательности.

Класс: GuessingNextElement

Метод: int guess(vector<int> a)

Ограничения: a содержит от 3 до 50 элементов в возрастающем порядке, 1 £ a[i] £ 10⁶.

Вход. Массив a содержит последовательность целых чисел.

Выход. Следующий элемент последовательности.

Пример входа

a

{364,843,1322,1801}

{394,1172,1950,2728,3506,4284,5062,5840}

{13,117,1053,9477,85293}

Пример выхода

2280

6618

767637

РЕШЕНИЕ

математика

По трем первым элементам последовательности можно установить, является ли она арифметической или геометрической прогрессией и соответственно найти разность d = a[1] – a[0] или знаменатель q = a[1] / a[0]. Поскольку массив а содержит только целые числа, то q будет целочисленным. Входная последовательность является арифметической прогрессией, если 2 * a[1] = a[0] + a[2] и геометрической иначе. Для нахождения следующего элемента следует к последнему элементу прибавить d в случае арифметической прогрессии или умножить последний элемент на q в случае геометрической прогрессии.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class GuessingNextElement

{

public:

int guess(vector<int> a)

{

int res,d;

if (2*a[1] == a[0] + a[2])

{

d = a[1] - a[0];

res = a[a.size()-1] + d;

} else

{

d = a[1] / a[0];

res = a[a.size()-1] * d;

}

return res;

}

};