ACM RTK - 2. skupina

Cevi

Na pravokotni mreži dimenzij v × s (pri čemer sta v in s manjša ali enaka 100) je vsaka celica prazna ali pa vsebuje enega od dveh tipov cevi. Prvi tip je zavita cev (tip L), ki povezuje dve sosednji stranici celice. Drugi tip je ravna cev (tip I), ki povezuje nasprotni stranici celice. Z eno potezo lahko zavrtimo celico (oz. cev v njej) za 90 stopinj v poljubno smer. S takimi potezami želimo povezati vse cevi tako, da ne bo nikjer kakšnega odprtega konca cevi. Opiši in dobro utemelji postopek, ki izračuna najmanjše število potez oz. ugotovi, da to ni mogoče.

Primer: mrežo na spodnji sliki lahko primerno uredimo v 11 potezah.