DAPC22-053.Abbreviated Aliases
Medium · 2 s · 256 MB
- icpc
- dapc
- 2022
You are the owner of a large successful internet site with lots of users. All these users have chosen an alias of exactly characters for logging into the site. Recently, you noticed that you started running into disk space issues: storing all these aliases takes up a lot of data!
You do not have enough money to buy extra storage, so you are looking for ways to reduce the storage space needed. A friend gives you the following compression idea that might help: instead of storing the full alias for each user, you might get away with only storing a prefix of that alias, as long as no other alias has the same prefix. For example, if you just have the aliases james and jacob, you can store only jam and jac and still be able to identify them both.
This idea sounds quite interesting to you, and you are looking forward to finally having more space available on your disk again. You would like to find out how much space you need to store all aliases using this compression technique.
Giriş formatı
The input consists of:
• One line with two integers and (, ), the number of aliases and the length of each alias.
• lines, each with an alias: a string consisting of exactly English lowercase characters (a-z). Each alias is unique.
Çıxış formatı
Output the total number of characters you still need to store if you apply this compression technique.
Qeyd
Source: Delft Algorithm Programming Contest 2022 · Author: Ragnar Groot Koerkamp · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 7 of the 23 original test cases (the largest) are omitted here to keep the problem lightweight.
Nümunələr
Giriş #1
2 5 james jacob
Çıxış #1
6
Giriş #2
4 4 xxxx yxxx xxyx yxxy
Çıxış #2
14