Pangram
vreme | memorija | ulaz | izlaz |
---|---|---|---|
1 s | 512 Mb | standardni izlaz | standardni ulaz |
Moreplovac Brle je u jednoj od svojih pustolovina nabasao na novo, neotkriveno ostrvo. Kada je pokušao da priđe ostrvu ugledao je rečenicu ispisanu ogromnim slovima u pesku. Nažalost, palmini listovi prekrivaju delove plaže, pa neki delovi rečenice nisu vidljivi. Poznato je da je ispisana rečenica savršen pangram (sadrži svako slovo engleske abecede tačno jednom) i sastoji se isključivo od slova engleske abecede i razmaka. Pritom, ne postoje dva susedna razmaka, i rečenica ne počinje niti se završava razmakom. Vaš zadatak je da pomognete Brletu da rekonstruiše ispisanu rečenicu, ukoliko je to moguće.
Opis ulaza
U prvoj liniji standardnog ulaza nalazi se broj . U drugoj liniji standardnog ulaza nalazi se string dužine , koji predstavlja ispisanu rečenicu iz Brletove perspektive. Pritom važi:
- se sastoji isključivo od slova engleske abecede (slova iz skupa ), karaktera _ koji označavaju razmake, i karaktera koji označavaju palmine listove tj. karaktere (slova ili razmake) koji nisu vidljivi.
- U ne postoje dva susedna razmaka, a ni prvi i poslednji karakter nisu razmaci.
Opis izlaza
U prvom i jedinom redu standardnog izlaza ispisati string , koji predstavlja rekonstruisanu rečenicu. Pritom mora da važi:
- se sastoji isključivo od slova engleske abecede i karaktera _ koji označavaju razmake.
- U ne postoje dva susedna razmaka, a ni prvi i poslednji karakter nisu razmaci.
- je savršen pangram.
- Moguće je dobiti od isključivo nizom zamena karaktera slovima engleske abecede ili razmacima.
Ukoliko ima više rešenja, ispisati bilo koje. Ukoliko takvo ne postoji (tj. rekonstrukcija nije moguća) Brle sanja i potrebno je ispisati string SAN
(velikim slovima).
Primer 1
Ulaz
29 abc????ghijklm_nopqrst???xyz?
Izlaz
abcdfe_ghijklm_nopqrstu_vxyzw
Primer 2
Ulaz
28 abcdefghijklmnopqrstuvwxy???
Izlaz
SAN
Objašnjenje primera
U prvom primeru možemo pretpostaviti da prva serija palminih listova prekriva karaktere , druga , a treća . Ovako dobijamo savršen pangram koji ispunjava sve uslove.
U drugom primeru je nemoguće zameniti tri palmina lista karakterima tako da se dobije savršen pangram koji ispunjava sve uslove, pa je u pitanju san.
Ograničenja
- .
Test primeri su podeljeni u pet disjunktnih grupa:
- U test primerima koji vrede 15 poena važi .
- U test primerima koji vrede 15 poena nema palminih listova.
- U test primerima koji vrede 15 poena postoji najviše jedan karakter prekriven palminim listom.
- U test primerima koji vrede 15 poena cela rečenica je prekrivena palminim listovima.
- U test primerima koji vrede 40 poena nema dodatnih ograničenja.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.