2232C1.md (2998B)
1 Source: https://codeforces.com/problemset/problem/2232/C1 2 3 C1. Seating Arrangement (Easy Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is the Easy version of the problem. The difference between the versions is that in this version, the constraints on $n$, $x$, $s$, $t$ are smaller. You can hack only if you solved all versions of this problem. 22 23 Alice's friends have come to the party, and now they are lining up to enter the party. 24 25 There are $x$ tables at the party with $s$ seats each. Each seat can only hold one person. 26 27 Each friend has one of these three following personalities: 28 29 * Introverts (I) who have to sit at an empty table 30 * Extroverts (E) who have to sit at a non-empty table 31 * Ambiverts (A) who can sit at any table. 32 33 Initially, every seat is empty. However, because Alice was eating cakes, her friends had already formed a line, which Alice cannot change their order. For each person in the line, Alice has to assign them a table or kick them out of the party. Each person is seated before the next person is assigned a table. 34 35 Wanting to have a lot of fun at the party, Alice needs to seat as many people as she can at the party. Help her find the maximum number of friends she can have at the party. 36 37 Note that once a friend is seated, they are not allowed to move even if they are not seated according to their personality anymore. 38 39 Input 40 41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. 42 43 The first line of each test case contains three integers $n$, $x$, and $s$ ($1 \le n,x,s \le 3000$) – the number of Alice's friends, the number of tables, and the number of seats per table. The second line contains a string $u$ of length $n$ consisting only of the letters A, E, and I, representing an ambivert, extrovert, and introvert respectively. 44 45 It is guaranteed that the sum of $n$ for all test cases is at most $3000$. 46 47 Output 48 49 For each test case, output an integer: the maximum number of people seated. 50 51 Example 52 53 Input 54 55 ``` 56 6 57 58 5 2 2 59 60 EIAIE 61 62 20 5 5 63 64 AEIEEEEIEAAEIEEEEIEA 65 66 8 2 4 67 68 AAAAAIEE 69 70 8 4 2 71 72 AIEAEAAI 73 74 8 3 3 75 76 AIEAEAAI 77 78 4 2 2 79 80 IAEE 81 ``` 82 83 Output 84 85 ``` 86 4 87 88 20 89 90 7 91 92 7 93 94 7 95 96 4 97 ``` 98 99 Note 100 101 In the first test case, there are $2$ tables with $2$ seats each. Here is one of the ways to achieve the maximum number of people seated. 102 103 The first person is an extrovert. Since all tables are empty, they have to leave the party. 104 105 The second person is an introvert. Alice can assign them to the first table, which is empty. 106 107 The third person is an ambivert. Alice can assign them to the first table. 108 109 The fourth person is an introvert. Alice can assign them to the second table, which is empty. 110 111 The fifth person is an extrovert. Alice can assign them to the second table, which is not empty. 112 113 Thus, four people are seated at the party. This is maximal since there are only four seats at the party.