CF861B

CF861B

​​ B. Which floor? time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard 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.

一共n只有100所以暴力枚举

枚举每层有多少个房间，然后验证是否正确，如果满足所有给的条件，就算一个n对应的层数

然后看n会对应几个层数，超过1就是-1

#include#include#define N 110int n,m,num[110],fl[110]; int main(){ freopen("cf.in","r",stdin); scanf("%d%d",&n,&m); if (n==1) {printf("1");return 0;} if (m==0){printf("-1");return 0;} for (int i=1;i<=m;++i) scanf("%d%d",&num[i],&fl[i]); int ans=0,cnt=0,tmp; for (int i=1;i<=100;++i){ bool flag=true; for (int j=1;j<=m;++j) if (num[j]<=(fl[j]-1)*i||num[j]>fl[j]*i){flag=false;break;} if (flag) { ++cnt; if (n%i==0) { ans=n/i;if (cnt==1) tmp=ans;if (ans!=tmp) {printf("-1");return 0;} }else { ans=n/i+1;if (cnt==1) tmp=ans;if (ans!=tmp) {printf("-1");return 0;} } } } printf("%d",tmp); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。