Preface

周六早上9点开始打的校赛初赛，中间基本没间断地打到6点左右写了16题（全队）

然后剩下两题C交给大腿队友了，B又完全没思路只好作罢

不过作为新生队伍能做16/18还是很猛的说，昨天的状态还行，队友也很给力（已经不能用给力来形容了简直就是带我飞了）

不过最后1h由于比赛的服务器崩了所以导致队友辛苦写了3h的C交不了还是有点难受的说，而且现在想上平台看下提交的代码也暂时找不到了

因此下面的题解部分如果是我写的题的话会附个代码（因为电脑里有存档），但不是我写的题可能就口胡个思路了的说

不管怎么说希望半个月之后的正赛能延续今天的好状态吧

关于题面和提交地址可以看CF上的镜像

A. 能量采集

本来早上看到题目有个雏形准备开写了，但有队友说他有思路就决定交给他了我先写别的去了

结果后面他写了一会发现做法假了，就只好上去救个场了，不过这题好像打破了我这次比赛连续将近10题的1A记录，WA了一发在转移方程的下标写错

回到正题，显然我们把所有相邻的可以走到的AA进行连边，题目就变成求在一个DAG上长度为\(k\)的路径的贡献，其中一个路径的贡献为从\((1,1)\)走到它的起点的方案数乘上它的终点走到\((n,m)\)的方案数

显然可以由此设计状态\(f_{i,j,p}\)表示以\((i,j)\)为结尾的所有长度为\(p\)的路径的起点的贡献之和，转移的话是非常trivial的

最后只要用所有的\(f_{i,j,k}\)作为终点乘上贡献值即可，而作为起点的贡献直接累计到\(f_{i,j,1}\)上即可

注意到我们并不用真的把DAG建出来，而是只要按照\(i+j\)的从小到大枚举状态即可，不过如果不想管那么多的话直接写个记搜也是可以的

总复杂度\(O(nmk)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=405,mod=998244353;
int n,m,k,g[N][N],f[N][N][N<<1],ans; char a[N][N];
inline int sum(CI x,CI y)
{
	return x+y>=mod?x+y-mod:x+y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i,j,x,y; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=n;++i) scanf("%s",a[i]+1);
	for (g[1][1]=i=1;i<=n;++i) for (j=1;j<=m;++j)
	if (i!=1||j!=1) g[i][j]=sum(g[i-1][j],g[i][j-1]);
	for (i=2;i<=n+m;++i) for (x=1;x<=n;++x)
	{
		if (y=i-x,y<1||y>m||a[x][y]=='B') continue;
		for (f[x][y][1]=g[x][y],j=2;j<=k;++j)
		{
			if (x>1&&a[x-1][y]=='A') f[x][y][j]=sum(f[x][y][j],f[x-1][y][j-1]);
			if (y>1&&a[x][y-1]=='A') f[x][y][j]=sum(f[x][y][j],f[x][y-1][j-1]);
		}
		ans=sum(ans,1LL*f[x][y][k]*g[n-x+1][m-y+1]%mod);
	}
	return printf("%d",1LL*ans*quick_pow(g[n][m])%mod),0;
}

B. A Boring Game

B和C是我们队全场唯二没写出来的两题，而且好像除了川大的校队爷死磕肝出C之外也没人过这两题的说

反正我想破脑袋想不出来，只会写个每次询问\(O(n)\)的暴力的说

大概看了眼题解的意思，因为在移动过程中若我们可以通过某个\(a_j\)，则在之后就只要考虑所有\(a_k>a_j\)的\(k\)就行了

换句话说我们关心的是区间最大值，因此可以建立一颗笛卡尔树，那么移动的过程就变成了不断往树上跳

而每次跳到一个点时这个点的所有子树一定就能被访问到，我们设\(Sb_x=\sum_{y\in subtree(x)} b_y\)，则能从\(x\)走到父亲的充要条件就是\(a_{fa(x)}-Sb_x\le v\)，其中\(v\)是初始的战力

因此我们对于每个点的\(a_{fa(x)}-Sb_x\)信息进行维护后，每次询问找到第一个大于\(v\)的边，这可以用树剖或者倍增实现

~~因此总复杂度为\(O(n\log^2 n)\)，题解说是单次询问一个\(\log\)的，但我不知道怎么实现的说~~

问了手学长可以直接倍增记录每个点向上跳\(2^i\)步的边的最大值，由于倍增在查询的时候本身自带类似二分的性质，因此可以直接做到一个\(\log\)

代码没写先坑了

C. 往日重现

