---
# System prepended metadata

title: Ukana s kartami

---

<table border=0>
<tr>
<td width="80%">
EJOI 2020 Day 2 </br>
<b>cards</b> (Slovene)
</td>
<td width="20%">
<img align="right" width="100"  src="https://i.imgur.com/KUVHoM0.png">
</td>
</tr>
</table>



# Ukana s kartami

Igralca bosta napravila ukano z $52$ kartami. Zaradi preglednosti so karte označene s celimi števili med $0$ in $51$.

Na začetku so naključno premešane karte postavljene na mizo tako, da jih prvi igralec lahko vidi. Nato lahko $S$-krat zamenja par kart. Pri vsaki menjavi si izbere karti na poziciji $i$ in $j$ ($i$ in $j$ sta lahko enaka) in ju zamenja tako, da gre $i$-ta karta na mesto, kjer je bila pred tem $j$-ta karta in obratno.

Nato prvi igralec obrne karte naokoli (da jih drugi igralec ne vidi) in brez stika z drugim igralcem zapusti mizo. Ob tem vrstni red kart ostane nespremenjen. Potlej k mizi pride drugi igralec, ki ima nalogo, da ugane, kje se nahaja karta z vrednostjo **target**. Ob tem lahko $T$-krat obrne eno izmed kart (ugiba). Če je katera izmed obrnjenih kart enaka **target**, igralca zmagata. Če mu zmanjka poizkusov, igro izgubita.

Tvoja naloga je, da napišeš dva programa, ki simulirata dejanja igralcev in zmagata v igri.

## Implementacijski napotki

Podana sta dva programa - *FirstPlayer* in *SecondPlayer*, in vzorčni ocenjevalnik.

V programu *FirstPlayer* implementiraj funkcijo:
```c
void swapCards(int cards[], int S, int T)
```
* Ocenjevalnik funkcijo pokliče le enkrat.
* *cards*: polje z začetno razporeditvijo kart od leve proti desni, ki ima natanko $52$ elementov označenih s števili med $0$ in $51$.
* $S$: število menjav.
* $T$: število dovoljenih ugibanj.

`swapCards` lahko kliče funkcijo:

```cpp
void doSwap(int i, int j)
```
* $i$: kazalec na prvo karto, ki jo želi igralec zamenjati. $(0 \leq i \leq 51)$
* $j$: kazalec na drugo karto, ki jo želi igralec zamenjati. $(0 \leq j \leq 51)$
* Funkcijo `doSwap` lahko pokličeš največ $S$ krat.

V programu *SecondPlayer* implementiraj funkcijo:
```cpp
void guessCard(int S, int T, int target)
```
* $S$: število menjav.
* $T$: število dovoljenih ugibanj.
* **target**: karta, ki jo mora igralec najti.

`guessCard` lahko kliče funkcijo:
```cpp
int guess(int idx)
```
* $idx$: kazalec na karto, ki jo želi igralec pogledati. $(0 \leq idx \leq 51$)
* Funkcija vrne vrednost karte na mestu $idx$.
* Funkcijo `guess` lahko kličeš največ $T$-krat.
* Če program ugane pravilno karto, se izvajanje samodejno zaustavi.

## Primer interakcije

<table>
<tr>
<td rowspan=2 width=15%>Primer vhoda ocenjevalniku</td>
<td colspan=3>Primeri klicev</td>
</tr>
<tr>
<td width=25%>Klic</td>
<td width=20%>Podklic</td>
<td width=40%>Vračilo</td>
</tr>
<tr>
<td rowspan=11>1 51<br>
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51<br>
1</td>
<td>swapCards([0,1,…], 1, 51)</td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td>doSwap(0, 1)</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td>Zamenja karti s kazalcem 0 in 1</td>
</tr>
<tr>
<td></td>
<td></td>
<td>swapCards se zaključi</td>
</tr>
<tr>
<td>guessCard(1, 51, 1)</td>
<td></td>
<td></td>
</tr>
<tr>
<td></td>
<td>guess(5)</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td>guess vrne 5</td>
</tr>
<tr>
<td></td>
<td>guess(1)</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td>guess vrne 0</td>
</tr>
<tr>
<td></td>
<td></td>
<td>guess(0)</td>
</tr>
<tr>
<td></td>
<td></td>
<td>Pravilno!</td>
</tr>
</table>


## Omejitve

* $1 \leq S \leq 52$
* $1 \leq T \leq 51$
* $0 \leq target \leq 52$

## Podnaloge

1. podnaloga (16 točk): $S = 52$ in $T = 1$
2. podnaloga (20 točk): $S + T = 52$
3. podnaloga (22 točk): $S = 13$ in $T = 27$
4. podnaloga (18 točk): $S = 1$ in $T = 26$
5. podnaloga (24 točk): Obstaja zmagovalna strategija za dana $S$ in $T$.
