L. Less Coin Tosses

Codeforces
IDCF10234L
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf [samples]
**Definitions** Let $ n, k \in \mathbb{Z}^+ $: number of tables per floor, staircase cost. Let $ S_2 \in \{0,1\}^n $: binary string indicating team presence on second floor (index 1 to $n$). Let $ S_1 \in \{0,1\}^n $: binary string indicating team presence on first floor (index 1 to $n$). Let $ T_1 = \{ i \in \{1, \dots, n\} \mid S_1[i-1] = 1 \} $: set of table indices with teams on floor 1. Let $ T_2 = \{ i \in \{1, \dots, n\} \mid S_2[i-1] = 1 \} $: set of table indices with teams on floor 2. Let $ p \in \{1,2\} \times \{1, \dots, n\} $: printer location (floor, table). **Inconvenience Function** For team at $ (f, a) \in (T_1 \times \{1\}) \cup (T_2 \times \{2\}) $ and printer at $ (p_f, p_a) $: $$ \text{inconvenience}(f, a, p_f, p_a) = \begin{cases} |a - p_a| & \text{if } f = p_f \\ a + k + p_a & \text{if } f \ne p_f \end{cases} $$ **Constraints** - $ T_1 \cup T_2 \ne \emptyset $ (at least one team). - Printer may be placed at any table (occupied or unoccupied) on either floor: $ p_f \in \{1,2\},\ p_a \in \{1, \dots, n\} $. **Objective** Find $ p^* = (p_f^*, p_a^*) $ minimizing: $$ \min_{p_f \in \{1,2\},\ p_a \in \{1,\dots,n\}} \max_{(f,a) \in T_1 \cup T_2} \text{inconvenience}(f, a, p_f, p_a) $$
API Response (JSON)
{
  "problem": {
    "name": "L. Less Coin Tosses",
    "description": {
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10234L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $: number of tables per floor, staircase cost.  \nLet $ S_2 \\in \\{0,1\\}^n $: binary string indicating team presence on second floor (index 1 to $n$).  \nLet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments