Kmet

PROBLEM 

Nek kmet ima množico polj, vsako od njih pa je obdano s cipresami. Isti kmet ima tudi nekaj podolgovatih pasov zemlje, na vsakem od njih pa so ciprese posajene v vrsti. Tako na poljih kot na pasovih je med vsakima dvema sosednjima cipresama zasajena tudi ena oljka. Drugih cipres ali oljk ta kmet nima.

Nekega dne je kmet hudo zbolel in začutil, da ne bo več dolgo živel. Nekaj dni pred smrtjo je poklical k sebi najstarejšega sina in mu dejal: »Dam ti katerihkoli Q cipres, ki si jih boš izbral, poleg njih pa še vse oljke, ki rastejo med kakšnima dvema izmed izbranih cipres.«  Načeloma lahko sin z vsakega polja in vsakega pasu izbere poljubno kombinacijo cipres. Ker ima najstarejši sin rad olive, bi rad tistih Q cipres izbral tako, da bo poleg njih podedoval tudi čim več oljk.

Polje 3 ima 8 cipres.

Polje 1 ima 13 cipres.

Polje 2 ima 4 ciprese.

Pas 1 ima 4 ciprese.

Pas 2 ima 8 cipres.

Pas 3 ima 6 cipres.

	

Slika 1. Primer razporeditve cipres; oljke niso narisane (na vsaki črti raste po ena).

Recimo, da so polja in pasovi takšna, kot jih prikazuje slika 1, in da bo sin dobil Q=17 cipres. Če hoče dobiti čimveč oljk, si mora izbrati vse ciprese s polj 1 in 2, tako da bo poleg cipres dobil še 17 oljk.

Napiši program, ki pri danih podatkih o poljih in pasovih in o številu cipres, ki jih mora sin izbrati, ugotovi največje možno število oljk, ki jih sin lahko podeduje.

VHODNI PODATKI

Ime vhodne datoteke je farmer.in. Prva vrstica vsebuje celo število Q, to je število cipres, ki jih mora sin izbrati; nato pa še celo število M (število polj) in celo število K (število pasov). Druga vrstica vsebuje M celih števil N1, N2,… NM, pri čemer je NI število cipres na polju I. Tretja vrstica vsebuje K celih števil R1, R2,… RK, pri čemer je RJ število cipres na pasu J.

IZHODNI PODATKI

Ime izhodne datoteke je farmer.out. V to datoteko izpiši eno vrstico, v njej pa eno celo število: največje možno število oljk, ki jih sin lahko podeduje.

PRIMER VHODA IN IZHODA

farmer.in						farmer.out

17 3 3
13 4 8
4 8 6

17

				

OMEJITVE

Pri vseh testnih primerih velja 0≤Q≤150000, 0≤M≤2000, 0≤K≤2000, za vsak NI tudi 3≤ NI ≤150 in za vsak RJ tudi 2≤ RJ ≤150. Skupno število cipres na vseh poljih in vseh pasovih je vsaj Q. Poleg tega je pri 50% testnih primerov Q≤1500.

Fidija

PROBLEM 

Slavni starogrški kipar Fidija se pripravlja na gradnjo še enega sijajnega spomenika. V ta namen potrebuje pravokotne marmorne plošče velikosti W1 ´ H1, W2 ´ H2, ..., WN ´ HN.  Uporabi lahko poljubno število plošč vsake od teh velikosti.

Fidija je dobil nek velik pravokoten kos marmorja. Rad bi ga razrezal, da bo dobil plošče želenih velikosti. Posamezne kose marmorja (bodisi prvotni kos ali pa manjše kose, dobljene s predhodnimi rezi) lahko prereže bodisi vodoravno po celi širini ali pa navpično po celi višini in tako dobi dva manjša kosa s celoštevilsko širino in višino. To je edini način rezanja, ki mu je na voljo, poleg tega pa kosov tudi ne more spajati skupaj. Ker so v marmorju vzorci, kosov ne sme vrteti: če dobi ploščo velikosti A ´ B, je ne more uporabiti kot ploščo velikosti B ´ A, razen če je A = B. Za vsako želeno velikost lahko uporabi poljubno število plošč (nič ali več). Če pa nek kos marmorja nima ene izmed želenih velikosti in oblik, ga bo treba zavreči. Fidijo zanima, kako razrezati prvotni kos marmorja tako, da ga bo šlo na koncu čim manj v odmet. 

