jump to navigation

Akademis busuk… Januari 20, 2009

Posted by marcadian in Story.
23 comments

Ok, hari ini sangat busuk.

Hari jumat lalu, dosen grafkom ga masuk karena sakit, di tempelan tertulis, kuliah pengganti hari selasa tgl 20 januari jam 3 sore ampe 7 malem.

Hari senin kuliah sistem operasi, sang dosen katanya disuruh akademis untuk mengadakan kuliah pengganti hari selasa tgl 20 januari, dari shift 3 ampe 6, begitu dibilang ada grafkom, tuh dosen bilang, akademis kasihnya jam segtu.

Hari ini, pas mulai KP sisop, si dosen bilang, dia dikasih akademis shift 3 – 6, dan yang grafkom itu dikasih shift  6 – 7.

Pas ke akademis tanya,

Mr x : wah mestinya mahasiswanya bilang ke dosennya, mestinya ga bisa itu

mhs : loh pak, ud bilang, katanya dikasih dari akademis itu jadwalnya

Mr x : wah ya mestinya ga bisa, yang booking duluan dapet duluan

mhs (tepatnya gua) : loh ini kok bisa pak? jadi kuliahnya gmana ?

Mr x : ya yang booking duluan sapa bla bla bla

OK, dasar tolol cape berdebat, tinggalin aja, jelas2 mereka yang atur jadwalnya. >.<

Yang menyetujui booking mereka, masa bisa dalam 1 shift, kuliah di 2 tempat? Kalo ud ada jadwal laen ya bookingnya ditolak donk, pindahin ke hari laen. Akhirnya td shift 6 dosen sisop ngalah dan mayoritas kelasnya kuliah grafkom. 

Akhirnya hari ini kuliah dari jam 11 siang ampe jam 9 malem!! *jam 1/2 9 ud pulang karena kuliah shift 6 – 7 ga ad istirahat*

Setau gua (dari informasi waktu POM), mahasiswa reguler itu jadwal kuliahnya dari jam 7 pagi ampe 7 malam, dan mahasiswa malam kuliahnya dari jam 3 ampe jam 9. 

Note buat yg ga tau: 

Shift 1 : 7.00 – 9.00

Shift 2 : 9.20 – 11.00

Shift 3 : 11.20 – 13.00

Shift 4 : 13.20 – 15.00

Shift 5 : 15.20 – 17.00

Shift 6 : 17.20 – 19.00

Shift 7 : 19.20 – 21.00

Semalam hanya tdr 5 jam, dari jam 5 pagi ampe jam 10an (maklum jam tdr eropa, waktu GMT , tinggalnya di daerah GMT +7) dan hari ini kuliah 10jam, mantap.

ZJU 3077 – Move to baggage office Januari 9, 2009

Posted by marcadian in Algo & Math.
Tags:
add a comment

Problem. This is a modified knapsack problem. One thing should remember that in real knapsack problem, the order of items doesn’t matter, but in this problem it does. 

Here is sample case:

S = 10

v1 10 9

v2 3 1

If the order like this then you can take both item, but if the order is the reverse you just can take one item. 10 – 3 + 1 < 10. So, what is the best order so that if we take item in that order, we are not lose other items ?

Lemma : Order by B value (input is v a b) descending is optimal ordering.

For example we have 2 items.

v1 a b1

v2 c b2

Where b1 > b2

Proof : Assume that this order is not optimal, then there is strength value, X where

X – a + b1 < c and X – c + b2 >= a

X + b1 < a+c and X + b2 >=  a + c, combine both equation, we have

X + b1 < a + c <= X + b2 , Substract with X

b1 < a + c – X <= b2

b1 < … <= b2, we conclude that b1 < b2 which contradict our assumption, therefore the order by decreasing of B value, is optimal. Here is the code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct
{
  int v,a,b;
}item;

bool operator<(item a,item b) { return a.b > b.b; }

int main()
{
  int s,t,n,b,v,a;
  item items[101];
  int best[1001];
  scanf("%d",&t);
  while (t--)
  {
    scanf("%d %d",&s,&n);
    for(int i=1;i<=n;i++)
      scanf("%d %d %d",&items[i].v,&items[i].a,&items[i].b);
    memset(best,-1,sizeof(best));
    sort(items+1,items+1+n);
    best[s] = 0;
    for(int i=1;i<=n;i++)
    {
      a = items[i].a;
      v = items[i].v;
      b = items[i].b;
      for(int j=0;j<=s+b-a;j++)
      {
        int temp = j + a - b;
        if (temp >= a && best[temp]!=-1)
          best[j] =  max(best[temp] + v, best[j]);
      }
    }
    printf("%d\n",*max_element(best,best+1+s));
  }
  return 0;
}

IOI 95 – Word Chains Januari 4, 2009

Posted by marcadian in Algo & Math.
Tags:
1 comment so far

Soal Trie lagi, kali ini diminta sequence katanya.Problem

(lagi…)

UVA 11488 – Hyper Prefix Sets Januari 4, 2009

Posted by marcadian in Algo & Math.
Tags:
add a comment

Another trie :D soal pertama di OJ yg AC pake trie, ini ga pake pointer2an cuma pake array 

(lagi…)

UVA 11539 – Another Word Game Januari 4, 2009

Posted by marcadian in Algo & Math.
Tags: ,
add a comment

Ok mari mulai ngepost source code kyk orang China, tp gua cm post yg menarik aja, ga bakal ada source code hello world sini :D

Karena baca di forum pada kena TLE untuk soal ini, jadi kali ini trienya pake pointer :P

(lagi…)