H. Hard Drive

Codeforces

IDCF10248H

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. You see, the hard drive is essentially a string of ones and zeros, and its weight depends on the number of "bit changes" in it: for any two adjacent bits storing two different values, the hard drive gets slightly heavier, so Pia cannot just store arbitrary information on it. To make matters worse, the drive is so old that some bits are already broken and will always store zeros. The first bit will never be broken, but the last bit will always be. Pia decides to treat this situation as a challenge: she is now trying to modify the information on the hard drive so that it has exactly the maximum number of bit changes permitted by the airline. However, the broken bits make this harder than expected, so she needs your help. Find a bit pattern which can be stored on the hard drive and has exactly the desired number of bit changes. The input consists of: Output a bit string of length $n$, representing Pia's hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists. ## Input The input consists of: One line with three integers $n$, $c$, and $b$ ($2 <= n <= 5 dot.op 10^5$, $1 <= c, b <= n -1$), the size of the hard drive in bits, the desired amount of bit changes, and the number of broken bits. The positions on the hard drive are numbered from $1$ to $n$. One line with $b$ integers $z_1, \\dots, z_b$ ($2 <= z_1 < z_2 < \\dots < z_b = n$), the positions of the broken bits on the hard drive. ## Output Output a bit string of length $n$, representing Pia's hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists. [samples]

**Definitions** Let $ D = [0, w] \times [0, h] $ be the rectangular door. Let $ W = \{ (x_{1,i}, y_{1,i}), (x_{2,i}, y_{2,i}) \}_{i=1}^n $ be the set of $ n $ wires, where each wire connects two distinct sides of $ D $, and no endpoint lies at a corner or within $ 10^{-6} $ of a corner. **Constraints** 1. $ 1 \le n \le 10^6 $, $ 1 \le w, h \le 10^8 $ 2. For each wire $ i $: - $ 0 \le x_{1,i}, x_{2,i} \le w $, $ 0 \le y_{1,i}, y_{2,i} \le h $ - The endpoints lie on different sides of the rectangle (i.e., one on left/right, the other on top/bottom, or one on top/bottom and the other on left/right) - No endpoint coincides with a corner or another wire endpoint (all points are distinct) **Objective** Find the minimum number $ k $ of straight line segments (cuts) such that: - Each cut connects two different sides of $ D $ (i.e., is a chord crossing the rectangle) - Each cut intersects every wire in $ W $ - No cut endpoint is within $ 10^{-6} $ of any wire endpoint or corner Output $ k $ and the $ k $ cuts as line segments $ (x_1, y_1) \to (x_2, y_2) $, with endpoints on different sides of $ D $.

API Response (JSON)

{
  "problem": {
    "name": "H. Hard Drive",
    "description": {
      "content": "Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. You see, the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10248H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. You see, the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ D = [0, w] \\times [0, h] $ be the rectangular door.  \nLet $ W = \\{ (x_{1,i}, y_{1,i}), (x_{2,i}, y_{2,i}) \\}_{i=1}^n $ be the set of $ n $ wires, where each wire connects two d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments