# Naloge - 2. šolsko

# Veriga

Igramo igro veriga števil. Zamislimo si naravno število $X$, vzamemo najmanjše naravno število, ki ni njegov delitelj. Postopek ponavljamo na dobljenem številu, dokler ne pridemo do števila $2$. Dolžina verige $veriga(X)$ je definirana kot dolžina dobljenega niza števil. Na primer, za število $6$ dobimo niz $6, 4, 3, 2$. Zatorej je $veriga(6) = 4$. Za naravna števila $A < B$ izračunajte vsoto verig števil med vključno $A$ in $B$. Torej izračunajte $veriga(A) + veriga(A + 1) + ... + veriga(B)$.

## Vhod

V eni vrstici se nahajata naravni števili $A$ in $B$ $(3 \leq A \leq B \leq 10^{17})$.

## Izhod

V eni vrstici izpišite iskano vsoto.

## Primeri

Vhod: `3 4`
Izhod: `5`

Vhod: `4 6`
Izhod: `9`

Vhod: `10 20`
Izhod: `29`

---

# Sosedska števila

Slavc poleg dobre hrane obožuje tudi sosedska števila, tj. števila, ki nimajo enakih sosednih števk. Za dano naravno število $n$ te Slavc prosi, da mu pomagaš poiskati najmanjše sosedsko število, ki je večje od $n$. Napiši program, ki s standardnega vhoda prebere celo število $n$ $(1 \leq n \leq 10^{18})$. Na izhod izpišite iskano sosedsko število (najmanjše celo število večje od $n$, v katerem ni dveh zaporednih enakih števk).

## 1. primer

Vhod: `1`
Izhod: `2`

## 2. primer

Vhod: `98`
Izhod: `101`

---

# Bitka

Bliža se odločilna bitka med človeštvom in roboti. Tajni agenti človeštva so ugotovili, da je $n$ robotov, na koncu pa se je izkazalo, da je preostalo tudi $n$ človeških bojevnikov. Iz izkušenj preteklih bitk ljudje vedo, da lahko $i$-tega človeka premaga le robot s številko $i$. Poveljnik se je odločil, da razvrsti ljudi. Ko je prejel skrivni načrt robotov, je pojasnil, da se bo $i$-ti človek boril proti robotu s številko $a_i$. Ekipa ljudi zmaga le, če vsak borec premaga robota v svoji bitki. Na začetku je poveljnik postavil $i$-tega človeka na $i$-to mesto. Nato pa je ugotovil, da je do bitke ostalo le še malo časa in če borce obdrži v dani formaciji, izgubijo. V eni potezi lahko poveljnik vzame borca iz konca vrste in ga prestavi na začetek. Pri tem se vsem ostali borci prestavijo na naslednjo pozicijo $1$. Tj. za $n = 3$ so borci na začetku razvrščeni v vrsto $[1, 2, 3]$. V eni potezi lahko borca s številko $3$ postavi na začetek vrste, ostali pa se premaknejo nazaj v vrsti. Takrat so razvršečni v vrsti $[3, 1, 2]$.

Napiši program, ki pove, koliko potez potrebuje poveljnik, da preuredi vrsto bojevnikov tako, da zmagajo v tej odločilni bitki.

## Vhod

S standardnega vhoda preberi celo število $n$ $(1 \leq n \leq 20000)$ - število borcev

V naslednji vrstici se nahaja $n$ različnih celih števil $a_1, a_2, ..., a_n$, kjer $a_i$ $(1 \leq a_i \leq n)$ predstavlja številko robota, ki se bo boril proti $i$-temu človeku.

## Izhod

Na izhod izpiši iskano število - minimalno število potez, ki jih potrebuje poveljnik, da razporedi četo v zmagovito. Če to ni možno, izpiši $-1$

## Primeri

### 1. primer

Vhod:

5
1 4 2 3 5

Izhod:

2

### 2. primer

Vhod:

5
1 3 5 2 4

Izhod:

-1

---

# Okoli sveta

Nina je nabrala večjo vsoto denarja, da lahko izpolni svoj življenjski cilj - pot okoli sveta. Stroške bo plačevala s kartico, a ji je banka namenila strogo omejitev, koliko denarja lahko porabi v enem nakupu. Zato mora Nina dobro pripraviti načrt poti.

Na poti želi obiskati nekaj izmed $N$ mest, ki so označena s števili med $1$ in $N$. Ugotovila je tudi, da ji je na voljo $M$ letalskih povezav, ki povezujejo mesta. Da bi bila pot čimbolj zanimiva, se je odločila, da si vsak dan ogleda eno mesto. Nino zanima najmanjša vsota maksimalnih cen letalskih vozovnic, s katerimi bo potovala okoli sveta. Zastavila ti bo nekaj vprašanj, ki sestojijo iz začetnega in končnega mesta, na dano vprašanje pa jo zanima najvišja cena vozovnice, ki jo mora Nina plačati, da pripotuje med izbranima krajema. Napiši program, ki odgovori na $Q$ takšnih vprašanj.

## Vhod

V prvi vrstici standardnega vhoda se nahajata celi števili $N$ in $M$.

V naslednjih $M$ vrsticah so podana tri cela števila $u$, $v$ in $w$ $(u \neq v)$, ki opisujejo letalsko povezavo med krajema $u$ in $v$, cena vozovnice je enaka $w$.

