CSES - Datatähti 2024 qualification mirror - Uolevin kalansaalis
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Uolevi on käynyt nostamassa kalaverkot. Verkkoon on tarttunut saaliiksi sekä haukia että katkarapuja.

Voit myydä jokaisen verkkoon jääneen hauen 11 kultakolikon hinnalla. Kuitenkin jokaisesta verkkoon jääneestä katkaravusta joudut maksamaan 1010 kultakolikkoa sakkoa.

Leikkaat verkkoon yhden kolmionmuotoisen reiän, jonka sisälle jäävää saalista ei lasketa myyntiin eikä sakkoon. Kuinka reikä kannattaa leikata, jotta saat suurimman mahdollisen määrän kultakolikoita?

Kalaverkko on n×mn\times m kokoinen kuusikulmioista koostuva ruudukko. Annettuna on tieto saaliin sijainnista verkossa siten, että jokainen kuusikulmio verkossa on joko tyhjä, sisältää hauen tai sisältää katkaravun.

TT-kokoinen kolmio ruudukossa koostuu TT vierekkäisestä vaakatasossa olevasta ruudusta, sekä ylös- tai alaspäin osoittavasta TT pituisesta kärjestä. Tätä on havainnollistettu kuvassa alla. Leikattava kolmio voi olla minkä tahansa positiivisen kokonaisluvun kokoinen, kunhan se on kokonaan verkon sisällä. Et voi jättää reikää leikkaamatta.

Kalaverkon koordinaatisto toimii seuraavan kuvan mukaisesti. Kuvaan on merkitty koordinaattiparit a,ba,b, jotka merkitsevät kuusikulmioruudun riviä ja saraketta.

Jos tarvitset tarkempaa kuvausta kuvien sisällöstä, voit lähettää viestin järjestelmässä kohdassa Messages.

Seuraavassa kuvassa on värjätty oranssilla kolme mahdollista reikää, jotka voisit leikata. Yksi rei'istä on on kokoa T=1T=1. Toinen reikä on kokoa T=2T=2 ja sen kärki osoittaa ylöspäin. Kolmas reikä on kokoa T=3T=3 ja sen kärki osoittaa alaspäin.

Syöte

Ensimmäisellä rivillä on kokonaisluvut nn, mm ja kk: verkon korkeus, leveys ja saaliin määrä.

Seuraa kk riviä muotoa aa bb cc: rivillä aa sarakkeella bb sijaitsevassa kuusikulmiossa on saalis cc. Saalis on joko merkki H eli hauki tai merkki K eli katkarapu.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen kultakolikoiden määrä jonka Uolevi voi saada saalistaan. Huomioi, että määrä saattaa olla negatiivinen.

Esimerkki

Syöte:

5 6 13
1 1 K
5 1 K
2 2 H
4 2 H
5 2 H
2 6 K
3 3 H
3 4 K
3 5 H
3 6 K
4 4 K
2 5 H
5 5 H

Tuloste:

-16

Selitys: Syötteen kalaverkko on havainnollistettu kuvassa. Leikkaamalla oranssilla merkityn alueen pois, ansaitset 16-16 kultakolikkoa jäljelle jäävistä 44 hauesta ja 22 katkaravusta.

Rajat

  • 1an1 \leq a \leq n
  • 1bm1 \leq b \leq m
  • 0knm0 \leq k \leq nm

Osatehtävä 1 (37 pistettä)

  • 1n,m101 \le n, m \le 10

Osatehtävä 2 (63 pistettä)

  • 1n,m5001 \le n, m \le 500