Автор | Сообщение |
|
Отправлено: 20.06.22 11:38. Заголовок: №3699-3702 (27.48-51) ошибка в решении
Здравствуйте! В предложенном к задаче решении есть один недочет. Вся суть решения сводится в итоге к тому, что чтобы получить сумму такой же четности, как и четность большинства составляющих ее чисел, нужно сколько-то раз поменять местами a и b. Если разница между четными и нечетными числами большая, то достаточно одного такого обмена. Главный вопрос в том, где та граница, когда одного обмена будет недостаточно. Чтобы сменить четность у суммы, можно заменить либо четное число на четное, либо наоборот нечетное на четное. Если мы меняем число с такой же четностью как у суммы, то после первой замены противоположный счетчик увеличивается на 1 и при этом сумма оказывается такой же четности, как и увеличенный счетчик. Если же мы заменяем число с противоположной сумме четностью, то сумма оказывается с четностью у уменьшенного счетчика и чтобы сумму вернуть к увеличивающемуся счетчику нужно произвести такую же замену еще раз. Например, слева будет изначально количество четных чисел, а справа - нечетных 0 0 Если сумма нечетная и мы меняем нечетное число на четное, то у нас получается четная сумма и счетчики 1 - 1 В итоге у нас сумма оказалась с такой же четностью как и больший счетчик Если же сумма нечетная и мы меняем четное число на нечетное, то сумма получается четная и счетчики -1 1 Теперь нужно еще раз четное число заменить на нечетное и тогда сумма станет нечетной и счетчики -2 2 Отбросим вариант, когда мы меняем число с такой же четностью, как и сумма, потому что там всегда нужно только 1 действие, будем рассматривать только случаи когда мы меняем числа с противоположной сумме четностью для разных вариантов изначальных счетчиков и для нечетной суммы: 1 0 (сумма нечетная, далее 1) 0 1 (0) -1 2(1) 2 0 (1) 1 1 (0) 0 2 (1) 3 0 (1) 2 1 (0) - конец, т.к. сумма оказалась у большего счетчика Если же мы тут заменим число с такой же четностью как и у суммы, то тоже за один ход получим результат 3 0 (1) 4 -1 (0) Итого, начиная с разницы в 3 между четными и нечетными числами ответ получается за 1 ход. В решении же эта граница начинается с 2: if abs(even-odd) > 1: delta0, delta1 = diff[0][0], diff[1][0] # добавить чётное или нечётное Что на самом деле ошибка, потому что после первой заметы четных и нечетных чисел станет поровну, а по условию чисел должно быть большинство.
|
|
|
Ответов - 11
[только новые]
|
|
|
Отправлено: 20.06.22 12:19. Заголовок: В задачах №3700 (27..
В задачах №3700 (27.49) №3701 (27.50) №3702 (27.51) те же проблемы
|
|
|
|
| Администратор
|
Сообщение: 3590
|
|
Отправлено: 24.06.22 09:58. Заголовок: beep пишет: Что на с..
beep пишет: цитата: | Что на самом деле ошибка, потому что после первой заметы четных и нечетных чисел станет поровну, а по условию чисел должно быть большинство. |
|
Приведите, пожалуйста, простой пример данных, на которых приведенная программа выдаст неверный ответ.
|
|
|
|
Отправлено: 26.06.22 12:22. Заголовок: Поляков, здравствуйт..
Поляков, здравствуйте. Например, для файла 8 3 4 3 6 3 8 3 10 3 12 2 5 2 7 2 9 ответ будет 60. Максимальная сумма 61, она состоит из 5 четных чисел и 3 нечетных чисел. Чтобы заменить одно четное на одно нечетное число нужно 4 заменить на 3 (разница 1), а чтобы заменить одно нечетное число на четное число, нужно заменить 5 на 2 (разница 3). Алгоритм выбирает менять 4 на 3 из-за того, что разница 1 меньше разницы 3, но получается при этом 5 - 1 = 4 четных числа и 3 + 1 = 4 нечетных числа, т.е. четных и нечетных чисел становится поровну. Алгоритм должен был сделать еще один обмен четного на нечетное (6 на 3 с разницей 3, тогда сумма 57, 3 четных числа и 4 нечетных), либо заменить один раз нечетное число на четное (5 на 2, тогда сумма равна 61 - 3 = 58, 6 четных чисел, 3 нечетных) и сделать вывод, что 58 > 57, поэтому нужно сделать 1 обмен, вместо двух. Единственное, что я не учел и не заметил, так это то, что в условии общее количество пар нечетное, поэтому разницы между количеством четных и нечетных чисел равной 2, так чтобы общее количество этих чисел было нечетным не может быть математически, эта разница может быть либо 1, либо 3, либо больше (разница в 2 может быть либо у обоих нечетных чисел, либо у обоих четных чисел, если суммировать их количество, оно всегда будет четным). Поэтому алгоритм все равно будет работать правильно, если количество пар будет гарантированно нечетным.
|
|
|
|
| Администратор
|
Сообщение: 3627
|
|
Отправлено: 29.06.22 13:49. Заголовок: beep пишет: ответ бу..
beep пишет: Такой ответ и выдает программа. Хотелось бы увидеть пример данных, когда программа работает неверно.
|
|
|
|
Отправлено: 29.06.22 15:35. Заголовок: Поляков, я и говорю,..
Поляков, я и говорю, что программа выдаст ответ 60, а он неправильный. Смотрите, максимальная сумма 61, 5 четных чисел, 3 нечетных числа. Дальше алгоритм в решении меняет 4 на 3 (1 строчка) и получается 61 - 1 = 60 (ответ), где 5 - 1 = 4 четных числа и 3 + 1 = 4 нечетных числа. Т.е. у нас четных и нечетных чисел равное количество. А по условию такого не может быть. цитата: | при условии, что чётность этой суммы совпадает с чётностью большинства выбранных чисел |
| А правильный ответ 58, 6 четных чисел, 2 нечетных числа.
|
|
|
|
Отправлено: 20.08.22 12:53. Заголовок: Поляков пишет: По у..
Поляков пишет: цитата: | По условию "набор состоит из нечетного числа пар натуральных чисел." |
| Об этом я написал сразу (понял уже после создания темы): beep пишет: цитата: | Единственное, что я не учел и не заметил, так это то, что в условии общее количество пар нечетное, поэтому разницы между количеством четных и нечетных чисел равной 2, так чтобы общее количество этих чисел было нечетным не может быть математически, эта разница может быть либо 1, либо 3, либо больше (разница в 2 может быть либо у обоих нечетных чисел, либо у обоих четных чисел, если суммировать их количество, оно всегда будет четным). Поэтому алгоритм все равно будет работать правильно, если количество пар будет гарантированно нечетным. |
| Но не понял, для чего Вы это написали: Поляков пишет: цитата: | Такой ответ и выдает программа. Хотелось бы увидеть пример данных, когда программа работает неверно. |
| Потому что ответ неверный, но такие наборы данных невозможны из-за данного ограничения.
|
|
|
|
| Администратор
|
Сообщение: 3670
|
|
Отправлено: 20.08.22 13:08. Заголовок: beep пишет: Потому ч..
beep пишет: цитата: | Потому что ответ неверный, но такие наборы данных невозможны из-за данного ограничения. |
|
Согласен.
|
|
|
|
Отправлено: 13.08.22 18:45. Заголовок: ап..
ап
|
|
|
|
| Администратор
|
Сообщение: 3658
|
|
Отправлено: 18.08.22 12:44. Заголовок: beep пишет: Что на с..
beep пишет: цитата: | Что на самом деле ошибка, потому что после первой заметы четных и нечетных чисел станет поровну, а по условию чисел должно быть большинство. |
|
1) Приведите, пожалуйста, простой пример данных, при которых программа выведет неверный ответ. 2) Как вы предлагаете исправить эту ошибку?
|
|
|
|
Отправлено: 19.08.22 15:40. Заголовок: 1) Приведите, пожалу..
цитата: | 1) Приведите, пожалуйста, простой пример данных, при которых программа выведет неверный ответ. |
| А чем этот не подходит? 8 3 4 3 6 3 8 3 10 3 12 2 5 2 7 2 9 цитата: | 2) Как вы предлагаете исправить эту ошибку? |
| Заменить допустимую разницу с 1 на 2 (с 2 до 3): if abs(even-odd) > 2: delta0, delta1 = diff[0][0], diff[1][0] # добавить чётное или нечётное
|
|
|
|
| Администратор
|
Сообщение: 3669
|
|
Отправлено: 20.08.22 10:09. Заголовок: beep пишет: А чем эт..
beep пишет: цитата: | А чем этот не подходит? 8 3 4 3 6 3 8 3 10 3 12 2 5 2 7 2 9 |
|
По условию "набор состоит из нечетного числа пар натуральных чисел."
|
|
|
|