Twix
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 3 s | 1000 Mb | standardni izlaz | standardni ulaz |
Nekada je postojala jedna fabrika koja je proizvodila Twix čokoladice, ali se kasnije podelila u dve. Sada jedna proizvodi levi a druga desni Twix. Da bi se napravila jedna čokoladica potrebno je N koraka pa svaka fabrika ima N stanica na kojima se ti koraci izvršavaju. Korak “i” se na dva načina može žavršiti, na način leve ili na način desne fabrike. Na primer, Twix je moguće preliti karamelom (leva fabrika) ili politi karamelom (desna fabrika). Ako je poznato koliko traje svaki korak u svakoj fabrici, javlja se pitanje za koliko je najbrže moguće napraviti Twix čokoladicu ukoliko se vlasnici fabrika pomire i dogovore da se u proizvodnji čokoladice mogu kombinovati stanice iz obe fabrike. Naravno, poznata su i vreme koje je potrebno da se kolač (u pripremi) prebaci iz jedne stanice u u jednoj fabrici u sledeću stanicu u drugoj fabrici.
Prvi red sadrži jedan ceo broj N koji označava broj stanica
Drugi red sadrži 2 cela broj S1[0] i S2[0], koji označavaju vreme trajanje prve stanice u svakoj fabrici.
Narednih N-1 redova sadrže po 4 cela broja:
S1[i] - vreme trajanje stanice i u prvoj fabrici
S2[i] - vreme trajanja stanice i u drugoj fabrici
P12[i] - vreme potrebno da se prebaci kolač iz i-1 stanice u prvoj fabrici u i-tu stanicu u drugoj fabrici
P21[i] - vreme potrebno da se prebaci kolač iz i-1 stanice u drugoj fabrici u i-tu stanicu u prvoj fabrici
Potrebno je ispisati najkraće vreme potrebno da se napravi Twix čokoladica.
N < 10 000 000
S[i] < 1000
3
1 4
5 2 1 1
1 2 1 3
6
Čokoladica se najbrže može napraviti tako što proizvodnja počne u fabrici 1, prođe prvu stanicu, zatim se prebaci u fabriku 2 i u fabrici 2 prođe kroz drugu i treću stanicu.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.