Hi, all!
This is not Tommyr7, 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
934A - Совместимая пара
Author quailty / Preparation quailty / Tutorial 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;
}
934B - Большая ставка
Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317
#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;
}
933A - Извилистые движения
Author visitWorld / Preparation visitWorld / Tutorial 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;
}
933B - Генеральная уборка
Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317
#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;
}
933C - Цветное зрелище
Author quailty / Preparation quailty / Tutorial 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;
}
#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;
}
933D - Оригинальное вырезание
Author skywalkert / Preparation skywalkert / Tutorial 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;
}
933E - Важнейшее объединение
Author skywalkert / Preparation skywalkert / Tutorial 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;
}
Thank you everyone!
Happy Valentine's Day and happy Lunar New Year!