F. The Best Strategy

Codeforces

IDCF10102F

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Carlo Ancelotti "Real Madrid's coach" is so Sad and disappointed, and Florentino Perez fired him after getting knocked out from the UEFA Champions League against Juventus. Carlo is so good in algorithms and strategies (he is an engineer), and he heard about the ACM competition and decided to train a team to qualify to ICPC. After 2 years of training Carlo became really experienced with his team, and now he knows how much time his team needs to solve a problem (read it and code it correctly). Given the required solving time for each problem, help Carlo to determine the highest number of problems his team can solve with the minimum possible penalty. The total penalty is the sum of penalties for all solved problems. The penalty for a solved problem is equal to the number of minutes which have passed after the starting of the contest when this problem is submitted. And the period of the contest is 300 minutes. Your program will be tested on one or more test cases. The first line of the input contains a single integer *T* (1 ≤ *T* ≤ 100) the number of test cases. Followed by *T* test cases. Each test case consists of two lines. The first line contains a single integer *N* (8 ≤ *N* ≤ 15), the number of problems .The next line consists of *N* integers separated by a single space: *pi* (4 ≤ *pi* ≤ 300) which refers to the solving time for each problem. For each test case print the highest number of problems his team can solve and the minimum possible penalty. ## Input Your program will be tested on one or more test cases. The first line of the input contains a single integer *T* (1 ≤ *T* ≤ 100) the number of test cases. Followed by *T* test cases. Each test case consists of two lines. The first line contains a single integer *N* (8 ≤ *N* ≤ 15), the number of problems .The next line consists of *N* integers separated by a single space: *pi* (4 ≤ *pi* ≤ 300) which refers to the solving time for each problem. ## Output For each test case print the highest number of problems his team can solve and the minimum possible penalty. [samples]

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ a_k \in \Sigma^* $ be a string with $ 4 \leq |a_k| \leq 1000 $, where $ \Sigma $ is the set of lowercase English letters. - Let $ b_k \in \Sigma^* $ be a string with $ |b_k| = 4 $. **Constraints** 1. $ 1 \leq T \leq \text{unknown upper bound (implied by input)} $ 2. For all $ k $, $ 4 \leq |a_k| \leq 1000 $ and $ |b_k| = 4 $. **Objective** For each test case $ k $, determine: - If $ b_k $ is a substring of $ a_k $, output **'good'**. - Else, if there exists an index $ i \in \{0, 1, \dots, |a_k|\} $ and a letter $ c \in \Sigma $ such that inserting $ c $ at position $ i $ in $ a_k $ yields a string containing $ b_k $ as a substring, output **'almost good'**. - Otherwise, output **'none'**.

API Response (JSON)

{
  "problem": {
    "name": "F. The Best Strategy",
    "description": {
      "content": "Carlo Ancelotti \"Real Madrid's coach\" is so Sad and disappointed, and Florentino Perez fired him after getting knocked out from the UEFA Champions League against Juventus.  Carlo is so good in algorit",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10102F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Carlo Ancelotti \"Real Madrid's coach\" is so Sad and disappointed, and Florentino Perez fired him after getting knocked out from the UEFA Champions League against Juventus.  Carlo is so good in algorit...",
      "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 $ a_k \\in \\Sigma^* $ be a string with $ 4 \\leq |a_k| \\leq 1000 $, wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments