{"problem":{"name":"E. Singhal and Missing Number","description":{"content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from code","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10276E"},"statements":[{"statement_type":"Markdown","content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._\n\nChitra is playing with consecutive numbers from $n$ to $m$ $(3 <= n + 2 <= m <= 10^9)$. Singhal tells her that the contest of Number Theory is over and concatenates all the numbers to a String But he miss *one number* from anywhere in the middle to concatenate.\n\nExample — If she is playing with numbers from $3$ to $7$. He can concatenates this in the following way - $3567$ missing $4$ or other possibility would be $3467$, $3457$, but not $4567$, $3456$ , $367$ , $357$.\n\nHe gave back this concatenated string to her. Help her in finding the missing number. If there are many solution to this, you have to find the minimum possible.\n\n*Note: It is guaranteed that a solution smaller than $10^9$ must exists in the given inputs.*\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.\n\nEach query contains a single concatenated string $S (1 <= | S | <= 10^5)$. $| S |$ is the length of the string.\n\nIt is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\nFor each test from the input print the missing number $< 10^9$. Print the answers to the tests in the order in which the tests are given in the input.\n\nIn the first query - the string S = _13_, then the sequence is $1$, $3$ and the missing number is $2$.\n\nIn the second query - the string S = _3457_, then the sequence is $3$, $4$, $5$, $7$ and the missing number is $6$.\n\nIn the third query - the string S = _1314151718_, then the sequence is $13$, $14$, $15$, $17$, $18$ and the missing number is $16$.\n\nIn the last query - the string S = _234235236238_, then the sequence is $234$, $235$, $236$, $238$ and the missing number is $237$.\n\n## Input\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a single concatenated string $S (1 <= | S | <= 10^5)$. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\n## Output\n\nFor each test from the input print the missing number $< 10^9$. Print the answers to the tests in the order in which the tests are given in the input.\n\n[samples]\n\n## Note\n\nIn the first query - the string S = _13_, then the sequence is $1$, $3$ and the missing number is $2$.In the second query - the string S = _3457_, then the sequence is $3$, $4$, $5$, $7$ and the missing number is $6$.In the third query - the string S = _1314151718_, then the sequence is $13$, $14$, $15$, $17$, $18$ and the missing number is $16$.In the last query - the string S = _234235236238_, then the sequence is $234$, $235$, $236$, $238$ and the missing number is $237$.","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} $ be the number of students.  \n- Let $ p_k \\in \\mathbb{Z} $ be the passing threshold percentage ($ 1 \\leq p_k \\leq 100 $).  \n- For each student $ i \\in \\{1, \\dots, n_k\\} $, define two scores: $ a_{k,i}, b_{k,i} \\in \\mathbb{Z} $ with $ b_{k,i} \\leq a_{k,i} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 \\times 10^3 $  \n2. $ 1 \\leq n_k \\leq 2 \\times 10^5 $ for each $ k $  \n3. $ 1 \\leq b_{k,i} \\leq a_{k,i} \\leq 10^9 $ for all $ i, k $  \n4. $ \\sum_{k=1}^T n_k \\leq 5 \\times 10^5 $  \n\n**Objective**  \nFor each test case $ k $, determine the maximum number of students that can pass under any assignment of mindsets (i.e., for each student $ i $, choose either $ a_{k,i} $ or $ b_{k,i} $ as their score), such that:  \n- Let $ x $ be the maximum score among all students in that assignment.  \n- A student passes if their score $ \\geq \\left\\lceil x \\cdot \\frac{p_k}{100} \\right\\rceil $.  \n- Maximize the number of passing students over all possible assignments.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10276E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}