Nizom čudnih događaja, članovi Komisije su postali vlasnici skladišta, u kojem se kutije drže poređane u niz. Svaki put kada se dostava pojavi da bi isporučila novu kutiju, potrebno je odlučiti da li će im se otvoriti prednja ili zadnja vrata, odnosno da li će kutija biti dodata na početak ili kraj niza.
Kada je potrebno izvaditi kutiju iz skladišta, član Komisije koji poslednji smisli razlog zašto baš on nema vremena mora da uđe na prednja vrata, pronađe traženu kutiju, iznese je i sredi skladište. Ako je kutija na poziciji , računato od početka niza (prva kutija je na poziciji ), ova operacija traje nanosekundi. Sređivanje uključuje "popravljanje" niza, tako da neće ostati prazno mesto (sve kutije nakon -te će se pomeriti za jedno mesto).
Pošto Komisija trenutno baš i nema vremena, zamolili su vas da preuzmete donošenje odluka tokom dostave. Dobili ste raspored za danas, u kom je dato vreme dostave i odnošenja svake kutije. Vaš zadatak je da odredite koliko je najmanje vremena potrebno provesti u vađenju kutija (u nanosekundama).
Opisi funkcija
Potrebno je da implementirate sledeću funkciju:
je broj kutija koje će tokom dana biti dostavljene u skladište (i kasnije izvađene), i su nizovi dužine u kojima je dat raspored -- je vreme dostave -te kutije (u minutima), a vreme kada će Komisija izvaditi istu kutiju iz skladišta.
Funkcija treba da vrati ceo broj -- vreme koje će Komisija provesti u skladištu (u nanosekundama), ako su dostave usmerene tako da je ovo vreme minimizovano. Svi nizovi su indeksirani od 0.
Primer
Neka je , i . Ovi parametri odgovaraju sledećem redosledu događaja:
- kutije 1, 2 i 3 se redom donose u skladište,
- kutije 1 i 3 (redom) se vade iz skladišta,
- kutija 4 se donosi, i
- kutije 4 i 2 se vade.
Optimalan raspored dostava je: kutije 1, 2 i 4 dostaviti na zadnja vrata, a 3 na prednja. U ovom slučaju, sve kutije osim 1 će biti prve u skladištu kada se vade, a kutija 1 će biti druga, tako da je ukupno vreme nanosekunda.
Ograničenja
- sve vrednosti i su međusobno različite
Podzadaci
- Podzadatak 1 [20 poena]:
- Podzadatak 2 [40 poena]:
- Podzadatak 3 [21 poena]:
- Podzadatak 4 [19 poena]: Nema dodatnih ograničenja
Detalji implementacije
Potrebno je da pošaljete tačno jedan fajl skladiste.cpp
koji
implementira pomenfutu funkciju. Osim tražene funkcije, vaš fajl može
sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne
biblioteke.
Vaša funkcija mora biti sledećeg oblika:
long long Resi(int N, int *A, int *B)
Vašim programima je dozvoljeno da menjaju sadržaj nizova/matrica, ali ne smeju da pristupaju van granica datih nizova.
Uz zadatak, obezbeđen vam je "template" fajl code.cpp
koje možete
koristiti i menjati po potrebi. Takođe vam je obezbeđen program
grader.cpp
koji služi da lakše testirate kodove. Ovaj program
učitava sa standardnog ulaza sledeće podatke:
- y prvom redu broj , i
- u narednih redova po dva broja: vrednosti i .
Zatim ovaj program zove vašu funkciju i štampa povratnu vrednost . Kodove ovih programa možete menjati po potrebi.
Comments