Tehtävänanto
On olemassa paljon kortteja, joista jokaiseen on kirjoitettu kokonaisluku väliltä $1$ – $1000$. Anna ja Bruno pelaavat seuraavaa peliä käyttäen näitä kortteja.
Annalla on pino, joka koostuu $A$ kortista, ja Brunolla on pino, joka koostuu $B$ kortista. Anna poistaa haluamansa määrän kortteja (myös $0$ korttia on sallittu) $A$ kortistaan muodostaakseen uuden pinon. Bruno poistaa jonkin määrän kortteja (myös $0$ korttia on sallittu) päältä ja jonkin määrän kortteja (myös $0$ korttia on sallittu) pohjalta $B$ kortista koostuvasta pinostaan muodostaakseen uuden pinon. Jäljelle jäävien korttien järjestystä ei kuitenkaan muuteta poistamisen yhteydessä. Jos näin muodostetut $2$ pinoa täsmäävät, toisessa pinossa olevien korttien lukumäärästä tulee $2$ pelaajan pistemäärä. Tässä $2$ pinoa täsmäävät, jos kummassakin pinossa olevien korttien lukumäärä $n$ on sama ja jokaiselle $i$-nnelle kortille ylhäältä lukien ($1 \le i \le n$) korteissa olevat kokonaisluvut ovat samat.
Oletetaan esimerkiksi, että Annalla on $5$ kortin pino, jossa on kokonaisluvut $1, 2, 3, 4, 5$ järjestyksessä ylhäältä alas, ja Brunolla on $4$ kortin pino, jossa on kokonaisluvut $3, 1, 4, 1$ järjestyksessä ylhäältä alas. Tällöin, jos Anna poistaa kortit $2, 3, 5$ ja Bruno poistaa päällimmäisen kortin $3$ ja alimmaisen kortin $1$, $2$ pelaajan pinot täsmäävät. Koska jäljelle jääneessä pinossa on $2$ korttia, $2$ pelaajaa saavat pistemäärän $2$.
Haluamme selvittää $2$ pelaajan pistemäärän suurimman mahdollisen arvon.
Tehtävä
Kun tiedot Annan ja Brunon korttipinoista on annettu, kirjoita ohjelma, joka etsii $2$ pelaajan pistemäärän suurimman mahdollisen arvon.
Rajoitukset
- $1 \le A \le 5000$: Korttien lukumäärä Annan pinossa.
- $1 \le B \le 5000$: Korttien lukumäärä Brunon pinossa.
- Kortteihin kirjoitetut kokonaisluvut ovat väliltä $1$ ja $1000$, rajat mukaan lukien.
Syöte
Lue seuraavat tiedot vakiosyötteestä.
- $1$. rivillä on kokonaisluvut $A, B$ välilyönnillä erotettuina.
- $2$. rivillä on $A$ kokonaislukua välilyönneillä erotettuina; $i$-s kokonaisluku ($1 \le i \le A$) ilmaisee Annan pinon ylhäältä $i$-nteen korttiin kirjoitetun kokonaisluvun.
- $3$. rivillä on $B$ kokonaislukua välilyönneillä erotettuina; $j$-s kokonaisluku ($1 \le j \le B$) ilmaisee Brunon pinon ylhäältä $j$-nteen korttiin kirjoitetun kokonaisluvun.
Tuloste
Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmaisee $2$ pelaajan pistemäärän suurimman mahdollisen arvon.
Osatehtävät
- Arvosteluaineiston pisteistä $10\%$ osuudessa pätevät $A \le 10, B \le 10$.
- Arvosteluaineiston pisteistä $50\%$ osuudessa pätevät $A \le 100, B \le 100$.
Esimerkki 1
Syöte
5 4 1 2 3 4 5 3 1 4 1
Tuloste
2
Tämä esimerkki vastaa tehtävänannossa esitettyä esimerkkiä.
Esimerkki 2
Syöte
6 5 4 1 5 2 3 4 4 5 4 2 3
Tuloste
3
Tässä esimerkissä on $2$ tapaa, joilla $2$ pelaajaa voivat saada pistemäärän $3$.
- Kun Anna poistaa kortit $1, 2, 3$ ja Bruno poistaa kortit $2, 3$, $2$ pelaajan pinoiksi tulee ylhäältä alas $4, 5, 4$, ja $2$ pelaajan pistemäärä on $3$ pistettä.
- Lisäksi kun Anna poistaa kortit $1, 5, 4$ ja Bruno poistaa päällimmäiset kortit $4$ ja $5$, $2$ pelaajan pinoiksi tulee ylhäältä alas $4, 2, 3$, ja $2$ pelaajan pistemäärä on $3$ pistettä.