# Planet HROSCH

Na planetu HROSCH v sistemu diamantne zvezde BPM 37093 (večkrat znane kot Lucy) so se odločili, da koledar priredijo lokalnim zahtevam. Za začetek merjenja časa so se odločili, da izberejo 21. januar 2021 ob 15:00 uri. Koledar je zelo podoben našemu, vendar ima vsak dan 25 ur, ura ima 45 minut in vsaka minuta 80 sekund. Koledar ima 12 mesecev, kjer imajo mesece enako število dni kot na Zemlji, je pa vsak februar dolg natanko 28 dni. So pa v letu lahko 4 prestopni meseci. Dodaten dan je v aprilu, če je leto deljivo s 3, dodatna dva dneva sta dodana v septembru, če je leto deljivo s 5 in dodatni trije dnevi so dodani v juniju in novembru, če je leto deljivo s 7, ne pa tudi s 3 ali/in 5.

## Vhod

Na vhodu se nahaja vrstica, ki vsebuje podatke o času v obliki:

YYYY/MM/DD HH:MM:SS

Zagotovljeno je, da so vsi datumi pred začetkom leta 2100. Vsi datumi bodo veljavni datumi v tem koledarju.

## Izhod

Na izhod izpiši število sekund, ki so potekle od prevzema tega koledarja.

## Primer

Vhod: `2021/02/01 14:00:00`
Izhod: `986400`

Vhod: `2035/02/28 24:44:79`
Izhod: `464705999`

# Parkomat

Parkirnina stane 1 evro, parkomat pa sprejema kovance za 1 evro in 2 evra.
Če stranka vstavi kovanec za 2 evra, parkomat pa ne premore nobenega kovanca
za 1 evro, nastanejo težave. Če parkomat na začetku vsebuje, denimo, dva
kovanca za 1 evro, se to zgodi pri zaporedju vstavljanj 22122: ko zadnja
stranka vstavi kovanec za 2 evra, ji parkomat ostanka ne more vrniti.

Napiši program, ki prebere števili $n$ in $k$ in izpiše število vseh zaporedij
vstavljanja $n$ kovancev, pri katerih **ne** pride do težav, če je v
parkomatu na začetku $k$ kovancev po 1 evro. Rezultat izpiši po modulu $(10^9 + 7)$ (tj. zanima nas ostanek pri deljenju rezultata s tem modulom).

## Vhod

Na vhodu sta podani celi števili $n \in [1, 100]$ in $k \in [0, n]$, ločeni s
presledkom. V 50\% testnih primerov velja $n \le [1, 20]$.

## Izhod
Izpiši iskano število zaporedij po modulu $(10^9 + 7)$.

## Primer

Vhod: `
6 2
`
Izhod: `50`

V tem primeru parkomat "preživi" vsa zaporedja razen 12222x, 21222x, 22122x
in 222xxx ($x$ lahko predstavlja enico ali dvojko).

# Plošča

Mirko in Slavko imata novo namizno igro. Igralna plošča ima obliko neskončnega polnega dvojiškega drevesa z nekaj dodatnimi povezavami. Natančneje, plošča je sestavljena iz vozlišč in neusmerjenih povezav med njimi. Korensko vozlišče se nahaja na vrhu plošče; pravimo, da ima globino nič. Nato je plošča definirana rekurzivno: vsako vozlišče ima natanko dva otroka, levega in desnega, na plošči pa se nahajata tik pod svojim staršem. Globina otroka je za eno večja od globine starša. Starš je povezan z otrokoma. Poleg tega je povezan tudi vsak par vozlišč, ki ima enako globino in je na plošči narisan en ob drugem. Glej tudi Sliko 1.


Vsaka pot po plošči je zaporedje korakov, ki nas premaknejo iz vozlišča do enega od njegovih sosedov v grafu. Vsak od korakov je opisan z enim od naslednjih znakov:
- ‘1’ opisuje premik iz vozlišča v njegovega levega otroka
- ‘2’ opisuje premik iz vozlišča v njegovega desnega otroka
- ‘U’ opisuje premik iz vozlišča v njegovega starša
- ‘L’ opisuje premik iz vozlišča v njegovega levega soseda na isti globini
- ‘R’ opisuje premik iz vozlišča v njegovega desnega soseda na isti globini

Če na primer začnemo v korenu in opravimo zaporedje korakov ‘221LU’, končamo v vozlišču A na Sliki 1.

## Naloga

Napiši program, ki sprejme dve vozlišči na igralni plošči in najde najmanjše število korakov, ki pripelje iz prvega vozlišča v drugega. Vozlišči bosta podani s potema, ki iz korena pripeljeta do teh dveh vozlišč. Če obe vhodni poti opisujeta isto vozlišče, je odgovor nič.

## Vhod

