From CEOIWiki

Contents 1 Testőrök 1.1 Feladat 1.2 Bemenet 1.3 Korlátok 1.4 Kimenet 1.5 Példa

[edit] Testőrök

Egy rendezvényen a székek négyzetrácsos elrendezésben vannak. Minden sorba és oszlopba adott számú testőrt kell elhelyezni!

[edit] Feladat

Írj programot, amely megadja, hogy el lehet-e helyezni a testőröket az igényeknek megfelelően!

Minden széken csak egy testőr ülhet!

[edit] Bemenet

A bemenet tömörített formában van megadva.

A bemenet a sorok leírásával kezdődik. Az első sor a sorcsoportok R számát tartalmazza. A következő R sor mindegyike 2 pozitív egész számot tartalmaz: a soronként szükséges testőrök számát és a csoportot alkotó sorok számát.

Ezt követi az oszlopok leírása. Az első sor az oszlopcsoportok C számát tartalmazza. A következő C sor mindegyike 2 pozitív egész számot tartalmaz: az oszloponként szükséges testőrök számát és a csoportot alkotó oszlopok számát.

[edit] Korlátok

Feltehető, hogy soronként megkövetelt testőrök száma megegyezik az oszlopokban megkövetelt testőrök számával, ez legfeljebb 10¹⁸.

Feltehető, hogy az összes pozitív egész szám legfeljebb .

Tejesül, hogy .

50 pontot lehet elérni a következő esetekben:

• a sorok száma legfeljebb
• az oszlopok száma legfeljebb
• a testőrök száma legfeljebb .

További 10 pont szerezhető, amikor .

[edit] Kimenet

Az egyetlen sorba az "1" egész számot kell kiírni, ha van megoldás, illetve a "0" számot, ha nincs megoldás.

[edit] Példa

input:

2
2 1
1 2
1
2 2

output:

1

Itt 2 sorcsoport van. Az első szerint egyetlen sorba kell tenni 2 testőrt, a második szerint a következő 2 sorba 1-1 testőrt kell tenni! Egyetlen oszlopcsoport van, ami szerint mindkét oszlopba 2 testőrt kell tenni! Egy lehetséges testőrelhelyezés a következő:

 XX
 X.
 .X

input:

2
3 2
1 1
2
3 2
1 1

output:

0

Itt az első 2 sorba 3-3 testőrt kell ültetni. Ezért minden oszlopban legalább 2 lenne. A második oszlopcsoport leírása szerint az utolsó oszlopban csak 1 lehet.