На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 64
ссылка на сообщение  Отправлено: 19.06.22 13:32. Заголовок: №3148 (27.42) вопрос по логике


Здравствуйте!

В каждой строчке дано 3 числа, каждое из них нужно положить в одно из подмножеств и в итоге должно получиться 2 подмножества, где сумма всех членов четная, и одно подмножество любой четности, где сумма максимальна (искомый результат).

В решении предложен алгоритм, который ищет минимальные расстояния от максимального числа отдельно для условно левой и правой колонки (первого и второго подмножества). А после прохождения всего файла встает важный вопрос, какие из подмножеств нужно корректировать, если ни одного, то все хорошо, если одно, то тоже не сложно найти какое число вычесть. Если оба подмножества нужно корректировать, то есть 2 варианта: удачный - это когда хотя бы в одной строке члены этих подмножеств имеют разную четность, тогда их просто можно поменять местами и снова все хорошо. Плохой же подразумевает, что на каждой строке члены корректируемых подмножеств всегда одной четности и тогда нужно найти такие строки, где член максимального подмножества имеет противоположную четность с корректируемыми подмножествами. И вот тут появляется мой вопрос и вся сложность задачи: главная проблема в том, что минимальное значение для корректировки может быть одновременно на одной строке для обоих корректируемых подмножеств. Этим и объясняется такая запутанная логика в решении.

Но ведь можно пойти намного проще. Нам всего лишь нужно найти первые 2 минимальных корректируемых значения и все. Если нужно скорректировать только 1 подмножество, то берем последний минимум, если оба - то последний + предпоследний. И все. Нам же никто не мешает менять местами члены каждой из корректируемых групп. Зачем искать отдельно для каждой группы по 2 минимума? Мы ведь всегда b можем поменять местами с a? И зачем вообще для минимального числа отслеживать минимум?

Например:

2 4 5
3 5 6

Нам ведь никто не мешает сделать так:

2 4 5
5 3 6

В чем смысл искать минимумы для самого маленького числа в строке, а потом через сложную логику искать правильную комбинацию, если самое маленькое число всегда можно поменять местами со средним и ничего не изменится с точки зрения четности?

Тогда мы просто на каждой строке сортируем числа, максимум прибавляем к результату, и сравниваем разницу между средним и максимальным числом в поисках двух минимумов, а потом уже либо ничего не вычитаем, либо первый минимум, либо оба и все?

Где я ошибаюсь? Как мы не старались бы, у нас всегда минимумы для левого столбца (множества) будут больше, чем для правого, только если нет строки где a1 == b1 и при этом еще должна найтись такая другая строка, где b1 == b2 и c1 == c2.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 8 [только новые]


Администратор




Сообщение: 3618
ссылка на сообщение  Отправлено: 24.06.22 13:32. Заголовок: Здравствуйте! Честно..


Здравствуйте! Честно сказать, мне не совсем понятна ваша идея и объяснение. Приведите, пожалуйста, ваше решение в виде программы.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 71
ссылка на сообщение  Отправлено: 27.06.22 14:17. Заголовок: Проблемы с предложен..


Проблемы с предложенным решением в ответах:

1) Для случая когда обе суммы нечетные, есть 2 варианта, первый - когда есть хотя бы одна строка, где четность у a и b отличаются, тогда ничего делать ненужно, ведь a и b можно поменять местами для s1 и s2 и тогда обе суммы станут четными, и второй случай - когда ни одной такой строки нет. За проверку на наличие этой строки в решении отвечает переменная diff0. Если diff0 == False, то вступает в работу следующая секция:

 
if s1 % 2 == 0 and s2 % 2 == 0:
print( s3 )
elif s1 % 2 != 0 and s2 % 2 != 0:
if diff0:
print( s3 )
else:
d = min( diff1[0][0] + diff2[1][0],
diff1[1][0] + diff2[0][0],
diff1[0][0] + diff1[1][0],
diff2[0][0] + diff2[1][0] )
if diff1[0][1] != diff2[0][1]:
d = min( d, diff1[0][0] + diff2[0][0] )
print( s3 - d )



Здесь слишком избыточная логика, ведь если во всех строках a и b имеют одну и ту же четность, то в diff1 и diff2 будут заноситься одни и те же значения:

 
if (c - a) % 2 == 1:
delta = c - a
if (c - b) % 2 == 1:
delta = c - b

if delta < diff1[0][0]:
diff1 = [ (delta, i), diff1[0] ]
elif delta < diff1[1][0]:
diff1[1] = (delta, i)
if (c - b) % 2 == 1:
delta = c - b

if delta < diff2[0][0]:
diff2 = [ (delta, i), diff2[0] ]
elif c - b < diff2[1][0]:
diff2[1] = (delta, i)