先ORZ一波神仙队友，基本把这题思路都想出来了，不过可惜因为服务器崩了没法交

首先暴力的想法就是我们枚举每个圆，然后考虑如果两个点一个在圆内一个在圆外那么这个圆的边界就一定要经过

然后考虑题目中给出的信息，所有圆都不相交，但是会有包含关系

可以想到如果我们添加一个半径无限大的圆，让所有圆向包含它的最小的圆连边，那么此时所有的圆之间就可以形成一个树结构

然后再结合样例画画我们发现，此时要求的就是两个包含了询问点的最小圆在树上的距离

这样就看起来很trivial了，但这道题最难的地方就在于如何建出这棵树

队友的写法是通过KD-Tree找到包含圆心的圆然后倍增找父亲，但我没细想也不知道对不对的说

然后看了眼题解的做法是对\(x\)轴用扫描线，分别维护上下半圆

每次扫描到某个圆的左边界（\(x_i-r_i\)）时，将上下半圆同时扔进平衡树里，并查询上半圆上方最近的半圆时哪一个

如果是某个上半圆，那么说明这两个圆是包含关系，这个上半圆对应的圆就是这个圆在树上对应的父亲

如果是某个下半圆，那么说明这两个圆在树上的关系相同，我们把当前这个圆的父亲置为找到的下半圆的父亲即可

然后关于查询点也是同理，最后我们在扫描到某个圆的右边界（\(x_i+r_i\)）时，删除这两个圆即可

具体实现应该可以用个set维护下，同时树上距离就是很naive的求LCA了，总复杂度\(O(n\log n)\)

代码也坑了因为感觉比B还难写

D. 小美爱画鱼

前中期看了一眼榜发现的签到题，首先可以根据\(x+y\)的值把所有在同一条对角线上的线段找出来

然后就变成一个区间覆盖的问题，按照左端点排序后简单计算一下即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,X1,Y1,X2,Y2; vector <pi> v[N]; bool flag; long long ans;
int main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (i=0;i<=200000;++i) v[i].clear();
		for (scanf("%d",&n),i=1;i<=n;++i)
		{
			scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
			v[X1+Y1].push_back(pi(X1,X2));
		}
		for (flag=1,ans=i=0;i<=200000;++i)
		{
			sort(v[i].begin(),v[i].end()); int R=0; ans+=i;
			for (auto [l,r]:v[i])
			if (l<R) flag=0,R=max(R,r);	else ans-=l-R,R=r;
			ans-=i-R;
		}
		puts(flag?"YES":"NO"); printf("%lld\n",ans);
	}
	return 0;
}

E.小团来打字

纯签到题，本来开局就一眼看到这题了，但队友告诉I和O更简单就先去做后面的了

先把所有相同的相连的字符合并了，然后就可以简单判断一个字符要按几次了

#include<cstdio>
#include<iostream>
#include<map>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,k,a[N],b[N],na[N],nb[N],cnt; map <int,int> ans;
inline int calc(CI t)
{
	if (t<=k) return t;
	if (t%k==0) return (t/k-1)*k*2LL+k;
	return t/k*k*2LL+t%k;
}
signed main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	RI i,j; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i) scanf("%lld%lld",&a[i],&b[i]);
	for (i=1;i<=n;)
	{
		for (j=i;j<=n&&a[j]==a[i];++j);
		na[++cnt]=a[i]; while (i<j) nb[cnt]+=b[i++];
	}
	for (i=1;i<=cnt;++i) ans[na[i]]+=calc(nb[i]);
	printf("%d\n",ans.size());
	for (auto [u,v]:ans) printf("%lld %lld\n",u,v);
	return 0;
}

F. 炸弹鸭

本来中午饭前准备把R的搜索写了然后去食堂的，但R我实在不太想写就找个理由写F去了把R扔了

很容易想到离线处理询问，从小到大考虑每个询问，这样所有边的加入也是从小到大的

然后考虑每次询问的本质其实就是问图中有多少个度数大于等于\(d_i+1\)的点有多少个

