Primer rešene naloge

Zvezde

Piše se leto 2012 in Nejc, ki takrat še ni vedel, da bo nekaj let kasneje mentor na letošnjem taboru, je v vroči poletni noči na domačem travniku zrl v zvezde in si predstavljal, kako navdušujoče bi bilo obiskati vesolje. Pohitel je domov in na list papirja narisal raketo, ki bi ga ponesla med zvezde. Nekoliko poenostavljena raketa, v kateri je prostora le zanj, je izgledala nekako tako:

     *
    ***
   *****
  *******
 *********
***********
***********
***********
***********
***********
***********
***********

Na taboru je več mentorjev, vendar leta 2012 še ni mogel vedeti, koliko natanko. Predpostavimo, da se raketa poveča glede na število mentorjev v raketi. Vsak mentor širini rakete doda 4 enote.

Pomagaj Nejcu narisati dovolj veliko raketo za vse mentorje, tako da napišeš program, ki vpraša za število mentorjev, nato pa izriše dovolj veliko raketo.

Rešitev

Najprej pokažimo primer rešitve v psevdokodu:

Vhod: Preberi število mentorjev v spremenljivko m

Izračunaj širino vrha rakete:
    višina_vrha = (m - 1) * 2 + 6

Zanka za izris vrha rakete:
    za i od 0 do višina_vrha - 1:
        izračunaj število presledkov = višina_vrha - i - 1
        izračunaj število zvezdic = 2 * i + 1
        izpiši (presledki * " ") + (zvezdice * "*")

Zanka za izris trupa rakete:
    za i od 0 do višina_vrha - 1:
        izpiši (2 * višina_vrha - 1) zvezdic

Sledi rešitev v programskem jeziku Python:

n = int(input("Stevilo mentorjev: "))
n = (n-1)*2+6

for i in range(n):
    print(" " * (n - i - 1) + "*" * (2 * i + 1))
for i in range(n):
    print("*" * (n*2 - 1))

1. naloga

Armstrongova števila

Ekipa mentorjev se pripravlja na vzlet iz skrivnega vesoljskega centra v Gorenju. Ob čakanju na zadnje odštevanje debata nanese na pionirje, ki so jim omogočili ta zgodovinski polet. Razvname se debata o programu Apollo. Matematični navdušenci kakršni so, ob omembi Neila Armstronga takoj pomislijo na matematika Armstronga in njegova narcistična števila.

Število z n števkami je Armstrongovo oz. narcistično, kadar je seštevek potenc individualnih števk enak samemu številu.

$$abcd... = a^n + b^n + c^n + d^n + ...$$

Pomagaj jim napisati program, ki kot vhod prejme poljubno pozitivno število x in vrne 1, če je število Armstrongovo, v nasprotnem primeru pa 0.

2. naloga

Vračilo denarja

Hitro po tem, ko so zapustili svoje osončje, je ekipa naletela na vesoljsko plovilo neznanega izvora. Komunikacija ni bila ravno preprosta, vendar so kaj kmalu uspeli ugotoviti, da gre za trgovsko ladjo. Napiši funkcijo, ki simulira obnašanje blagajne in bo mentorjem olajšala trgovanje v vesolju.

Funkcija naj prejme dve števili:

Funkcija mora:

  1. Preveriti, ali je plačilo zadostno.
  2. Če denarja ni dovolj, naj vrne obvestilo, koliko denarja še manjka.
  3. Če je denarja dovolj, naj vrne seznam bankovcev in kovancev, s katerimi naj blagajna vrne razliko, in sicer z najmanjšim možnim številom enot.

Uporabiti smeš sledeče enote: [100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]

Primeri

vrni_denar(13.37, 20)
# Izpis:
# {'5': 1, '1': 1, '0.5': 1, '0.1': 1, '0.02': 1, '0.01': 1}

vrni_denar(15.99, 15)
# Izpis:
# 'Premalo denarja! Manjka še 0.99 €'

3. naloga

Vesoljska slovnica

