Identifier Sequence
Time limit7sMemory limit128 MB
Split a digit string into the maximum number of pieces so that no two pieces have the same numeric value, with leading zeros allowed.
- Level
Medium7 of 10
- Topics
- String, Dynamic programming, Hash map
- Solved
- No attempts yet
Problem
Johnny is a hacker, and he recently obtained the database of a large bank. His most important task is to extract the clients' IDs from it. The IDs are sorted and concatenated into a single sequence of digits, without marks showing where each concatenation happened. Those marks are stored in a separate file that Johnny does not have. Johnny wants to recover the IDs, that is, compute how many IDs can be obtained by cutting the sequence into pieces. Johnny believes in his luck: if there are many ways to cut the sequence, the one that maximises the number of IDs must be the correct one.
The IDs were assigned at different stages, so they can have different lengths and leading zeroes. Johnny knows that each ID has a unique numerical value when read as a number in base-10 positional notation.
Input
The first and only line of the input contains a sequence of () base-10 digits. There are no other characters between the digits, in particular no spaces. This is the sequence of IDs that Johnny has.
Output
Print one natural number: the maximal number of clients' IDs into which the sequence can be cut.
Hint
The sequence of clients' IDs corresponding to the answer is 1, 05, 40, 910. The ID 05 has numerical value 5.