LATVIJAS REPUBLIKAS 12. INFORMĀTIKAS
OLIMPIĀDES III POSMA UZDEVUMI

1. "Šifrogramma Džeimsam Bondam"

Slavenajam aģentam 007 (Džeimsam Bondam) bija kāda literatūrā neaprakstīta rakstura iezīme. Ja viņš saņēma šifrogrammu, kas saturēja kādu noteiktu ciparu virkni, tad Dž.Bonds kļuva nervozs, kas uz kādu laiku ievērojami pazemināja viņa darbaspējas.

Par laimi, visas šādas ciparu virknes bija zināmas Viņa Karaliskās Augstības šifrēšanas dienesta vadītājam Mr X, kurš nodēvēja šādas virknes par "bīstamām". Bija zināms, ka visas bīstamās virknes satur ne mazāk kā trīs un ne vairāk kā deviņus ciparus. Lai lieki nekaitinātu superaģentu, Mr X ieteica rīkoties šādi – Džeimsam Bondam paredzētajā šifrogrammā atrast tādu bīstamo ciparu virkni, kura šifrogrammā sākas visvairāk pa kreisi un nosvītrot tās pirmo un pēdējo ciparu, tādējādi saīsinot šifrogrammas kopgarumu par diviem cipariem. Ja vienā šifrogrammas vietā sākas vairākas bīstamās virknes, tad ciparus nosvītrot īsākajā no tām. Pēc tam atkārtot šo darbību ar jauniegūto šifrogrammu un tā turpināt tik ilgi, kamēr iegūtajā šifrogrammā nav nevienas bīstamās ciparu kombinācijas.

Uzrakstiet datorprogrammu, kas realizē Mr X piedāvāto algoritmu.

Ievaddati

Ievaddatu faila SLIKTIE.DAT pirmajā rindā dota viena naturāla skaitļa k (k£ 10000) vērtība - bīstamo ciparu virkņu skaits. Katrā no nākošajām k faila rindām dota pa vienai bīstamajai ciparu virknei. Katras virknes garums ir ne mazāk kā trīs un ne vairāk kā deviņi cipari. Katra bīstamā virkne failā ir dota tieši vienreiz.

Ievaddatu faila BONDS.DAT pirmajā rindā dota ciparu virkne bez atdalošiem tukšumsimboliem – šifrogrammas sākotnējais saturs. Šifrogrammas garums ir vismaz 1 un ne vairāk kā 250 cipari.

Izvaddati

Izvaddatu failam BONDS.REZ jāsatur tikai viena rinda un tajā jābūt ciparu virknei – pārveidotās šifrogrammas tekstam.

Piemērs
Ievaddati (2 faili)                     Izvaddati                     Piezīme
(fails SLIKTIE.DAT) (fails BONDS.REZ) Pārveidošana notika
4                 325                             šādi: 3370250 ®
3702                                37250 ® 325
330
370
7250

(fails BONDS.DAT)
3370250


2. "Šķērsojot upi"

Aļaskas iedzīvotājam Džonam ceļā uz tuvāko pilsētu ir jāšķērso plata, neaizsalstoša upe.

Džons rīkojas pavisam vienkārši - iejūdz savus suņus kamanās, kamanām pieāķē laivu un dodas ceļā. Kad sasniegta upe, Džons sēžas laivā un pārceļ pāri visus suņus. Vienā no upes sķērsošanas reizēm Džons pieāķē kamanas pie laivas, un tā Džons ar visiem suņiem un kamanām veiksmīgi ir ticis pāri upei. Taču ne vienmēr tas ir tik vienkārši, kā varētu likties - daži suņi, kad Džons nav klāt, savā starpā ķildojas un tos upes šķērsošanas laikā nevar atstāt vienā krastā bez uzraudzības. Savukārt, tos suņus, kuri savā starpā neķildojas, var droši atstāt jebkurā krastā un nekas slikts nenotiks. Par laimi, Džons zina, kuri suņi savstarpēji nesatiek.

Gadās, ka Džona pajūgā ir pieci suņi - Viesulis, Lācis, Brīnums, Niknais un Argots. Lācis ķildojas ar Viesuli, Nikno un Argotu. Brīnums ķildojas ar Viesuli un Nikno. Citi suņi savā starpā neķildojas. Tad Džonam pietiek ar trīsvietīgu laivu, t.i., vienā upes šķērsošanas reizē viņš var pārvest divus suņus. Turklāt mazākais upes šķērsošanu skaits ar šādu laivu ir 7 (katrs suns aizņem vienu vietu, kamanas vietu neaizņem):
pārved pāri Lāci un Brīnumu;‚Lāci pārved atpakaļ;ƒpārved pāri Argotu un Lāci;
„pārved Lāci un Brīnumu atpakaļ;…pārved pāri Nikno un Viesuli; †atpakaļ pārbrauc tukšā;‡pārved pāri Lāci un Brīnumu, un turpina ceļu.