Это значит, что diff1 всегда будет такой же, как diff2 и все, что нужно сделать, это просто вычесть оба элемента из любого из них.

2) Когда у нас нечетна только s1, то это может быть только в случае, если строк, где четность a и b отличается, нечетное количество. В любых других случаях у нас четность s1 и s2 будет совпадать. Тогда мы в любом случае попадаем в следующую секцию:

 
elif s1 % 2 != 0:
diff = diff1[0][0]
if diff0:
if len(diff0) > 1 or diff2[0][1] != diff0[0]:
diff = min( diff, diff2[0][0] )
elif diff2[1][1] != diff0[0]:
diff = min( diff, diff2[1][0] )
print( s3 - diff )



Но поскольку diff0 это логическое значение, то алгоритм тут выдаст ошибку при попытке померить длину логического значения (а еще есть попытка обратиться к первому члену логического значения). Т.е. здесь уже алгоритм не работает. Далее я попытаюсь догадаться, что автор имел в виду.

Давайте разберемся, какие значения могут попасть в diff1 и diff2. Если у a и b одинаковая четность, то если у c четность такая же, алгоритм пропускает такую строку, а если другая, то в diff1 и diff2 попадает одно и то же значение (c - b, i) (если оно меньше тех, что уже есть в diff1/2). Если у a и b, четности разные, то в diff1 попадает c - a, если у c и a четности разные, а в diff2 попадает c - b, если у c и b четности разные.

Теперь давайте разберемся, какие случаи могут быть, если у a и b четности разные:

 
a b c
1 0 0
0 1 1
1 0 1
0 1 0


В итоге если c нечетное, то добавляется нечетное число в сумму и убирается четное (условно +1), а если c четное, то убирается нечетное число и добавляется четное (условно -1).

Поскольку у нас в diff1 хранится в первом элементе минимальная возможная разница для изменения четности s1, то сравнивать нужно 2 варианта: первый, изменение четности s1 с помощью diff1[0], и второй - изменение четности s2:
* с помощью diff2[0], при условии, что строк где четности a и b не совпадают больше одной,
* с помощью diff2[0], когда строка, где четности a и b не совпадают, одна и номер этой строки не совпадает с diff2[0][1],
* с помощью diff2[1], когда строка, где четности a и b не совпадают, одна и номер этой строки не совпадает с diff2[2][1].

Получается, что в diff0 должны храниться все i строк, у которых четности a и b не совпадают. Поскольку чтобы только одна сумма была нечетной, требуется нечетное количество строк, где четность у a и b не совпадают, то проверка на пустоту diff0 бессмысленна.

3) С суммой s2 все то же самое, что и с суммой s1 нужно делать. В diff2[0] лежит минимальный способ изменить четность s2. Это можно сделать либо помощью строки где a % 2 == b % 2 and b % 2 != c % 2, либо где a % 2 != b % 2 and b % 2 != c % 2. При этом не учитывается вариант, где s1 можно изменить с помощью diff1[0], в котором лежит c - a при a % 2 != b % 2 and a % 2 != c % 2, такое что diff1[0][0] < diff2[0][0] and len(diff0) > 1. Поэтому и файл со следующими данными

 
3
2 5 10
4 7 15
2 3 5



алгоритм обрабатывает неверно и дает неправильный результат (25, а на самом деле 27).

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 72
ссылка на сообщение  Отправлено: 27.06.22 14:44. Заголовок: Если исправлять алго..


Если исправлять алгоритм в решении, то он должен выглядеть как-то так

 
Fin = open("27-42a.txt")

N = int(Fin.readline())
s1 = s2 = s3 = 0
diff0 = []
diff1 = [ (1e10, -1), (1e10, -1) ]
diff2 = [ (1e10, -1), (1e10, -1) ]
for i in range(N):
a, b, c = map( int, Fin.readline().split() )
a, b, c = sorted( [a, b, c] )
s1 += a
s2 += b
s3 += c
if (b - a) % 2 == 1:
diff0.append(i)
if (c - a) % 2 == 1:
delta = c - a
if (c - b) % 2 == 1:
delta = c - b
if delta < diff1[0][0]:
diff1 = [ (delta, i), diff1[0] ]
elif delta < diff1[1][0]:
diff1[1] = (delta, i)
if (c - b) % 2 == 1:
delta = c - b
if delta < diff2[0][0]:
diff2 = [ (delta, i), diff2[0] ]
elif c - b < diff2[1][0]:
diff2[1] = (delta, i)
#print( s1, s2, s3, diff1, diff2 )

Fin.close()

print( 's1 =', s1, 's2 =', s2 )
print( 's3 =', s3 )
print( 'b <-> a:', diff0 )
print( 'c <-> a:', diff1 )
print( 'c <-> b:', diff2 )

