L. Lottery Tickets

Codeforces

IDCF10262L

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Setsuna is almost out of money! Therefore, she always thinks about ways to get rich overnight. She finds that buying lottery tickets is a wonderful choice, and she decides to use her lucky number as the lottery number. Setsuna uses some unique methods to pick her lucky numbers. She will first select $n$ magic cards. Each card is written with a digit between $0$ and $9$ inclusively. Then she will use some cards to construct a number. She believes that the largest number she can construct which can be divided by 4 is her lucky number. It is unnecessary to use all the cards, and it is possible that such lucky number does not exist. Because she is daydreaming of getting rich, only you can help her find this lucky number. The input consists of multiple test cases. The first line contains a single integer $t (1 <= t <= 3 times 10^5)$, indicating the number of test cases. Each of the next $t$ lines contains $10$ integers $c_0, c_1, \\\\cdots, c_9 (0 <= c_i <= 10^5, sum_{i = 0}^9 c_i > 0)$, where $c_i$ indicates the number of cards written with number $i$. It is guaranteed that the sum of $sum_{i = 0}^9 c_i$ of all test cases does not exceed $3 times 10^5$. For each test case given in the input, print the lucky number(without leading zero) or $-1$ if such lucky number does not exist. ## Input The input consists of multiple test cases. The first line contains a single integer $t (1 <= t <= 3 times 10^5)$, indicating the number of test cases.Each of the next $t$ lines contains $10$ integers $c_0, c_1, \\\\cdots, c_9 (0 <= c_i <= 10^5, sum_{i = 0}^9 c_i > 0)$, where $c_i$ indicates the number of cards written with number $i$.It is guaranteed that the sum of $sum_{i = 0}^9 c_i$ of all test cases does not exceed $3 times 10^5$. ## Output For each test case given in the input, print the lucky number(without leading zero) or $-1$ if such lucky number does not exist. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case, let $ c_i \in \mathbb{Z}_{\geq 0} $ denote the count of cards with digit $ i \in \{0, 1, \dots, 9\} $, where $ \sum_{i=0}^9 c_i > 0 $. **Constraints** 1. $ 1 \leq t \leq 3 \times 10^5 $ 2. $ 0 \leq c_i \leq 10^5 $ for all $ i \in \{0, 1, \dots, 9\} $ 3. $ \sum_{i=0}^9 c_i > 0 $ for each test case 4. Total sum of $ \sum_{i=0}^9 c_i $ across all test cases $ \leq 3 \times 10^5 $ **Objective** For each test case, find the largest integer (without leading zeros) that can be formed using a non-empty subset of the available cards such that the number is divisible by 4. If no such number exists, output $-1$. A number is divisible by 4 if and only if its last two digits form a number divisible by 4.

API Response (JSON)

{
  "problem": {
    "name": "L. Lottery Tickets",
    "description": {
      "content": "Setsuna is almost out of money! Therefore, she always thinks about ways to get rich overnight.  She finds that buying lottery tickets is a wonderful choice, and she decides to use her lucky number as",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10262L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Setsuna is almost out of money! Therefore, she always thinks about ways to get rich overnight. \n\nShe finds that buying lottery tickets is a wonderful choice, and she decides to use her lucky number as...",
      "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, let $ c_i \\in \\mathbb{Z}_{\\geq 0} $ denote the count of cards with digit $ i \\in \\{0, 1, \\dots, 9\\} $, whe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments