Znzryb's Blog

CF-1016-D. Skibidi Table

Posted on 2025-04-09 Edited on 2026-04-06

思路讲解

其实这个题面应该是一个很经典的类似于莫顿编码的东西。

莫顿编码图片

当然，和莫顿编码还是稍微有点区别

思路就是针对每个询问递归的找就行了。

AC代码

https://codeforces.com/contest/2093/my

源代码

// Problem: D. Skibidi Table
// Contest: Codeforces - Codeforces Round 1016 (Div. 3)
// URL: https://codeforces.com/contest/2093/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,Q,T,A[MAXN];

inline ll binpow(ll x,ll k){	// 哈哈，复习一下快速幂
	ll res=1;
	while(k){
		if(k&1) res*=x;
		x*=x;
		k>>=1;
	}
	return res;
}

inline bool isIn(ll x,ll y,ll x1,ll y1,ll x2,ll y2){
	if(x<x1 || x>x2) return false;
	if(y<y1 || y>y2) return false;
	return true;
}
/*
1 4
3 2
*/
ll findNum(ll x,ll y,ll x1,ll y1,ll x2,ll y2,ll l,ll r){
	if(l==r) return l;
	ll midx=x1+x2>>1,midy=y1+y2>>1;
	ll divPt1=l+(r-l)/4+1,divPt2=l+(r-l)/2+1,divPt3=l+3*(r-l)/4+1;
	if(isIn(x,y,x1,y1,midx,midy)){
		return findNum(x,y,x1,y1,midx,midy,l,divPt1-1);
	}else if(isIn(x,y,midx+1,midy+1,x2,y2)){
		return findNum(x,y,midx+1,midy+1,x2,y2,divPt1,divPt2-1);
	}else if(isIn(x,y,midx+1,y1,x2,midy)){
		return findNum(x,y,midx+1,y1,x2,midy,divPt2,divPt3-1);
	}else{
		return findNum(x,y,x1,midy+1,midx,y2,divPt3,r);
	}
}

pll findPos(ll num,ll x1,ll y1,ll x2,ll y2,ll l,ll r){
	if(x1==x2 && y1==y2) return {x1,y1};
	ll midx=x1+x2>>1,midy=y1+y2>>1;
	ll divPt1=l+(r-l)/4+1,divPt2=l+(r-l)/2+1,divPt3=l+3*(r-l)/4+1;
// #ifdef LOCAL
    // cerr << x1<<" "<<y1<<" "<<x2<<" "<<y2<<" lr:"<<l<<" "<<r<<" "<<divPt1<<" "<<divPt2<<" "<<divPt3 << '\n';
// #endif
	if(num>=l && num<divPt1){
		return findPos(num,x1,y1,midx,midy,l,divPt1-1);
	}else if(num>=divPt1 && num<divPt2){
		return findPos(num,midx+1,midy+1,x2,y2,divPt1,divPt2-1);
	}else if(num>=divPt2 && num<divPt3){
		return findPos(num,midx+1,y1,x2,midy,divPt2,divPt3-1);
	}else{
		return findPos(num,x1,midy+1,midx,y2,divPt3,r);
	}
}

