J. Feeling of Comradeship

Codeforces

IDCF10081J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

I was tired. Tired of hiding and wandering. Throw the rules out the window, odds are you'll go that way too. I just wanted everything to be finished. The crying heavens had already given a verdict for me, I was just looking for somebody to execute it. The castle of Dragon was not defenseless, it was ready for my visit. The beast inside me was woking up and rubbing his eyes. I had already known every single bandit guarding Dragon's castle. It was quite useful to have connections in knight orders. There were only n men there. There had been some bigger frays. And not all of them desperately wanted to die by my hand that night. I knew that the i-th of them would have decided to fight only if at least ai other bandits had decided the same. I was slowly approaching the gates, wondering what was the maximal number of people who might have opposed me. The first line contains a single integer n (1 ≤ n ≤ 105) — the number of bandits in the castle of Dragon. The second line contains n integers separated by spaces: ai (0 ≤ ai ≤ 109) — the minimal number of other bandits with whom together the i-th bandit is ready to fight. Output a single integer — the maximal number of bandits that might be ready to fight for Dragon's castle. ## Input The first line contains a single integer n (1 ≤ n ≤ 105) — the number of bandits in the castle of Dragon.The second line contains n integers separated by spaces: ai (0 ≤ ai ≤ 109) — the minimal number of other bandits with whom together the i-th bandit is ready to fight. ## Output Output a single integer — the maximal number of bandits that might be ready to fight for Dragon's castle. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ M_k: \Sigma \times \Sigma \to \Sigma $ be a symmetric binary operation over $ \Sigma = \{a, b, \dots, z\} $, represented by a $ 26 \times 26 $ matrix where $ M_k[i][j] $ is the result of combining the $ i $-th and $ j $-th lowercase letters (with $ a = 1, \dots, z = 26 $), and $ M_k[i][j] = M_k[j][i] $. - Let $ A_k = (a_1, a_2, \dots, a_n) \in \Sigma^n $ be the input string of length $ n = |A_k| $, with $ 1 \leq n \leq 10{,}000 $. - Let $ V = \{a, e, i, o, u\} \subset \Sigma $ be the set of vowels. **Constraints** 1. $ 1 \leq T \leq \text{some bound (unspecified)} $ 2. For each $ k $: - $ M_k $ is symmetric: $ M_k[i][j] = M_k[j][i] $ for all $ i,j \in \{1,\dots,26\} $ - $ 1 \leq |A_k| \leq 10{,}000 $ **Game Rules** - Two moves: - **LEFT**: Replace the two rightmost characters $ (a_{n-1}, a_n) $ with $ M_k(a_{n-1}, a_n) $, reducing string length by 1. - **RIGHT**: Replace the two leftmost characters $ (a_1, a_2) $ with $ M_k(a_1, a_2) $, reducing string length by 1. - Players alternate turns, Salah starts first. - Game ends when string has length 1. - Salah wins if the final character $ \in V $; otherwise Marzo wins. - Both players play optimally. **Objective** For each test case $ k $, determine the winner under optimal play: $$ \text{Winner}(k) = \begin{cases} \text{Salah} & \text{if the final character under optimal play} \in V \\ \text{Marzo} & \text{otherwise} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "J. Feeling of Comradeship",
    "description": {
      "content": "I was tired. Tired of hiding and wandering. Throw the rules out the window, odds are you'll go that way too. I just wanted everything to be finished. The crying heavens had already given a verdict for",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10081J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "I was tired. Tired of hiding and wandering. Throw the rules out the window, odds are you'll go that way too. I just wanted everything to be finished. The crying heavens had already given a verdict for...",
      "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 $ M_k: \\Sigma \\times \\Sigma \\to \\Sigma $ be a symmetric binary operation...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments