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

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

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

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





Сообщение: 51
ссылка на сообщение  Отправлено: 11.05.22 17:20. Заголовок: Задание 27 (задача 70)


Здравствуйте! Подскажите, пож., в чем ошибка алгоритма? С файлом А получается правильный ответ, с файлом B - 1365905, в таблице - 1365890. При этом, условие задачи выполняется: полученная разница делится на 5 и является максимальной.

 

a = open('27-70a.txt')
n = int(a.readline())
c = []
for i in range(n):
c.append(list(map(int, a.readline().split())))


d_max = [max(i) for i in c]
d_min = [min(i) for i in c]
s_max = sum(d_max)
s_min = sum(d_min)

diff = [max(i) - min(i) for i in c]
diff.sort()

# нахождение в diff мин. разницы чисел (i) с остатком от деления на 5,
# равным остатку от деления на 5 разницы сумм макс. и мин. чисел
for i in diff:
if i % 5 == (s_max - s_min) % 5:
print(s_max - s_min - i)
break

# 115 1365890 (1365905)




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







Сообщение: 41
ссылка на сообщение  Отправлено: 13.05.22 09:28. Заголовок: В этой задаче необхо..


В этой задаче необходимо применять "метод частичных сумм". Через минимальную разность не получится найти ответ.

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





Сообщение: 56
ссылка на сообщение  Отправлено: 13.05.22 09:37. Заголовок: Доброе утро. Предлож..


Доброе утро. Предложенный алгоритм дает правильные ответы по задачам такого типа. Конкретно в этой задаче я не учел, что минимальную разницу пары надо вычитать дважды.

 
a = open('27-70a.txt')
n = int(a.readline())
c = []
for i in range(n):
c.append(list(map(int, a.readline().split())))

# c = [[13,18], [18,10],[15,8],[19,11],[7,15]]

d_max = [max(i) for i in c]
d_min = [min(i) for i in c]
s_max = sum(d_max)
s_min = sum(d_min)

diff = [max(i) - min(i) for i in c]
diff.sort()

for i in diff:
if (s_max - s_min - 2 * i) % 5 == 0:
print(s_max - s_min - 2 * i)
break

# 115 1365890




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





Сообщение: 42
ссылка на сообщение  Отправлено: 13.05.22 10:41. Заголовок: Проблема в том, что ..


Проблема в том, что метод разностей учитывает только одну минимальную разность с нужным остатком, но еще меньшая разность может быть сформирована из нескольких разностей с другими остатками. Вам повезло, что используемый метод дал правильный ответ. Это моя недоработка! Надо будет сгенерировать новый набор данных.
Кстати, первый раз вижу решение на основе метода минимальных разностей для этой задачи. Креативно!

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





Сообщение: 57
ссылка на сообщение  Отправлено: 13.05.22 10:49. Заголовок: Вы правы. В этом слу..


Вы правы. В этом случае я делаю перебор разных вариантов с предварительным определением остатка в задачах, где сумма должна быть кратна заданному параметру. Если не должна быть кратна, еще проще.
 

...

s = sum([max(i) for i in c])
print(s%5) # = 3

ost_1 = [i for i in d if i % 5 == 1]
ost_2 = [i for i in d if i % 5 == 2]
ost_3 = [i for i in d if i % 5 == 3]

print(max(s - ost_3[0], s - ost_2[0] - ost_1[0], s - ost_1[0] - ost_1[1] - ost_1[2]))
a.close()




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





Сообщение: 43
ссылка на сообщение  Отправлено: 13.05.22 11:20. Заголовок: > В этом случае..


> В этом случае я использую перебор разных вариантов с предварительным определением остатка в задачах...

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

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

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