codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.