我们直接把每个点的度数用树状数组维护下即可，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
struct Data
{
	int x,y,w; //for ques w=k,x=d,y=id
	friend inline bool operator < (const Data& A,const Data& B)
	{
		return A.w<B.w;
	}
}e[N],ques[N]; int n,m,q,ans[N],deg[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline void add(RI x,CI y)
		{
			for (;x<=m+1;x+=lowbit(x)) bit[x]+=y;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
		}
		#undef lowbit
}T;
signed main()
{
	//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
	RI i,j; for (scanf("%d%d%d",&n,&m,&q),i=1;i<=m;++i)
	scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
	for (i=1;i<=q;++i)
	scanf("%d%d",&ques[i].x,&ques[i].w),ques[i].y=i;
	sort(e+1,e+m+1); sort(ques+1,ques+q+1);
	for (i=1;i<=n;++i) T.add(deg[i]=1,1);
	for (i=j=1;i<=q;++i)
	{
		while (j<=m&&e[j].w<=ques[i].w)
		{
			int x=e[j].x,y=e[j].y; ++j;
			T.add(deg[x],-1); T.add(++deg[x],1);
			T.add(deg[y],-1); T.add(++deg[y],1);
		}
		ans[ques[i].y]=T.get(ques[i].x+1);
	}
	for (i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}

G. Guard the Kingdom

在此我要点名向BFS之神ztc开膜，上周的中石大校赛和这次的初赛的BFS思路都是他教我的，还有上周的CF的E题也有BFS做法

首先在认真阅读题意后我们发现第一问其实是很好处理的，直接把每个重要城市设为起点然后跑最短路

求出每个城市\(x\)到其最近的重要城市的距离\(dis_x\)，同时再顺带记录下到每个点最近的重要城市个数\(f_x\)

然后现在问题是如何求没个重要城市被多少个军队保护，乍一想感觉以每个军队为起点做最短路显然是不行的，顿感无力

其实解决方法很简单，当我们在前面那次BFS时，若一条边\(u\to v\)松弛了\(v\)的状态（无论是\(dis_v\)还是\(f_v\)），那么最后统计军队对城市的影响时这条边就是有贡献的

因此我们每次松弛成功就在一个新图上加入一条\(v\to u\)的边，然后最后在新图上转移第二问的答案即可

直接讲可能不太好理解，建议直接看代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,m,k,x,t[N],c[N],dis[N],f[N],g[N],stk[N],top; bool vis[N];
vector <int> v[N],r[N]; queue <int> q;
inline void BFS1(void)
{
	while (!q.empty())
	{
		int now=q.front(); stk[++top]=now; q.pop();
		for (int to:v[now])
		{
			if (dis[now]+1<dis[to]) dis[to]=dis[now]+1,f[to]=f[now],r[to].push_back(now),q.push(to);
			else if (dis[now]+1==dis[to]) f[to]+=f[now],r[to].push_back(now);
		}
	}
}
inline void BFS2(void)
{
	for (RI i=top;i;--i)
	{
		int now=stk[i]; g[now]+=vis[now];
		for (int to:r[now]) g[to]+=g[now];
	}
}
int main()
{
	//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&m,&k),i=2;i<=n;++i)
	scanf("%d",&x),v[i].push_back(x),v[x].push_back(i);
	for (i=1;i<=m;++i) scanf("%d",&t[i]),vis[t[i]]=1;
	for (i=1;i<=n;++i) dis[i]=1e9,f[i]=0;
	for (i=1;i<=k;++i) scanf("%d",&c[i]),dis[c[i]]=0,f[c[i]]=1,q.push(c[i]);
	for (BFS1(),BFS2(),i=1;i<=m;++i) printf("%d%c",f[t[i]]," \n"[i==m]);
	for (i=1;i<=k;++i) printf("%d%c",g[c[i]]," \n"[i==k]);
	return 0;
}

H. 约瑟夫问题

这题比赛时我想了一个\(O(n\log^2 n)\)的做法然后因为不想写线段树上二分就丢给队友写了，队友直接掏出树状数组上二分这种我OI时期都不会的科技直接薄纱了

首先我们可以把已经出列的人置为\(0\)，还未出列的人置为\(1\)，假设我们不考虑已经出列的人而是正常向后报\(x\)个人

很显然随着\(x\)的增加这些人中还在队列中的人数（即向后跳\(x\)次得到的元素和）是单调不降的，因此我们只要二分找到第一个\(\ge k\)的位置即可

然后刚开始我傻了以为只能二分套树状数组的，但是后面发现其实把增量对\(n\)取模后可以直接在数据结构上二分

不过看官方的sol好像说两个\(\log\)是能过的，但不知道为什么ztc写了两个\(\log\)T掉了的说

代码我懒得写了就鸽了

I. 公主连结！Re:Dive

这题我纯一点没参与，不知道队友怎么写的说，这场数学相关的我都是纯没参与

今天结合sol大概自己在大英的课上推了下，首先可以变成\(8x+10z=n-9y\)，然后找出奇偶性正确的\(y\)然后再同除以\(2\)得到\(4x+5z=\frac{n-9y}{2}\)

然后就是一个经典的直线上整点个数问题，稍微手玩下我们发现只要求\(\sum \lfloor\frac{\frac{n-9y}{2}}{4}\rfloor -\lceil\frac{\frac{n-9y}{2}}{5}\rceil+1\)即可

然后这个就是个经典的类欧几里得了，由于很多系数其实都是给定的，所以可能存在数值上的封闭解，因为我大概看了下队友的做法是直接推出一个公式的

代码还是一如既往地没有

J. 数矩形

这题也不是我写的，不过今天看了下是个傻逼题的说

首先由于矩形的对边平行且相等，因此我们可以枚举点对，然后把这条边对应的向量\((a,b)\)用map存起来

但是还要考虑到另外一对边是和这条边垂直的，因此我们假设有两个对应的边向量都是\((a,b)\)的点\((x_1,y_1),(x_2,y_2)\)

则显然有\((x_1-x_2,y_1-y_2)\cdot (a,b)=0\)，化简一下就是\(ax_1+by_1=ax_2+by_2\)

那么我们在存map的时候多加一个维度记录下\(ax+by\)的值即可

当然代码也还是没写的说

看了下sol好像可以利用矩形对角线相互平分且相等这一性质，记录每个点对的中点和长度两个信息即可，不过和这个也大差不差

K. 打地鼠

这题当时比赛的时候我想过但没想到只要做树的情况就好了，还是靠队友大力切掉带飞了

首先要发现题目保证图联通，因此对于\(m\ge n\)的情况一定存在某个长度大于等于\(3\)的环，此时无论击打序列如何地鼠总存在一种方案不被打中，因此一定Lose

因此我们只要考虑树的情况即可，考虑直接开一个长为\(n\)的布尔数组表示每个点是否有可能有地鼠，当这个数组全为\(0\)时则获胜，否则我们可以直接\(O(n)\)模拟一遍更新这个数组状态

总复杂度\(O(n^2)\)，足以通过此题，代码还是没有

L. 树边重排

纯签到题

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,x,y,fa[N]; vector <int> v[N];
inline void DFS(CI now)
{
	for (int to:v[now]) if (to!=fa[now]) fa[to]=now,DFS(to);
}
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (DFS(n),i=1;i<n;++i) printf("%d ",fa[i]);
	return 0;
}

