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:934A]↵
**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>↵
↵
<spoiler summary="Solution (cyand1317)">↵
~~~~~↵
#include <cmath>↵
#include <cstdio>↵
#include <algorithm>↵
↵
static const int MAXN = 3;↵
static const double EPS = 1e-9;↵
↵
static int n;↵
static int x[MAXN], y[MAXN], r[MAXN];↵
↵
// -2: internally separate↵
// -1: internally tangent↵
// 0: intersecting↵
// +1: externally tangent↵
// +2: externally separate↵
static int g[MAXN][MAXN];↵
// Number of points passed by all three circles↵
static int conc;↵
↵
inline int rel(int a, int b)↵
{↵
int dssq = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]),↵
dfsq = (r[a] - r[b]) * (r[a] - r[b]),↵
smsq = (r[a] + r[b]) * (r[a] + r[b]);↵
↵
if (dssq < dfsq) return -2;↵
else if (dssq == dfsq) return -1;↵
else if (dssq < smsq) return 0;↵
else if (dssq == smsq) return +1;↵
else return +2;↵
}↵
↵
inline void get_intersections(int a, int b, double ix[2], double iy[2])↵
{↵
double angle = atan2(y[b] - y[a], x[b] - x[a]);↵
double ds = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));↵
double delta = acos((ds * ds + r[a] * r[a] - r[b] * r[b]) / (2.0 * r[a] * ds));↵
ix[0] = x[a] + r[a] * cos(angle + delta);↵
iy[0] = y[a] + r[a] * sin(angle + delta);↵
ix[1] = x[a] + r[a] * cos(angle - delta);↵
iy[1] = y[a] + r[a] * sin(angle - delta);↵
}↵
↵
inline bool on_circle(int a, double x0, double y0)↵
{↵
return fabs((x[a] - x0) * (x[a] - x0) + (y[a] - y0) * (y[a] - y0) - r[a] * r[a]) <= EPS;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n - 1; ++i)↵
for (int j = i + 1; j < n; ++j)↵
g[i][j] = g[j][i] = rel(i, j);↵
↵
conc = 0;↵
if (n == 3) {↵
for (int i = 0; i < 2; ++i) {↵
for (int j = i + 1; j < 3; ++j) if (g[i][j] >= -1 && g[i][j] <= +1) {↵
int k = 3 - i - j;↵
double ix[2], iy[2];↵
get_intersections(i, j, ix, iy);↵
if (on_circle(k, ix[0], iy[0])) ++conc;↵
if (on_circle(k, ix[1], iy[1]) && g[i][j] == 0) ++conc;↵
break;↵
}↵
if (conc != 0) break;↵
}↵
}↵
↵
if (n == 1) {↵
puts("2");↵
} else if (n == 2) {↵
puts(g[0][1] == 0 ? "4" : "3");↵
} else if (n == 3) {↵
int x[3] = { g[0][1], g[0][2], g[1][2] };↵
std::sort(x, x + 3);↵
if (x[0] == -2) {↵
printf("%d\n", 4 + (x[1] == 0) + (x[2] == 0));↵
} else if (x[0] == -1) {↵
if (x[1] == -1) {↵
printf("%d\n", x[2] == -1 ? 4 : (6 - x[2]));↵
} else {↵
switch (x[1] * 10 + x[2]) {↵
case 00: printf("%d\n", 7 - conc); break;↵
case 01: puts("6"); break;↵
case 02: puts("5"); break;↵
case 11: case 12: case 22: puts("4"); break;↵
default: puts("> <");↵
}↵
}↵
} else if (x[0] >= +1) {↵
puts(x[0] == +1 && x[2] == +1 ? "5" : "4");↵
} else { // x[0] == 0↵
switch (x[1] * 10 + x[2]) {↵
case 00: printf("%d\n", 8 - conc); break;↵
case 01: printf("%d\n", 7 - conc); break;↵
case 02: puts("6"); break;↵
case 11: puts("6"); break;↵
case 12: puts("5"); break;↵
case 22: puts("5"); break;↵
default: puts("> <");↵
}↵
}↵
} else puts("> <");↵
↵
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:934A]↵
**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>↵
↵
<spoiler summary="Solution (cyand1317)">↵
~~~~~↵
#include <cmath>↵
#include <cstdio>↵
#include <algorithm>↵
↵
static const int MAXN = 3;↵
static const double EPS = 1e-9;↵
↵
static int n;↵
static int x[MAXN], y[MAXN], r[MAXN];↵
↵
// -2: internally separate↵
// -1: internally tangent↵
// 0: intersecting↵
// +1: externally tangent↵
// +2: externally separate↵
static int g[MAXN][MAXN];↵
// Number of points passed by all three circles↵
static int conc;↵
↵
inline int rel(int a, int b)↵
{↵
int dssq = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]),↵
dfsq = (r[a] - r[b]) * (r[a] - r[b]),↵
smsq = (r[a] + r[b]) * (r[a] + r[b]);↵
↵
if (dssq < dfsq) return -2;↵
else if (dssq == dfsq) return -1;↵
else if (dssq < smsq) return 0;↵
else if (dssq == smsq) return +1;↵
else return +2;↵
}↵
↵
inline void get_intersections(int a, int b, double ix[2], double iy[2])↵
{↵
double angle = atan2(y[b] - y[a], x[b] - x[a]);↵
double ds = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));↵
double delta = acos((ds * ds + r[a] * r[a] - r[b] * r[b]) / (2.0 * r[a] * ds));↵
ix[0] = x[a] + r[a] * cos(angle + delta);↵
iy[0] = y[a] + r[a] * sin(angle + delta);↵
ix[1] = x[a] + r[a] * cos(angle - delta);↵
iy[1] = y[a] + r[a] * sin(angle - delta);↵
}↵
↵
inline bool on_circle(int a, double x0, double y0)↵
{↵
return fabs((x[a] - x0) * (x[a] - x0) + (y[a] - y0) * (y[a] - y0) - r[a] * r[a]) <= EPS;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);↵
↵
for (int i = 0; i < n - 1; ++i)↵
for (int j = i + 1; j < n; ++j)↵
g[i][j] = g[j][i] = rel(i, j);↵
↵
conc = 0;↵
if (n == 3) {↵
for (int i = 0; i < 2; ++i) {↵
for (int j = i + 1; j < 3; ++j) if (g[i][j] >= -1 && g[i][j] <= +1) {↵
int k = 3 - i - j;↵
double ix[2], iy[2];↵
get_intersections(i, j, ix, iy);↵
if (on_circle(k, ix[0], iy[0])) ++conc;↵
if (on_circle(k, ix[1], iy[1]) && g[i][j] == 0) ++conc;↵
break;↵
}↵
if (conc != 0) break;↵
}↵
}↵
↵
if (n == 1) {↵
puts("2");↵
} else if (n == 2) {↵
puts(g[0][1] == 0 ? "4" : "3");↵
} else if (n == 3) {↵
int x[3] = { g[0][1], g[0][2], g[1][2] };↵
std::sort(x, x + 3);↵
if (x[0] == -2) {↵
printf("%d\n", 4 + (x[1] == 0) + (x[2] == 0));↵
} else if (x[0] == -1) {↵
if (x[1] == -1) {↵
printf("%d\n", x[2] == -1 ? 4 : (6 - x[2]));↵
} else {↵
switch (x[1] * 10 + x[2]) {↵
case 00: printf("%d\n", 7 - conc); break;↵
case 01: puts("6"); break;↵
case 02: puts("5"); break;↵
case 11: case 12: case 22: puts("4"); break;↵
default: puts("> <");↵
}↵
}↵
} else if (x[0] >= +1) {↵
puts(x[0] == +1 && x[2] == +1 ? "5" : "4");↵
} else { // x[0] == 0↵
switch (x[1] * 10 + x[2]) {↵
case 00: printf("%d\n", 8 - conc); break;↵
case 01: printf("%d\n", 7 - conc); break;↵
case 02: puts("6"); break;↵
case 11: puts("6"); break;↵
case 12: puts("5"); break;↵
case 22: puts("5"); break;↵
default: puts("> <");↵
}↵
}↵
} else puts("> <");↵
↵
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!
