Автор | Сообщение |
|
Отправлено: 27.11.20 12:58. Заголовок: ЕГЭ 27 2021
Добрый день, Константин Юрьевич! Вопрос по задачам 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
[только новые]
|
|
|
| Администратор
|
Сообщение: 2165
|
|
Отправлено: 27.11.20 13:10. Заголовок: olik76 пишет: почему..
olik76 пишет: цитата: | почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? Спасибо за ответ |
|
Минимальная сумма, получаемая при выборе двух минимальных чисел в каждой паре, изменяется так: 7, 19, 36, 41, 49, 54. Полученный результат (54) делится на 9. Поэтому в одной паре число нужно заменить, причем так, чтобы разница заменяемого и заменяющего числа не делилась на 9. Это достигается при замене в тройке 9 8 11: вместо 9 выбираем 11. Ответ: 54 + 2 = 56.
|
|
|
|
Отправлено: 27.11.20 14:16. Заголовок: В данном примере пол..
В данном примере получается, что пары чисел, у которых минимальная разность с ненулевым остатком от деления на 9 уже входят в сумму - пары 2 и 3; 3 и 4, а также пара 9 и 8. Следующая по величине разность равна 2 - между числами 9 и 11. Эту разность мы и прибавляем.
|
|
|
|
Отправлено: 29.11.20 08:15. Заголовок: BSL пишет: Вот пр..
Вот программа. Какого условия тогда не хватает для поиска искомой суммы? #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; }
|
|
|
|
| Администратор
|
Сообщение: 2168
|
|
Отправлено: 29.11.20 11:17. Заголовок: tim_ol@mail.ru пишет..
tim_ol@mail.ru пишет: цитата: | Какого условия тогда не хватает для поиска искомой суммы? |
|
Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит.
|
|
|
|
Отправлено: 07.12.20 14:14. Заголовок: Во-первых, индексы п..
цитата: | Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит. |
| Возможно, опечатка есть, но ответы в Excel-e и в C++ одинаковы. Но на основной вопрос,я ответа так и не увидела : почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? В этом случае, сумма получается меньше, чем у вас в критериях
|
|
|
|
| Администратор
|
Сообщение: 2207
|
|
Отправлено: 07.12.20 14:35. Заголовок: tim_ol@mail.ru пишет..
tim_ol@mail.ru пишет: цитата: | почему к искомой сумме нужно прибавить разность с меньшим остатком от 9, а не просто минимальную разность с остатком не 0? |
|
Где вы это увидели? Нужно прибавить как раз минимальную разность с ненулевым остатком. Покажите программу, по которой вы считаете, будем искать ошибку. Возможно, я неправ.
|
|
|
|
Отправлено: 08.12.20 13:54. Заголовок: https://i.postimg.cc..
У меня получается ответ для файла А 15142, а у вас ответ 15148 Для файла В ответ верный, не понимаю, что не так я делаю. Прикрепила картинку в Excel, надеюсь, вы сможете помочь мне понять.
|
|
|
|
| Администратор
|
Сообщение: 2213
|
|
Отправлено: 09.12.20 09:49. Заголовок: tim_ol@mail.ru пишет..
tim_ol@mail.ru пишет: цитата: | Для файла В ответ верный, не понимаю, что не так я делаю. |
|
Обратите внимание, что в задаче из тройки нужно выбрать два числа. В строке 17 вы выбираете, естественно, два наименьших - 96 и 127. Если вы будете менять эту пару, возможны только замены 96<->301 и 127<->301. А там разности далеко не 31.
|
|
|
|
Отправлено: 10.12.20 06:20. Заголовок: БЛАГОДАРЮ, ТЕПЕРЬ ПО..
БЛАГОДАРЮ, ТЕПЕРЬ ПОНЯТНО!
|
|
|
|