M. 操作系统计算题

终于来了一个我写的题了，这题当时还是狗运来了，好像就一队过了还WA了挺多发的

然后我看了下感觉是个半平面交裸体但感觉精度不太好搞，但当时手头上没题了就只能硬上了，结果30min写完+一遍过还是很爽的

说回题目首先\(x_i\le t\)的条件对于求最大值一点用没有可以直接丢了，同理前面那个\(1\)也没意义不用管，只要考虑\(\frac{1}{s_i}\times t-\frac{x_i}{s_i}\)的最大值即可

考虑把\(t\)看成横坐标，\(\frac{1}{s_i}\times t-\frac{x_i}{s_i}\)的值看作纵坐标，每个进程显然就是一条直线

然后就是求对于某个\(t\)，最上方的直线是哪条，这个算是半平面交的裸题了吧（不过这题直线斜率都是正的也可以说是求下凸壳）

我们找出所有的分界点后对于询问直接二分即可，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
const double EPS=1e-12;
inline int cmp(const double& x)
{
	if (fabs(x)<EPS) return 0; return x<0?-1:1;
}
struct line
{
	double k,b;
	friend inline bool operator < (const line& A,const line& B)
	{
		int t=cmp(A.k-B.k); if (t) return t<0; return A.b>B.b;
	}
}l[N]; int n,x,s,m,t,stk[N],top; double p[N];
inline double getx(const line& A,const line& B)
{
	if (!cmp(A.k-B.k)) return -1e18; return (B.b-A.b)/(A.k-B.k);
}
int main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i)
	scanf("%d%d",&x,&s),l[i]=(line){1.0/s,-1.0*x/s};
	for (sort(l+1,l+n+1),i=1;i<=n;++i)
	{
		if (top&&!cmp(l[stk[top]].k-l[i].k)) continue;
		while (top>1&&cmp(getx(l[stk[top]],l[i])-getx(l[stk[top]],l[stk[top-1]]))<=0) --top;
		stk[++top]=i;
	}
	for (i=1;i<top;++i) p[i]=getx(l[stk[i]],l[stk[i+1]]);
	for (p[top]=1e18,scanf("%d",&m),i=1;i<=m;++i)
	{
		scanf("%d",&t); int id=lower_bound(p+1,p+top+1,t)-p;
		double tmp=l[stk[id]].k*t+l[stk[id]].b;
		if (cmp(tmp)<0) puts("-1"); else printf("%.6lf\n",tmp+1.0);
	}
	return 0;
}

