Codeforces Round #434 (Div. 2, based on Technocup 2018 Elimination Round 1)&&Codeforces 861B Which

B. Which floor?

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

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 ki, fi (1 ≤ ki ≤ 100, 1 ≤ fi ≤ 100), which means that the flat ki is on the fi-th floor. All values ki 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.

Examples

Input

10 3
6 2
2 1
7 3

Output

4

Input

8 4
3 1
6 2
5 2
2 1

Output

-1

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.

题目链接:http://codeforces.com/contest/861/problem/B

分析:直接看代码吧,代码给出了详细注释!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=200;
 4 int n,m,cur=0,idx=0;;
 5 int should[N+10];
 6 inline void ok(int per)
 7 {
 8     int now=1,cnt=0;//now是当前的楼层,cnt是当前楼层的公寓数目
 9     int temp=1;
10     for(int dd=1;dd<=100;dd++)//枚举第dd间房子在哪里
11     {
12         cnt++;//当前楼层的公寓数目递增。
13         if(cnt>per)//如果公寓数目大于每层的楼层数
14         {
15             cnt=1;//进入下一层
16             now++;//楼层个数递增
17         }
18         if(should[dd]!=0&&should[dd]!=now)
19             return;
20         if(dd == n)
21             temp=now;
22         //如果dd公寓不应该在第now层,就结束
23     }
24     //是一个合法的分配
25     if(cur==0)//如果之前没有找到过合法的。
26     {
27         idx=temp;//第n个房子,它就在第now层
28         cur=1;//找到的解数目为1
29     }
30     else//数目大于0了 
31     {
32         if(cur==1)//如果只有一个解的话
33         {
34             if(idx==temp)//如果第n间房子的层数和当前一样,退出
35                 return;
36         }
37         cur++;//否则,答案递增。
38     }
39 }
40 int main(void)
41 {
42     cin>>n>>m;
43     for(int i=1;i<=m;i++)
44     {
45         int x,y;
46         cin>>x>>y;
47         should[x]=y;//x号公寓房子啊第y层
48     }
49     for(int i=1;i<=102;i++)//枚举每层有i间公寓
50         ok(i);
51     if(cur>1||cur==0)//如果解的个数太多,或没解。
52         cout<<-1;
53     else
54         cout<<idx;
55     return 0;
56 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

22350
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

27080
来自专栏小樱的经验随笔

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 ...

28870
来自专栏calmound

HDU 1024 Max Sum Plus Plus

http://acm.hdu.edu.cn/showproblem.php?pid=1024 题意:可不连续的m个子段的最大和 分析:首先由于n很大,所以需要运...

31040
来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.6K90
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

9610
来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

31290
来自专栏小樱的经验随笔

华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood ? B.Choosy in Food •F[i]:从第I个点到终点的期望步数 •F[i] = (F[i +...

36270
来自专栏calmound

Contest - 中南大学第六届大学生程序设计竞赛(Semilive)

题1:1160十进制-十六进制 注意他给的数据范围 2^31,int是 2^31-1 #include<iostream> using namespace st...

27240
来自专栏wannshan(javaer,RPC)

dubbo负载均衡代码分析3(加权轮询策略)

接上篇 https://cloud.tencent.com/developer/article/1109577 加权轮询,我第一次没理解,个人觉得不好理解。于是...

41660

扫码关注云+社区

领取腾讯云代金券