Kaksi taloudestaan tarkkaa kalastajaa suorittaa kalastamista yhdessä verkoilla. Päivän päätteeksi he jakavat saamansa kalat. Kalastajat ovat hyvin tarkkoja siitä, että kummallekin tulee mahdollisimman tarkkaan puolet kalojen arvosta. Kullakin kalalla on arvo ja jakamisen yhteydessä mitään kalaa ei voi osittaa, vaan jokainen kala päätyy kokonaisuudessaan jommalle kummalle kalastajalle. Usealla kalalla voi olla sama arvo. Sinun tehtävänäsi on tehdä ohjelma, joka jakaa kalat kahteen ``kasaan'' siten, että kalakasojen arvot ovat mahdollisimman lähellä toisiaan. Kalakasan arvo on kasassa olevien yksittäisten kalojen arvojen summa, ja tyhjän kasan arvo on 0.
Anna ohjelmallesi nimi TASAUS (.CPP, .C,
.PAS).
Syöttötiedoston TASAUS.IN (huomaa, että tiedoston
nimi on kokonaan isolla kirjoitettu) ensimmäisellä rivillä on
kalojen lukumäärä N. Jokaisella seuraavalla N:llä
rivillä on tasan yksi kokonaisluku. Tiedoston toisella rivillä on
ensimmäisen kalan arvo W1, kolmannella rivillä on toisen kalan
arvo W2, neljännellä rivillä kolmannen kalan arvo W3, ..., ja
tiedoston N+1:llä rivillä on N:nnen kalan arvo
WN. Kalojen arvojen ei tarvitse olla
suuruusjärjestyksessä.
Esimerkiksi, jos kaloja on 5 ja niiden arvot ovat 5, 8, 13, 14
ja 27, voisi tiedoston TASAUS.IN sisältö olla
seuraava:
5 8 5 13 27 14
Tulostiedostoon TASAUS.OUT kirjoitetaan yksi
kokonaisluku, joka on mahdollisimman pieni kalakasojen arvojen
eroituksen itseisarvo.
Ylläolevassa esimerkissä kalat voitaisiin jakaa kasoihin
siten, että niiden arvot ovat 5+13+14=32 ja 8+27=35, jolloin
kalakasojen arvojen eroituksen itseisarvo on abs(32 - 35) = 3.
Tuolloin tiedostossa TASAUS.OUT tulee olla:
3
Ohjelmaasi testataan useilla testisyötteillä ja jokaisesta voi saada 0 ... 10 pistettä. Testien tulokset summataan yhteen.
Jos ohjelmasi ei saa muodostettua tulostiedostoa aikarajan puitteissa tai tiedoston ensimmäisellä rivillä on jotain muuta kuin yksi kokonaisluku, saa ohjelmasi nolla pistettä kyseisestä testistä. Muutoin ohjelmasi saa 0 ... 10 pistettä seuraavien periaatteiden mukaan. Oletetaan, että kyseisen ongelman parhaassa mahdollisessa ratkaisussa kasojen arvojen erotuksen itseisarvo on x ja ohjelmasi tuottaa vastauksena arvon y. Jos y < x, saa ohjelmasi nolla pistettä -- eli liian pieni luku vie kaikki pisteet. Muussa tapauksessa ohjelmasi saa min(0, 10 - (y-x)), eli jokainen ylittävä arvoyksikkö vähentää yhden pisteen, mutta nollaa vähempää ei voi saada.
Testitapauksissa on vähintään kolme testiä, joissa N >= 15; ja vähintään puolet testitapauksista on sellaisia, joissa N <= 10.
Kuvankäsittelysovelluksen yhteydessä haluttaisiin selvittää, miten suorakaiteen muotoiset kuviot sisältyvät toisiinsa. Tässä tehtävässä tarkastellaan yksinkertaisuuden vuoksi vain viivasegmenttejä ja niiden sisältyvyyttä toisiinsa. Tässä tehtävässä kaikkien viivasegmenttien ajatellaan sijaitsevan samalla vaakasuoralla viivalla (voit ajatella sen vaikkapa X-akseliksi), jolloin niitä voidaan esittää alku- ja loppupisteen x-koordinanttiarvoilla. Aina alkupisteen koordinanttiarvo on pienempi kuin loppupisteen koordinanttiarvo. Kaikki koordinanttiarvot ovat kokonaislukuja väliltä -10000 ... 10000 (miinus kymmenentuhatta ... kymmenentuhatta).
Ajatellaan, että on kaksi viivasegmenttiä: A ja B. Olkoon viivasegmentin A alkupiste a1 ja loppupiste vastaavasti a2 (jolloin siis a1 < a2). Samoin viivasegmentin B alkupiste on b1 ja loppupiste b2 (ja tiedetään, että b1 < b2). Sanotaan, että viivasegmentti A on viivasegmentin B sisällä, jos A:n alku- ja loppupisteet ovat aidosti B:n alku- ja loppupisteen välissä, eli b1 < a1 < a2 < b2.
Tehtävässä ohjelmallesi annetaan N viivasegmenttiä, jotka on numeroitu 1 ... N. Sinun pitää määrittää pisin sellainen viivasegmenttien ketju, että jokaiselle ketjun viivasegmentille (paitsi viimeiselle) pätee, että kyseinen viivasegmentti sisältyy ketjun seuraavaan viivasegmenttiin.
Anna ohjelmallesi nimi VIIVAT (.CPP, .C, .PAS).
Syöttötiedoston VIIVAT.IN (huomaa, että tiedoston
nimi on kokonaan isolla kirjoitettu) ensimmäisellä rivillä on
viivasegmenttien lukumäärä N. Jokaisella seuraavalla
N:llä rivillä on tasan kaksi kokonaisluku yhdellä
välilyönnillä toisistaan eroitettuna. Tiedoston toisella rivillä
on ensimmäisen viivasegmentin alku- ja loppupisteet; alkupiste
ensin ja loppupiste sitten. Vastaavasti kolmannella rivillä on
toisen viivasegmentin alku- ja loppupisteet, neljännellä rivillä
kolmannen viivasegmentin alku- ja loppupisteet, ..., ja tiedoston
N+1:llä rivillä on N:nnen viivasegmentin alku- ja
loppupisteet. Viivasegmentit eivät ole missään erityisessä
järjestyksessä.
Esimerkiksi, jos viivasegmenttejä on 4 ja ne ovat [-2..2],
[-1..1], [-3..4] ja [5..6] voisi tiedoston VIIVAT.IN
sisältö olla seuraava:
4 -2 2 -1 1 -3 4 5 6
Tulostiedostoon VIIVAT.OUT tulee muodostaa
ensimmäiselle riville tasan yksi kokonaisluku, joka on pisimmän
muodostettavissa olevan sisäkkäisten viivasegmenttien ketjun
pituus. Jos ohjelmasi saa tällaiseksi vastaukseksi luvun
x, niin seuraavalla rivillä tulee olla kyseisen x:n
pituisen viivasegmenttiketjun viivasegmenttien numerot
sisäkkäisyysjärjestyksessä, alkaen sisimmästä ja päätyen siihen
viivasegmentiin, joka sisältää kaikki edelliset. Viivasegmenttien
numerot tulee eroittaa toisistaan yhdellä välilyönnillä. Jos
suurin pituus on saavutettavissa usealla viivasegmenttiketjulla,
niin riittää tulostaa niistä mikä tahansa.
Ylläolevassa esimerkissä toinen viivasegmentti (eli [-1..1])
sisältyy ensimmäiseen (eli segmenttiin [-2..2]), joka puolestaan
sisältyy kolmanteen segmenttiin ([-3..4]). Tuolloin tiedostossa
VIIVAT.OUT tulee olla:
3 2 1 3
Huomaa, että tulostiedoston toisella rivillä on ensin sisimmän viivasegmentin numero. Viivasegmenttien numerot luetellaan ketjun mukaisessa sisäkkäisyysjärjestyksessä ja viimeisenä on ketjun viimeisen viivasegmentin numero. Kyseinen segmentti sisältää kaikki ketjun edelliset segmentit.
Ohjelmaasi testataan useilla testisyötteillä ja jokaisesta ohjelmasi saa joko täydet pisteet tai nolla pistettä. Testien tulokset summataan yhteen.
Jos ohjelmasi ei saa muodostettua tulostiedostoa aikarajan puitteissa tai tulostiedoston muoto on jotenkin virheellinen, saa ohjelmasi nolla pistettä kyseisestä testistä. Jos ohjelmasi saa selville maksimaalisen muodostettavissa olevan ketjun pituuden ja tiedoston toisella rivillä olevien viivasegmenttien numerot muodostavat laillisen sisäkkäisten viivasegmenttien ketjun (joka on kyseistä pituutta), saa ohjelmasi täydet pisteet. Muutoin ohjelmasi saa nolla pistettä kyseisestä testistä.