V naslednji vrstici je podan $Q$.

Tej vrstici sledi $Q$ vrstic s celima številoma $s$ in $f$ $(s \neq f)$, ki opisujeta tekoče vprašanje za pot, ki se prične v mestu $s$ in konča v mestu $f$.

## Izhod

Na izhod izpiši vsoto odgovorov na vprašanja.

## Omejitve

- $2 \leq N, M \leq 10^5$
- $1 \leq Q \leq 10^6$
- $1 \leq u, v, s, f \leq N$
- $1 \leq w \leq 10^9$

## Primer

Vhod:

7 10
1 2 4
1 4 8
2 3 2
2 5 9
3 4 1
3 7 3
4 6 6
4 7 7
5 7 5
6 7 10
3
1 5
2 4
3 6

Izhod:

13

## Komentar


V tem primeru imamo $7$ mest povezanih z $10$ letalskimi povezavami. Število vprašanj je $3$.

Prvo vprašanje je $s = 1$ in $f = 5$. Da bi prispeli na cilj (mesto $5$) moramo uporabiti eno od linij $7 \to 5$ ali $2 \to 5$. Izberemo $7 \to 5$, ker je cenejša. Zatorej je odgovor na to vprašanje $5$.

Pri naslednjih vprašanjih opazimo, da sta optimalni smeri $2 \to 3 \to 4$ in $3 \to 4 \to 6$. Če želimo, da Nina uspešno prepotuje svet, sta minimalni omejitvi banke $2$ in $6$. Končen odgovor je torej $13$, kar je vsota odgovorov na vsa vprašanja: $13 = 5 + 2 + 6$

---

# Nanomečnina

Programersko podjetje Nanomečnina ima $n$ zaposlenih. Vsakemu zaposlenemu je dodeljena edinstvena številka med $1$ in $n$. Vsako uspešno podjetje ima jasno hierarhično strukturo (ve se, kdo je direktor, kdo je vodja ekipe, kdo je programer ...). Direktorju je dodeljena številka $1$. Vsak zaposleni z izjemo šefa ima natanko enega neposrednega šefa. Neposredni šef zaposlenega s številko $i$ ima številko $p_i$ $(p_i < i)$.

Zaposlenec $x$ je neposredno podrejen $y$-u, če je $p_x = y$. Torej je $y$ šef $x$-u. Za $k > 1$ velja: Zaposlenec $x$ je $k$-krat podrejen $y$-u, če je $p_x$ podrejen $y$-u $k-1$-krat.

Direktor bo poslal nekaj zaposlenih na izpopolnjevanje tako, da izbere vrednosti $L$ in $R$ in na izobraževanje pošlje zaposlene, ki imajo številko $i$ $(L \leq i \leq R)$. Preden je izbral vrednosti $L$ in $R$ je prejel nekaj želja zaposlenih. Na primer, $j$-to željo opisujeta števili $u_j$ in $k_j$, kar pomeni, da zaposleni $u_j$ želi, da se na izpopolnjevanje pošlje enega izmed njegovih $k_j$-krat podrejenih.

Ker pa direktor stremi k manjšanju stroškov, si direktor želi, da izbere takšen $L$ in $R$, da bo na izpopolnjevanje šlo čim manj zaposlenih. A pri tem želi ustreči vsem željam.

Napiši program, ki upošteva hierarhično obliko podjetja, želje zaposlenih in vrne vrednosti $L$ in $R$, da na izobraževanje pošlje vse zaposlene s številkami med $L$ in $R$, a da je teh najmanj.

Če obstaja več takšnih parov števil, izpiši tistega, pri katerem je $L$ najmanjši.

## Vhod

V prvi vrstici standardnega vhoda se nahaja $n$ $(2 \leq n \leq 200000)$.
V drugi vrstici se nahaja $n-1$ števil $p_2, p_3, ..., , p_n$ $(1 \leq p_i \leq n)$, ki predstavljajo številko neposrednega šefa.
V tretji vrstici vhoda se nahaja celo število $m$ $(1 \leq m \leq 200000)$ - število želja zaposlenih.
V naslednjih $m$ vrsticah se nahajajo pari celih števil $u_j$ in $k_j$ $(1 \leq u_j < n)$$(1 \leq k_j < n)$ - želje zaposlenih. Lahko predpostavite, da ima zaposleni $u_j$ vsaj enega podrejenega na nivoju $k_j$.

## Izhod

Na izhod izpiši vrednosti števil $L$ in $R$.

## 1. primer

Vhod:

7
1 1 2 2 3 3 
3
1 1 
3 1 
1 2

Izhod:

3 6

## 2. primer

Vhod:

10 
1 2 2 2 1 5 6 4 7 
10 
1 4 
4 1 
4 1 
5 2 
7 1 
4 1 
1 2 
2 1 
7 1 
5 2 

Izhod:

5 10

---

# Omejitve

| Naloga | Čas [s] | Spomin [MB] |
| -------- | -------- | -------- |
| veriga | 0,5 | 32 |
| stevila | 0,2 | 32 |
| bitka | 0,5 | 32 |
| pot | 1 | 256 |
| nano | 0,5 | 64 |