Prva vrstica vsebuje največ 100 000 znakov – pot od korena do prvega vozlišča.
Prva vrstica vsebuje največ 100 000 znakov – pot od korena do drugega vozlišča.
Poti bosta veljavni; z drugimi besedami, vse opisane korake bo na plošči mogoče opraviti.

## Izhod

Izpiši eno samo število – dolžino najkrajše poti, ki vodi od prvega vozlišča do drugega.

## Podnaloge

Naj bo D največja globina, do katere sežeta obe vhodni poti.
- V testnih primerih, vrednih skupaj 20 točk, bo D največ 10.
- V testnih primerih, vrednih skupaj 40 točk, bo D največ 50.
- V testnih primerih, vrednih skupaj 70 točk, bo D največ 1000.

## Primeri

### 1. primer

Vhod:

111RRRRRRR
222

Izhod:

0

### 2. primer

Vhod:

221LU
12L2

Izhod:

3

### 3. primer

Vhod:

11111
222222

Izhod:

10

# Križec-krožec

Igra križec-krožec se igra na mreži velikosti $N \times N$, ki je na začetku delno zaponljena z $X$-i in $O$-ji. Cilj je zapolniti mrežo z $X$-i in $O$-ji po naslednjih pravilih:

1. Vsaka vrstica in vsak stolpec mora imeti enako število $X$-ov in $O$-jev
2. V nobeni vrstici in v nobenem stolpcu ne smeta biti več kot dva enaka simbola zaporedoma
3. Vsaka vrstica je različna od preostalih, vsak stolpec je različen od preostalih

## Primer


## Vhod

Na vhodu se nahaja celo število $1 \leq N \leq 20$, ki prestavlja velikost igralne mreže. Sledi niz, ki opisuje začetno stanje na mreži. Niz predstavlja mrežo vrstico po vrstico gledano od zgoraj navzdol, prazna polja pa nadomeščajo števila, ki povedo, koliko praznih polj je vmes.

Zgornjemu primeru torej ustreza zapis:

--OX-O---------X--OX-X----O--------O

ki se prevede na zapis:

2OX1O9X2OX1X4O8O

## Izhod

Na izhod izpiši šestnajstiško zapisano glavno diagonalo (od zgoraj levo do spodaj desno). To storiš v treh korakih. Prvo ustvariš niz Xov in Ojev iz glavne diagonale. Drugič, zamenjaj vsak X z 1 in O z 0 in si ta niz zamisli kot dvojiški zapis števila. Tretjič, zapiši to dvojiško število v šestnajstiškem sistemu. Uporabljaj velike črke A, B, C, ... F. Odstrani vse vodilne ničle v šestnajstiškem zapisu.

Primer glavne diagonale v zgornjem primeru je `XOXXXO`. Ta se prevede v `101110`, kar je v šestnajstiškem sistemu `2E`

## Primeri

Vhod: `8 2O3O2X9O2XXX3X5O3O5XX1X1X9X1X2`
Izhod: `E6`

# Odboj

Pri igri kartezičnega biljarda postavimo kroglo na mizo brez lukenj. Nato kroglo poženemo v gibanje. Ko zadane rob, se odbije pod kotom, ki je enak vpadnemu in nato nadaljuje z odbijanjem (glej primer 1). Če krogla zadane kot, se odbije pod kotom, ki je enak vpadnemu (glej primer 2). Kota označena za 1 in 2 sta enaka.

### Primer 1

Na mizi velikosti $2 \times 14$ postavimo kroglo na mesto (11, 7) in jo pospešimo tako, da se ob stiku z zgornjo stranico mize premakne 6 enot v desno, nato se krogla odbije od zgornje stranice in zadane ob desni rob 4 enote nižje itd.


### Primer 2

Primer odboja v kotu


## Vhod

Na vhodu se nahaja vrstica s podatki o velikosti mize (širina in višina v tem vrstnem redu), izhodišče krogline poti (urejen par - (x, y)), lokacija, kje krogla prvič zadane ob rob (urejen par) ter število $K$. Vsa števila so cela števila in so ločena s presledkom.

## Izhod

Na izhod izpiši kje na mizi se nahaja krogla po $K$ odbojih. To vrednost zaokroži (pri 0,5 zaokroži navzgor). Če je krogla po $K$ odbojih na levem ali desnem robu, izpiši vrednost koordinate y, če je krogla po $K$ odbojih na zgornjem ali spodnjem robu, izpiši koordinato x. Če je krogla po $K$ odbojih v kotu, izpiši tisto koordinato, ki je večja.

## Primeri

### 1. primer

Vhod: `20 15 11 7 17 15 2`
Izhod: `11`

### 2. primer

Vhod: `20 15 15 12 20 0 2`
Izhod: `8`

### 3. primer

Vhod: `10 6 5 3 8 6 4`
Izhod: `6`