Kot primer si mislimo, da je v spodnji sliki širina prvotnega kosa 21 enot, višina pa 11 in da so želene velikosti plošč 10 ´ 4, 6 ´ 2, 7 ´ 5 in 15 ´ 10. Najmanjša možna površina zavrženih delov je 10 in spodnja slika prikazuje eno od možnih zaporedij rezov, ki dosežejo izgubo s površino 10.

Napiši program, ki pri dani velikosti začetnega kosa marmorja in želenih velikostih plošč izračuna najmanjšo površino delov, ki jih bo treba zavreči.

VHODNI PODATKI

Ime vhodne datoteke je phidias.in. Prva vrstica vsebuje dve celi števili: najprej W, širino prvotnega kosa marmorja, nato pa še H, višino prvotnega kosa. Druga vrstica vsebuje eno celo število N: število želenih velikosti plošč. Naslednjih N vrstic vsebuje želene velikosti plošč. Vsaka od teh vrstic vsebuje dve celi števili: najprej širino Wi, nato pa še višino Hi tiste želene velikosti plošče (1 ≤ i ≤ N). 

IZHODNI PODATKI

Ime izhodne datoteke je phidias.out. Ta datoteka naj vsebuje eno vrstico, v njej pa eno celo število: najmanjšo skupno površino delov prvotnega kosa, ki jih bo treba zavreči. 

PRIMER VHODA IN IZHODA

phidias.in						phidias.out

21 11
4
10 4
6 2
7 5
15 10

10

				

OMEJITVE

Pri vseh testnih primerih velja 1 ≤ W ≤ 600, 1 ≤ H ≤ 600, 0 ≤ N ≤ 200, 1 ≤ Wi  ≤ W in 1 ≤ Hi ≤ H. Poleg tega pri 50% testnih primerov velja tudi W ≤ 20, H ≤ 20 in N ≤ 5.

Empodiji

PROBLEM 

Staroveški matematik in filozof Pitagora je verjel, da je narava realnosti matematična. Dandanašnji biologi preučujejo lastnosti biozaporedij. Biozaporedje je zaporedje M celih števil, ki:
•	vsebuje vsa števila od 0 do M–1, vsako natanko enkrat;
•	se začne z 0 in konča z M–1;
•	noben element ni natanko za 1 večji od svojega neposrednega predhodnika.
Strnjenim podzaporedjem biozaporedij pravimo segmenti.

Segmentu biozaporedja pravimo uokvirjen interval, če vsebuje vsa cela števila, ki so po vrednosti med vrednostjo prvega elementa (ki mora biti najmanjši element v tem segmentu) in vrednostjo zadnjega elementa (ki mora biti največji element v tem segmentu in mora biti različen od prvega elementa). Uokvirjenemu intervalu pravimo empodij, če ne vsebuje nobenega krajšega uokvirjenega intervala.

Za primer si oglejmo biozaporedje (0,3,5,4,6,2,1,7). Biozaporedje kot celota je že sámo uokvirjen interval. Vendar pa vsebuje tudi en manjši uokvirjen interval, (3,5,4,6), zato to biozaporedje kot celota ni empodij. Uokvirjeni interval (3,5,4,6) pa ne vsebuje nobenega krajšega uokvirjenega intervala, zato to je empodij. To je tudi edini empodij v tem biozaporedju.

Napiši program, ki poišče v danem biozaporedju vse empodije. 

VHODNI PODATKI

Ime vhodne datoteke je empodia.in. Prva vrstica vsebuje eno celo število M, to je dolžina vhodnega biozaporedja. Naslednjih M vrstic vsebuje vse elemente biozaporedja v takem vrstnem redu, v kakršnem se v zaporedju pojavljajo. Vsaka od teh M vrstic vsebuje po eno celo število. 

IZHODNI PODATKI

Ime izhodne datoteke je empodia.out. V prvo vrstico izpiši eno celo število H: število empodijev v vhodnem biozaporedju. Naslednjih H vrstic naj opisuje vse empodije v vhodnem biozaporedju, in sicer po naraščajočem indeksu začetka empodija.  Vsaka od teh vrstic naj vsebuje dve celi števili A in B (v tem vrstnem redu), ločeni s presledkom, pri čemer je A-ti element vhodnega biozaporedja prvi element empodija, B-ti element vhodnega biozaporedja pa je zadnji element empodija.

PRIMER VHODA IN IZHODA

empodia.in						empodia.out

8
0
3
5
4
6
2
1
7

1
2 5

OMEJITVE

Pri enem testnem primeru bo za velikost vhodnega zaporedja veljalo 1000000≤M≤1100000, pri vseh ostalih pa bo veljalo 1≤M≤60000. Pri 50% testnih primerov bo veljalo tudi M≤2600.