Форум Всеукраїнської інтернет-олімпіади NetOI

program toys2019;
var   
   countAns, n, i, curcoin, cnt1, cnt2, cnt5: longint;

begin
   read(n);
   cnt1:=0; cnt2:=0; cnt5:=0;
   for countAns:=1 to n do begin
      read(curcoin);
      if curcoin=1 then cnt1:=cnt1+1 else 
         if curcoin=2 then begin
            if cnt1>0 then begin dec(cnt1); inc(cnt2); end
               else begin write(countAns-1); halt; end;
         end
         else 
            begin
               if cnt2>=2 then begin cnt2:=cnt2-2; inc(cnt5); end
               else if (cnt2>0) and (cnt1>=2) then begin dec(cnt2); cnt1:=cnt1-2; inc(cnt5); end
               else if cnt1>=4 then begin cnt1:=cnt1-4; inc(cnt5) end
               else begin write(countAns-1); halt; end;
            end;
            
   end;
   write(countAns);
end.

Итак. Идея решения.
Будем хранить в 3-х переменных кол-во монет номиналом 1, 2 и 5.
Понятно, что если на вход приходит 1, то это супер: просто увеличиваем cnt1 на единицу. Сдачи не надо.
Если пришла двойка, то cnt2++ и тут 2 ситуации:
1)Есть хотя бы 1 монета номиналом 1 (cnt1>0) тогда выдаём сдачу (cnt1--). Понятно, что иначе выдать сдачу нельзя.
2)Если единичек нет, то мы не можем выдать сдачу и прекращаем работу.
Если пришло 5, то cnt5++;
С пятёркой заковырка: можно выдать сдачу 3-я способами:
1 1 1 1 1
1 1 1 2
1 2 2
Какой выгоднее? Ну рассуждаем логически: единичка самая лучшая монета(ей всегда можно выдать вообще любую сумму).
Двойка чуток "похуже". Пятёрка - вообще "бесполезная": мы её только принимаем и не можем использовать при выдачи сдачи.
Значит всегда лучше выдавать так, что бы затратить как можно меньше единичек(они нам ещё могут пригодится для размена).
Если можем выдать 1 2 2 - выдаём, иначе пробуем 1 1 1 2 и только потом 1 1 1 1 1.
Если выдать не получается никак, то завершаем работу. Как-то так.

Відредаговано GeniusDP (2020-11-11 16:02:56)