B. Which floor?

Codeforces

IDCF861B

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

In a building where Polycarp lives there are _equal_ number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbered from 1 from lower to upper floors. That is, the first several flats are on the first floor, the next several flats are on the second and so on. Polycarp don't remember the total number of flats in the building, so you can consider the building to be infinitely high (i.e. there are infinitely many floors). Note that the floors are numbered from 1. Polycarp remembers on which floors several flats are located. It is guaranteed that this information is not self-contradictory. It means that there exists a building with equal number of flats on each floor so that the flats from Polycarp's memory have the floors Polycarp remembers. Given this information, is it possible to restore the exact floor for flat _n_? ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100, 0 ≤ _m_ ≤ 100), where _n_ is the number of the flat you need to restore floor for, and _m_ is the number of flats in Polycarp's memory. _m_ lines follow, describing the Polycarp's memory: each of these lines contains a pair of integers _k__i_, _f__i_ (1 ≤ _k__i_ ≤ 100, 1 ≤ _f__i_ ≤ 100), which means that the flat _k__i_ is on the _f__i_\-th floor. All values _k__i_ are distinct. It is guaranteed that the given information is not self-contradictory. ## Output Print the number of the floor in which the _n_\-th flat is located, if it is possible to determine it in a unique way. Print _\-1_ if it is not possible to uniquely restore this floor. [samples] ## Note In the first example the 6-th flat is on the 2-nd floor, while the 7-th flat is on the 3-rd, so, the 6-th flat is the last on its floor and there are 3 flats on each floor. Thus, the 10-th flat is on the 4-th floor. In the second example there can be 3 or 4 flats on each floor, so we can't restore the floor for the 8-th flat.

在波利卡普居住的楼中，每层楼的公寓数量相等。遗憾的是，波利卡普不记得每层有多少公寓，但他记得公寓的编号是从 #cf_span[1] 开始，从底层到顶层依次递增的。也就是说，前若干个公寓位于第一层，接下来的若干个位于第二层，依此类推。波利卡普不记得楼中公寓的总数，因此你可以认为这栋楼是无限高的（即有无限多层）。注意，楼层编号从 #cf_span[1] 开始。波利卡普记得若干公寓所在的楼层。保证这些信息不自相矛盾，即存在一个每层公寓数相等的楼，使得波利卡普记忆中的公寓恰好位于他所记得的楼层上。根据这些信息，能否唯一确定第 #cf_span[n] 号公寓所在的楼层？第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ m ≤ 100]），其中 #cf_span[n] 是你需要确定其所在楼层的公寓编号，#cf_span[m] 是波利卡普记忆中的公寓数量。接下来 #cf_span[m] 行，每行描述波利卡普的记忆：每行包含一对整数 #cf_span[ki, fi]（#cf_span[1 ≤ ki ≤ 100]，#cf_span[1 ≤ fi ≤ 100]），表示公寓 #cf_span[ki] 位于第 #cf_span[fi] 层。所有 #cf_span[ki] 的值互不相同。保证所给信息不自相矛盾。如果能唯一确定第 #cf_span[n] 号公寓所在的楼层，请输出该楼层编号；如果无法唯一确定，请输出 _-1_。在第一个例子中，第 6 号公寓位于第 2 层，而第 7 号公寓位于第 3 层，因此第 6 号公寓是其所在层的最后一间，每层有 3 间公寓。因此，第 10 号公寓位于第 4 层。在第二个例子中，每层可能有 3 或 4 间公寓，因此无法唯一确定第 8 号公寓所在的楼层。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ m ≤ 100]），其中 #cf_span[n] 是你需要确定其所在楼层的公寓编号，#cf_span[m] 是波利卡普记忆中的公寓数量。#cf_span[m] 行接下来，描述波利卡普的记忆：每行包含一对整数 #cf_span[ki, fi]（#cf_span[1 ≤ ki ≤ 100]，#cf_span[1 ≤ fi ≤ 100]），表示公寓 #cf_span[ki] 位于第 #cf_span[fi] 层。所有 #cf_span[ki] 的值互不相同。保证所给信息不自相矛盾。 ## Output 如果能唯一确定第 #cf_span[n] 号公寓所在的楼层，请输出该楼层编号；如果无法唯一确定，请输出 _-1_。 [samples] ## Note 在第一个例子中，第 6 号公寓位于第 2 层，而第 7 号公寓位于第 3 层，因此第 6 号公寓是其所在层的最后一间，每层有 3 间公寓。因此，第 10 号公寓位于第 4 层。在第二个例子中，每层可能有 3 或 4 间公寓，因此无法唯一确定第 8 号公寓所在的楼层。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the target flat number. Let $ m \in \mathbb{Z}_{\geq 0} $ be the number of remembered flat-floor pairs. Let $ M = \{(k_i, f_i) \mid i \in \{1, \dots, m\}\} $ be the set of remembered pairs, where $ k_i $ is the flat number and $ f_i $ is its floor. Let $ x \in \mathbb{Z}^+ $ be the (unknown) number of flats per floor. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 0 \leq m \leq 100 $ 3. For each $ (k_i, f_i) \in M $: - $ 1 \leq k_i \leq 100 $ - $ 1 \leq f_i \leq 100 $ - All $ k_i $ are distinct. 4. For each $ (k_i, f_i) \in M $, it holds that: $$ f_i = \left\lceil \frac{k_i}{x} \right\rceil $$ (i.e., the floor of flat $ k_i $ is determined by $ x $). **Objective** Determine the unique value of $ f_n = \left\lceil \frac{n}{x} \right\rceil $, given that $ x \in \mathbb{Z}^+ $ satisfies all constraints from $ M $. If exactly one such $ x $ exists, output $ \left\lceil \frac{n}{x} \right\rceil $. If multiple valid $ x $ yield different $ f_n $, output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Which floor?",
    "description": {
      "content": "In a building where Polycarp lives there are _equal_ number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbere",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF861B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a building where Polycarp lives there are _equal_ number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbere...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在波利卡普居住的楼中，每层楼的公寓数量相等。遗憾的是，波利卡普不记得每层有多少公寓，但他记得公寓的编号是从 #cf_span[1] 开始，从底层到顶层依次递增的。也就是说，前若干个公寓位于第一层，接下来的若干个位于第二层，依此类推。波利卡普不记得楼中公寓的总数，因此你可以认为这栋楼是无限高的（即有无限多层）。注意，楼层编号从 #cf_span[1] 开始。\n\n波利卡普记得若干公寓所在的楼层。保证这...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the target flat number.  \nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the number of remembered flat-floor pairs.  \nLet $ M = \\{(k_i, f_i) \\mid i \\in \\{1, \\dots...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments