ŠIOM — Žodžių ratas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1999_3e2_zodziu_ratas_vyr.in

Rezultatų failas: lmio_1999_3e2_zodziu_ratas_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Žodžių ratas

Duotas žodynas, sudarytas iš $m$ žodžių, ir tuščias ratas, turintis n langelių. Langeliai sunumeruoti nuo 1 iki $n$ laikrodžio rodyklės apėjimo tvarka. Žodžiai (iš duoto žodyno) talpinami į ratą pagal tokias taisykles:

Žodis turi būti rašomas po vieną raidę į vieną rato langelį pagal laikrodžio rodyklę;
Žodžiai gali persikloti;
Bet kurios dvi gretimos rato raidės turi priklausyti bent vienam tam pačiam žodžiui;
Rate negali likti tuščių langelių.

Pavyzdžiui, duotas žemiau esantis žodynas. SAMBA TAISYKLA LOBIS TIMPA BATAI SENIS PALTAI AIDAI TIKSLO IMTI

Jo žodžiais pirmasis ratas užpildytas teisingai, antrasis pradėtas pildyti klaidingai. Mat dvi gretimos raidės $IS$ nepriklauso nei žodžiui $BATAI$ , nei žodžiui $SAMBA$ .

Pavyzdys

Užduotis

Parašykite algoritmą, kuris surašytų į ratą žodžius pagal aukščiau išvardintas taisykles taip, kad rate esančių žodžių ilgių suma būtų didžiausia.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du skaičiai – rato dydis $n$ ir žodžių skaičius žodyne $m$ . Likusiose m eilučių įrašytas žodynas po vieną žodį į eilutę. Visi žodžiai sudaryti tik iš didžiųjų raidžių ir žodžio ilgis neviršija 20 simbolių. Jei vieno žodžio galūnė sutampa su kito žodžio pradžia, tai vadinsime sąryšiu. Pradiniai duomenys tokie, kad sąryšių skaičius žodyne neviršija 110.

Rezultatai

Pirmoje eilutėje įrašykite du skaičius – rate įrašytų žodžių ilgių sumą $s$ ir rate įrašytų žodžių skaičių $sk$ . Į likusias $2\\cdotpsk$ eilučių įrašykite rate esančius žodžius, kiekvienam žodžiui skirdami po dvi eilutes. Pirmoje eilutėje įrašykite rato langelio numerį kuriame yra pirmoji žodžio raidė, antroje – patį žodį. Jei sprendinio nėra, įrašykite žodį $NEGALIMA$ .

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
24 10 SAMBA TAISYKLA LOBIS TIMPA BATAI SENIS PALTAI AIDAI TIKSLO IMTI	35 7 1 BATAI 4 AIDAI 8 IMTI 10 TIKSLO 14 LOBIS 18 SENIS 22 SAMBA	Pavyzdys atitinka sąlygoje pateiktą pavyzdį

Ribojimai