Форум » Массивы, сортировка, работа с файлами » неправильное УСЛОВИЕ в 6611 » Ответить
неправильное УСЛОВИЕ в 6611
karandashov: Здравствуйте, уважаемый админ. Нашёл ошибку в задании 6611. Дело в том, что на правильный ответ (27994 245) можно выйти только при условии, что: "если пришедший гном не находит себе котёл, то он уходит". Эта фраза в условии отсутствует, а значит гномы по идее должны стоять в очереди, пока котёл не освободиться, однако тогда ответ получается другой (28236 250). Предлагаю к рассмотрению свой код: [pre2] q = 0 def how_many_potion_before_1440(start, maxCount): global q if start >= 1440: return 0 result = min(maxCount, 1440-start) q = max(q, result) return result # считывание данных f = open("26-125.txt", "r") lines = f.readlines() d, p = map(int, lines[0].split()) gnoms = [] for i in range(1, len(lines)): t, mana = map(int, lines.split()) gnoms.append([t, mana]) # предподготовка gnoms.sort() pots = [0]*p # когда котёл освободиться? # движок k = 0 for gnom in gnoms: t, mana = gnom if mana < 2: continue time_cooking = mana // 2 # гномы ждут своей очереди, поэтому: t = max(t, min(pots)) # ищем котёл for i in range(len(pots)): if t >= pots: if pots > 0: t += 2 pots = t+time_cooking count = how_many_potion_before_1440(t, time_cooking) k += count break print(k) print(q) [/pre2] По сути, за то, будет гном уходить или стоять до посинения в очереди отвечает кусочек: t = max(t, min(pots)) Так как у меня этот кусок есть, то гном будет ждать освобождения какого-то котла. И это не сходится с ответом. Если же я эту строчку удалю, то гном просто уйдёт, если не будет котла для него, и тогда получится правильный ответ. Моё предложение: добавьте пожалуйста в условие фразу: "если пришедший гном не находит себе котёл, то он уходит" - или поменяйте ответ. Спасибо
Ответов - 3
Hofsiedge: По-моему, вычитать start нужно не из 1440, а из 1440 + 1, чтобы считать последнюю минуту дня. В файле минуты начинаются с 1, а не с нуля, так что последней минутой суток будет минута 1440. Например, гном, пришедший в минуту 1439, успеет сварить два зелья - в минуты 1439 и 1440. Если не добавлять единицу, получится 1440 - 1439 = 1 минута. Без этой поправки и очереди действительно получается (27994 245). С учётом последней минуты суток и без очереди выходит (28010 245). Без последней минуты, но с очередью - (28236 250). С обеими поправками - (28255 250). Привожу упрощённый (и без ошибок форматирования оригинала) код для варианта с учётом последней минуты и ожидания: [pre2] with open("1.txt") as f: _, POTS = map(int, f.readline().split()) gnomes = sorted((int(t), int(mana)) for t, mana in map(str.split, f)) pots = [0] * POTS # минуты освобождения котлов total = max_single = 0 for t, mana in gnomes: time_cooking = mana // 2 start = max(t, min(pots)) # время начала с ожиданием в очереди # ищем котёл for x in range(POTS): if start >= pots[x]: if pots[x] > 0: start += 2 pots[x] = start + time_cooking # + 1, потому что включая 1440-ую минуту count = max(min(24 * 60 + 1 - start, time_cooking), 0) max_single = max(max_single, count) total += count break print(total, max_single) [/pre2]
xoreaxeax: Hofsiedge пишет: По-моему, вычитать start нужно не из 1440, а из 1440 + 1, чтобы считать последнюю минуту дня. В файле минуты начинаются с 1, а не с нуля, так что последней минутой суток будет минута 1440. Например, гном, пришедший в минуту 1439, успеет сварить два зелья - в минуты 1439 и 1440. Если не добавлять единицу, получится 1440 - 1439 = 1 минута. Согласен с этим. Тоже получал ответы (28010 245) и (28255 250) и не мог понять, в чем дело. Еще в решении в первом сообщении, мне кажется, не учитывается, подошел ли гном к грязному котлу или чистому. Например, how_many_potion_before_1440(1440, 1) для чистого котла должна выдавать 0 (поскольку зелье варится в последнюю минуту суток 1440), но для грязного этот же вызов должен вернуть 1 (посколько в минут 1440 и 1441 гном ждет, и зелье варится уже в следующие сутки, а значит должно быть проигнорировано).
Ж: В условии все верно! Гном ждет, пока освободится котел. У вас, кажется, ошибка в том, что вы подходите к котлу, освободившемуся ранее других, а надо к котлу с мин. номером [pre2] f=open('c:/26-125.txt') d,p=list(map(int,f.readline().split())) s=sorted([list(map(int,c.split())) for c in f.readlines()]) s=[[c[0],c[1]//2] for c in s if c[1]>1] # убрали гномов с малым количеством маны, превратили ману в порции зелья ma=0; k=[0]*p; l=[] for i in range(len(s)): for j in range(p): if s[0]>=min(k): #есть пустой котел на этот момент времени if s[0] >= k[j] or k[j]==min(k) and k[j]<1440: # дошли до этого пустого котла после того, как он освободился, или дождались его освобождения l.append(min(s[1] , 1440 - s[0]-2*(k[j]!=0))) # либо успели до конца суток сварить все, на что была мана , либо варили , пока сутки не окончились k[j] = s[0] + s[1] + 2*(k[j]!=0) break print(sum(l), max(l)) [/pre2]
полная версия страницы