Po uspešno zaključeni izmenjavi surovin, je ekipa želela nadaljevati z nadgradnjo njihovega univerzalnega prevajalnika, saj bo komunikacija ključnega pomena za nadaljevanje misije. Pomagaj jim napisati program, ki prebere poljubno besedo in izpiše, najmanj koliko črk je potrebno odstraniti, da beseda postane palindrom.

Primer

Odstraniti moramo najmanj 1 črko, da iz besede baba dobimo palindrom bab.

baba
1

4. naloga

Leto 2052 - Vesoljska postaja Raj

S prijatelji ste se po kratki vesoljski vožnji ravno vkrcali na vesoljsko postajo, kjer boste preživeli počitnice. Na poti v sobe srečate zaskrbljenega možakarja, ki se vidno poti in nestrpno gleda v prazno. Pogled usmeri k vam: "Kaj bomo zdaj? Sistem za dostavo pošte se je pokvaril! Z ekipo AI inženirjev se trudimo že dve uri, vendar algoritma nikakor ne uspemo vajbniti!". Na vaših majicah opazi simbol Poletnega tabora računalništva in reče: "Vi ste stara šola, mogoče nas vi rešite in pripravite delujoč algoritem?".

Algoritem

Poštni vesoljski čoln vozi do Zemlje in nazaj. Ekipe poštarjev čoln skrbno natovarjajo s paketi. Vsak paket ima določeno prostornino in plačilo, ki ga pošiljatelj ponuja za dostavo. Vesoljski čoln ima omejitev največje skupne prostornine tovora: največ 100 zvezdnih kubikov. Manjša prostornina paketa torej pomeni več hkrati dostavljenih paketov. Poštna služba skuša izbirati pakete tako, da bo čimvečji izkopiček (zaslužek), tudi če včasih to pomeni manjše število dostavljenih paketov.

Napiši algoritem, ki pametno izbere pakete iz nabora vseh paketov tako, da je skupna vsota plačil najvišja.

Vhod

V prvi vrstici prebereš število čakajočih paketov. Za vsakega sledi svoja vrstica iz dveh številk: prva je prostornina paketa, druga pa plačilo. Ne pozabi, da je prostornina čolna omejena na 100 enot, ni pa nujno, da je vesoljski čoln napolnjen v celoti, da se to finančno najbolj izplača.

Primer vhoda

> 6
30 10
40 25
50 40
20 10
50 30
5 5

Izhod

Izpiši zaporedne številke naloženih paketov v eni vrstici ločeno s presledki. Prvi paket ima zaporedno številko 0. Vrstni red izpisa številk ni pomemben.

Primer izhoda

> 2 1 5

5. naloga

Porazdeljena ohromitev vesolja

Mentorji se pripravljajo na pot nazaj na Zemljo, da se lahko pripravijo na tabor. Preko vesoljskega omrežja že pošiljajo prijavnice vsem predhodnim in novim potencialnim udeležencem. Na žalost pa so vesoljski pirati sprožili napad na vesoljsko omrežje, zato se naša ekipa boji, da prijavnice ne bodo prispele pravočasno!

Ta visoko sofisticiran napad deluje s poplavljanjem visokega števila brezpredmetnih sporočil proti Zemlji, ki nato zasičijo kvantne vesoljske povezave in s tem preprečijo prenos pomembnih podatkov. Naša ekipa ima na voljo topologijo tega vesoljskega omrežja, ki je sestavljena iz vozlišč in kvantnih povezav z določeno kapaciteto.

Če jim uspe najti povezave, ki se pri tem napadu popolnoma zasičijo, lahko to informacijo posredujejo Vesoljskemu centru, ki bo nato lahko ukrepal.

Naloga

Topološki podatki vsebujejo seznam:

Prvih s vozlišč v seznamu so vozlišča, ki jih napadalci uporabljajo za pošiljanje sporočil, medtem ko zadnje vozlišče predstavlja Zemljo, kamor pošiljajo ta brezpredmetna sporočila.

Najdi povezave, ki se pri tem napadu popolnoma zasičijo, in njihovo skupno kapaciteto.

Primer vhodnih podatkov:

6 8 2
0 1 4
0 3 1
1 2 1
1 3 1
2 4 3
2 5 2
3 4 3
4 5 4

Ta topologija vsebuje 6 vozlišč in 8 povezav. Napadalci pošiljajo podatke iz prvih dveh vozlišč (0 in 1) in na zadne vozlišče (5). V tem primeru se popolnoma zasičijo povezave 0,3, 1,2 in 1,3, katerih skupna kapaciteta je 1 + 1 + 1 = 5.

Vhodni podatki

Vhodni podatki vesoljske omrežne topologije:

150 235 5
0 70 47
0 83 15
0 94 40
0 148 29
1 27 29
1 67 21
1 84 19
1 85 19
1 99 43
1 121 20
1 23 25
2 19 42
2 28 37
3 120 35
3 136 32
3 142 21
4 93 44
4 148 19
4 145 48
5 11 50
5 86 34
6 101 26
6 124 27
6 136 44
7 27 44
7 96 27
7 111 17
8 9 34
8 17 10
8 77 23
9 97 39
9 113 37
10 69 33
10 83 31
10 110 25
11 24 36
11 30 35
11 47 22
12 29 34
12 69 11
12 131 46
12 147 15
13 149 48
14 29 39
14 75 41
14 145 43
15 66 36
16 58 15
16 135 29
16 149 29
17 50 19
17 79 21
18 36 26
18 112 48
18 125 37
18 138 40
19 136 41
20 61 18
20 122 20
20 123 46
20 140 46
21 77 40
21 113 18
21 122 34
21 136 40
22 67 48
22 104 49
22 122 41
23 53 14
23 70 40
24 85 43
24 141 37
25 40 18
25 51 26
25 66 45
26 30 40
26 145 37
27 114 44
29 31 33
29 131 34
31 53 25
32 117 19
33 36 12
33 149 37
34 52 12
34 66 20
34 87 27
34 90 30
34 118 23
35 115 36
35 125 32
35 147 23
36 144 49
37 53 17
38 45 29
38 64 24
39 49 25
39 73 46
39 149 10
40 41 27
40 92 37
40 145 25
40 146 34
41 107 12
42 64 31
42 102 31
43 120 20
44 51 17
44 133 33
45 145 24
46 50 43
46 78 50
46 84 25
46 103 47
46 144 24
47 124 49
48 133 16
49 55 26
49 137 41
50 132 23
50 149 20
51 104 44
53 64 19
53 80 35
53 81 43
53 95 19
53 124 44
53 127 21
53 135 22
54 56 16
54 77 34
54 135 37
55 128 26
56 68 48
56 73 37
56 104 34
57 76 46
57 87 26
57 131 27
58 119 37
58 130 38
59 95 36
60 108 17
60 116 24
61 84 35
61 109 19
62 99 47
63 82 37
64 76 35
64 77 13
64 118 49
65 88 44
65 102 21
65 117 21
65 128 39
68 74 33
69 75 12
69 80 47
69 84 14
69 91 17
69 111 46
69 133 12
70 79 16
71 148 35
72 91 25
73 100 24
73 134 18
74 85 27
74 121 34
74 125 22
74 134 45
74 145 31
75 92 37
75 124 37
76 87 21
76 119 36
77 91 19
77 119 45
78 149 43
79 99 27
79 110 45
79 129 48
80 104 35
80 137 43
81 112 37
82 97 30
82 102 16
83 98 13
83 148 40
84 88 47
85 116 38
86 133 22
88 118 16
88 149 31
89 92 34
89 149 40
90 93 32
90 120 48
91 140 47
92 120 16
93 129 29
95 115 21
95 137 47
96 99 26
96 129 23
97 125 42
97 130 12
98 138 18
101 110 22
102 141 10
103 106 41
103 122 34
104 146 46
105 124 40
106 149 38
108 117 33
108 121 18
110 135 25
110 140 11
110 148 49
111 137 21
124 148 15
126 131 40
128 138 26
128 144 26
128 148 15
131 140 40
133 145 43
133 147 29
136 149 16
137 146 30
139 140 22
143 144 45
143 149 33
144 149 21