Nevienā brīdī vienā krastā bez uzraudzības nav atstāti divi savstarpēji ķildīgi suņi. Savukārt, ja savā starpā ķildotos vēl arī Argots un Viesulis, tad jau vairs ar trīsvietīgu laivu nepietiktu.

Uzrakstiet programmu, kas dotajam suņu skaitam un dotajām attiecībām starp suņiem aprēķina mazāko vietu skaitu laivā, ar kuru var pārvest pāri upei visus suņus, un atrod kādu suņu pārvešanas ar šādu laivu plānu. Papildus punkts tiks piešķirts, ja atrastais upes šķērsošanu skaits būs mazākais iespējamais.

Ievaddati

Faila UPE.DATpirmā rinda satur vienu naturālu skaitli N (1 £ N £ 10) - suņu skaitu pajūgā. Uzskatiet, ka suņi ir sanumurēti ar skaitļiem 1,2,3,…,N. Otrā rinda satur veselu nenegatīvu skaitli K, kas raksturo ķildīgo suņu pāru skaitu. Nākamās K rindas satur pa vienam ķildīgo suņu pārim formā "a b", kur a un b ir suņu numuri (1 £ a, b £ N, a ¹ b). Starp numuriem ir tukšumsimbols.

Ir uzrādīti visi ķildīgo suņu pāri, katrs pāris ir minēts tieši vienreiz. Noteiktam suņu pārim atbilst gan pieraksts “a b”, gan “b a”, bet failā ir tikai viens no tiem.

Izvaddati

Faila UPE.REZpirmajai rindai jāsatur viens naturāls skaitlis X - mazākais laivā nepieciešamo vietu skaits, lai varētu suņus pārvest pāri upei iepriekš aprakstītajā veidā. Faila otrajā rindā jābūt vienam naturālam skaitlim Y- upes šķērsošanu skaitam, kāds nepieciešams, lai ar X-vietīgu laivu pārvestu pāri upei visus suņus iepriekš aprakstītajā veidā. Nākamajām Y rindām katrai jāraksturo vienu upes šķērsošanu pareizā secībā. Faila i+2. rinda raksturo i-to pārbraucienu un ir formā:

a1 a2 a3 … aj 0

, kur a1 a2 a3 … aj ir to suņu, kuri i-tajā šķērsošanas reizē ir jāved pāri upei, numuri augošā secībā. Katri divi blakus numuri jāatdala ar tukšumsimbolu. Katras rindas beigās jābūt 0, kas no pēdējā numura atdalīts ar tukšumsimbolu. Pārbraucienu ar tukšu laivu apzīmē rinda, kurā ir tikai simbols 0.

Piemērs
Ievaddati (fails UPE.DAT)     Izvaddati (fails UPE.REZ)
5                 3
5                 7
1 2               2 4 0
2 3               2 0
4 3               1 2 0
4 5               2 4 0
2 5               3 5 0
                  0
                  2 4 0


3. "Spoku pils"

Taisnstūrveida spoku pilij, kurā ir NM istabas, kopš neatminamiem laikiem ir spēkā sekojoši likumi:

  1. ceļinieks no ārpuses var nonākt tikai istabā ar koordinātām (1;1)
  2. izkļūt no spoku pils var tikai tad, ja izdevies nonākt istabā ar koordinātām (N;M);
  3. katrā pils istabā uz grīdas ar krītu ir uzrakstīts maģiskais skaitlis - kāds naturāls skaitlis no 1 līdz 13;
  4. ceļinieks var iedomāties vienu no astoņiem virzieniem (paralēli pils ārmalām vai pa diagonālēm) un tūlīt kā vēja plēsts viņš tiek pārvietots iedomātajā virzienā tik istabas tālāk, kāds bija šajā istabā uzrakstītais maģiskais skaitlis. Ja tas nav iespējams (šajā virzienā tik daudz istabu nemaz nav), tad nekas nenotiek, un ceļiniekam, lai nokļūtu kur citur, jāiedomājas cits virziens.
  5. divreiz pēc kārtas pārvietoties vienā un tajā pašā virzienā nevar.
Piemēram, ja ceļiniekam izdevies nokļūt pils (kurā ir 54 istabas un kuras plāns redzams zīmējumā) istabā ar koordinātām (3;3), tad ar vienu pārvietošanos ir iespējams nokļūt tikai istabās (1;1), (3;1), (1;3), (5;1) un (5;3). Savukārt, lai no istabas (3;2), izdarot tikai divas pārvietošanās, nokļūtu istabā (5;4) (tikai nonākot šajā istabā, var izkļūt no pils), nevar pirmajā reizē pārvietoties uz (4;3) (jo tad nākošreiz vajadzētu vēlreiz pārvietoties tajā pašā virzienā - ko darīt nevar), bet vispirms jāpārvietojas uz (2;1).

Uzrakstiet programmu, kas dotam pils plānam nosaka, kāds ir mazākais pārvietošanos skaits, lai ceļinieks no istabas (1;1) nokļūtu istabā (N;M), ievērojot visus pilī spēkā esošos likumus.

