Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Perica eldöntötte, hogy bejárja egész Szerbiát, külön hangsúlyt helyezve a vízesések meglátogatására. Amikor a Gostilje vízesésnél járt, megpróbálta meghatározni a víz folyását a vízesés alján.
Mint tudjuk, a vízesés magassága \(h\) méter, szélessége pedig \(n\) méter. A vízesés balról és jobbról is korlátos, tehát a víz sohasem folyik balra vagy jobbra a határain túl. Ami még érdekes, hogy a vízesésben kövek lehetnek, amelyek megváltoztathatják a víz irányát. Amikor tehát a függőleges vízsugár a kőre érkezik, szétválik, és egy része balra, másik része jobbra folyik tovább. Ha a kő a vízesés jobb vagy bal oldali határa mellett helyezkedik el, a teljes vízáram egyik irányba terelődik. Egymás mellett több kő is elhelyezkedhet. Ilyenkor a víz átirányításra kerül az egész kősorozat elejére és végére. Minden magasságszinten létezik azonban legalább egy hely, ahol nincs kő, így a víz biztosan tud haladni a vízesés alja irányába.
Formálisan a vízesést kezelhetjük \(h \times n\) bináris mátrixként, amelyben minden mező vagy átjárható, vagy követ tartalmaz. A sorindexek kezdőértéke 1 úgy, hogy az első sor a mátrix tetején, а \(h\)-dik sor pedig a mátrix alján található. A vízáram értéke minden oszlop tetején 1. A víz minden oszlopban áramlik lefelé mindaddig, amíg kőnek nem ütközik. Ha kővel találkozik a vízáram két egész szám értékű részre oszlik. Fele jobbra, fele balra halad. Ha a vízáram értéke páratlan, a felmaradt egyes balra vagy jobbra halad a következő szabály szerint:
ha a sor páratlan, a felmaradt egyes balra halad;
ha a sor páros, a felmaradt egyes jobbra halad.
Amennyiben a mátrix sorában több egymásután következő nulla (több egymást követő kő) van, akkor a teljes vízáram a blokk felett két részre oszlik. Egyik fele a blokk melletti első hely irányába balra, a másik fele az első hely irányába jobbra halad. A felmaradt egyes szabálya itt is érvényes. Ha a sor páratlan, a felmaradt egyes balra, az első hely irányába halad, ha viszont a sor páros, a felmaradt egyes jobbra halad, a blokk melletti első szabad mező irányába. Ha a kő a vízesés bal vagy jobb oldalán helyezkedik el, a teljes vízáram az ellentétes irányba terelődik. Olyan mátrixsor nincs, ahol minden helyen nulla áll.
Perica adott nektek egy mátrixot, amely a vízesést ábrázolja. Feladatotok az, hogy meghatározzátok a vízáram értékét a vízesés alján, minden pontban.
A szabványos bement első sorában két érték: \(h\) és \(n\) áll, amelyek sorban a mátrix magasságát és szélességét adják meg. Minden következő, összesen \(h\) sorban \(n\) szám található a \(\{0, 1\}\) halmazból. A \(0\) azt jelenti, hogy az adott mezőben kő található, míg az \(1\) átjárható mezőt definiál.
A szabványos kimenet egyetlen sorában \(n\) szám jelenik meg ‒ a vízáram értéke a vízesés alján, a mátrix minden oszlopában.
1 3
1 0 12 0 13 3
1 1 0
1 0 1
0 1 10 2 13 3
0 1 0
1 0 1
1 1 01 2 04 5
1 0 1 0 1
1 1 0 0 1
0 1 1 1 0
1 0 1 0 11 0 3 0 15 7
1 1 1 1 0 0 0
1 0 1 0 1 0 1
1 1 0 0 0 1 0
1 0 0 1 1 0 1
0 1 1 0 1 1 00 2 1 0 2 2 0Az első példában egyetlen sor van, és annak közepén a kő. Mivel páratlan sorról van szó, a középen haladó vízáram balra terelődik.
A második példában az első sor után \([1, 2, 0]\) az áramok értéke, mert a víz a harmadik oszlopból balra terelődik, mert az a kő a jobb oldalon van. A második sor után az áramok értéke \([2, 0, 1]\), mert a két egyes középen ketté válik. Végül a harmadik sor után a vízáramok értéke \([0, 2, 1]\), mert az áram a széléről az ellentétes irányba terelődik.
A harmadik példában az áramok értéke a sorok után:
0 3 0
1 0 2
1 2 0
A negyedik példában az áramok értéke a sorok után:
2 0 2 0 1
2 1 0 0 2
0 3 0 2 0
1 0 3 0 1
Az ötödik példában az áramok értéke a sorok után:
1 1 1 4 0 0 0
1 0 4 0 2 0 0
1 3 0 0 0 3 0
2 0 0 2 1 0 2
0 2 1 0 2 2 0
A tesztpéldák 5 független csoportba oszthatók: