magnify

Žirklės

Pradinių duomenų failas:
zirkles.in  
Rezultatų failas:
zirkles.out  
Laiko apribojimas:
2 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Vilius ir Adomas žaidžia tokį žaidimą. Jie turi M×N matmenų stačiakampį popieriaus lapą. Žaidimas vyksta taip:

  • Vilius perkerpa stačiakampį į du mažesnius stačiakampius. Abu gauti stačiakampiai turi būti sveiki (ilgis ir plotis turi būti sveikieji skaičiai).
  • Adomas perkerpa kiekvieną stačiakampį į du, taigi gaunami keturi stačiakampiai.
  • Vėl kerpa Vilius, gaunami aštuoni stačiakampiai.

Taigi, žaidėjai paeiliui perkerpa kiekvieną stačiakampį (išskyrus 1×1) į du mažesnius. Žaidėjas, kuris perkerpa paskutinį 1×2 stačiakampį į 1×1, laimi. Adomas yra labai protingas, todėl visuomet karpo optimaliai. Tačiau, kadangi gera pražia – pusė darbo, jūs padėsite Viliui atlikti pirmą perkirpimą.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas testų skaičius T (1 ≤ T ≤ 1000). Kitose T eilučių įrašyta po du sveikuosius skaičius M ir N (1 ≤ M, N ≤ 400) – tai pradinio stačiakampio plotis ir ilgis.

Rezultatai

Į rezultatų failą programa turi išvesti T eilučių, kuriose būtų atsakymai į kiekvieną testą.

  • išveskite raidę H ir sveiką skaičių K, jei Vilius turi kirpti vertikaliai ir padalinti pradinį stačiakampį į M×K ir M×(N−K),
  • išveskite raidę V ir sveiką skaičių K, jei Vilius turi kirpti vertikaliai ir padalinti pradinį stačiakampį į K×N ir (M−K)×N,
  • išveskite −1, jei Vilius neturi laiminčios strategijos.

Pavyzdys

Pradiniai duomenys Rezultatai Komentaras
4
1 1
1 2
1 3
1 4
-1
H 1
-1
H 1
  1. Negalima perkirpti 1×1,
  2. Laiminti situacija, tereikia perkirpti 1×2 pusiau,
  3. Adomas laimės perkirpdamas 1×2,
  4. Vienas iš būdų yra perkirpti stačiakampį horizontaliai į 1×1 ir1×3.
© Bronė Narkevičienė