Форум » Обработка числовых последовательностей » ЕГЭ 27 2021 » Ответить

ЕГЭ 27 2021

olik76: Добрый день, Константин Юрьевич! Вопрос по задачам 27 с подобной формулировкой: Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел не делилась на 9 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000. Пример входного файла: 6 8 3 4 4 8 12 9 8 11 2 8 3 12 3 5 1 4 11 Для указанных входных данных значением искомой суммы должно быть число 56. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B. Вопрос: почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? Спасибо за ответ

Ответов - 9

Поляков: olik76 пишет: почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? Спасибо за ответ Минимальная сумма, получаемая при выборе двух минимальных чисел в каждой паре, изменяется так: 7, 19, 36, 41, 49, 54. Полученный результат (54) делится на 9. Поэтому в одной паре число нужно заменить, причем так, чтобы разница заменяемого и заменяющего числа не делилась на 9. Это достигается при замене в тройке 9 8 11: вместо 9 выбираем 11. Ответ: 54 + 2 = 56.

BSL: В данном примере получается, что пары чисел, у которых минимальная разность с ненулевым остатком от деления на 9 уже входят в сумму - пары 2 и 3; 3 и 4, а также пара 9 и 8. Следующая по величине разность равна 2 - между числами 9 и 11. Эту разность мы и прибавляем.

tim_ol@mail.ru: Вот программа. Какого условия тогда не хватает для поиска искомой суммы? [pre2] #include <iostream> #include <fstream> #include <vector> #include <algorithm> //для сортировки using namespace std; main () { int i, min_d = 10000, x, y, z, n, sum = 0; vector <int> v(3), r(2); //автоматически обнуляются ifstream F("27-31a.txt"); F >> n; while (F >> x >> y >> z) { v[0] = x; v[1] = y; v[2] = z; sort(v.begin(), v.end()); //сортировка вектора от начала до конца //cout <<v.at(0) << " " << v.at(1)<<" "<<v.at(2) << endl; sum = sum + v[0] + v[1]; if (v[2] - v[1] < v[1] - v[0] && (v[2] - v[1] ) % 9 != 0 && v[2] - v[1]<min_d) min_d = v[2] - v[1]; else if (v[2] - v[1] > v[1] - v[0] && ( v[1] - v[0] ) % 9 != 0 && v[1] - v[0]<min_d) min_d = v[1] - v[0]; } if (sum % 9 != 0) cout << sum; else cout <<sum + min_d; }[/pre2]


Поляков: tim_ol@mail.ru пишет: Какого условия тогда не хватает для поиска искомой суммы? Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит.

tim_ol@mail.ru: Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит. Возможно, опечатка есть, но ответы в Excel-e и в C++ одинаковы. Но на основной вопрос,я ответа так и не увидела : почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? В этом случае, сумма получается меньше, чем у вас в критериях

Поляков: tim_ol@mail.ru пишет: почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0?Где вы это увидели? Нужно прибавить как раз минимальную разность с ненулевым остатком. Покажите программу, по которой вы считаете, будем искать ошибку. Возможно, я неправ.

tim_ol@mail.ru: У меня получается ответ для файла А 15142, а у вас ответ 15148 Для файла В ответ верный, не понимаю, что не так я делаю. Прикрепила картинку в Excel, надеюсь, вы сможете помочь мне понять.

Поляков: tim_ol@mail.ru пишет: Для файла В ответ верный, не понимаю, что не так я делаю. Обратите внимание, что в задаче из тройки нужно выбрать два числа. В строке 17 вы выбираете, естественно, два наименьших - 96 и 127. Если вы будете менять эту пару, возможны только замены 96<->301 и 127<->301. А там разности далеко не 31.

tim_ol@mail.ru: БЛАГОДАРЮ, ТЕПЕРЬ ПОНЯТНО!



полная версия страницы