codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

933.md (17111B)


      1 Source: https://codeforces.com/blog/entry/57763
      2 
      3 Hi, all!
      4 
      5 This is not [Tommyr7](/profile/Tommyr7 "Мастер 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!
      6 
      7 Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future!
      8 
      9 Here are some of the detailed tutorials!
     10 
     11 ### Tutorials
     12 
     13 ### [934A - Совместимая пара](/contest/934/problem/A "Codeforces Round 462 (Div. 2)")
     14 
     15 **Author** [quailty](/profile/quailty "Гроссмейстер quailty") / **Preparation** [quailty](/profile/quailty "Гроссмейстер quailty") / **Tutorial** [quailty](/profile/quailty "Гроссмейстер quailty")
     16 
     17 **Tutorial**
     18 
     19 Tutorial is loading...
     20 
     21 **Solution (quailty)**
     22 
     23 ```
     24 #include<bits/stdc++.h>
     25 using namespace std;
     26 typedef long long ll;
     27 const ll INF=(1LL<<60)-1;
     28 ll a[55],b[55];
     29 int main()
     30 {
     31     int n,m;
     32     scanf("%d%d",&n,&m);
     33     for(int i=1;i<=n;i++)
     34         scanf("%lld",&a[i]);
     35     for(int i=1;i<=m;i++)
     36         scanf("%lld",&b[i]);
     37     ll res=INF;
     38     for(int i=1;i<=n;i++)
     39     {
     40         ll now=-INF;
     41         for(int j=1;j<=n;j++)if(j!=i)
     42             for(int k=1;k<=m;k++)
     43                 now=max(now,a[j]*b[k]);
     44         res=min(res,now);
     45     }
     46     printf("%lld\n",res);
     47     return 0;
     48 }
     49 ```
     50 
     51 ### [934B - Большая ставка](/contest/934/problem/B "Codeforces Round 462 (Div. 2)")
     52 
     53 **Author** [Tommyr7](/profile/Tommyr7 "Мастер Tommyr7") / **Preparation** [cyand1317](/profile/cyand1317 "Гроссмейстер cyand1317") / **Tutorial** [cyand1317](/profile/cyand1317 "Гроссмейстер cyand1317")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (Tommyr7)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63 using namespace std;
     64 int n,k;
     65 int main()
     66 {
     67 	scanf("%d",&k);
     68 	if (k>36) printf("%d\n",-1);
     69 	else
     70 	{
     71 		while (k>0)
     72 		{
     73 			if (k>=2)
     74 			{
     75 				printf("%d",8);
     76 				k-=2;
     77 			} else
     78 			{
     79 				printf("%d",9);
     80 				k-=1;
     81 			}
     82 		}
     83 		printf("\n");
     84 	}
     85 	return 0;
     86 }
     87 ```
     88 
     89 ### [933A - Извилистые движения](/contest/933/problem/A "Codeforces Round 462 (Div. 1)")
     90 
     91 **Author** [visitWorld](/profile/visitWorld "Эксперт visitWorld") / **Preparation** [visitWorld](/profile/visitWorld "Эксперт visitWorld") / **Tutorial** [visitWorld](/profile/visitWorld "Эксперт visitWorld")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution (visitWorld)**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 
    102 #define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i)
    103 #define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
    104 #define fi first
    105 #define se second
    106 #define mp(x, y) make_pair(x, y)
    107 #define pb(x) push_back(x)
    108 #define bin(x) (1 << (x))
    109 #define SZ(x) int((x).size())
    110 
    111 using namespace std;
    112 typedef pair<int, int> pii;
    113 typedef vector<int> Vi;
    114 typedef long long ll;
    115 
    116 template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
    117 template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }
    118 
    119 const int MAX_N = 2005;
    120 
    121 int pre[MAX_N][2], suf[MAX_N][2];
    122 int g[MAX_N][MAX_N][2][2];
    123 int w[MAX_N], N;
    124 
    125 int main() {
    126 	scanf("%d", &N);
    127 	rep (i, 0, N) { scanf("%d", &w[i]); w[i]--; }
    128 	rep (i, 0, N) {
    129 		if (i) memcpy(pre[i], pre[i - 1], sizeof pre[i]);
    130 		down (j, 2, w[i]) upmax(pre[i][j], pre[i][w[i]] + 1);
    131 	}
    132 	down (i, N, 0) {
    133 		if (i < N - 1) memcpy(suf[i], suf[i + 1], sizeof suf[i]);
    134 		rep (j, 0, w[i] + 1) upmax(suf[i][j], suf[i][w[i]] + 1);
    135 	}
    136 	int ans = pre[N - 1][1];
    137 	rep (i, 0, N) {
    138 		rep (a, 0, w[i] + 1) rep (b, w[i], 2) {
    139 			g[i][i][a][b] = 1;
    140 		}
    141 	}
    142 	rep (l, 1, N) rep (i, 0, N - l) {
    143 		int j = i + l;
    144 		rep (l, 0, 2) rep (a, 0, 2 - l) {
    145 			int b = a + l;
    146 			g[i][j][a][b] = max((a < 1 ? g[i][j][a + 1][b] : 0), (b ? g[i][j][a][b - 1] : 0));
    147 			upmax(g[i][j][a][b], g[i + 1][j][a][b] + (b == w[i]));
    148 			upmax(g[i][j][a][b], g[i][j - 1][a][b] + (a == w[j]));
    149 			upmax(ans, (i ? pre[i - 1][a] : 0) + g[i][j][a][b] + (j < N - 1 ? suf[j + 1][b] : 0));
    150 		}
    151 	}
    152 	printf("%d\n", ans);
    153 	return 0;
    154 }
    155 ```
    156 
    157 ### [933B - Генеральная уборка](/contest/933/problem/B "Codeforces Round 462 (Div. 1)")
    158 
    159 **Author** [Tommyr7](/profile/Tommyr7 "Мастер Tommyr7") / **Preparation** [cyand1317](/profile/cyand1317 "Гроссмейстер cyand1317") / **Tutorial** [cyand1317](/profile/cyand1317 "Гроссмейстер cyand1317")
    160 
    161 **Tutorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Solution (Tommyr7)**
    166 
    167 ```
    168 #include <bits/stdc++.h>
    169 using namespace std;
    170 long long p;
    171 int k;
    172 int cnt=0;
    173 int ans[107];
    174 int get()
    175 {
    176 	int x=p%k;
    177 	if (x<0) x+=k;
    178 	return x%k;
    179 }
    180 int main()
    181 {
    182 	scanf("%lld%d",&p,&k);
    183 	while (p!=0)
    184 	{
    185 		++cnt;
    186 		ans[cnt]=get();
    187 		p-=get();
    188 		p/=(-k);
    189 	}
    190 	printf("%d\n",cnt);
    191 	for (int i=1;i<=cnt;i++)
    192 		printf("%d ",ans[i]);
    193 	printf("\n");
    194 	return 0;
    195 }
    196 ```
    197 
    198 ### [933C - Цветное зрелище](/contest/933/problem/C "Codeforces Round 462 (Div. 1)")
    199 
    200 **Author** [quailty](/profile/quailty "Гроссмейстер quailty") / **Preparation** [quailty](/profile/quailty "Гроссмейстер quailty") / **Tutorial** [quailty](/profile/quailty "Гроссмейстер quailty")
    201 
    202 **Tutorial**
    203 
    204 Tutorial is loading...
    205 
    206 **Solution (quailty)**
    207 
    208 ```
    209 #include<bits/stdc++.h>
    210 using namespace std;
    211 
    212 typedef long double db;
    213 const db eps=1e-12;
    214 
    215 struct Point
    216 {
    217     db x,y;
    218     Point(){}
    219     Point(db _x,db _y):x(_x),y(_y){}
    220     Point operator + (const Point &t)const
    221     {
    222         return Point(x+t.x,y+t.y);
    223     }
    224     Point operator - (const Point &t)const
    225     {
    226         return Point(x-t.x,y-t.y);
    227     }
    228     Point operator * (const db &t)const
    229     {
    230         return Point(x*t,y*t);
    231     }
    232     Point operator / (const db &t)const
    233     {
    234         return Point(x/t,y/t);
    235     }
    236     bool operator < (const Point &t)const
    237     {
    238         return fabs(x-t.x)<eps ? y<t.y : x<t.x;
    239     }
    240     bool operator == (const Point &t)const
    241     {
    242         return fabs(x-t.x)<eps && fabs(y-t.y)<eps;
    243     }
    244     db len()const
    245     {
    246         return sqrt(x*x+y*y);
    247     }
    248     Point rot90()const
    249     {
    250         return Point(-y,x);
    251     }
    252 };
    253 
    254 struct Circle
    255 {
    256     Point o;
    257     db r;
    258     Circle(){}
    259     Circle(Point _o,db _r):o(_o),r(_r){}
    260     friend vector<Point> operator & (const Circle &c1,const Circle &c2)
    261     {
    262         db d=(c1.o-c2.o).len();
    263         if(d>c1.r+c2.r+eps || d<fabs(c1.r-c2.r)-eps)
    264             return vector<Point>();
    265         db dt=(c1.r*c1.r-c2.r*c2.r)/d,d1=(d+dt)/2;
    266         Point dir=(c2.o-c1.o)/d,pcrs=c1.o+dir*d1;
    267         dt=sqrt(max(0.0L,c1.r*c1.r-d1*d1)),dir=dir.rot90();
    268         return vector<Point>{pcrs+dir*dt,pcrs-dir*dt};
    269     }
    270 }p[5];
    271 
    272 struct DSU
    273 {
    274     int fa[5];
    275     void init(int n)
    276     {
    277         for(int i=1;i<=n;i++)
    278             fa[i]=i;
    279     }
    280     int find(int x)
    281     {
    282         return fa[x]==x ? x : fa[x]=find(fa[x]);
    283     }
    284     void merge(int x,int y)
    285     {
    286         x=find(x),y=find(y);
    287         if(x!=y)fa[x]=y;
    288     }
    289 }dsu;
    290 
    291 int main()
    292 {
    293     int n;
    294     scanf("%d",&n);
    295     for(int i=1;i<=n;i++)
    296         cin>>p[i].o.x>>p[i].o.y>>p[i].r;
    297     vector<Point> all;
    298     dsu.init(n);
    299     int e=0;
    300     for(int i=1;i<=n;i++)
    301     {
    302         vector<Point> pat;
    303         for(int j=1;j<=n;j++)if(i!=j)
    304         {
    305             vector<Point> tmp=p[i]&p[j];
    306             if(!tmp.empty())dsu.merge(i,j);
    307             for(int k=0;k<(int)tmp.size();k++)
    308                 all.push_back(tmp[k]),pat.push_back(tmp[k]);
    309         }
    310         sort(pat.begin(),pat.end());
    311         e+=unique(pat.begin(),pat.end())-pat.begin();
    312     }
    313     sort(all.begin(),all.end());
    314     int v=unique(all.begin(),all.end())-all.begin(),c=0;
    315     for(int i=1;i<=n;i++)
    316         c+=(dsu.find(i)==i);
    317     cout<<e-v+c+1<<endl;
    318     return 0;
    319 }
    320 ```
    321 
    322 **Solution (cyand1317)**
    323 
    324 ```
    325 #include <cmath>
    326 #include <cstdio>
    327 #include <algorithm>
    328 
    329 static const int MAXN = 3;
    330 static const double EPS = 1e-9;
    331 
    332 static int n;
    333 static int x[MAXN], y[MAXN], r[MAXN];
    334 
    335 // -2: internally separate
    336 // -1: internally tangent
    337 //  0: intersecting
    338 // +1: externally tangent
    339 // +2: externally separate
    340 static int g[MAXN][MAXN];
    341 // Number of points passed by all three circles
    342 static int conc;
    343 
    344 inline int rel(int a, int b)
    345 {
    346     int dssq = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]),
    347         dfsq = (r[a] - r[b]) * (r[a] - r[b]),
    348         smsq = (r[a] + r[b]) * (r[a] + r[b]);
    349 
    350     if (dssq < dfsq) return -2;
    351     else if (dssq == dfsq) return -1;
    352     else if (dssq < smsq) return 0;
    353     else if (dssq == smsq) return +1;
    354     else return +2;
    355 }
    356 
    357 inline void get_intersections(int a, int b, double ix[2], double iy[2])
    358 {
    359     double angle = atan2(y[b] - y[a], x[b] - x[a]);
    360     double ds = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
    361     double delta = acos((ds * ds + r[a] * r[a] - r[b] * r[b]) / (2.0 * r[a] * ds));
    362     ix[0] = x[a] + r[a] * cos(angle + delta);
    363     iy[0] = y[a] + r[a] * sin(angle + delta);
    364     ix[1] = x[a] + r[a] * cos(angle - delta);
    365     iy[1] = y[a] + r[a] * sin(angle - delta);
    366 }
    367 
    368 inline bool on_circle(int a, double x0, double y0)
    369 {
    370     return fabs((x[a] - x0) * (x[a] - x0) + (y[a] - y0) * (y[a] - y0) - r[a] * r[a]) <= EPS;
    371 }
    372 
    373 int main()
    374 {
    375     scanf("%d", &n);
    376     for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);
    377 
    378     for (int i = 0; i < n - 1; ++i)
    379         for (int j = i + 1; j < n; ++j)
    380             g[i][j] = g[j][i] = rel(i, j);
    381 
    382     conc = 0;
    383     if (n == 3) {
    384         for (int i = 0; i < 2; ++i) {
    385             for (int j = i + 1; j < 3; ++j) if (g[i][j] >= -1 && g[i][j] <= +1) {
    386                 int k = 3 - i - j;
    387                 double ix[2], iy[2];
    388                 get_intersections(i, j, ix, iy);
    389                 if (on_circle(k, ix[0], iy[0])) ++conc;
    390                 if (on_circle(k, ix[1], iy[1]) && g[i][j] == 0) ++conc;
    391                 break;
    392             }
    393             if (conc != 0) break;
    394         }
    395     }
    396 
    397     if (n == 1) {
    398         puts("2");
    399     } else if (n == 2) {
    400         puts(g[0][1] == 0 ? "4" : "3");
    401     } else if (n == 3) {
    402         int x[3] = { g[0][1], g[0][2], g[1][2] };
    403         std::sort(x, x + 3);
    404         if (x[0] == -2) {
    405             printf("%d\n", 4 + (x[1] == 0) + (x[2] == 0));
    406         } else if (x[0] == -1) {
    407             if (x[1] == -1) {
    408                 printf("%d\n", x[2] == -1 ? 4 : (6 - x[2]));
    409             } else {
    410                 switch (x[1] * 10 + x[2]) {
    411                     case 00: printf("%d\n", 7 - conc); break;
    412                     case 01: puts("6"); break;
    413                     case 02: puts("5"); break;
    414                     case 11: case 12: case 22: puts("4"); break;
    415                     default: puts("> <");
    416                 }
    417             }
    418         } else if (x[0] >= +1) {
    419             puts(x[0] == +1 && x[2] == +1 ? "5" : "4");
    420         } else {    // x[0] == 0
    421             switch (x[1] * 10 + x[2]) {
    422                 case 00: printf("%d\n", 8 - conc); break;
    423                 case 01: printf("%d\n", 7 - conc); break;
    424                 case 02: puts("6"); break;
    425                 case 11: puts("6"); break;
    426                 case 12: puts("5"); break;
    427                 case 22: puts("5"); break;
    428                 default: puts("> <");
    429             }
    430         }
    431     } else puts("> <");
    432 
    433     return 0;
    434 }
    435 ```
    436 
    437 ### [933D - Оригинальное вырезание](/contest/933/problem/D "Codeforces Round 462 (Div. 1)")
    438 
    439 **Author** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert") / **Preparation** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert") / **Tutorial** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert")
    440 
    441 **Tutorial**
    442 
    443 Tutorial is loading...
    444 
    445 **Solution (skywalkert)**
    446 
    447 ```
    448 #include <bits/stdc++.h>
    449 typedef long long LL;
    450 const int mod = (int)1e9 + 7, inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv5 = (mod * 2 + 1) / 5, inv7 = (mod + 1) / 7;
    451 const int inv6 = (LL)inv2 * inv3 % mod, inv30 = (LL)inv5 * inv6 % mod, inv42 = (LL)inv6 * inv7 % mod;
    452 const int coeff[4][8] = {
    453 {0, 1}, // sum(b^0) = n
    454 {0, inv6, inv2, inv3}, // sum(b^2) = 1/6 n + 1/2 n^2 + 1/3 n^3
    455 {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
    456 {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
    457 };
    458 LL n;
    459 int f[4], g[4], ans;
    460 int main() {
    461 	scanf("%lld", &n);
    462 	int nn = n % mod;
    463 	f[0] = nn * (nn + 1LL) % mod * (nn + 2) % mod;
    464 	f[1] = (3LL * nn + 4) % mod;
    465 	f[2] = mod - 3LL * (nn + 2) % mod;
    466 	f[3] = 2;
    467 	for(int x = 0; (LL)x * x <= n; ++x) {
    468 		LL rem = n - (LL)x * x;
    469 		int yLim = (int)ceil(sqrtl(rem));
    470 		for( ; (LL)yLim * yLim <= rem; ++yLim);
    471 		for( ; (LL)yLim * yLim > rem; --yLim);
    472 		int sum = 0, x2 = (LL)x * x % mod, x4 = (LL)x2 * x2 % mod, x6 = (LL)x2 * x4 % mod;
    473 		g[0] = (f[0] + (LL)f[1] * x2 + (LL)f[2] * x4 + (LL)f[3] * x6) % mod;
    474 		g[1] = (f[1] + 2LL * f[2] * x2 + 3LL * f[3] * x4) % mod;
    475 		g[2] = (f[2] + 3LL * f[3] * x2) % mod;
    476 		g[3] = f[3];
    477 		for(int i = 0; i < 4; ++i) {
    478 			int tmp = 0;
    479 			for(int j = i << 1 | 1; j >= 0; --j)
    480 				tmp = ((LL)tmp * yLim + coeff[i][j]) % mod;
    481 			sum = (sum + (LL)g[i] * (tmp << 1 | !i)) % mod;
    482 		}
    483 		x && (sum <<= 1) >= mod && (sum -= mod);
    484 		(ans += sum) >= mod && (ans -= mod);
    485 	}
    486 	ans = (LL)ans * inv6 % mod;
    487 	printf("%d\n", ans);
    488 	return 0;
    489 }
    490 ```
    491 
    492 **Solution (demon1999)**
    493 
    494 ```
    495 #include <bits/stdc++.h>
    496 
    497 using namespace std;
    498 
    499 #define re return
    500 #define sz(a) (int)a.size()
    501 #define mp(a, b) make_pair(a, b)
    502 #define fi first
    503 #define se second
    504 #define re return
    505 #define forn(i, n) for (int i = 0; i < int(n); i++)
    506 #define bend(a) a.begin(),a.end()
    507 typedef long long ll;
    508 typedef vector<int> vi;
    509 typedef pair<int, int> pii;
    510 typedef pair<long long, long long> pll;
    511 typedef long double ld;
    512 typedef unsigned long long ull;
    513 const ll mod = int(1e9) + 7;
    514 
    515 ll n, sum1, sum2, sum3, sum4, ans;
    516 vector<ll> cp;
    517 
    518 ll mdd(ll c) {
    519 	c %= mod;
    520 	if (c < 0) c += mod;
    521 	re c;
    522 }
    523 
    524 ll pow1(ll k, ll st) {
    525 	ll ans = 1;
    526 	while (st) {
    527 		if (st & 1) ans = mdd(ans * k);
    528 		k = mdd(k * k);
    529 		st >>= 1;
    530 	}
    531 	re ans;
    532 }
    533 
    534 ll get_sum(ll n) {
    535 	n %= mod;
    536 	n += mod;
    537 	n %= mod;
    538 	re (n * (n + 1) / 2LL) % mod;
    539 }
    540 
    541 ll get_cnt(ll a) {
    542 	a = mdd(a);
    543 	re mdd(mdd(2LL * mdd(a * a) * a) - mdd(3LL * mdd(a * a) * mdd(n + 2)) + mdd(mdd(a) * mdd(3LL * n + 4)) + mdd(n) * mdd(mdd(mdd(n) * mdd(n)) + 3LL * n + 2LL));
    544 }
    545 
    546 int main() {
    547 	iostream::sync_with_stdio(0), cin.tie(0);
    548 	cin >> n;
    549 	for (ll k = 1; k * k <= n; k++) {
    550 		ll c = mdd(k * k);
    551 		cp.push_back(k * k);
    552 		sum1 = mdd(sum1 + c);
    553 		sum2 = mdd(sum2 + mdd(c * c));
    554 		sum3 = mdd(sum3 + mdd(mdd(c * c) * c));
    555 		sum4 = mdd(sum4 + get_cnt(c));
    556 		//cout << sum4 << "\n";
    557 	}
    558 	ans = mdd(get_cnt(1) + 4LL * sum4);
    559 	ll k1 = 2, k2 = mdd(-3LL * (n + 2)), k3 = mdd(3LL * n + 4);
    560 	for (ll a = 0; ; a++){
    561 		while (sz(cp) && cp.back() + (a+1LL) * (a + 1LL) > n) {
    562 			ll c = mdd(cp.back() + a * a);
    563 			sum1 = mdd(sum1 - c);
    564 			sum2 = mdd(sum2 - mdd(c * c));
    565 			sum3 = mdd(sum3 - mdd(mdd(c * c) * c));
    566 			sum4 = mdd(sum4 - mdd(get_cnt(c)));
    567 			cp.pop_back();
    568 			continue;
    569 		}		
    570 		if (sz(cp) == 0) break;
    571 		ll k = mdd(2LL * a + 1), ksq = mdd(k * k), ktr = mdd(ksq * k);
    572 		//cout << sum4 << "\n";
    573 		sum4 = mdd(sum4 + mdd(ll(sz(cp)) * mdd(k1 * ktr + k2 * ksq + k3 * k)) +
    574 			   mdd(sum1 * mdd(2LL * k * k2 + 3LL * k1 * ksq)) +
    575 			   mdd(sum2 * mdd(3LL * k * k1)));
    576 		//cout << sum4 << "\n";
    577 		ans = mdd(ans + 4LL * sum4);
    578 		sum3 = mdd(sum3 + mdd(ll(sz(cp)) * ktr) + mdd(sum2 * 3LL * k) + mdd(ksq * 3LL * sum1));
    579 		sum2 = mdd(sum2 + mdd(ll(sz(cp)) * ksq) + mdd(2LL * sum1 * k));
    580 		sum1 = mdd(sum1 + mdd(ll(sz(cp)) * k));
    581 		//cout << sum3 << " " << sum2 << " " << sum1 << "\n";
    582 	}
    583 	//cout << ans /6<< "\n";
    584 	ans = mdd(ans * pow1(6, mod - 2));
    585 	cout << ans;
    586 }
    587 ```
    588 
    589 ### [933E - Важнейшее объединение](/contest/933/problem/E "Codeforces Round 462 (Div. 1)")
    590 
    591 **Author** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert") / **Preparation** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert") / **Tutorial** [skywalkert](/profile/skywalkert "Кандидат в мастера skywalkert")
    592 
    593 **Tutorial**
    594 
    595 Tutorial is loading...
    596 
    597 **Solution (skywalkert)**
    598 
    599 ```
    600 #include <bits/stdc++.h>
    601 using namespace std;
    602 typedef long long LL;
    603 const int maxn = (int)3e5 + 3;
    604 int n, a[maxn], cnt, p[maxn], m, out[maxn];
    605 LL f[maxn];
    606 bool v[maxn];
    607 int descension(int pos) {
    608 	int dt = min(a[pos], a[pos + 1]);
    609 	if(dt)
    610 		out[++m] = pos;
    611 	a[pos] -= dt;
    612 	a[pos + 1] -= dt;
    613 	return dt;
    614 }
    615 int main() {
    616 	scanf("%d", &n);
    617 	for(int i = 1; i <= n; ++i) {
    618 		scanf("%d", a + i);
    619 		LL odd = f[max(i - 2, 0)] + a[i], even = f[max(i - 3, 0)] + max(a[i - 1], a[i]);
    620 		f[i] = min(odd, even);
    621 		v[i] = f[i] != odd;
    622 	}
    623 	// a[n + 1] = 0;
    624 	LL ans = min(f[n - 1], f[n]);
    625 	// printf("%lld\n", ans);
    626 	for(int i = n - (ans == f[n - 1]); i > 0; i -= 2 + v[i])
    627 		p[++cnt] = i;
    628 	reverse(p + 1, p + cnt + 1);
    629 	for(int i = 1; i <= cnt; ++i) {
    630 		int pre = p[i - 1], cur = p[i], ctr = 0;
    631 		if(v[cur])
    632 			ctr += descension(cur - 1);
    633 		ctr += descension(pre + 1);
    634 		ctr += descension(cur);
    635 		assert(ctr == f[cur] - f[pre]);
    636 	}
    637 	printf("%d\n", m);
    638 	for(int i = 1; i <= m; ++i)
    639 		printf("%d\n", out[i]);
    640 	return 0;
    641 }
    642 ```
    643 
    644 Thank you everyone!
    645 
    646 Happy Valentine's Day and happy Lunar New Year!