print("Ответ:")
if s1 % 2 == 0 and s2 % 2 == 0:
print( s3 )
elif s1 % 2 != 0 and s2 % 2 != 0:
if diff0:
print( s3 )
else:
print( s3 - diff1[0][0] - diff1[1][0])
elif s1 % 2 != 0:
diff = diff1[0][0]
if diff0:
if len(diff0) > 1 or diff2[0][1] != diff0[0]:
diff = min( diff, diff2[0][0] )
elif diff2[1][1] != diff0[0]:
diff = min( diff, diff2[1][0] )
print( s3 - diff )
elif s2 % 2 != 0:
d = diff2[0][0]
if len(diff0) > 1: d = min(d, diff1[0][0])
print( s3 - d )


Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 73
ссылка на сообщение  Отправлено: 27.06.22 15:04. Заголовок: И вот мой итоговый в..


И вот мой итоговый вариант, который выглядит проще, как мне кажется:

 
Fin = open("27-42a.txt")

N = int(Fin.readline())
s1 = s2 = s3 = 0
swap = [[], []]
diff = [ 1e10, 1e10 ]
flag = 0

for i in range(N):
a, b, c = map( int, Fin.readline().split() )
a, b, c = sorted( [a, b, c] )
s1 += a
s2 += b
s3 += c
if b % 2 != a % 2:
swap[c % 2].append(c - (a if a % 2 != c % 2 else b))
elif b % 2 != c % 2:
flag += b
delta = c - b
if delta < diff[0]:
diff = [ delta, diff[0] ]
elif c - b < diff[1]:
diff[1] = delta

Fin.close()

for a in swap:
a.sort()

if s1 % 2 == 0 and s2 % 2 == 0:
print( s3 )
elif s1 % 2 != 0 and s2 % 2 != 0:
if swap[0] or swap[1]:
print( s3 )
else:
print(s3 - sum(diff))
else:
delta = [diff[0]]
if flag % 2: swap[0], swap[1] = swap[1], swap[0]
if swap[0]: delta.append(swap[0][0])
if swap[1] and (swap[0] or len(swap[1]) > 1): delta.append(swap[1][0])
print(s3 - min(delta))


Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 3628
ссылка на сообщение  Отправлено: 29.06.22 13:56. Заголовок: Спасибо. Действитель..


Спасибо. Действительно, решение получилось проще. С удовольствием добавлю его. Как сослаться на авторство?

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 76
ссылка на сообщение  Отправлено: 29.06.22 15:20. Заголовок: Поляков, спасибо! Та..


Поляков, спасибо! Так и можно "beep". У меня и для других задач бывают решения, которые и проще (понятнее, ну для меня, естественно) выглядят и/или существенно быстрее работают. Есть смысл их выкладывать, чтобы Вы добавляли их к ответам?

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 3630
ссылка на сообщение  Отправлено: 29.06.22 15:40. Заголовок: beep пишет: Есть смы..


beep пишет:
 цитата:
Есть смысл их выкладывать, чтобы Вы добавляли их к ответам?

Если они принципиально лучше, чем те, что выложены на сайте, то, конечно, выкладывайте. Или лучше присылайте на почту (не всегда успеваю просматривать форум).

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник




Сообщение: 417
ссылка на сообщение  Отправлено: 14.12.22 12:39. Заголовок: У меня получилось со..


У меня получилось совсем просто
Гарантируется ли, что рабиение на три суммы существует?
Не смогла придумать пример, где ответ моей программы отличается от ответа программ, представленных на сайте. Интересуют случаи когда одна из сумм нечетная.
 
Fin = open("27.txt")

N = int(Fin.readline())
s1 = s2 = s3 = 0
count_ab = 0
delta_bc1 = delta_bc2 = delta_ac = 10 ** 10

for i in range(N):
a, b, c = map(int, Fin.readline().split())
a, b, c = sorted([a, b, c])
s1 += a
s2 += b
s3 += c
count_ab += (b - a) % 2
if (c - a) % 2 == 1 and (c - b) % 2 == 0:
delta_ac = min(c - a, delta_ac)

if (c - b) % 2 == 1:
if c - b < delta_bc1:
delta_bc2 = delta_bc1
delta_bc1 = c - b
else:
delta_bc2 = min(delta_bc2, c - b)
print(s1, s2, s3, count_ab, delta_ac, delta_bc1, delta_bc2)

if s1 % 2 == 0 and s2 % 2 == 0:
print(s3)
elif s1 % 2 != 0 and s2 % 2 != 0:
if count_ab == 0:
s3 -= (delta_bc2 + delta_bc1)
print(s3)
else:
s3 -= min(delta_bc1, delta_ac)
print(s3)


Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 47
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет