Текущ брой на Списание ИнфоМан
 


Балканска олимпиада по информатика 2005, Задача 1.2. REQUESTS

Уловието на задачата може да прочетете тук.

Решение

Нека на дадена стъпка трябва да се извади елемент от кутията. Разглеждаме две ситуации:

1) В кутията има елемент X, за който времето на валидност ще е изтекло преди следващата заявка за обновяване за този предмет иливъобще няма такава следваща. В този случай най-оптимално е да се извади именно този обект X, за да се освободи място за новия. Това е така, защото за този обект е ясно, че следващата заявка за него ще струва 1, независимо дали даденият обект е в кутията или не. Ако следваща заявка няма, то ситуацията е подобна – независимо дали обектът е в кутията или не, за него няма да се плаща повече.

2) В случай, че няма такъв обект,се изважда този обект от кутията, за който следващата заявка е най-далеч в бъдещето. Това се прави, защото обектите, които ще бъдат обновени по-скоро, имат по-голям шанс да останат в кутията до момента на тяхното следващо обновяване, при което няма да се заплаща нищо.

Следвайки тази логика се получава оптимално поставяне и вадене на обекти от кутията спрямо зададените заявки.

Интересна подробност за самите тестове от състезанието е, че при тях се приема, че моментите започват от нулевия, докато в условието е поставено изискване да се започва от първи.

Примерна реализация

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

 int a[1024],b[1024];
 int list[128],d[128];
 int used[128];
 int n,k,res;

 int main ()
  {
   int i,j,t,cnt,last;
   freopen("requests.in","r",stdin);
   freopen("requests.out","w",stdout);
   scanf("%d%d",&k,&n);
   for (i=1;i<=n;i++)
    {
     scanf("%d%d",&a[i],&b[i]);
     //b[i]++;
    }
   cnt=0;
   for (i=1;i<=n;i++)
    if (cnt==k)
     {
// check if we have the element in the box
      for (j=1;j<=k;j++)
       if (list[j]==a[i])
        break;
      if (j<=k)
       {
        if (d[j]<i) res++;
        list[j]=a[i];
        d[j]=b[i];
        continue;
       }
// remove invalid element
      for (j=1;j<=k;j++)
       if (d[j]<i)
        break;
      if (j<=k)
       {
        res++;
        list[j]=a[i];
        d[j]=b[i];
        continue;
       }
// remove the farthest element or that which will expire
      res++;
      last=-1;
      memset(used,0,sizeof(used));
      for (t=i+1;t<=n;t++)
       {
        for (j=1;j<=k;j++)
         if (d[j]>=t && list[j]==a[t] && used[j]==0) break;
        if (j<=k)
         {
          used[j]=1;
          last=j;
         }
       }
      for (j=1;j<=k;j++)
       if (used[j]==0) break;
      if (j>k) j=last;
      list[j]=a[i];
      d[j]=b[i];
     }
      else
       {
        for (j=1;j<=cnt;j++)
         if (list[j]==a[i])
          break;
        if (j>cnt) cnt++;
        if (d[j]<i) res++;
        list[j]=a[i];
        d[j]=b[i];
       }
   printf("%d\n",res);
   return 0;
  }



Автор: Ростислав Руменов


обратно към брой 27