{"problem":{"name":"C. Smart Thief","description":{"content":"Ayu managed to steal Budi's treasure box and ready to uncover any secret Budi hides. Unfortunately, the treasure box has some security system to prevent any unauthorized person (e.g., Ayu) from openin","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10200C"},"statements":[{"statement_type":"Markdown","content":"Ayu managed to steal Budi's treasure box and ready to uncover any secret Budi hides. Unfortunately, the treasure box has some security system to prevent any unauthorized person (e.g., Ayu) from opening it.\n\nTo unlock the treasure box, Ayu has to input a correct PIN (Personal Identification Number) of length $N$, which of course, she doesn't have. Ayu has no choice other than trying all possible PIN combinations. However, Ayu notices that this security system has an interesting (old) mechanism.\n\nWhen you enter an $N$ digits PIN, it is evaluated automatically and promptly, i.e. you don't need to push some \"enter\" button to confirm the PIN. Whenever your entered PIN is wrong, it removes the oldest (first) digit and shifts all the remaining to the left, thus, you only need to enter one more (last) digit to make it $N$ length again.\n\nFor example, let $N = 4$. If we input _204320435_, then we actually test 6 PINs (with 5 different PINs): \n\nAs a CS student, Ayu knows that finding the correct PIN by trying all possible combinations can be very time-consuming, but alas, there's no other way. Ayu decides that she wants to test at least $K$ different PINs on the first day. Your task is to help Ayu by simply giving her the string $S$ which contains at least $K$ different PINs. Ayu doesn't care which PIN she's going to test (so long at least there are $K$ different PINs) or whether any PIN is tested more than once in $S$, but string $S$ needs to be as short as possible. If there is more than one possible string for $S$, you can output any of them.\n\nNote that, as this system is quite old, there are only $M$ available digits ranging from $0$ to $9$. \n\nInput begins with a line containing three integers: $N$ $M$ $K$ ($1 <= N <= 100000$, $1 <= M <= 10$, $1 <= K <= min (M^N, 100000)$), representing the PIN length, the number of available digits, and the minimum number of PINs to be tested, respectively. The next line contains $M$ integers: $A_i$ ($0 <= A_i <= 9$), representing the available digits. You may assume all $A_i$ are distinct. You may also assume that the values of $N$, $M$, and $K$ are chosen such that the answer contains no longer than $100000$ digits\n\nOutput in a line the *shortest* string which contains at least $K$ different PINs as its substring. If there is more than one such string, you can output any of them.\n\n_Explanation for the sample input/output #1_\n\nThere are $5$ different PINs of length $3$ tested with the string _7477447_, i.e. _447_, _477_, _744_, _747_, and _774_.\n\n_Explanation for the sample input/output #2_\n\nThere are $9$ different PINs of length $2$ tested with the string _1234554321_, i.e. _12_, _21_, _23_, _32_, _34_, _43_, _45_, _54_, and _55_.\n\n_Explanation for the sample input/output #3_\n\nThere are $2$ different PINs of length $6$ tested with the string _9353593_, i.e. _353593_, and _935359_.\n\n## Input\n\nInput begins with a line containing three integers: $N$ $M$ $K$ ($1 <= N <= 100000$, $1 <= M <= 10$, $1 <= K <= min (M^N, 100000)$), representing the PIN length, the number of available digits, and the minimum number of PINs to be tested, respectively. The next line contains $M$ integers: $A_i$ ($0 <= A_i <= 9$), representing the available digits. You may assume all $A_i$ are distinct. You may also assume that the values of $N$, $M$, and $K$ are chosen such that the answer contains no longer than $100000$ digits\n\n## Output\n\nOutput in a line the *shortest* string which contains at least $K$ different PINs as its substring. If there is more than one such string, you can output any of them.\n\n[samples]\n\n## Note\n\n_Explanation for the sample input/output #1_There are $5$ different PINs of length $3$ tested with the string _7477447_, i.e. _447_, _477_, _744_, _747_, and _774_._Explanation for the sample input/output #2_There are $9$ different PINs of length $2$ tested with the string _1234554321_, i.e. _12_, _21_, _23_, _32_, _34_, _43_, _45_, _54_, and _55_._Explanation for the sample input/output #3_There are $2$ different PINs of length $6$ tested with the string _9353593_, i.e. _353593_, and _935359_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of columns (grid has 1 row and $ n_k $ columns).  \n- Let $ G_k = (g_{k,1}, g_{k,2}, \\dots, g_{k,n_k}) $ be a sequence of characters, where each $ g_{k,i} \\in \\{ \\text{'.', '#', 'o', 's', 'e'} \\} $.  \n- Let $ s_k $ and $ e_k $ be the unique indices such that $ g_{k,s_k} = \\text{'s'} $ and $ g_{k,e_k} = \\text{'e'} $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 27000 $  \n2. $ 2 \\le n_k \\le 2 \\times 10^5 $ for each $ k $  \n3. $ \\sum_{k=1}^T n_k \\le 2 \\times 10^6 $  \n4. Each grid contains exactly one 's' and one 'e'.  \n5. Cells with types '#', 'o', 's', 'e' **cannot** be changed. Only '.' cells may be converted to '#' (blocked).  \n6. Movement is allowed only between adjacent (left/right) empty cells ('.' or 's' or 'e').  \n\n**Objective**  \nFind the minimum number of '.' cells to convert to '#' such that there is **no path** from $ s_k $ to $ e_k $ through adjacent empty cells.  \nIf it is impossible to disconnect $ s_k $ from $ e_k $ (e.g., if they are separated by a mandatory obstacle), output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10200C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}