N. 本质不同的 01 环计数

队友吃饭的间隙给了一个式子，然后我闲着没事就实现了一下，由此可见这把我纯在躺

首先考虑连续的长为\(k\)的子段和都相同，其实就是个平移区间的操作，因此我们有\(\forall i\in[0,n-1],a_i=a_{(i+k)\ \bmod\ n}\)

这个显然等价于将环分成了\(\gcd(n,k)\)个部分，每个部分内部的所有数的值必须相等，换句话说答案只和\(\gcd(n,k)\)有关

因此我们现在就要求所有本质不同的长为\(\gcd(n,k)\)的\(0/1\)环方案数，容易想到通过枚举最小循环节的长度来计算（因为去除本质不同的方案和最小循环节的长度有关）

我们设最小循环节的长度为\(i\)，粗暴地想方案数就是\(2^i\)，但还要减去那些最小循环节长度是\(i\)的真约数的方案数

因此总结一下设\(f_i\)表示最小循环节的长度为\(i\)的本质不同的环的个数，则\(f_i=\frac{1}{i}\times (2^i-\sum_{j|i\and j\ne i}f_j)\)

然后最后统计答案就很简单了，直接有\(g_i=\sum_{j|i} f_i\)，最后每个询问的答案就是\(g_{\gcd(n,k)}\)

然后这么做的复杂度是\(O(n\ln n)\)的，在我电脑上预处理就要跑2.5s的说，不知道交上去会不会T

比赛时队友给的式子应该时用Burnside/Polya定理推出来的，直接有\(g(n)=\frac{1}{n}\times \sum_{d|n} \phi(d)\times 2^{\frac{n}{d}}\)

因此可以把预处理的复杂度降到\(O(n)\)，由于询问的次数较少可以每次枚举约数，比赛时稳妥起见采用了后面这种写法

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005,mod=998244353;
int t,n,k,pri[N],cnt,pw[N],phi[N],f[N]; bool vis[N];
inline int sum(CI x,CI y)
{
	return x+y>=mod?x+y-mod:x+y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int gcd(CI n,CI m)
{
	return m?gcd(m,n%m):n;
}
inline void init(CI n)
{
	RI i,j; phi[1]=1; for (RI i=2,j;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i,phi[i]=i-1;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		if (vis[i*pri[j]]=1,i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
        else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
	}
	for (pw[0]=i=1;i<=n;++i) pw[i]=sum(pw[i-1],pw[i-1]);
	/*for (i=1;i<=n;++i) for (j=i;j<=n;j+=i)
	f[j]=sum(f[j],1LL*phi[i]*pw[j/i]%mod);
	for (i=1;i<=n;++i) f[i]=1LL*f[i]*quick_pow(i)%mod;*/
}
inline int calc(CI n)
{
	if (~f[n]) return f[n]; int ret=0;
	for (RI i=1;i*i<=n;++i) if (n%i==0)
	{
		ret=sum(ret,1LL*phi[i]*pw[n/i]%mod);
		if (n!=i*i) ret=sum(ret,1LL*phi[n/i]*pw[i]%mod);
	}
	return f[n]=1LL*ret*quick_pow(n)%mod;
}
int main()
{
	//freopen("N.in","r",stdin); freopen("N.out","w",stdout);
	for (scanf("%d",&t),init(1000000),memset(f,-1,sizeof(f));t;--t)
	scanf("%d%d",&n,&k),printf("%d\n",calc(gcd(n,k)));
	return 0;
}

O. 爬塔

纯贪心模拟题，每次尽量往上爬，知道打不过了再用回溯，而回溯的次数显然可以直接计算出来

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,a[N],pfx[N],sum,ans;
signed main()
{
	//freopen("O.in","r",stdin); freopen("O.out","w",stdout);
	RI i; for (scanf("%lld",&n),i=1;i<=n;++i)
	scanf("%lld",&a[i]),pfx[i]=pfx[i-1]+a[i];
	for (sum=i=1;i<=n;++i)
	{
		if (sum>=a[i]) sum+=a[i]; else
		{
			int tmp=(a[i]-sum+pfx[i-1])/(pfx[i-1]+1);
			ans+=tmp; sum+=tmp*(pfx[i-1]+1)+a[i];
		}
	}
	return printf("%lld",ans),0;
}