inline void solve(){
	cin>>N>>Q;
	FOR(i,1,Q){
		char op1,op2;
		cin>>op1>>op2;
		if(op2=='>'){
			ll x,y;
			cin>>x>>y;
			cout<<findNum(x,y,1,1,binpow(2,N),binpow(2,N),1,binpow(2,2*N))<<"\n";
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
		}else{
			ll num;
			cin>>num;
			pll res=findPos(num,1,1,binpow(2,N),binpow(2,N),1,binpow(2,2*N));
			cout<<res.fi<<" "<<res.se<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2093/submission/314848827
*/

心路历程（WA，TLE，MLE……）

ABC-382-E - Expansion Packs

Posted on 2025-04-09 Edited on 2026-04-06

思路讲解

参考以下题解：

https://www.luogu.com.cn/article/z6wql8q2

FOR(i,1,N){cin>>P[i];}
FOR(i,0,N){		// 抽到第i张卡，有多大的概率抽到j张稀有卡
	FOR(j,0,N){
		if(i>0 && j>0){
			//				这第i张没出货			第i张出货了
			dp[i][j]=dp[i-1][j]*(1.0-P[i]/100.0)+dp[i-1][j-1]*(P[i]/100.0);
		}else if(j==0 && i>0){
			dp[i][j]=dp[i-1][j]*(1.0-P[i]/100.0);
		}else if(i==0 && j==0){	
			dp[i][j]=1.0;
		}else{ // 剩下的抽0张卡，获得>0张卡的概率自然是0
			dp[i][j]=0;
		}
	}
}

前面这个求抽到第 i 张卡，有多大的概率恰好抽到 j 张稀有卡，还是不难的。

但是这道题目要求的是抽到至少 X 张卡的数学期望，这个的转移有点难，也有点难想。

exp_i=1+\displaystyle\sum_{j=0}^{N}exp_{max(0,i-j)}\times dp[N][j]

( $ exp_i$ 代表抽到至少 i 张的期望包数， $dp[N][j]$ 代表该包抽到恰好 j 张稀有卡的概率 )

这个式子初看很难理解，其实细看之下，还是不那么难理解的，1是我这次抽，所以 $+1$ ，但是我们是要转移的，需要从别的情况转移过来，那从哪些情况那？其实就是从 $\displaystyle\sum_{j=0}^{N}exp_{max(0,i-j)}$ 这些情况转移过来，但是这些转移是有概率的，多大的概率那？ $dp[N][j]$ 。

当然因为左右两边都包含 $exp_i$ 其实我们还要进行一个移项。

exp_i=1+exp_i\times dp[N][0]+\displaystyle\sum_{j=1}^{N}exp_{max(0,i-j)}\times dp[N][j]\\ exp_i(1-dp[N][0])=1+\displaystyle\sum_{j=1}^{N}exp_{max(0,i-j)}\times dp[N][j]\\ exp_i=(1+\displaystyle\sum_{j=1}^{N}exp_{max(0,i-j)}\times dp[N][j])\ /\ (1-dp[N][0])

你可能会说，我还是不理解这个 $+1$ ，或者为什么不是直接用 $X/每包的期望稀有卡数量$ 。那么我问你，这个得到至少一张稀有卡的期望可能小于 1 吗？不可能吧，因为不可能一包卡都不开就拿到了一张稀有卡吧？所以其实这个 $+1$ 就是这里的转移必须要用开卡包来转移。

AC代码

https://atcoder.jp/contests/abc382/submissions/65982174

源代码

// Problem: E - Expansion Packs
// Contest: AtCoder - AtCoder Beginner Contest 382
// URL: https://atcoder.jp/contests/abc382/tasks/abc382_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,X,M,K,T,P[MAXN];
// 抽到第i张卡，有多大的概率抽到j张稀有卡
DB dp[5010][5010];
DB Exp[5010];
/*
gi:期望抽gi次.抽出至少i张稀有卡
fi:一包卡恰好有：i张稀有卡概率
*/
inline void solve(){
	cin>>N>>X;
	FOR(i,1,N){cin>>P[i];}
	FOR(i,0,N){		// 抽到第i张卡，有多大的概率抽到j张稀有卡
		FOR(j,0,N){
			if(i>0 && j>0){
				//				这第i张没出货			第i张出货了
				dp[i][j]=dp[i-1][j]*(1.0-P[i]/100.0)+dp[i-1][j-1]*(P[i]/100.0);
			}else if(j==0 && i>0){
				dp[i][j]=dp[i-1][j]*(1.0-P[i]/100.0);
			}else if(i==0 && j==0){	
				dp[i][j]=1.0;
			}else{ // 剩下的抽0张卡，获得>0张卡的概率自然是0
				dp[i][j]=0;
			}
		}
	}

#ifdef LOCAL
    FOR(i,0,N){		// 抽到第i张卡，有多大的概率抽到j张稀有卡
		FOR(j,0,N){
			cerr<<dp[i][j]<<" ";
		}
		cerr<<"\n";
	}
#endif
	// gi:期望抽gi次.抽出至少i张稀有卡
	// G[0]=0;
	FOR(i,1,X){
		DB sum=0;
		FOR(j,1,N){
			if(i-j<0) break;
			sum+=dp[N][j]*Exp[i-j];
		}
		Exp[i]=(1+sum)/(1-dp[N][0]);
	}
	cout<<setprecision(15)<<fixed<<Exp[X]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://atcoder.jp/contests/abc382/submissions/65982174
*/

心路历程（WA，TLE，MLE……）

ABC-382-F - Falling Bars

Posted on 2025-04-09 Edited on 2026-04-06

思路讲解

// 首先，上面的块是不会影响下面的块，只有下面的块影响上面的块的份
// 思路其实也不复杂，就是看在这个块下面的块中最高的在哪里。
// 相当于一个range最小值查询，需要用线段树区间修改

AC代码

https://atcoder.jp/contests/abc382/submissions/64644331

源代码

// Problem: F - Falling Bars
// Contest: AtCoder - AtCoder Beginner Contest 382
// URL: https://atcoder.jp/contests/abc382/tasks/abc382_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,H,W;
struct BAR{	// 之前的代码，直接在这个结构体当中重载
	ll x,y,len,idx;
	bool operator<(const BAR &other) const{
		if(x!=other.x) return x>other.x;
		if(y!=other.y) return y<other.y;
		if(len!=other.len) return len<other.len;
		return false;
	}
};
struct SegTreeRMQ{
	ll l=0,r=0,val=INF;
}tr[MAXN*4];

ll lazy[MAXN*4];

inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}

inline bool isDisj(ll l,ll r,ll l_,ll r_){	// 是否不相交，isDisjoint
	return (r_<l || l_>r);
}

inline void pushdown(ll node){
	if(tr[node].l==tr[node].r) return;
	if(lazy[node]!=0){
		tr[ls(node)].val=lazy[node];
		tr[rs(node)].val=lazy[node];
		lazy[ls(node)]=lazy[node];
		lazy[rs(node)]=lazy[node];
		lazy[node]=0;
	}
}

inline void pushup(ll node){
	node>>=1;
	while(node){
		tr[node].val=min(tr[ls(node)].val,tr[rs(node)].val);
		node>>=1;
	}
}

void build(ll node,ll l,ll r){
	if(l>r) return;
	if(l==r){
		tr[node].l=l;
		tr[node].r=r;
		return;
	}
	ll mid=l+r>>1;
	tr[node].l=l;
	tr[node].r=r;
	build(ls(node),l,mid);
	build(rs(node),mid+1,r);
}

void modify(ll node,ll l,ll r,ll val){
	if(isDisj(l,r,tr[node].l,tr[node].r)) return;
	pushdown(node);
	if(l<=tr[node].l && tr[node].r<=r){
		tr[node].val=val;
		lazy[node]=val;
		pushup(node);
		return;
	}
	if(!isDisj(l,r,tr[ls(node)].l,tr[ls(node)].r)) modify(ls(node),l,r,val);
	if(!isDisj(l,r,tr[rs(node)].l,tr[rs(node)].r)) modify(rs(node),l,r,val);
}

ll query(ll node,ll l,ll r){
	if(isDisj(l,r,tr[node].l,tr[node].r)) return INF;
	pushdown(node);
	if(l<=tr[node].l && tr[node].r<=r){
		return tr[node].val;
	}
	ll res=INF;
	if(!isDisj(l,r,tr[ls(node)].l,tr[ls(node)].r)) res=min(res,query(ls(node),l,r));
	if(!isDisj(l,r,tr[rs(node)].l,tr[rs(node)].r)) res=min(res,query(rs(node),l,r));
	return res;
}

ll ans[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>H>>W>>N;
	vector<BAR> bar(N+5,(BAR){0,0,0});
	FOR(i, 1, N){
		cin>>bar[i].x>>bar[i].y>>bar[i].len;
		bar[i].idx=i;
	}
	sort(bar.begin()+1,bar.begin()+1+N);
	// 首先，上面的块是不会影响下面的块，只有下面的块影响上面的块的份
	// 思路其实也不复杂，就是看在这个块下面的块中最高的在哪里。
	// 相当于一个range最小值查询，需要用线段树区间修改
	build(1,1,W);
	FOR(i,1,N){
		ll x=bar[i].x,y=bar[i].y,len=bar[i].len,idx=bar[i].idx;
		ll res=query(1,y,y+len-1);
		if(res==INF) ans[idx]=H;
		else ans[idx]=res-1;
		modify(1,y,y+len-1,ans[idx]);
// #ifdef LOCAL
    // FOR(i,1,W*4){
    	// cerr<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].val<<"\n";
    // }
    // cerr<<"\n";
// #endif
	}
	FOR(i,1,N){
		cout<<ans[i]<<"\n";
	}
	
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc382/submissions/64644331
*/

心路历程（WA，TLE，MLE……）

ABC-400-E - Ringo's Favorite Numbers 3

Posted on 2025-04-08 Edited on 2026-04-06

思路讲解

约数个数定理

ABC-383-D - 9 Divisors

其实这个约数个数定理是显然的

你想p1的指数有 $0～e_1$ 也就是 $e_1+1$ 种选择，同理，每种都有 $e_k+1$ 种选择

那么根据乘法原理，约束个数也就是 $d(n)=(e_1+1)(e_2+1)…(e_k+1)$

当然喽，只有素因子可以这么玩，非素因子这么玩可能会有重复

当然这道题目关键点不在上面。

$N=p_1^{e_1}p_2^{e_2}$ 由题意可得，e1为偶数，e2也为偶数。所以其实400数要求是完全平方数，而且是只由两个素因子构成。那么其实也就是要求平方数由两个素因子组成。

哈哈，其实这种也是有点套路，一般来说这种都是直接枚举素因子的

我们用埃氏筛筛出所有1e6以内的素数，存储在primes中。然后就枚举就完了。

枚举代码

for(int i=0;i<primes.size();++i){
	ll p=primes[i];
	for(ll j=p;j<=MAXN-10;j*=p){
		for(int k=i+1;k<primes.size();++k){
			ll pk=primes[k];
			if(pk*j>MAXN-10) break;
			for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
				if(p_k*j>MAXN-10) break;
				fitNum.pb(p_k*j);
			}
		}
	}
}

AC代码

源代码

// Problem: E - Ringo's Favorite Numbers 3
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
vector<ll> fitNum;	// 符合含有两个素因子的数

inline void solve(){
	cin>>N;
	ll sqN=sqrtl(N);
// #ifdef LOCAL
    // cerr << sqN << '\n';
// #endif
	ll sqAns=*prev(upper_bound(all(fitNum),sqN));
	cout<<sqAns*sqAns<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// 先进行预处理
	for(int i=2;i<=MAXN-10;++i){
		isPrime[i]=true;
	}
	// 埃氏筛
	// 假设MAXN-10以内有一个合数没有标记，那么他必然有一个小于sqrt(MAXN-10)的因子
	for(int i=2;i*i<=MAXN-10;++i){
		if(isPrime[i]){
			for(int j=2*i;j<=MAXN-10;j+=i){
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN-10;++i){
		if(isPrime[i]) primes.pb(i);
	}
	
	for(int i=0;i<primes.size();++i){
		ll p=primes[i];
		for(ll j=p;j<=MAXN-10;j*=p){
			for(int k=i+1;k<primes.size();++k){
				ll pk=primes[k];
				if(pk*j>MAXN-10) break;
				for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
					if(p_k*j>MAXN-10) break;
					fitNum.pb(p_k*j);
				}
			}
		}
	}
	sort(all(fitNum));
// #ifdef LOCAL
    // for(int i=0;i<=10;++i){
    	// cerr<<fitNum[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc400/submissions/64639281
*/

心路历程（WA，TLE，MLE……）

这个ll是非常需要的，写成int以后就TLE了，可能是因为溢出了。

for(int i=0;i<primes.size();++i){
	ll p=primes[i];
	for(ll j=p;j<=MAXN-10;j*=p){
		for(int k=i+1;k<primes.size();++k){
			ll pk=primes[k];
			if(pk*j>MAXN-10) break;
			for(ll p_k=pk;p_k<=MAXN-10;p_k*=pk){
				if(p_k*j>MAXN-10) break;
				fitNum.pb(p_k*j);
			}
		}
	}
}

ABC-400-C - 2^a b^2 （使用sqrtl）

Posted on 2025-04-06 Edited on 2026-04-06

思路讲解

赛时想到思路了，也写出来了，但是死活都会WA四个点。

这种问题一般就是转化成二进制想，其实2^a就是二进制下右移a位。

最后靠AI手写了个二分的开方程序过了，这个是在有点离谱，现在在想我的程序为什么会WA。

找到一个博客，说sqrt是有点问题。

https://codeforces.com/blog/entry/107717

利用sqrtl就过了，离谱，floor(sqrt(i))就不行。

其实sqrtl其实是传入参数为long double，那么其实还是精度问题。我直接这么调用其实还有一个自动向下的隐式转换。

https://en.cppreference.com/w/c/numeric/math/sqrt

AC代码

https://atcoder.jp/contests/abc400/submissions/64576953

源代码

// Problem: C - 2^a b^2
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

inline void solve(){
	cin>>N;
	// ll cnt=0;
	// for(ll i=N;i>0;i/=2){
		// ++cnt;
	// }
// #ifdef LOCAL
    // cerr << cnt << '\n';
// #endif	
	ll ans=0;
	// ll cnt=0;
	// ll upRes=0;
	for(ll i=N>>1;i>0;i>>=1){
		ll res=sqrtl(i); //-floor(sqrt(i>>1));
		res=ceil(res*1.0l/2);
		// ++cnt;
// #ifdef LOCAL
    // cerr<<i<<" " << res << '\n';
// #endif
		ans+=res; // *cnt
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

666