Отправлено: 16.06.23 07:44. Заголовок: неправильное УСЛОВИЕ в 6611

Здравствуйте, уважаемый админ.
Нашёл ошибку в задании 6611. Дело в том, что на правильный ответ (27994 245) можно выйти только при условии, что: "если пришедший гном не находит себе котёл, то он уходит". Эта фраза в условии отсутствует, а значит гномы по идее должны стоять в очереди, пока котёл не освободиться, однако тогда ответ получается другой (28236 250).

Предлагаю к рассмотрению свой код:

 
 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) 
 

По сути, за то, будет гном уходить или стоять до посинения в очереди отвечает кусочек:
t = max(t, min(pots))
Так как у меня этот кусок есть, то гном будет ждать освобождения какого-то котла. И это не сходится с ответом.
Если же я эту строчку удалю, то гном просто уйдёт, если не будет котла для него, и тогда получится правильный ответ.

Моё предложение: добавьте пожалуйста в условие фразу: "если пришедший гном не находит себе котёл, то он уходит" - или поменяйте ответ.
Спасибо

 Отправлено: 17.06.23 18:11. Заголовок: Поправка к предложенному решению

По-моему, вычитать start нужно не из 1440, а из 1440 + 1, чтобы считать последнюю минуту дня. В файле минуты начинаются с 1, а не с нуля, так что последней минутой суток будет минута 1440. Например, гном, пришедший в минуту 1439, успеет сварить два зелья - в минуты 1439 и 1440. Если не добавлять единицу, получится 1440 - 1439 = 1 минута.

Без этой поправки и очереди действительно получается (27994 245). С учётом последней минуты суток и без очереди выходит (28010 245). Без последней минуты, но с очередью - (28236 250). С обеими поправками - (28255 250).

Привожу упрощённый (и без ошибок форматирования оригинала) код для варианта с учётом последней минуты и ожидания:

 
 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) 
 

 Отправлено: 17.06.23 23:20. Заголовок: Hofsiedge пишет: По..

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 гном ждет, и зелье варится уже в следующие сутки, а значит должно быть проигнорировано).

 Отправлено: 24.06.23 08:38. Заголовок: В условии все верно...

В условии все верно! Гном ждет, пока освободится котел.
У вас, кажется, ошибка в том, что вы подходите к котлу, освободившемуся ранее других, а надо к котлу с мин. номером

 
 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))