Отправлено: 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] # добавить чётное или нечётное

Что на самом деле ошибка, потому что после первой заметы четных и нечетных чисел станет поровну, а по условию чисел должно быть большинство.

 Отправлено: 20.06.22 12:19. Заголовок: В задачах №3700 (27..

В задачах

№3700 (27.49)
№3701 (27.50)
№3702 (27.51)

те же проблемы

 Отправлено: 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 может быть либо у обоих нечетных чисел, либо у обоих четных чисел, если суммировать их количество, оно всегда будет четным). Поэтому алгоритм все равно будет работать правильно, если количество пар будет гарантированно нечетным.

 Отправлено: 29.06.22 13:49. Заголовок: beep пишет: ответ бу..

beep пишет:

цитата:

ответ будет 60.

Такой ответ и выдает программа. Хотелось бы увидеть пример данных, когда программа работает неверно.

 Отправлено: 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 может быть либо у обоих нечетных чисел, либо у обоих четных чисел, если суммировать их количество, оно всегда будет четным). Поэтому алгоритм все равно будет работать правильно, если количество пар будет гарантированно нечетным.

Но не понял, для чего Вы это написали:
Поляков пишет:

цитата:

Такой ответ и выдает программа. Хотелось бы увидеть пример данных, когда программа работает неверно.

Потому что ответ неверный, но такие наборы данных невозможны из-за данного ограничения.

 Отправлено: 20.08.22 13:08. Заголовок: beep пишет: Потому ч..

beep пишет:

цитата:

Потому что ответ неверный, но такие наборы данных невозможны из-за данного ограничения.

Согласен.

 Отправлено: 13.08.22 18:45. Заголовок: ап..

ап

 Отправлено: 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] # добавить чётное или нечётное

 Отправлено: 20.08.22 10:09. Заголовок: beep пишет: А чем эт..

beep пишет:

цитата:

А чем этот не подходит? 8 3 4 3 6 3 8 3 10 3 12 2 5 2 7 2 9

По условию "набор состоит из нечетного числа пар натуральных чисел."