K. Army

Codeforces

IDCF10106K

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

When HIAST CPC 2016 was finally over, Feras found himself taking the last place !! He went home exhausted from all the hard problems he had tried to solve in the contest. In order to take his mind off the problems for a while, he decided to play a PC game. Yes, he decided to play his favorite game Army (Army is an advanced version of the well known game Red Alert). Rules for Army are quite simple. On the battlefield you have the following 3 concepts: Each one of your soldiers may guard exactly one place, and each place may be guarded by exactly one soldier. In order for a soldier to guard a certain place, he needs to have exactly one weapon. Your job is to cover as many places as possible. However, it's not that simple. On one hand, your soldiers are a bit moody. For the ith soldier you are given two lists: On the other hand, for each place you are given a list consisting of Ck weapons indicating the weapons available at the kth place. Therefore, if you assign soldier x to guard place y, then he can only have one of the weapons available at place y. Please note that it's possible that many places have the same kind of weapons. i.e. 2 places may have the same kind of weapons. Place y is called "guarded" if there is a soldier x standing on place y and carrying a weapon z, such that: Feras is exhausted from HIAST CPC, and he felt frustrated because he couldn't find the perfect distribution for soldiers in order to guard as many places as possible, so he asked for your help. Can you help poor Feras to feel better about him self? Help him calculate the maximum number of places that could be guarded. The first line of input contains a single integer T, indicating the number of test cases. The second line of input consists of three integers (1 ≤ N ≤ 100), (1 ≤ M ≤ 100) and (1 ≤ W ≤ 100), indicating the number of soldiers, the number of places and the number of weapons, respectively. Then N lines follow. The ith line of them describes the places which the ith soldier prefers. Each line starts with an integer Yi denoting the number of the places, followed by Yi distinct integers (1 ≤ yi ≤ M) separated by spaces indicating the list of places which the ith soldier prefers. N lines follow. The ith line of them describes the weapons which the ith soldier prefers. Each line starts with an integer Zi denoting the number of the weapons, followed by Zi distinct integers (1 ≤ zi ≤ W) separated by spaces indicating the list of weapons which the ith soldier prefers. M lines follow. The kth line of them describes the weapons available at the kth place. Each line starts with an integer Ck denoting the number of the weapons, followed by Ck distinct integers (1 ≤ ck ≤ W) separated by spaces indicating the list of the weapons available at the kth place. For each test case print a single line containing the maximum number of places that can be guarded. ## Input The first line of input contains a single integer T, indicating the number of test cases.The second line of input consists of three integers (1 ≤ N ≤ 100), (1 ≤ M ≤ 100) and (1 ≤ W ≤ 100), indicating the number of soldiers, the number of places and the number of weapons, respectively.Then N lines follow. The ith line of them describes the places which the ith soldier prefers. Each line starts with an integer Yi denoting the number of the places, followed by Yi distinct integers (1 ≤ yi ≤ M) separated by spaces indicating the list of places which the ith soldier prefers.N lines follow. The ith line of them describes the weapons which the ith soldier prefers. Each line starts with an integer Zi denoting the number of the weapons, followed by Zi distinct integers (1 ≤ zi ≤ W) separated by spaces indicating the list of weapons which the ith soldier prefers.M lines follow. The kth line of them describes the weapons available at the kth place. Each line starts with an integer Ck denoting the number of the weapons, followed by Ck distinct integers (1 ≤ ck ≤ W) separated by spaces indicating the list of the weapons available at the kth place. ## Output For each test case print a single line containing the maximum number of places that can be guarded. [samples]

Let $ N \in \mathbb{Z}^+ $ be the number of days in a year. Find the smallest integer $ k \geq 1 $ such that the probability of at least one shared birthday among $ k $ people exceeds $ 0.5 $, i.e., $$ 1 - \prod_{i=0}^{k-1} \left(1 - \frac{i}{N}\right) > 0.5 $$

API Response (JSON)

{
  "problem": {
    "name": "K. Army",
    "description": {
      "content": "When HIAST CPC 2016 was finally over, Feras found himself taking the last place !! He went home exhausted from all the hard problems he had tried to solve in the contest. In order to take his mind of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "When HIAST CPC 2016 was finally over, Feras found himself taking the last place !!\n\nHe went home exhausted from all the hard problems he had tried to solve in the contest. In order to take his mind of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ N \\in \\mathbb{Z}^+ $ be the number of days in a year.\n\nFind the smallest integer $ k \\geq 1 $ such that the probability of at least one shared birthday among $ k $ people exceeds $ 0.5 $, i.e.,\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments