965——Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

http://codeforces.com/contest/965/

codeforces

2018.6.12模拟参加（A,B两题）
2018.6.17整理

A：模拟
B：暴力判断（枚举每个点，计算）
C： k 个小朋友围成一圈分 n 个糖 按照 1−k 的顺序轮流给糖。每次给 x 块糖，不足 x 块糖则丢掉结束。规定 x<=M 且 没有小朋友分到的糖的次数比D多（圈数）。求 1号小朋友最多分到多少颗糖。
$(2≤n≤10^{18}, 2≤k≤n, 1≤M≤n, 1≤D≤min(n,1000), M⋅D⋅k≥n)$

考试时没做出来。
D很小，如果D已知，可以贪心的求出一号最多拿多少糖。1拿D次，其他的拿D-1次。

Dx+(D-1)(k-1)x <= n （只要小于等于n就行）
x <= n/(Dk-k+1)
ans = D*x
所以x=n/(Dk-k+1)时最优，枚举每个D即可。

D：
有一些青蛙过河。河宽w . 他们每次可以跳 [1,l]区间内任意长度。河上每个位置 i 有 ai个石头，踩一下就会沉下去。最大化青蛙过河的只数。

模拟参加时的思路：
河岸的青蛙必须都要跳出第一步。所以答案最大是到1-L之间的石头的个数。然后在[1~L],[L+1,2L],[2L+1,3L]...这些区间内取最小值。
显然不对。

比如
最大可以跳三个。
1 1 0 0 0 1
那么这组样例是0，而按上面的做法是1。
（考试时想到了这组样例，知道为什么不对，但没有想到改正）

改正：在所有[1,L],[2,L+1],[3,L+2]的区间里取最小值。

模拟参加的思路2
每个青蛙在i可以跳到[i+1,i+L],贪心：越往右越好；写的不怎么对。。。

E：留坑

代码

//A
int main()
    int  k = read(), n =read(),s = read(),p = read();
    int ans,t;
    if (n % s == 0) t = (n/s);
    else t = (n/s) + 1;
    int t2 = t * k;
    if (t2 % p == 0) ans = t2 / p;
    else ans = t2 / p + 1;
    cout << ans;
    return 0;
}

//C
int main() {
    LL n,m,k,D,ans = 0;
    std::cin >> n >> k >> m >> D;
    for (int d=1; d<=D; ++d) {
        LL x = n/(d*k-k+1);
        if (x==0) break;
        if (x > m) x = m;
        ans = std::max(ans,x*d);
    }
    std::cout << ans;
    return 0;
}

//D
int main() {
    int n = read(),L = read();
    for (int i=1; i<n; ++i) {
        s[i] = s[i-1] + read();
    }
    int ans = 1e9;
    for (int i=L; i<n; ++i) {
        ans = min(ans,s[i]-s[i-L]); // r = i,l = i-L+1
    }
    cout << ans;
    return 0;
}