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
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
Taisnstūrveida spoku pilij, kurā ir N“M istabas, kopš neatminamiem laikiem ir spēkā sekojoši likumi:
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
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. |
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