 #айнидсомбадихелп #янепрогерятолькоучусь
Писала я недавно пробник ЕГЭ по информатике. Кое-что решить не удалось. Задача: есть N неотрицательных чисел, меньших 1000. Для каждого числа вычисляется сумма цифр. И нужно вывести ту сумму, которая реже всего встречается. Нужно написать программу, которая решит это дело эффективно. Под эффективно понимается то, что: а) время её работы при увеличении N в k раз увеличится не более, чем в k раз б) необходимый объём памяти не превышает 1 килобайта и не увеличивается с ростом N В общем, спасите маленького глупого школьника - объясните, как это решается. PS неэффективно я эту фигню, конечно, решила, но мне вот прям интересно нормальное решение 23 апреля 2017
|
|
|
|
EnGhost
А ещё по той же логике можно было вывести 0 |
|
 |
|
|
Если непонятно, погугли идею сортировки подсчетом
|
|
|
|
 |
|
|
Darth Vаder
Это самое очевидное и простейшее решение. А вот насчет оптимизации подобного я чего-то придумать ничего не могу. |
|
|
|
|
EnGhost
Так критериям удовлетворяет А лучше линии не получится Потому что надо читать числа, а это и так линия |
|
 |
|
|
Да, протупил. Массив на 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); } |
|
Включить тёмную тему
Популярное
VKontakte
WhatsApp
Telegram
Отключить рекламу
