leprechaun: #айнидсомбадихелп #янепрогерятолькоучусь Писала я недавно пробник ЕГЭ по информатике. Кое-что решит

#айнидсомбадихелп #янепрогерятолькоучусь
Писала я недавно пробник ЕГЭ по информатике. Кое-что решить не удалось.
Задача: есть N неотрицательных чисел, меньших 1000. Для каждого числа вычисляется сумма цифр. И нужно вывести ту сумму, которая реже всего встречается.
Нужно написать программу, которая решит это дело эффективно. Под эффективно понимается то, что:
а) время её работы при увеличении N в k раз увеличится не более, чем в k раз
б) необходимый объём памяти не превышает 1 килобайта и не увеличивается с ростом N

В общем, спасите маленького глупого школьника - объясните, как это решается.

PS неэффективно я эту фигню, конечно, решила, но мне вот прям интересно нормальное решение

23 апреля 2017

Отключить рекламу

13 комментариев

	pskovoroda 23 апреля 2017
27, казалось бы. А при чём тут информатика, если всё на пальцах решается? Программа выглядит так: printf ("27\n");

	Руконожка 23 апреля 2017
Мм, на решуегэ нет пояснений разве?

	MonkAlex Онлайн 23 апреля 2017
pskovoroda с чего бы 27? 999 может не входить в пространство N. 2

	EnGhost 23 апреля 2017
MonkAlex Более того, никто не сказал, что среди N чисел не может быть повторов.

	leprechaun 23 апреля 2017
Noctua там я не нашла

Program No 6

23 апреля 2017

Есть решение за линейное время и константу по памяти

Создаете массив на тридцать элементов заполненный нулями

Итерируетесь по вашим числам, считаете у каждого сумму цифр, увеличиваете на один значение в том массиве по соотв индексу

Далее очевидно, ищете минимальное значение в массиве

	Program No 6 23 апреля 2017
На каком-то пайтоне пишется в пару строк

	leprechaun 23 апреля 2017
EnGhost А ещё по той же логике можно было вывести 0

	Program No 6 23 апреля 2017
Если непонятно, погугли идею сортировки подсчетом

	leprechaun 23 апреля 2017
Darth Vаder И ведь как просто получается Эх, обидно, что сама не додумалась

	EnGhost 23 апреля 2017
Darth Vаder Это самое очевидное и простейшее решение. А вот насчет оптимизации подобного я чего-то придумать ничего не могу.

	Program No 6 23 апреля 2017
EnGhost Так критериям удовлетворяет А лучше линии не получится Потому что надо читать числа, а это и так линия

pskovoroda

23 апреля 2017

Да, протупил. Массив на 28 ячеек и сумма в каждой, по окончании прохода — поиск наименьшего (это быстрее, чем находить минимум на каждой итерации)

template<class T>
int less_frequent_sum (T* data, size_t size) {
int sum[28];
for (int i = 0; i < 28; sum [i ++] = 0);
for (int i = 0; i < size; i ++)
sum [sum_of_digits (data [i])] ++;
return min_non_zero (sum);
}