link

暑假期间，学校不提供午餐，Gnar 只好找伙计们一起点外卖。
尴尬的是，外卖很快送到却没人乐意去校门口拿，毕竟户外可是 35degree!text{C}35°C 高温！此时 Gnar 想到了好主意：“我给一人捏了一张纸团，其中一张写有记号，不如我们抓阄决定，谁抽到带记号的谁去拿！”
于是 Gnar 连续拿了六天的外卖。
这可让他不服又委屈：“换个规则！一人准备三张纸团，五张有记号，每人抽三张，记号最多的去拿！”
Gnar 紧张地展开手中的纸团，两个记号赫然映在眼前。大伙们刚想放声大笑他的非酋运气，有人缓缓举起三张纸片说道：“我也抽到了两个记号……”

前言

是一道蛮有意思的题目~ 而且标题也不戳~ 刚看还可能会懵了，但稍微想一下就能弄明白了

既然是月赛，那么题解肯定要写详细点了，还看不懂可以来私信问我

并且对我这种蒟蒻或者数学水平差点的同学都非常友好

建议比赛时候来一打

思路

试想，你有$n+1$个题目，但是只有$n$个同学要做，那么必然就会有一个同学要做两道题是不是？废话

这称之为“抽屉原理”，也就是题目标签中的“鸽笼”。

回到题目，我们可以看做把$k$个带记号的纸团分到$n$个人的手里，要求有恰好$p$个人是最多的。

显而易见，这$p$个人拿的有标记的纸团是一样多的，那么他们每个人最多拿$\lfloor \frac{k}{p} \rfloor$ 个有标记纸团，否则$k$就不够有$p$人拿最多的标记纸团了。

我们设想这样的情况：

有正好$p$个人拿了$\lfloor \frac{k}{p} \rfloor$ 个有标记纸团，此时还剩下$k - \lfloor \frac{k}{p} \rfloor \times k$个有标记的纸团，但这么多纸团不管怎么分到剩下$n-p$个人手里时，这$n-p$个人手里还是有人拿了超过$\lfloor \frac{k}{p} \rfloor$张纸团。

这种分配显然不符合要求，那怎么办呢？

如果让那$p$个人少拿纸团，那么剩下$n-p$个人手里必定会有人拿更多纸团，还是不行，所以这种情况是一定不行的。

那么就很简单了

倘若$\lceil \frac{k - \lfloor \frac{k}{p} \rfloor \times k }{n-p}\rceil \geq \lfloor \frac{k}{p} \rfloor$ 那么就是不行的，此处向上取整是因为纸团显然是整数个，不能取等的原因是因为如果取等那么就不是恰好$p$个人满足条件了。

当答案为真时构造可以直接用上面提到的情况。

其他地方要注意的是写代码时注意精度问题和$n=p$的特判

代码

#include<bits/stdc++.h>
#define int long long
//注意n*m可能超出int范围
using namespace std;
int n,m,k,p,las;
int check(int x){//此处x是k/p向下取整
    if(n==p){//n=p时的特判，不然下面会除以0
        if(x*p!=k) return 0;
        else return 1;
    }
    //算完ceil后注意要转为int
    //（当然如果下面用乘法可以避免精度问题）
    if(min(m,(int)(ceil((double)(k-x*p)/(n-p))))>=x) return 0;
    return 1;
}
signed main(){
    cin>>n>>m>>k>>p;   
    int ans=k/p;
    ans=min(ans,m);//此处是避免k/p向下取整大于m，拿的有标记纸团显然不能大于一共拿的纸团数
    if(check(ans)){
        cout<<"Yes\n";
        las=(k-ans*p);//所剩余的有标记纸团
        for(int i=0;i<p;i++){//显然有p个拿了ans个标记纸团
            cout<<ans<<' '<<m-ans<<endl;
        }
        for(int i=0;i<(n-p);i++){//此处剩余部分的构造可以让尽量多的人拿ans-1个纸团，剩下的人不拿纸团
            int tmp=ans-1;
            tmp=min(tmp,las);
            las-=tmp;
            cout<<tmp<<' '<<m-tmp<<endl;
        }
    }
    else{
        cout<<"No\n";
    }
    return 0;
}