Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1997_3e1_saskes_vyr.in

Rezultatų failas: lmio_1997_3e1_saskes_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Šaškės: viena prieš vieną

Šimtalangėje šaškių lentoje yra dvi paprastosios šaškės: balta ir juoda. Baltoji laimi, jei numuša juodąją. Baltoji pralaimi, jeigu ją numuša juodoji. Jei abi šaškės taikiai prasilenkia, tai laikoma, kad yra lygiosios, t. y. nebenagrinėjamas paprastųjų šaškių virtimas damomis ir tolesnė jų kova. Šaškės stumdomos tik juodaisiais langeliais. Paveiksle parodytas lentos juodųjų langelių numeravimas.

< insert image here >

Situacija nusakoma dviem skaičiais b ir j: b – baltosios šaškės langelio numeris,ir j – juodosios šaškės langelio numeris. Baltoji šaškė eina aukštyn (link langelių su mažesniais numeriais), juodoji – žemyn.

Užduotis

Parašykite programą, kuri rastų geriausią baltosios šaškės ėjimą duotoje situacijoje, t. y. tokį, kad baltoji laimėtų, jeigu ji gali laimėti arba pasiektų lygiąsias, jeigu ji gali jas pasiekti (bet negali laimėti).

Jei baltoji šaškė negali nei laimėti, nei pasiekti lygiųjų, tai pasirenkamas bet kuris ėjimas (vis tiek pralošime). Visais atvejais reikia laikyti, kad juodoji šaškė lošia optimaliai.

Pradiniai duomenys

Pradiniai duomenys – du sveikieji skaičiai b ir j. Pradiniai duomenys yra tokie, kad baltoji šaškė visada turi kur eiti (nėra situacijos, pavyzdžiui b=6 ir j=1), taip pat nėra kirtimo situacijos (akivaizdus baltosios šaškės laimėjimas).

Rezultatai

Rezultatas – vienas skaičius – langelio, į kurį turi eiti baltoji šaškė, numeris.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
22 12
 
17
 
arba 18, nes vis tiek pralaimėta
 
28 12
 
22
 
pergalė
 
38 17
 
33
 
galima pasiekti tik lygiąsias

Ribojimai

6\\leqb\\leq50

1\\leqj\\leq45

Tiems, kas nelošia šaškėmis. 1. Šaškės gali stovėti tik ant juodųjų langelių. 2. Šaškė gali eiti tik pirmyn įstrižai į gretimą langelį, pvz, baltoji šaškė iš 38 langelio gali eiti į 32 arba 33 langelį, iš 15 langelio – tik į 20, o juodoji šaškė iš 38 langelio – į 42 arba 43 langelį. 3. Šaškė kerta kitos spalvos šaškę, jei jos abi stovi tos pačios įstrižinės gretimuose langeliuose ir toje pačioje įstrižainėje už kertamos šaškės yra tuščias langelis. Pavyzdžiui, jeigu 20 ir 24 langeliuose yra skirtingų spalvų šaškės, tai jos viena kitą kerta, o nukirs ta, kurios eilė eiti; jei šaškės yra langeliuose 20 ir 25, tai kirsti gali tik 25 langelio šaškė (jeigu jos eilė eiti). 4. Kirsti galima abiem kryptimis – pirmyn ir atgal.