Отправлено: 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? Если нужен минимальный остаток, то нужно в условии это прописать, а иначе как детям объяснять? Спасибо за ответ

 Отправлено: 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; 
 }

 Отправлено: 29.11.20 11:17. Заголовок: tim_ol@mail.ru пишет..

tim_ol@mail.ru пишет:

цитата:

Какого условия тогда не хватает для поиска искомой суммы?

Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит.

 Отправлено: 07.12.20 14:14. Заголовок: Во-первых, индексы п..

цитата:

Во-первых, индексы проверить (опечатки во втором условии). Посмотрите в пошаговом режиме, что происходит.

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

 Отправлено: 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, надеюсь, вы сможете помочь мне понять.

 Отправлено: 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. Заголовок: БЛАГОДАРЮ, ТЕПЕРЬ ПО..

БЛАГОДАРЮ, ТЕПЕРЬ ПОНЯТНО!