Ievaddati
Teksta faila PILS.DAT pirmajā rindā dotas divu naturālu skaitļu N un M vērtības - istabu skaits plānā horizontālā un vertikālā virzienā (1£N,M£100).
Katrā no nākošajām M rindām doti N naturāli skaitļi - attiecīgajā istabu rindā uz grīdas uzrakstīto skaitļu vērtības.
Faila i+1-ajā rindā ir dota informācija par plāna i-to istabu rindu.
Katrā faila rindā starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.

Izvaddati
Teksta faila PILS.REZ pirmajā rindā jāizvada viens naturāls skaitlis - mazākais nepieciešamais pārvietošanos skaits.
Ja istabā ar koordinātām (N;M) dotajam pils plānam nonākt nav iespējams, teksta faila PILS.REZ pirmajā rindā jāizvada vārds NEVAR.

Piemērs
Ievaddati(fails PILS.DAT)       Izvaddati(fails PILS.REZ)
5 4                 4
3 3 6 7 11
3 2 1 1 3
3 2 2 1 1
2 1 2 2 1


4. "Gudrības akmeņi"
 
 
Arheologs Lāpsta jau vairākus gadus nodarbojas ar gudrības akmeņu izpēti. Katrs gudrības akmens ir kubs, kuram uz katras skaldnes uzzīmēta bulta, kas vērsta vai nu pret malu, vai arī pret virsotni. Katru atrasto gudrības akmeni Lāpsta nofotografē no trim dažādām pusēm, iegūstot trīs fotoattēlus - skatus. Vienam akmenim katrā skatā virsotne, kura ir kopīga visām redzamajām skaldnēm, ir cita (par šo virsotņu savstarpējo izvietojumu nekas nav zināms). Viens šādu attēlu komplekts ir redzams 1.zīmējumā.
1.zīmējums. Trīs viena akmeņa skati.
2.zīmējums. Bultu apzīmējumi.
Lai ievadītu informāciju par katru gudrības akmeņa skatu datorā, Lāpsta ir izstrādājis noteiktu sistēmu :
Pirmkārt, katru iespējamo bultu Lāpsta ir apzīmējis ar citu ciparu, kā redzams 2.zīmējumā.
Otrkārt, katram gudrības akmeņa skatam Lāpsta pielieto 3.zīmējumā redzamo transformāciju, kur ai*apzīmē bultiņai ai atbilstošo ciparu saskaņā ar 2.zīmējumā redzamo kodējumu. Tādējādi katram skatam tiek iegūts atbilstošs trīsciparu skaitlis - skata kodējums. Pirmajā zīmējumā redzamo skatu kodējumi ir 833, 286 un 878.
Lāpsta ir nolēmis pāriet uz citu gudrības akmeņu kodēšanas sistēmu un no katriem trim iegūtajiem skatiem iegūt 4.zīmējumā redzamās formas akmeņa virsmas izklājumu un kodēt to kā sešciparu skaitli ,izmantojot 2.zīmējumā redzamo bultiņu kodējumu ar cipariem. Protams, vienam un tam pašam akmenim var būt dažādi kodējumi, jo, piemēram, 1.zīmējumā redzamajiem skatiem atbilst 5.zīmējumā redzamie izklājumi (pie kam tie ir tikai daži no iespējamajiem). Šo izklājumu kodējumi pēc Lāpstas sistēmas ir : 436746, 181228 un 784218.

3.zīmējums. Skata trīsciparu kodējuma iegūšana.
4.zīmējums. Izklājuma forma.5.zīmējums. Izklājumu paraugi.
Diemžēl, pārvācoties uz jauno laboratoriju, gudrības akmeņu skatu kolekcijas secība var būt sajaukta, tādēļ iespējams, ka šādu virsmas izklājumu no trīs skatiem iegūt nebūs iespējams.

Uzrakstiet programmu, kas nosaka, vai trīs dotie gudrības akmeņu skati var atbilst vienam un tam pašam akmenim, un, ja tā, tad atrod vienu akmeņa virsmas izklājuma kodējumu.

Ievaddati
Teksta failam AKMENS.DAT ir trīs rindas. Katrā rindā ir dots naturāls trīsciparu skaitlis - viena gudrības akmeņa skata kodējums.

Izvaddati
Ja dotie gudrības akmeņu attēli var būt viena akmeņa skati, tad teksta faila AKMENS.REZ pirmajā rindā jāizvada sešciparu naturāls skaitlis - viens no šī gudrības akmeņa virsmas izklājuma iespējamajiem kodējumiem. Ja dotie attēli nevar būt viena gudrības akmeņa trīs skati, tad teksta faila AKMENS.REZ pirmajā rindā jāizvada viens vārds NAV.

Piemērs
Ievaddati (fails AKMENS.DAT)      Izvaddati (fails AKMENS.REZ)
833                   181228
286
878



Mājup Uz uzdevumu un testu arhīvu