Odločitveni seznam

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Odločitveni seznam je logični izraz, kot na primer ta, ki ga prikazuje spodnji diagram. Predstavljamo si ga lahko kot zelo dolg ifelif...else stavek.

seznam

Omejili se bomo na odločitvene sezname, ki imajo v vozliščih zgolj disjunkcije (dovolimo negirane spremenljivke, ne pa tudi negiranih disjunkcij). Disjunkcije lahko vsebujejo poljubno število spremenljivk. Podan imamo seznam vhodov in izhodov, ki so bili generirani z neznanim odločitvenim seznamom. Ta seznam želimo rekonstruirati. Za podan seznam vhodov (tj. vrednosti logičnih spremenljivk) in izhodov poiščite odločitveni seznam z minimalnim številom vozlišč (lahko tudi 0), ki se s podanimi vhodi ujema (ali pa izpišite, da tak seznam ne obstaja). Če obstaja več pravilnih rešitev, izpišite poljubno izmed njih. Minimizirati je treba zgolj število vozlišč seznama, ne pa tudi dolžine izrazov znotraj njih.

Vhodni podatki

V prvi vrstici se nahajata celi števili n in m. Pri tem je n število spremenljivk, m pa število znanih vhodov in pripadajočih izhodov. Sledi m vrstic – v vsaki je opisan en vhod in pripadajoči izhod. V posamezni vrstici je tako podanih n s presledkom ločenih logičnih vrednosti (tj. vrednosti spremenljivk x_1, \ldots, x_n) in njihov pripadajoči izhod, ki je ločen z nazorno (in nepotrebno) puščico "-->" (glejte primere).

Omejitve vhodnih podatkov

  • 1 \leq n,m \leq 100

Izhodni podatki

Če se seznama, ki bi bil konsistenten z vsemi znanimi vhodi, ne da sestaviti, izpišite niz "Tak seznam ne obstaja". Sicer izpišite primer seznama z minimalnim številom vozlišč, ki ustreza vhodom. Vsako vozlišče naj bo opisano v svoji vrstici.

V i-ti vrstici izpišite vsebino i-tega vozlišča odločitvenega seznama. Izpišite logični izraz v vozlišču, kjer namesto logičnega operatorja \lor zapišete "or", namesto negacije \neg pa "!". Spremenljivke x_1, \ldots, x_n zapišete kot "x1" {}, \ldots, "xn". Nato zapišite puščico "-->" in pripadajoči izhod. Vsebino zadnjega vozlišča (torej "else vrednost") izpišite v ločeni vrstici.

Na primer, odločitveni seznam z zgornje slike bi zapisali takole:

x1 or !x3 --> 0
!x2 or x3 --> 1
0

Primeri

Vhod

2 3
1 0 --> 1
1 1 --> 0    
0 1 --> 0

Izhod

!x1 or x2 --> 0
1

Vhod

2 2
0 0 --> 0
0 0 --> 1

Izhod

Tak seznam ne obstaja

Komentar

V prvem primeru podana rešitev ni edina možna.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task