|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.01.2021, 21:47 | #1 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Сумма чисел, не делящаяся на три (из ЕГЭ)
Есть задача из сборника по ЕГЭ.
Имеется набор данных (файл), состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. В первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000. Пример организации исходных данных во входном файле: 6 1 3 5 12 6 9 5 4 3 3 1 1 Для указанных входных данных значением искомой суммы должно быть число 32. Перебирать разные варианты не рекомендуется из-за возможного большого числа входных данных. Не могу сообразить, какой алгоритм можно придумать. Например, можно было бы создать очередь на некоторое небольшое число таких пар. В начале просто выбираем максимальный элемент и суммируем. В конце проверяем делимость суммы на три и если делится, то рассматриваем (перебираем) элементы, которые сохранились в очереди. Но какой размер очереди будет гарантировать нормальную работу алгоритма??? Поделитесь, пожалуйста, алгоритмом или ссылкой на что либо подобное.
Как-то так, ...
|
13.01.2021, 10:12 | #2 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Решение найдено.
1. Считываем очередную пару 2. Максимальное число из пары добавляем в сумму 3. Вычисляем разность в паре и проверяем эту разность на кратность тройке. Если некратна, то: - при первом обнаружении сохраняем и корректируем флажок. - при повторном обнаружении такой разности, сохраняем минимальную. 4. Проверяем сумму на кратность 3 5. Если сумма делится, то корректируем (заменяем ранее добавленное число, при условии, что подходящая разность пар была найдена) на найденную минимальную разность, а иначе просто выводим вычисленное значение. 6. Если в наборе данных нет пар, разность которых некратно 3, а сумма кратна 3, то выводим 0. Код:
https://inf-ege.sdamgia.ru/problem?id=11363 К сожалению поиск выдавал либо правила кратности, либо всё что есть в Сети о ЕГЭ. Наконец то угадал форму запроса: "сумма пар не кратная 3 (ЕГЭ информатика)" и попал на подходящие сайты.
Как-то так, ...
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Выведите случайную серию чисел из 0 и 1 такую, что сумма чисел в ней больше 10. | anteletaceve | Помощь студентам | 13 | 31.03.2019 10:57 |
[C++]: Даны три числа. Если сумма двух наименьших из них больше третьего, найти среднее геометрическое всех трех чисел, иначе - среднее арифметическое | LanaTsvik | Помощь студентам | 2 | 08.10.2016 15:05 |
Сумма цифр (ЕГЭ) | isst | Помощь студентам | 4 | 29.01.2015 20:13 |
Java: Дан двумерный массив чисел А размером 6х6 и одномерный массив Х из 6-ти чисел. Заменить первые три строки массива A | vikysha55 | Помощь студентам | 1 | 16.04.2014 10:50 |
Сумма с несколькими критериями, подсчёт/сумма нечётных чисел | XPsihopaTX | Microsoft Office Excel | 3 | 11.10.2012 15:00 |