Форум » Обработка числовых последовательностей » Задание №3151 » Ответить
Задание №3151
Михаил Титаренко: Здравствуйте. В файле B, а также в тестовом примере ответ сошелся, однако с файлом А возникла проблема. Поначалу у меня всё идет как в авторском решении, s1, s2 и s3 совпадают, а также (если я ничего не перепутал) и разности. Далее необходимо к s3 прибавить разности с s1 и s2 - 25 и 11, и из 1197 должно получиться 1233. Однако в ответе 1239. Не могу понять почему. До замен: s1 = 2834; s2 = 2820; s3 = 1197; dif(s1->s3)= 11; dif(s2->s3) = 25; После замен: s1 = 2823; s2 = 2795; s3 = 1233. Код: [more][pre2]#include <iostream> #include <fstream> #include <algorithm> using namespace std; int main() { ifstream fin("27-45a.txt"); int N; fin >> N; int s1, s2, s3, sum1 = 0, sum2 = 0, sum3 = 0, dif1 = 213123123, dif2 = 123123123,check=0; for (int i = 0; i < N; ++i) { fin >> s1 >> s2 >> s3; if (s1 <= s2 && s1 <= s3) { sum1 += s2; sum2 += s3; sum3 += s1; if ((s2 - s1) % 2 != 0 && s2 - s1 < dif1) dif1 = s2 - s1; if ((s3 - s1) % 2 != 0 && s3 - s1 < dif2) dif2 = s3 - s1; if (abs(s3 - s2) % 2 != 0) check = 1; continue; } if (s2 <= s1 && s2 <= s3) { sum1 += s1; sum2 += s3; sum3 += s2; if ((s1 - s2) % 2 != 0 && s1 - s2 < dif1) dif1 = s1 - s2; if ((s3 - s2) % 2 != 0 && s3 - s2 < dif2) dif2 = s3 - s2; if (abs(s3 - s1) % 2 != 0) check = 1; continue; } if (s3 <= s1 && s3 <= s2) { sum1 += s1; sum2 += s2; sum3 += s3; if ((s1 - s3) % 2 != 0 && s1 - s3 < dif1) dif1 = s1 - s3; if ((s2 - s3) % 2 != 0 && s2 - s3 < dif2) dif2 = s2 - s3; if (abs(s1 - s2) % 2 != 0) check = 1; } } cout << sum1 << " " << sum2 << " " << sum3 << " " << dif1 << " " << dif2 << endl; if (sum1 % 2 == 0 && sum2 % 2 == 0 && check==0) { sum3 += dif1; sum3 += dif2; sum1 -= dif1; sum2 -= dif2; } else if (sum1 % 2 != 0 && sum2 % 2 == 0) { sum3 += dif2; sum2 -= dif2; } else if (sum1 % 2 == 0 && sum2 % 2 != 0) { sum3 += dif1; sum1 -= dif1; } cout << sum1 << " " << sum2 << " " << sum3 << " " << dif1 << " " << dif2 << endl; return 0; }[/pre2][/more] Само задание: Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел как в первой, так и во второй группе должна быть нечётной. Определите минимально возможную сумму всех чисел в третьей группе.
Ответов - 7
Поляков: Михаил Титаренко пишет: После замен: s1 = 2823; s2 = 2795; s3 = 1233. Попробуйте найти такую выборку, что сумма равна 1233. Вот распределение чисел с суммой третьей группы 1239: Желтым фоном выделены ячейки, где произошла перестановка в сравнении с первоначальным вариантом, когда из каждой тройки в третью группу выбирается наименьшее число.
Михаил Титаренко: Проанализировал результат, который выдает программа, и понял, в чём ошибка у меня - программа ищет сразу две разности, а в этом файле так совпало, что минимальная разность между первой и третьей и второй и третьей группой находится в одном ряду, т.е. происходит две замены, что неосуществимо.
Поляков: Михаил Титаренко пишет: минимальная разность между первой и третьей и второй и третьей группой находится в одном ряду, т.е. происходит две замены, что неосуществимо. Да, это специально подстроенная ловушка.
ganilova: Здравствуйте! А где посмотреть авторский вариант решения?
Поляков: ganilova пишет: А где посмотреть авторский вариант решения? На сайте в файле 27data.zip. Это задача 45 из основного сборника.
1Stefsun: Добрый день! Не сходиться ответ с файлом В на 1(больше получается). Алгоритм такой: в "3" столбец суммируем наибольшие числа из каждой тройки (Поучилось 454694534). Так как сумма первых двух столбцов не изменить без третьего (нечетной разности нет в парах). Ищем две наименьших разностей "3"-го и среднего (Получились числа 25 и 26). вычитаем. Ответ 454694483. Где моя ошибка.
1Stefsun: Напечатал и понял, что число 26 четное. Не проверил. Исправил и получил числа(25 и 27) Ошибка глупая, а время потерял. И еще. Проверять надо нечетные разности и между "3"-м и минимальным столбцом, ведь там могла оказаться вторая минимальная нечетная разность. Спасибо!
полная версия страницы