Матч 411, Число с максимальным счетом

(MaximumScoredNumber)

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

Каждому целому неотрицательному числу соответствует такое количество очков, сколькими способами оно может быть представлено в виде суммы двух квадратов. Например, двойка имеет только одно представление: 2 = 1² + 1², а тройка – ни одного. Среди чисел от lowerBound до upperBound включительно найти то, которое имеет наибольшее количество очков. Если таких чисел несколько, то вернуть наибольшее.

Класс: MaximumScoredNumber

Метод: int getNumber(int lowerBound, int upperBound)

Ограничения:0 £ upperBound £ 10000, 0 £ lowerBound £ upperBound.

Вход. Два числа lowerBound и upperBound.

Выход. Наибольшее число между lowerBound и upperBound, имеющее наибольшее количество очков.

Пример входа

lowerBound	upperBound
0	2
0	30
0	10000

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

2

25

9425

РЕШЕНИЕ

элементарные вычисления + полный перебор

Вычислим в m[i] количество очков числа i при помощи полного перебора: для каждого 0 £ i, j £ MAX увеличим значение m[i*i + j*j] на 1. Находим и возвращаем индекс наибольшего элемента среди чисел от m[lowerBound] до m[upperBound].

Функция max_element возвращает наименьший индекс наибольшего элемента, а нам необходимо найти наибольший индекс наибольшего элемента. Поэтому обернем часть массива m[lowerBound.. upperBound], найдем в нем наименьший индекс k наибольшего элемента при помощи max_element. Ответом будет индекс upperBound – (k – lowerBound) = upperBound + lowerBound – k.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#define MAX 10001

using namespace std;

int m[MAX];

class MaximumScoredNumber

{

public:

int getNumber(int lowerBound, int upperBound)

{

int i,j;

for(i = 0; i * i <= upperBound; i++)

for(j = i; i*i + j*j <= upperBound; j++)

m[i*i + j*j]++;

reverse(m + lowerBound, m + upperBound + 1);

return m + upperBound + lowerBound –

max_element(m + lowerBound, m + upperBound + 1);

}

};