Hi, coders! I welcome you to LiShi Simulation Contest 3.
Details of the contest:
- Tournament Time: 2020/2/13-2020/2/29
- Place: Here
- Problem Count:3(100+100+100)
- Time: 1 Hour
- Difficulty: D2B-D2C
- Subtask: YES for all three problems!
- Characters: Ookami,Doragon,Ninetail,XGN,ZJS
- Writer: XGN
- Source of the problem: All original
Wow, such close LSS isn't it? Played Temmie's game today and is surprised that there is a similar character as Ookami!
Problem A - The Idiom Number
Key observation: Duplicate letters doesn't change the relative value of two integers
For example, "11223" "11332" both match "AABBC", and 11223<11332. So I can say for certain that when chaning "AABBC" to "ABC", the first integer is still smaller, because 123<132.
So we remove all duplicate letters in the string and only leave the first occurance of each letter. Then we needs to find out the k-th smallest integer. This is pretty easy as all letters are different now.
We just need to minus 1 from T and set corresponding letters to digits. Don't forget to add 1 in the first digit.
For example, find the 6th smallest "AABCD" can be turned to find the 6th smallest "ABCD". To find out that, we minus 1 from T and get T=0005. So we set A=0+1=1(because it's the first letter),B=0,C=0,D=5. Thus the answer is 11005.
Problem B - Village Tour
One-sentence solution: The answer is 2 times the total length of the edges minus the diameter of the tree
Consider this problem If we start from 1 fixed point and pass each node at least 1 time and back to the fixed point, what's the distance we will walk at least?. The answer is always 2 times the total length of the edges. If we consider the fixed point to be the root of the tree. Then for each edge, we will walk down once and walk up once in the best route.
Then let's consider this problem If we start from 1 fixed point and pass each node at least 1 time and end at another point, what's the distance we will walk at least?. The answer is always 2 times the total length of the edges minus the depth of the tree if the fixed point is considered as the root. The proof is homework for readers.
Then we will discover the solution for this problem. Proof is homework for readers too.
Problem C - The cards
This problem is the same problem as OBCYSIO Ep.28.5.
Search on this site to find the problem.