codeforces-scrape

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

2141B.md (2425B)


      1 Source: https://codeforces.com/problemset/problem/2141/B
      2 
      3 B. Games
      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 Alice and Bob are planning to play an online game together but haven't decided on which one yet. Alice has a list of $n$ games she enjoys: $a_1, a_2, \dots, a_n$. Bob, on the other hand, has a list of $m$ games he likes: $b_1, b_2, \dots, b_m$. They share at least one game in common between their lists.
     22 
     23 To choose a game, they take turns suggesting games from their lists. Alice begins by suggesting one of her favorite games. If Bob likes it, they play that game. If not, Bob suggests one of his favorite games. If Alice likes it, they play that game. This alternating process continues, with Alice and Bob each suggesting games from their lists in turn, ensuring that no game is suggested more than once.
     24 
     25 Your task is to calculate the maximum possible number of suggestions they will make while choosing which game to play.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 100$).
     32 
     33 The second line contains $n$ integers $a_1 \lt a_2 \lt \cdots \lt a_n$ ($1 \le a_i \le 100$).
     34 
     35 The third line contains $m$ integers $b_1 \lt b_2 \lt \cdots \lt b_m$ ($1 \le b_i \le 100$).
     36 
     37 Arrays $a$ and $b$ contain at least one common integer.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the maximum possible number of suggestions they will make while choosing which game to play.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 2 3
     51 
     52 1 2
     53 
     54 2 3 5
     55 
     56 1 1
     57 
     58 5
     59 
     60 5
     61 
     62 4 2
     63 
     64 1 3 4 7
     65 
     66 4 6
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 3
     73 1
     74 4
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, the maximum number of suggestions is $3$. It is achieved as follows:
     80 
     81 * Alice suggests game $1$, but Bob does not like it;
     82 * Bob suggests game $5$, but Alice does not like it;
     83 * Alice suggests game $2$, which Bob likes, and they go to play that game.
     84 
     85 In the second test case, Alice can only suggest game $5$, which Bob likes, so they will immediately go to play it.
     86 
     87 In the third test case, the maximum number of suggestions is $4$. It is achieved as follows:
     88 
     89 * Alice suggests game $7$, but Bob does not like it;
     90 * Bob suggests game $6$, but Alice does not like it;
     91 * Alice suggests game $1$, but Bob does not like it;
     92 * Bob suggests game $4$, which Alice likes, and they go to play it.