Hi, all!↵
↵
This is not [user:Tommyr7,2018-02-14], but the **impostor** behind the round again (guess who I am? :P). The statements are written by me. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future!↵
↵
Here are some of the detailed tutorials!↵
↵
### Tutorials↵
↵
### [problem:934B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n,k;↵
int main()↵
{↵
scanf("%d",&k);↵
if (k>36) printf("%d\n",-1);↵
else↵
{↵
while (k>0)↵
{↵
if (k>=2)↵
{↵
printf("%d",8);↵
k-=2;↵
} else↵
{↵
printf("%d",9);↵
k-=1;↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long p;↵
int k;↵
int cnt=0;↵
int ans[107];↵
int get()↵
{↵
int x=p%k;↵
if (x<0) x+=k;↵
return x%k;↵
}↵
int main()↵
{↵
scanf("%lld%d",&p,&k);↵
while (p!=0)↵
{↵
++cnt;↵
ans[cnt]=get();↵
p-=get();↵
p/=(-k);↵
}↵
printf("%d\n",cnt);↵
for (int i=1;i<=cnt;i++)↵
printf("%d ",ans[i]);↵
printf("\n");↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
A]↵
**Author** [user:quailty,2018-02-14] / **Preparation** [user:quailty,2018-02-14] / **Tutorial** [user:quailty,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934A]↵
</spoiler>↵
↵
<spoiler summary="Solution (quailty)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
const ll INF=(1LL<<60)-1;↵
ll a[55],b[55];↵
int main()↵
{↵
int n,m;↵
scanf("%d%d",&n,&m);↵
for(int i=1;i<=n;i++)↵
scanf("%lld",&a[i]);↵
for(int i=1;i<=m;i++)↵
scanf("%lld",&b[i]);↵
ll res=INF;↵
for(int i=1;i<=n;i++)↵
{↵
ll now=-INF;↵
for(int j=1;j<=n;j++)if(j!=i)↵
for(int k=1;k<=m;k++)↵
now=max(now,a[j]*b[k]);↵
res=min(res,now);↵
}↵
printf("%lld\n",res);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:934B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n,k;↵
int main()↵
{↵
scanf("%d",&k);↵
if (k>36) printf("%d\n",-1);↵
else↵
{↵
while (k>0)↵
{↵
if (k>=2)↵
{↵
printf("%d",8);↵
k-=2;↵
} else↵
{↵
printf("%d",9);↵
k-=1;↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933A]↵
**Author** [user:visitWorld,2018-02-14] / **Preparation** [user:visitWorld,2018-02-14] / **Tutorial** [user:visitWorld,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933A]↵
</spoiler>↵
↵
<spoiler summary="Solution (visitWorld)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i)↵
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)↵
#define fi first↵
#define se second↵
#define mp(x, y) make_pair(x, y)↵
#define pb(x) push_back(x)↵
#define bin(x) (1 << (x))↵
#define SZ(x) int((x).size())↵
↵
using namespace std;↵
typedef pair<int, int> pii;↵
typedef vector<int> Vi;↵
typedef long long ll;↵
↵
template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }↵
template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }↵
↵
const int MAX_N = 2005;↵
↵
int pre[MAX_N][2], suf[MAX_N][2];↵
int g[MAX_N][MAX_N][2][2];↵
int w[MAX_N], N;↵
↵
int main() {↵
scanf("%d", &N);↵
rep (i, 0, N) { scanf("%d", &w[i]); w[i]--; }↵
rep (i, 0, N) {↵
if (i) memcpy(pre[i], pre[i - 1], sizeof pre[i]);↵
down (j, 2, w[i]) upmax(pre[i][j], pre[i][w[i]] + 1);↵
}↵
down (i, N, 0) {↵
if (i < N - 1) memcpy(suf[i], suf[i + 1], sizeof suf[i]);↵
rep (j, 0, w[i] + 1) upmax(suf[i][j], suf[i][w[i]] + 1);↵
}↵
int ans = pre[N - 1][1];↵
rep (i, 0, N) {↵
rep (a, 0, w[i] + 1) rep (b, w[i], 2) {↵
g[i][i][a][b] = 1;↵
}↵
}↵
rep (l, 1, N) rep (i, 0, N - l) {↵
int j = i + l;↵
rep (l, 0, 2) rep (a, 0, 2 - l) {↵
int b = a + l;↵
g[i][j][a][b] = max((a < 1 ? g[i][j][a + 1][b] : 0), (b ? g[i][j][a][b - 1] : 0));↵
upmax(g[i][j][a][b], g[i + 1][j][a][b] + (b == w[i]));↵
upmax(g[i][j][a][b], g[i][j - 1][a][b] + (a == w[j]));↵
upmax(ans, (i ? pre[i - 1][a] : 0) + g[i][j][a][b] + (j < N - 1 ? suf[j + 1][b] : 0));↵
}↵
}↵
printf("%d\n", ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long p;↵
int k;↵
int cnt=0;↵
int ans[107];↵
int get()↵
{↵
int x=p%k;↵
if (x<0) x+=k;↵
return x%k;↵
}↵
int main()↵
{↵
scanf("%lld%d",&p,&k);↵
while (p!=0)↵
{↵
++cnt;↵
ans[cnt]=get();↵
p-=get();↵
p/=(-k);↵
}↵
printf("%d\n",cnt);↵
for (int i=1;i<=cnt;i++)↵
printf("%d ",ans[i]);↵
printf("\n");↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933C]↵
**Author** [user:quailty,2018-02-14] / **Preparation** [user:quailty,2018-02-14] / **Tutorial** [user:quailty,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933C]↵
</spoiler>↵
↵
<spoiler summary="Solution (quailty)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
typedef long double db;↵
const db eps=1e-12;↵
↵
struct Point↵
{↵
db x,y;↵
Point(){}↵
Point(db _x,db _y):x(_x),y(_y){}↵
Point operator + (const Point &t)const↵
{↵
return Point(x+t.x,y+t.y);↵
}↵
Point operator - (const Point &t)const↵
{↵
return Point(x-t.x,y-t.y);↵
}↵
Point operator * (const db &t)const↵
{↵
return Point(x*t,y*t);↵
}↵
Point operator / (const db &t)const↵
{↵
return Point(x/t,y/t);↵
}↵
bool operator < (const Point &t)const↵
{↵
return fabs(x-t.x)<eps ? y<t.y : x<t.x;↵
}↵
bool operator == (const Point &t)const↵
{↵
return fabs(x-t.x)<eps && fabs(y-t.y)<eps;↵
}↵
db len()const↵
{↵
return sqrt(x*x+y*y);↵
}↵
Point rot90()const↵
{↵
return Point(-y,x);↵
}↵
};↵
↵
struct Circle↵
{↵
Point o;↵
db r;↵
Circle(){}↵
Circle(Point _o,db _r):o(_o),r(_r){}↵
friend vector<Point> operator & (const Circle &c1,const Circle &c2)↵
{↵
db d=(c1.o-c2.o).len();↵
if(d>c1.r+c2.r+eps || d<fabs(c1.r-c2.r)-eps)↵
return vector<Point>();↵
db dt=(c1.r*c1.r-c2.r*c2.r)/d,d1=(d+dt)/2;↵
Point dir=(c2.o-c1.o)/d,pcrs=c1.o+dir*d1;↵
dt=sqrt(max(0.0L,c1.r*c1.r-d1*d1)),dir=dir.rot90();↵
return vector<Point>{pcrs+dir*dt,pcrs-dir*dt};↵
}↵
}p[5];↵
↵
struct DSU↵
{↵
int fa[5];↵
void init(int n)↵
{↵
for(int i=1;i<=n;i++)↵
fa[i]=i;↵
}↵
int find(int x)↵
{↵
return fa[x]==x ? x : fa[x]=find(fa[x]);↵
}↵
void merge(int x,int y)↵
{↵
x=find(x),y=find(y);↵
if(x!=y)fa[x]=y;↵
}↵
}dsu;↵
↵
int main()↵
{↵
int n;↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++)↵
cin>>p[i].o.x>>p[i].o.y>>p[i].r;↵
vector<Point> all;↵
dsu.init(n);↵
int e=0;↵
for(int i=1;i<=n;i++)↵
{↵
vector<Point> pat;↵
for(int j=1;j<=n;j++)if(i!=j)↵
{↵
vector<Point> tmp=p[i]&p[j];↵
if(!tmp.empty())dsu.merge(i,j);↵
for(int k=0;k<(int)tmp.size();k++)↵
all.push_back(tmp[k]),pat.push_back(tmp[k]);↵
}↵
sort(pat.begin(),pat.end());↵
e+=unique(pat.begin(),pat.end())-pat.begin();↵
}↵
sort(all.begin(),all.end());↵
int v=unique(all.begin(),all.end())-all.begin(),c=0;↵
for(int i=1;i<=n;i++)↵
c+=(dsu.find(i)==i);↵
cout<<e-v+c+1<<endl;↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933D]↵
**Author** [user:skywalkert,2018-02-14] / **Preparation** [user:skywalkert,2018-02-14] / **Tutorial** [user:skywalkert,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933D]↵
</spoiler>↵
↵
<spoiler summary="Solution (skywalkert)">↵
~~~~~↵
#include <bits/stdc++.h>↵
typedef long long LL;↵
const int mod = (int)1e9 + 7, inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv5 = (mod * 2 + 1) / 5, inv7 = (mod + 1) / 7;↵
const int inv6 = (LL)inv2 * inv3 % mod, inv30 = (LL)inv5 * inv6 % mod, inv42 = (LL)inv6 * inv7 % mod;↵
const int coeff[4][8] = {↵
{0, 1}, // sum(b^0) = n↵
{0, inv6, inv2, inv3}, // sum(b^2) = 1/6 n + 1/2 n^2 + 1/3 n^3↵
{0, mod - inv30, 0, inv3, inv2, inv5}, // sum(b^4) = -1/30 n + 1/3 n^3 + 1/2 n^4 + 1/5 n^5↵
{0, inv42, 0, mod - inv6, 0, inv2, inv2, inv7} // sum(b^6) = 1/42 n - 1/6 n^3 + 1/2 n^5 + 1/2 n^6 + 1/7 n^7↵
};↵
LL n;↵
int f[4], g[4], ans;↵
int main() {↵
scanf("%lld", &n);↵
int nn = n % mod;↵
f[0] = nn * (nn + 1LL) % mod * (nn + 2) % mod;↵
f[1] = (3LL * nn + 4) % mod;↵
f[2] = mod - 3LL * (nn + 2) % mod;↵
f[3] = 2;↵
for(int x = 0; (LL)x * x <= n; ++x) {↵
LL rem = n - (LL)x * x;↵
int yLim = (int)ceil(sqrtl(rem));↵
for( ; (LL)yLim * yLim <= rem; ++yLim);↵
for( ; (LL)yLim * yLim > rem; --yLim);↵
int sum = 0, x2 = (LL)x * x % mod, x4 = (LL)x2 * x2 % mod, x6 = (LL)x2 * x4 % mod;↵
g[0] = (f[0] + (LL)f[1] * x2 + (LL)f[2] * x4 + (LL)f[3] * x6) % mod;↵
g[1] = (f[1] + 2LL * f[2] * x2 + 3LL * f[3] * x4) % mod;↵
g[2] = (f[2] + 3LL * f[3] * x2) % mod;↵
g[3] = f[3];↵
for(int i = 0; i < 4; ++i) {↵
int tmp = 0;↵
for(int j = i << 1 | 1; j >= 0; --j)↵
tmp = ((LL)tmp * yLim + coeff[i][j]) % mod;↵
sum = (sum + (LL)g[i] * (tmp << 1 | !i)) % mod;↵
}↵
x && (sum <<= 1) >= mod && (sum -= mod);↵
(ans += sum) >= mod && (ans -= mod);↵
}↵
ans = (LL)ans * inv6 % mod;↵
printf("%d\n", ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933E]↵
**Author** [user:skywalkert,2018-02-14] / **Preparation** [user:skywalkert,2018-02-14] / **Tutorial** [user:skywalkert,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933E]↵
</spoiler>↵
↵
<spoiler summary="Solution (skywalkert)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long LL;↵
const int maxn = (int)3e5 + 3;↵
int n, a[maxn], cnt, p[maxn], m, out[maxn];↵
LL f[maxn];↵
bool v[maxn];↵
int descension(int pos) {↵
int dt = min(a[pos], a[pos + 1]);↵
if(dt)↵
out[++m] = pos;↵
a[pos] -= dt;↵
a[pos + 1] -= dt;↵
return dt;↵
}↵
int main() {↵
scanf("%d", &n);↵
for(int i = 1; i <= n; ++i) {↵
scanf("%d", a + i);↵
LL odd = f[max(i - 2, 0)] + a[i], even = f[max(i - 3, 0)] + max(a[i - 1], a[i]);↵
f[i] = min(odd, even);↵
v[i] = f[i] != odd;↵
}↵
// a[n + 1] = 0;↵
LL ans = min(f[n - 1], f[n]);↵
// printf("%lld\n", ans);↵
for(int i = n - (ans == f[n - 1]); i > 0; i -= 2 + v[i])↵
p[++cnt] = i;↵
reverse(p + 1, p + cnt + 1);↵
for(int i = 1; i <= cnt; ++i) {↵
int pre = p[i - 1], cur = p[i], ctr = 0;↵
if(v[cur])↵
ctr += descension(cur - 1);↵
ctr += descension(pre + 1);↵
ctr += descension(cur);↵
assert(ctr == f[cur] - f[pre]);↵
}↵
printf("%d\n", m);↵
for(int i = 1; i <= m; ++i)↵
printf("%d\n", out[i]);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Thank you everyone!↵
↵
Happy Valentine's Day and happy Lunar New Year!
↵
This is not [user:Tommyr7,2018-02-14], but the **impostor** behind the round again (guess who I am? :P). The statements are written by me. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future!↵
↵
Here are some of the detailed tutorials!↵
↵
### Tutorials↵
↵
### [problem:934
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n,k;↵
int main()↵
{↵
scanf("%d",&k);↵
if (k>36) printf("%d\n",-1);↵
else↵
{↵
while (k>0)↵
{↵
if (k>=2)↵
{↵
printf("%d",8);↵
k-=2;↵
} else↵
{↵
printf("%d",9);↵
k-=1;↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long p;↵
int k;↵
int cnt=0;↵
int ans[107];↵
int get()↵
{↵
int x=p%k;↵
if (x<0) x+=k;↵
return x%k;↵
}↵
int main()↵
{↵
scanf("%lld%d",&p,&k);↵
while (p!=0)↵
{↵
++cnt;↵
ans[cnt]=get();↵
p-=get();↵
p/=(-k);↵
}↵
printf("%d\n",cnt);↵
for (int i=1;i<=cnt;i++)↵
printf("%d ",ans[i]);↵
printf("\n");↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
**Author** [user:quailty,2018-02-14] / **Preparation** [user:quailty,2018-02-14] / **Tutorial** [user:quailty,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934A]↵
</spoiler>↵
↵
<spoiler summary="Solution (quailty)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
const ll INF=(1LL<<60)-1;↵
ll a[55],b[55];↵
int main()↵
{↵
int n,m;↵
scanf("%d%d",&n,&m);↵
for(int i=1;i<=n;i++)↵
scanf("%lld",&a[i]);↵
for(int i=1;i<=m;i++)↵
scanf("%lld",&b[i]);↵
ll res=INF;↵
for(int i=1;i<=n;i++)↵
{↵
ll now=-INF;↵
for(int j=1;j<=n;j++)if(j!=i)↵
for(int k=1;k<=m;k++)↵
now=max(now,a[j]*b[k]);↵
res=min(res,now);↵
}↵
printf("%lld\n",res);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:934B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:934B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n,k;↵
int main()↵
{↵
scanf("%d",&k);↵
if (k>36) printf("%d\n",-1);↵
else↵
{↵
while (k>0)↵
{↵
if (k>=2)↵
{↵
printf("%d",8);↵
k-=2;↵
} else↵
{↵
printf("%d",9);↵
k-=1;↵
}↵
}↵
printf("\n");↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933A]↵
**Author** [user:visitWorld,2018-02-14] / **Preparation** [user:visitWorld,2018-02-14] / **Tutorial** [user:visitWorld,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933A]↵
</spoiler>↵
↵
<spoiler summary="Solution (visitWorld)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i)↵
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)↵
#define fi first↵
#define se second↵
#define mp(x, y) make_pair(x, y)↵
#define pb(x) push_back(x)↵
#define bin(x) (1 << (x))↵
#define SZ(x) int((x).size())↵
↵
using namespace std;↵
typedef pair<int, int> pii;↵
typedef vector<int> Vi;↵
typedef long long ll;↵
↵
template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }↵
template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }↵
↵
const int MAX_N = 2005;↵
↵
int pre[MAX_N][2], suf[MAX_N][2];↵
int g[MAX_N][MAX_N][2][2];↵
int w[MAX_N], N;↵
↵
int main() {↵
scanf("%d", &N);↵
rep (i, 0, N) { scanf("%d", &w[i]); w[i]--; }↵
rep (i, 0, N) {↵
if (i) memcpy(pre[i], pre[i - 1], sizeof pre[i]);↵
down (j, 2, w[i]) upmax(pre[i][j], pre[i][w[i]] + 1);↵
}↵
down (i, N, 0) {↵
if (i < N - 1) memcpy(suf[i], suf[i + 1], sizeof suf[i]);↵
rep (j, 0, w[i] + 1) upmax(suf[i][j], suf[i][w[i]] + 1);↵
}↵
int ans = pre[N - 1][1];↵
rep (i, 0, N) {↵
rep (a, 0, w[i] + 1) rep (b, w[i], 2) {↵
g[i][i][a][b] = 1;↵
}↵
}↵
rep (l, 1, N) rep (i, 0, N - l) {↵
int j = i + l;↵
rep (l, 0, 2) rep (a, 0, 2 - l) {↵
int b = a + l;↵
g[i][j][a][b] = max((a < 1 ? g[i][j][a + 1][b] : 0), (b ? g[i][j][a][b - 1] : 0));↵
upmax(g[i][j][a][b], g[i + 1][j][a][b] + (b == w[i]));↵
upmax(g[i][j][a][b], g[i][j - 1][a][b] + (a == w[j]));↵
upmax(ans, (i ? pre[i - 1][a] : 0) + g[i][j][a][b] + (j < N - 1 ? suf[j + 1][b] : 0));↵
}↵
}↵
printf("%d\n", ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933B]↵
**Author** [user:Tommyr7,2018-02-14] / **Preparation** [user:cyand1317,2018-02-14] / **Tutorial** [user:cyand1317,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long p;↵
int k;↵
int cnt=0;↵
int ans[107];↵
int get()↵
{↵
int x=p%k;↵
if (x<0) x+=k;↵
return x%k;↵
}↵
int main()↵
{↵
scanf("%lld%d",&p,&k);↵
while (p!=0)↵
{↵
++cnt;↵
ans[cnt]=get();↵
p-=get();↵
p/=(-k);↵
}↵
printf("%d\n",cnt);↵
for (int i=1;i<=cnt;i++)↵
printf("%d ",ans[i]);↵
printf("\n");↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933C]↵
**Author** [user:quailty,2018-02-14] / **Preparation** [user:quailty,2018-02-14] / **Tutorial** [user:quailty,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933C]↵
</spoiler>↵
↵
<spoiler summary="Solution (quailty)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
typedef long double db;↵
const db eps=1e-12;↵
↵
struct Point↵
{↵
db x,y;↵
Point(){}↵
Point(db _x,db _y):x(_x),y(_y){}↵
Point operator + (const Point &t)const↵
{↵
return Point(x+t.x,y+t.y);↵
}↵
Point operator - (const Point &t)const↵
{↵
return Point(x-t.x,y-t.y);↵
}↵
Point operator * (const db &t)const↵
{↵
return Point(x*t,y*t);↵
}↵
Point operator / (const db &t)const↵
{↵
return Point(x/t,y/t);↵
}↵
bool operator < (const Point &t)const↵
{↵
return fabs(x-t.x)<eps ? y<t.y : x<t.x;↵
}↵
bool operator == (const Point &t)const↵
{↵
return fabs(x-t.x)<eps && fabs(y-t.y)<eps;↵
}↵
db len()const↵
{↵
return sqrt(x*x+y*y);↵
}↵
Point rot90()const↵
{↵
return Point(-y,x);↵
}↵
};↵
↵
struct Circle↵
{↵
Point o;↵
db r;↵
Circle(){}↵
Circle(Point _o,db _r):o(_o),r(_r){}↵
friend vector<Point> operator & (const Circle &c1,const Circle &c2)↵
{↵
db d=(c1.o-c2.o).len();↵
if(d>c1.r+c2.r+eps || d<fabs(c1.r-c2.r)-eps)↵
return vector<Point>();↵
db dt=(c1.r*c1.r-c2.r*c2.r)/d,d1=(d+dt)/2;↵
Point dir=(c2.o-c1.o)/d,pcrs=c1.o+dir*d1;↵
dt=sqrt(max(0.0L,c1.r*c1.r-d1*d1)),dir=dir.rot90();↵
return vector<Point>{pcrs+dir*dt,pcrs-dir*dt};↵
}↵
}p[5];↵
↵
struct DSU↵
{↵
int fa[5];↵
void init(int n)↵
{↵
for(int i=1;i<=n;i++)↵
fa[i]=i;↵
}↵
int find(int x)↵
{↵
return fa[x]==x ? x : fa[x]=find(fa[x]);↵
}↵
void merge(int x,int y)↵
{↵
x=find(x),y=find(y);↵
if(x!=y)fa[x]=y;↵
}↵
}dsu;↵
↵
int main()↵
{↵
int n;↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++)↵
cin>>p[i].o.x>>p[i].o.y>>p[i].r;↵
vector<Point> all;↵
dsu.init(n);↵
int e=0;↵
for(int i=1;i<=n;i++)↵
{↵
vector<Point> pat;↵
for(int j=1;j<=n;j++)if(i!=j)↵
{↵
vector<Point> tmp=p[i]&p[j];↵
if(!tmp.empty())dsu.merge(i,j);↵
for(int k=0;k<(int)tmp.size();k++)↵
all.push_back(tmp[k]),pat.push_back(tmp[k]);↵
}↵
sort(pat.begin(),pat.end());↵
e+=unique(pat.begin(),pat.end())-pat.begin();↵
}↵
sort(all.begin(),all.end());↵
int v=unique(all.begin(),all.end())-all.begin(),c=0;↵
for(int i=1;i<=n;i++)↵
c+=(dsu.find(i)==i);↵
cout<<e-v+c+1<<endl;↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933D]↵
**Author** [user:skywalkert,2018-02-14] / **Preparation** [user:skywalkert,2018-02-14] / **Tutorial** [user:skywalkert,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933D]↵
</spoiler>↵
↵
<spoiler summary="Solution (skywalkert)">↵
~~~~~↵
#include <bits/stdc++.h>↵
typedef long long LL;↵
const int mod = (int)1e9 + 7, inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv5 = (mod * 2 + 1) / 5, inv7 = (mod + 1) / 7;↵
const int inv6 = (LL)inv2 * inv3 % mod, inv30 = (LL)inv5 * inv6 % mod, inv42 = (LL)inv6 * inv7 % mod;↵
const int coeff[4][8] = {↵
{0, 1}, // sum(b^0) = n↵
{0, inv6, inv2, inv3}, // sum(b^2) = 1/6 n + 1/2 n^2 + 1/3 n^3↵
{0, mod - inv30, 0, inv3, inv2, inv5}, // sum(b^4) = -1/30 n + 1/3 n^3 + 1/2 n^4 + 1/5 n^5↵
{0, inv42, 0, mod - inv6, 0, inv2, inv2, inv7} // sum(b^6) = 1/42 n - 1/6 n^3 + 1/2 n^5 + 1/2 n^6 + 1/7 n^7↵
};↵
LL n;↵
int f[4], g[4], ans;↵
int main() {↵
scanf("%lld", &n);↵
int nn = n % mod;↵
f[0] = nn * (nn + 1LL) % mod * (nn + 2) % mod;↵
f[1] = (3LL * nn + 4) % mod;↵
f[2] = mod - 3LL * (nn + 2) % mod;↵
f[3] = 2;↵
for(int x = 0; (LL)x * x <= n; ++x) {↵
LL rem = n - (LL)x * x;↵
int yLim = (int)ceil(sqrtl(rem));↵
for( ; (LL)yLim * yLim <= rem; ++yLim);↵
for( ; (LL)yLim * yLim > rem; --yLim);↵
int sum = 0, x2 = (LL)x * x % mod, x4 = (LL)x2 * x2 % mod, x6 = (LL)x2 * x4 % mod;↵
g[0] = (f[0] + (LL)f[1] * x2 + (LL)f[2] * x4 + (LL)f[3] * x6) % mod;↵
g[1] = (f[1] + 2LL * f[2] * x2 + 3LL * f[3] * x4) % mod;↵
g[2] = (f[2] + 3LL * f[3] * x2) % mod;↵
g[3] = f[3];↵
for(int i = 0; i < 4; ++i) {↵
int tmp = 0;↵
for(int j = i << 1 | 1; j >= 0; --j)↵
tmp = ((LL)tmp * yLim + coeff[i][j]) % mod;↵
sum = (sum + (LL)g[i] * (tmp << 1 | !i)) % mod;↵
}↵
x && (sum <<= 1) >= mod && (sum -= mod);↵
(ans += sum) >= mod && (ans -= mod);↵
}↵
ans = (LL)ans * inv6 % mod;↵
printf("%d\n", ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:933E]↵
**Author** [user:skywalkert,2018-02-14] / **Preparation** [user:skywalkert,2018-02-14] / **Tutorial** [user:skywalkert,2018-02-14]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:933E]↵
</spoiler>↵
↵
<spoiler summary="Solution (skywalkert)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long LL;↵
const int maxn = (int)3e5 + 3;↵
int n, a[maxn], cnt, p[maxn], m, out[maxn];↵
LL f[maxn];↵
bool v[maxn];↵
int descension(int pos) {↵
int dt = min(a[pos], a[pos + 1]);↵
if(dt)↵
out[++m] = pos;↵
a[pos] -= dt;↵
a[pos + 1] -= dt;↵
return dt;↵
}↵
int main() {↵
scanf("%d", &n);↵
for(int i = 1; i <= n; ++i) {↵
scanf("%d", a + i);↵
LL odd = f[max(i - 2, 0)] + a[i], even = f[max(i - 3, 0)] + max(a[i - 1], a[i]);↵
f[i] = min(odd, even);↵
v[i] = f[i] != odd;↵
}↵
// a[n + 1] = 0;↵
LL ans = min(f[n - 1], f[n]);↵
// printf("%lld\n", ans);↵
for(int i = n - (ans == f[n - 1]); i > 0; i -= 2 + v[i])↵
p[++cnt] = i;↵
reverse(p + 1, p + cnt + 1);↵
for(int i = 1; i <= cnt; ++i) {↵
int pre = p[i - 1], cur = p[i], ctr = 0;↵
if(v[cur])↵
ctr += descension(cur - 1);↵
ctr += descension(pre + 1);↵
ctr += descension(cur);↵
assert(ctr == f[cur] - f[pre]);↵
}↵
printf("%d\n", m);↵
for(int i = 1; i <= m; ++i)↵
printf("%d\n", out[i]);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Thank you everyone!↵
↵
Happy Valentine's Day and happy Lunar New Year!
