Շարժական տառերով տպիչ
Դուք ունեք շարժական տառերով տպիչ (movable type printer), հին տպագրական սարք, որը պահանջում է մետաղական փոքր տառերով շարել բառերը: Այս տպիչը թույլ է տալիս կատարել հետևյալ երեք գործողությունները.
- Գործող բառի վերջում տառ ավելացնել
- Ջնջել վերջին տառը, եթե այն գոյություն ունի
- Տպել գործող բառը
Ձեր խնդիրը (առաջադրանքը) գրել ծրագիր է, որը ստանալով
n բառ, պետք է պարզի, թե նվազագույն քանի գործողությամբ հնարավոր է տպել այդ բոլոր բառերը (ցանկացած հերթականությամբ): Բացի այդ, ծրագիրը պետք է ցուցադրի գործողությունների այն հաջորդականությունը, որը թույլ է տալիս հասնել այդ նվազագույնին:Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 25,000), որը նշում է տպվող բառերի քանակը:Այնուհետև տրված են
n տողեր, որոնցից յուրաքանչյուրն ընդգրկում է մեկ բառ, որը կազմված է միայն փոքրատառ լատինատառերից (a - z): Բոլոր բառերն יהיו տարբեր:Ելք
Ծրագիրը պետք է ելքում տպի մեկ ամբողջ թիվ
m, որը ցույց է տալիս նվազագույն գործողությունների քանակը բոլոր բառերն ընտրված հերթականությամբ տպելու համար:Հաջորդ
m տողերից յուրաքանչյուրում պետք է գրվի մեկ նիշ, որը նկարագրում է գործողությունը.- Եթե գործողությունը տառ ավելացնելն է, տպեք հենց այն տառը:
- Եթե գործողությունը հեռացնելն է, տպեք «-» (մինուսանիշ):
- Եթե գործողությունը տպելն է, տպեք «P» (մեծատառ P):
Օրինակ
Մուտք | Ելք |
3
print
the
poem | 20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB