Автор | Сообщение |
|
Отправлено: 06.01.21 22:05. Заголовок: Задача 27-26
Добрый день! В задаче 26 необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел в шестнадцатеричной системе счисления оканчивалась на F и при этом была минимально возможной. В моей программе на Паскале ответы для файла B сходятся, а вот для файла А нет. Не понятно почему. Обратился к авторскому решению на Python и тоже ничего не понял. Поэтому я вставил в авторскую программу печать пары входных чисел, их разности и окончания этой разности в шестнадцатеричной системе счисления. Вот что получилось: 749 245 504 8 756 979 223 15 174 345 171 11 565 915 350 14 168 381 213 5 594 478 116 4 895 738 157 13 910 372 538 10 43 458 415 15 297 193 104 8 434 905 471 7 751 498 253 13 103 722 619 11 238 374 136 8 549 487 62 14 26 631 605 13 325 741 416 0 133 695 562 2 160 177 17 1 109 253 144 0 6245 5 [144, 17, 178, 195, 116, 133, 166, 183, 104, 121, 250, 171, 188, 157, 62, 79] 6495 0x195f Последние две строки напечатаны авторской программой, где и указан ответ. 6245+250=6495 Из распечатанных мной выше разностей видно, что числа 250 там нет. Где автор его взял? Распечатаны все входные числа и все их разности. Разность 538 даёт окончание на F, но не минимальную сумму. Похоже, что минимум даст 6245+213+116+17=6591
|
|
|
Ответов - 4
[только новые]
|
|
|
| Администратор
|
Сообщение: 2288
|
|
Отправлено: 07.01.21 20:51. Заголовок: Олег Шумков пишет: И..
Олег Шумков пишет: цитата: | Из распечатанных мной выше разностей видно, что числа 250 там нет. |
|
Вы не учитываете, что оптимальное решение может быть получено заменой в нескольких строках. В начале файла ege27.doc разбирается похожая задача.
|
|
|
|
Отправлено: 07.01.21 22:30. Заголовок: Поляков пишет: Вы н..
Поляков пишет: цитата: | Вы не учитываете, что оптимальное решение может быть получено заменой в нескольких строках. |
| Разве не учитываю? Мой ответ получен из суммы трёх разностей, оканчивающихся в шестнадцатеричной системе на 5, 4 и 1. 5+4+1=10, что и нужно добавить к 5 чтоб получить 15 т.е. F. 213+116+17=346 и наконец 6245+346=6591 Ответ: 6591 А вот откуда взялось число 250 вы мне можете объяснить?
|
|
|
|
| Администратор
|
Сообщение: 2289
|
|
Отправлено: 07.01.21 22:51. Заголовок: Олег Шумков пишет: А..
Олег Шумков пишет: цитата: | А вот откуда взялось число 250 вы мне можете объяснить? |
|
250 = 171 + 62 + 17.
|
|
|
|
Отправлено: 08.01.21 09:53. Заголовок: Поляков пишет: 250 ..
Поляков пишет: Вот теперь понятно! Спасибо большое! 11+14+1+5=31, так же как и 47, 63 и т.д. оканчивается на F в шестнадцатеричной системе. Это не так привычно и наглядно, как в десятичной: 9, 19, 29 и т.д.
|
|
|
|