KSP.sk

Korešpondenčný seminár z programovania

Priklady 4. kola

Mili nasi riesitelia,

na uvod by sme sa chceli ospravedlnit za to, ze ste na zadania museli tak dlho cakat. Casu na riesenie vam vsak nechame dost - riesenia by ste nam mali poslat (a nezabudnut dake tie znamky) do 31. maja. Tych, co by si radi zariesili aj nieco "akcnejsie", by sme radi upozornili na IPSC (http://www.st.fmph.uniba.sk/www/csp/ipsc).

KSPaci
  1. O Kiribatskej mape
  2. O tajnej sluzbe
  3. O Danovej kostre
  4. Lalco lyziarom
  5. O profesorovi Indigovi a vile Amalke IV

1. O Kiribatskej mape

Kiribatsky kral KIRI-KIRI investoval obrovske peniaze do vesmirneho programu, a to mu vytykaju vsetci jeho odporcovia. Aby utisil hlas nespokojneho ludu, KIRI-KIRI sa rozhodol, ze vyriesi legendarnu otazku o pocte Kiribatskych ostrovov. A tak si dal urobit satelitny snimok s obrovskym rozlisenim na ktorom sa da rozoznat, kde je more a kde je sus. Napiste pre KIRI-KIRIho program, ktory mu spocita kolko ostrovov ma Kiribatske suostrovie. Vzhladom na velky rozmer mapy si nemozete pamatat celu mapu, ale iba niekolko riadkov z nej.

Uloha: Vas program ma k dispozicii vstupny subor. Tento subor na prvom riadku obsahuje dve cele cisla M, N, kde M je pocet riadkov a N pocet stlpcov mapy. Nasleduje M riadkov, kazdy z nich obsahuje N znakov 0 a 1, kde 0 oznacuje more a 1 sus.

Pocet riadkov nie je nijako zhora obmedzeny (M*N moze byt omnoho viac ako velkost dostupnej pamati), ale mozete predpokladat, ze niekolko riadkov sa do pamati zmesti. Vystupom vasho programu ma byt pocet ostrovov v suostrovi. Poznamka: Ostrovy sa mozu dotykat rohmi.

Priklad:
Vstup:

5 5

01000

11100

01000

00111

Vystup:
Kiribatske suostrovie ma 2 ostrovy.

2. O tajnej sluzbe

Nemenovana tajna sluzba dostala prikaz monitorovat pohyb podozrivych osob. Sledovane osoby by samozrejme nemali tusit, ze ich niekto sleduje. Na tento ucel vymyslel riaditel onej tanej sluzby system SPS - satelitny pozorovaci system.

Kazdy satelit systemu SPS ma schopnost sledovat obdlznik uzemia s rozmermi a x b. Kvoli stabilite satelitu musi byt tento obdlznik otoceny stranou a vo vychodozapadnom a stranou b v severojuznom smere. Pre kazdu sledovanu osobu agenti tajnej sluzby zistili polohu dolezitych objektov, v ktorych sa obvykle zdrziava. Je v statnom zaujme, aby vsetky objekty, v ktorych sa mozu nachadzat podozrive osoby, boli ostro sledovane. Satelity SPS su vsak pomerne drahe, preto sa riaditel rozhodol rozmestnit ich tak, aby ich potreboval co najmenej. Coskoro bude musiet predlozit navrh rozpoctu na buduci rok, velmi rychlo by teda potreboval vediet, kolko tych satelitov vlastne potrebuje.

Uloha: Napiste program, ktory nacita rozmery uzemia, pozorovaneho jednym satelitom, pocet sledovanych objektov n a suradnice vsetkych objektov (x[1],y[1]), ... (x[n],y[n]) a vypise, kolko najmenej satelitov je treba na to, aby kazdy objekt bol pozorovany aspon jednym satelitom.

Poznamka: Satelit sleduje obdlznik aj s okrajom.

Priklad:
Vstup
a = 2, b = 1.5
0.0 1.0
-1.0 0.0
1.0, 0.0
0.0 -1.0

Vystup
Treba minimalne 2 satelity.

3. O Danovej kostre

Dano je student - zoznamte sa - pred rokom odisiel studovat do Ameriky. Chudak, vtedy este netusil, ako je tam draho. Stipendium, ktore mal rozplanovane az do leta, minul uz teraz. Za posledne dva dolare si kupil plechovku piva a sadol si na lavicku do parku. Tam si ho vsimol "podnikatel" Johnny, ktory hned pochopil v akej situacii sa Dano ocitol. Johnny ponukol Danovi, ze od neho odkupi kosti, jeho vlastne kosti, za $30 kus (ti chlapici dnes uz obchoduju so vsetkym).

Dano hned na druhy den zabehol na rontgen. Tam zistili, ze Dano sa sklada z N uzlovych bodov ocislovanych od 1 po N, ktore su navzajom poprepajane kostami. Kazda kost spaja dva uzlove body. Dalej je kazda kost charakterizovana svojou hrubkou. Ked Dano videl ten obrovsky kapital, ktory v sebe nosi, zaleskli sa mu oci stastim a rozhodol sa, ze niektore kosti predsa len preda. Stanovil si vsak dve podmienky:

  1. Kazde dva uzlove body jeho tela musia ostat prepojene, teda musi existovat cesta (po kostiach) od kazdeho uzloveho bodu do kazdeho ineho uzloveho bodu.
  2. Najtensia kosticka, ktora Danovi ostane bude najhrubsia mozna (vzhladom na prvu podmienku).
Teda Dano chce, aby ostal suvisly a aby najkrehsia cast jeho kostry bola co najpevnejsia - logicke, nie?

Uloha: Dano si podla rontgenu vyhotovil zoznam svojich kosti. Tento zoznam udava pre kazdu kost, ktore dva uzlove body spaja a aku ma hrubku. Pomozte chudakovi Danovi, ktory na take mnozstvo udajov nestaci. Poradte mu, ktore kosti ma predat, tak aby zarobil co najviac a pritom dodrzal vsetky podmienky, ktore si stanovil.

Poznamka: Este nieco - Dano je skvely programator, neprijme hocaky algoritmus! Pokuste sa vyriesit ulohu co najefektivnejsie - najlepsie v casovej zlozitosti porovnatelnej s poctom kosti.

Vstup:
N=5
z 1 do 2 hrubka 10
z 2 do 3 hrubka 6
z 2 do 4 hrubka 3
z 3 do 5 hrubka 7
z 4 do 5 hrubka 7
z 3 do 4 hrubka 8

Vystup:
Predaj kosti:
z 2 do 4
z 3 do 4

Minimalna hrubka: 6

4. Lalco lyziarom

Lalco vsetko bol. Raz bol dokonca lyziarom. Ako tak schadzal snehove plane, vhupla mu do hlavy myslienocka: "Mozno keby som sa vyviezol este dvoma vlekmi a az potom zisiel dolu druhou stranou kopca, bolo by toho lyzovania viac ako statia v radoch na vleky. Ale keby som sa vyviezol radsej hentymi troma vlekmi..."

A tak tam stal na Alpskom gruni a hutal, ktorymi vlekmi sa ma vyviest a po ktorych zjazdovkach potom zist dolu, aby dosiahol co najlepsi pomer casu na zjazdovkach a casu na vlekoch. Nakoniec to aj vyhutal. Podari sa to aj vam?

Uloha: V Alpach je n lyziarskych stanovist, m zjazdoviek a k vlekov. Zjazdovky aj vleky vzdy vedu medzi nejakymi lyziarskymi stanovistami, zjazdovky vzdy z vyssie polozeneho do nizsie polozeneho a vleky z nizsie polozeneho do vyssie polozeneho. Na vstupe su zadane 3 cele cisla n,m,k. Nasleduje m+k trojic celych cisel. Prvych m trojic popisuje zjazdovky (z ktoreho do ktoreho stanovista vedu a trvanie zjazdu), dalsich k trojic popisuje vleky (z ktoreho do ktoreho stanovista vedu a ako dlho trva cakanie a vyvoz vlekom). Spravna trasa sa sklada z dvoch faz: v prvej faze sa Lalco z nejakeho stanovista vyvezie niekolkymi vlekmi, v druhej faze sa niekolkymi zjazdovkami spusti naspat do stanovista, z ktoreho vyrazil. Ulohou vasho programu je vypisat trasu, ktora ma najvyssi pomer medzi casom stravenym na zjazdovkach a casom stravenym na vlekoch.

Priklad:
Vstup:
n=5, m=4, k=3
zjazdovky:
z 1 do 3, 12min
z 2 do 3, 6min
z 3 do 4, 9min
z 5 do 4, 9min

vleky:
zo 4 do 5, 12min
z 5 do 1, 12min
zo 4 do 2, 18min

Vystup:
trasa: 4, 5, 1, 3, 4 (pomer 0.875)

5. O profesorovi Indigovi a vile Amalke IV

 Profesor Indigo robil na svojom pocitaci PP Amalka Inside pomerne rozsiahle upravy. Konkretne sa mu podarilo k pocitacu pripojit rozhranie pre ciernu skrinku. Cierna skrinka je zariadenie, ktore vie pocitat nejaku funkciu. Napriklad cierna skrinka pre funkciu function cudo(x,y): integer pocitajucu x+y^2 pre zadany vstup x=2, y=3 vrati hodnotu 11. Profesora ale zaujimaju prefikanejsie cierne skrinky, take, ktore reprezentuju orientovane grafy. Pripojenim takejto ciernej skrinky ziska pocitac pristup k dvom funkciam: 
function pocet_vrcholov: integer;
function hrana(a,b : integer): boolean;
Funkcia pocet_vrcholov vracia pocet vrcholov grafu n (vrcholy su cislovane 1,2,... n), funkcia hrana(a,b) vracia true prave vtedy, ak z vrchola a do vrchola b vedie hrana (nemusi platit hrana(a,b) = hrana(b,a)). Obe funkcie vracaju vysledok okamzite, t.j. v jednotkovom case. Pre ine programovacie jazyky si vhodne definicie lahko domyslite sami.

Prirodzene, kazdemu grafu prinalezi vlastna cierna skrinka. Profesorovi k uspesnemu vedeckemu vyskumu chyba uz len jedina malickost: Pre graf dany ciernou skrinkou zistit, ci sa da dostat z kazdeho vrchola do kazdeho.

Neprijemne je, ze pocet vrcholov je obvykle velmi velky a PP Amalka Inside ma obmedzenu pamat (aby sa do pocitaca zmestila cierna skrinka, musel profesor vybrat vacsinu pamatovych modulov).

Uloha: Napiste program pre PP Amalka Inside, ktory (nebude mat ziadny vstup) skonci s vysledkom ano, ak dana cierna skrinka popisuje graf s uvedenou vlastnostou. V opacnom pripade vsetky moznosti vetvenia vypoctu musia viest k odpovedi nie. Snazte sa minimalizovat pamatove naroky. Na tom, ako dlho bude vypocet trvat, vobec nezalezi. Predpokladajte, ze pocet_vrcholov sa akurat zmesti do premennej typu integer, resp. int (2*pocet_vrcholov sa uz nezmesti).

Poznamka: Skuste porozmyslat nad tym, kolko pamate potrebujete na pocitaci PP Amalka Inside a kolko by ste potrebovali, ak by ste nemali k dispozicii sluzby vily Amalky.

1999, Organizers of the CSP
Podporte nás

Účet

Prihlasovanie už nefunguje. Používaj nový KSP web.
 
loading

Redirecting