CodeForces 858B Which floor?

本文介绍了一个算法问题,通过已知部分楼层与房间号的关系,来推断特定房间位于哪一层。该算法考虑了不同情况下的特殊情况,并通过输入输出示例帮助理解。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

题目:

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 ≤ 1000 ≤ 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 ≤ 1001 ≤ 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.


代码:

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
    int m,n,i,x,y,mi=0,ma=105,k=0,ans,flag=1;
    scanf("%d%d",&m,&n);
    if(n==0)
    {
        if(m==1)printf("1\n");                  //特判m=1,n=0
        else printf("-1\n");                    //特判m>1,n=0
    }
    else
    {
        for(i=0;i<n;i++)                        //x为已知房间数 y为楼层
        {                                       //y-1楼最大值为x-1 y楼最小值为x
            int w;
            scanf("%d%d",&x,&y);                //接下来找到最大值里的最小值,最小值里的最大值
            if(y==1)                            //防止除0
                if(x>mi)mi=x;
            else
            {
                w=(x-1)/(y-1);                  //上一层最大值
                if(w<ma)ma=w;                   //找到最大值里的最小值存到ma

                w=0;                            //除不尽结果要+1
                if(x%y!=0)w++;
                w+=x/y;                         //找到最小值里的最大值存到mi
                if(w>mi)mi=w;
            }
        }
        if(m%mi!=0)k++;                         //确定可能楼层是否唯一
        k+=m/mi;
        ans=k;
        k=0;
        if(m%ma!=0)k++;
        k+=m/ma;
        if(ans!=k)flag=0;
        if(flag==1)
            printf("%d\n",ans);
        else
            printf("-1\n");
    }
    return 0;
}



### 关于 Codeforces 1853B 的题解与实现 尽管当前未提供关于 Codeforces 1853B 的具体引用内容,但可以根据常见的竞赛编程问题模式以及相关算法知识来推测可能的解决方案。 #### 题目概述 通常情况下,Codeforces B 类题目涉及基础数据结构或简单算法的应用。假设该题目要求处理某种数组操作或者字符串匹配,则可以采用如下方法解决: #### 解决方案分析 如果题目涉及到数组查询或修改操作,一种常见的方式是利用前缀和技巧优化时间复杂度[^3]。例如,对于区间求和问题,可以通过预计算前缀和数组快速得到任意区间的总和。 以下是基于上述假设的一个 Python 实现示例: ```python def solve_1853B(): import sys input = sys.stdin.read data = input().split() n, q = map(int, data[0].split()) # 数组长度和询问次数 array = list(map(int, data[1].split())) # 初始数组 prefix_sum = [0] * (n + 1) for i in range(1, n + 1): prefix_sum[i] = prefix_sum[i - 1] + array[i - 1] results = [] for _ in range(q): l, r = map(int, data[2:].pop(0).split()) current_sum = prefix_sum[r] - prefix_sum[l - 1] results.append(current_sum % (10**9 + 7)) return results print(*solve_1853B(), sep='\n') ``` 此代码片段展示了如何通过构建 `prefix_sum` 来高效响应多次区间求和请求,并对结果取模 \(10^9+7\) 输出[^4]。 #### 进一步扩展思考 当面对更复杂的约束条件时,动态规划或其他高级技术可能会被引入到解答之中。然而,在没有确切了解本题细节之前,以上仅作为通用策略分享给用户参考。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值