codeforces-scrape

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

820.md (8926B)


      1 Source: https://codeforces.com/blog/entry/52946
      2 
      3 First, I apologize for problems with round and serious problem with Div1A/Div2C. It was very important round for me and, as always, something goes wrong. [KAN](/profile/KAN "Grandmaster KAN") have already [wrote about this](//codeforces.com/blog/entry/52944).
      4 
      5 Anyway, there are problems, so editorial must exists. Due some circumstances, Editorial will be upload in parts. Also, most of tutorials will contain main ideas how to solve task, not ready algorithm.
      6 
      7 Tutorial is loading...
      8 
      9 **code**
     10 
     11 ```
     12 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     13 #define forn(i, n) fore(i, 0, n)
     14 
     15 int c, l, v0, v1, a;
     16 
     17 inline bool read() {
     18 	if(!(cin >> c >> v0 >> v1 >> a >> l))
     19 		return false;
     20 	
     21 	return true;
     22 }
     23 
     24 inline void solve() {
     25 	int pos = v0;
     26 	int t = 1;
     27 	
     28 	int add = v0;
     29 	
     30 	while(pos < c) {
     31 		add = min(v1, add + a);
     32 		
     33 		pos += add - l;
     34 		t++;
     35 	}
     36 	
     37 	cout << t << endl;
     38 }
     39 ```
     40 
     41 Tutorial is loading...
     42 
     43 **code**
     44 
     45 ```
     46 int n, a;
     47 
     48 inline bool read() {
     49 	if(!(cin >> n >> a))
     50 		return false;
     51 	
     52 	return true;
     53 }
     54 
     55 inline void solve() {
     56 	int base = n * a / 180;
     57 	base = max(1, min(n - 2, base));
     58 	
     59 	int bk = base;
     60 	for(int ck = max(1, base - 2); ck <= min(n - 2, base + 2); ck++) {
     61 		if(abs(180 * ck - n * a) < abs(180 * bk - n * a))
     62 			bk = ck;
     63 	}
     64 	
     65 	cout << 2 << " " << 1 << " " << bk + 2 << endl;
     66 }
     67 ```
     68 
     69 Tutorial is loading...
     70 
     71 **code**
     72 
     73 Tutorial is loading...
     74 
     75 **code**
     76 
     77 ```
     78 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     79 #define forn(i, n) fore(i, 0, n)
     80 
     81 typedef long long li;
     82 
     83 const int N = 1000 * 1000 + 555;
     84 
     85 int n, p[N];
     86 
     87 inline bool read() {
     88 	if(!(cin >> n))
     89 		return false;
     90 	forn(i, n)
     91 		assert(scanf("%d", &p[i]) == 1);
     92 	return true;
     93 }
     94 
     95 li sum[N], df[N], res[N];
     96 
     97 inline void add(int lf, int rg, int k, int b) {
     98 	if(lf > rg)
     99 		return;
    100 				
    101 	sum[lf] += b;
    102 	df[lf] += k;
    103 	
    104 	sum[rg + 1] -= b + k * 1ll * (rg - lf);
    105 	df[rg] -= k;
    106 }
    107 
    108 inline void calc() {
    109 	li curdf = 0;
    110 	forn(i, n) {
    111 		sum[i] += curdf;
    112 		curdf += df[i];
    113 	}
    114 	
    115 	li cursm = 0;
    116 	forn(i, n) {	
    117 		cursm += sum[i];
    118 		res[i] += cursm;
    119 	}
    120 }
    121 
    122 inline void solve() {
    123 	memset(sum, 0, sizeof sum);
    124 	memset(df, 0, sizeof df);
    125 	memset(res, 0, sizeof res);
    126 	
    127 	forn(i, n) {
    128 		int c1 = i + 1, p1 = 0;
    129 		int c2 = n,     p2 = p1 + c2 - c1;
    130 		int c3 = i,     p3 = p2 + c3;
    131 		
    132 		if(p[i] <= c3) {
    133 			add(p1, p2, 1, c1 - p[i]);
    134 			add(p2 + 1, p2 + p[i], -1, p[i] - 1);
    135 			add(p2 + p[i] + 1, p3, 1, 1);
    136 		} else {
    137 			add(p1, p1 + p[i] - c1, -1, p[i] - c1);
    138 			add(p1 + p[i] - c1 + 1, p2, 1, 1);
    139 			add(p2 + 1, p3, -1, p[i] - 1);
    140 		}
    141 	}
    142 	
    143 	calc();
    144 	
    145 	int ans = 0;
    146 	forn(i, n)
    147 		if(res[ans] > res[i])
    148 			ans = i;
    149 			
    150 	cout << res[ans] << " " << ans << endl;
    151 }
    152 ```
    153 
    154 Tutorial is loading...
    155 
    156 **code**
    157 
    158 ```
    159 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    160 #define forn(i, n) fore(i, 0, n)
    161 
    162 #define all(a) (a).begin(), (a).end()
    163 #define sqr(a) ((a) * (a))
    164 #define sz(a) int(a.size())
    165 #define mp make_pair
    166 #define pb push_back
    167 
    168 typedef long long li;
    169 typedef pair<int, int> pt;
    170 typedef pair<li, li> ptl;
    171 
    172 const int INF = int(1e9);
    173 const li INF64 = li(INF) * INF;
    174 
    175 int n[3], m[3], s[3];
    176 
    177 inline bool read() {
    178 	if(scanf("%d %d %d", &n[0], &n[1], &n[2]) != 3)
    179 		return false;
    180 	forn(i, 3)
    181 		assert(scanf("%d", &m[i]) == 1);
    182 	forn(i, 3)
    183 		assert(scanf("%d", &s[i]) == 1);
    184 	return true;
    185 }
    186 
    187 const int N = 2 * 1000 * 1000 + 55;
    188 int ls[N];
    189 
    190 inline void precalc() {
    191 	memset(ls, -1, sizeof ls);
    192 	
    193 	ls[0] = ls[1] = 1;
    194 	fore(i, 2, N) {
    195 		if(ls[i] != -1)
    196 			continue;
    197 			
    198 		ls[i] = i;
    199 		for(li j = i * 1ll * i; j < N; j += i)
    200 			if(ls[j] == -1)
    201 				ls[j] = i;
    202 	}
    203 }
    204 
    205 inline vector<pt> fact(int n[3]) {
    206 	vector<int> divs;
    207 	
    208 	forn(i, 3) {
    209 		int cur = n[i];
    210 		while(ls[cur] != cur) {
    211 			divs.pb(ls[cur]);
    212 			cur /= ls[cur];
    213 		}
    214 		if(cur > 1)
    215 			divs.pb(cur);
    216 	}
    217 	
    218 	sort(all(divs));
    219 	vector<pt> ans;
    220 	
    221 	int u = 0;
    222 	while(u < sz(divs)) {
    223 		int v = u;
    224 		while(v < sz(divs) && divs[v] == divs[u])
    225 			v++;
    226 		
    227 		ans.pb(mp(divs[u], v - u));
    228 		u = v;
    229 	}
    230 	
    231 	return ans;
    232 }
    233 
    234 li ans;
    235 
    236 li nn, mm, ss;
    237 vector<pt> fs;
    238 vector<li> bad;
    239 
    240 void calcDivs(int pos, li val) {
    241 	if(pos >= sz(fs)) {
    242 		ans += (val <= nn);
    243 		return;
    244 	}
    245 	
    246 	li cv = 1;
    247 	forn(i, fs[pos].y + 1) {
    248 		calcDivs(pos + 1, val * cv);
    249 		
    250 		cv *= fs[pos].x;
    251 	}
    252 }
    253 
    254 void calcInEx(int pos, li val, int cnt) {
    255 	if(pos >= sz(bad)) {
    256 		li k = cnt ? -1 : 1;
    257 		
    258 		ans += k * (mm / val);
    259 		return;
    260 	}
    261 	
    262 	calcInEx(pos + 1, val, cnt);
    263 	calcInEx(pos + 1, val * bad[pos], cnt ^ 1);
    264 }
    265 
    266 inline void solve() {
    267 	ans = 0;
    268 	s[0] *= 2;
    269 	
    270 	nn = n[0] * 1ll * n[1] * 1ll * n[2];
    271 	mm = m[0] * 1ll * m[1] * 1ll * m[2];
    272 	ss = s[0] * 1ll * s[1] * 1ll * s[2];
    273 	
    274 	fs = fact(s);
    275 	calcDivs(0, 1);
    276 	
    277 	bad.clear();
    278 	vector<pt> fn = fact(n);
    279 	
    280 	forn(i, sz(fn)) {
    281 		li cv = fn[i].x;
    282 		forn(k, fn[i].y) {
    283 			if(ss % cv != 0) {
    284 				bad.pb(cv);
    285 				break;
    286 			}
    287 			cv *= fn[i].x;
    288 		}
    289 	}
    290 	
    291 	calcInEx(0, 1, 0);
    292 	
    293 	printf("%I64d\n", ans);
    294 }
    295 ```
    296 
    297 Tutorial is loading...
    298 
    299 **code**
    300 
    301 ```
    302 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    303 #define forn(i, n) fore(i, 0, n)
    304 
    305 #define all(a) (a).begin(), (a).end()
    306 #define sqr(a) ((a) * (a))
    307 #define sz(a) int(a.size())
    308 #define mp make_pair
    309 #define pb push_back
    310 
    311 #define x first
    312 #define y second
    313 
    314 typedef long long li;
    315 typedef long double ld;
    316 typedef pair<int, int> pt;
    317 
    318 const int INF = int(1e9);
    319 const li INF64 = li(INF) * INF;
    320 
    321 int gcd(int a, int b) {
    322 	if(a == 0)
    323 		return b;
    324 	return gcd(b % a, a);
    325 }
    326 
    327 int exgcd(int a, li &x, int b, li &y) {
    328 	if(a == 0) {
    329 		x = 0, y = 1;
    330 		return b;
    331 	}
    332 	
    333 	li xx, yy;
    334 	int g = exgcd(b % a, xx, a, yy);
    335 	
    336 	x = yy - b / a * xx;
    337 	y = xx;
    338 	
    339 	return g;
    340 }
    341 
    342 const int N = 200 * 1000 + 555;
    343 int t, n, a[N];
    344 
    345 inline bool read() {
    346 	if(!(cin >> t >> n))
    347 	    return false;
    348 	forn(i, n)
    349 		assert(scanf("%d", &a[i]) == 1);
    350 	return true;
    351 }
    352 
    353 int pf[N], s;
    354 
    355 inline li up(li a, li b) {
    356 	return (a + b - 1) / b;
    357 }
    358 
    359 inline int findPos(int a, int b, int c) {
    360 	li x, y;
    361 	int g = exgcd(a, x, b, y);
    362 	assert(c % g == 0);
    363 	
    364 	x *= +c / g;
    365 	y *= -c / g;
    366 	assert(a * 1ll * x - b * 1ll * y == c);
    367 	
    368 	int ag = a / g;
    369 	int bg = b / g;
    370 	
    371 	li k = 0;
    372 	if(x < 0)
    373 		k = up(-x, bg);
    374 	if(x >= bg)
    375 		k = -up(x - bg, bg);	
    376 	x += bg * k;
    377 	y += ag * k;
    378 		
    379 	assert(0 <= x && x < bg);
    380 	
    381 	k = 0;
    382 	if(y < 0)
    383 		k = up(-y, ag);
    384 	x += bg * k;
    385 	y += ag * k;
    386 
    387 	return x;
    388 }
    389 
    390 map< int, set<pt> > cycle;
    391 
    392 int ans[N];
    393 
    394 inline void solve() {
    395 	cycle.clear();
    396 	pf[0] = 0;
    397 	fore(i, 1, n)
    398 		pf[i] = (pf[i - 1] + a[i]) % t;
    399 	
    400 	s = (a[0] + pf[n - 1]) % t;
    401 	int g = gcd(s, t);
    402 	
    403 	forn(i, n) {
    404 		int st = pf[i] % g;
    405 		auto& cc = cycle[st];
    406 		
    407 		int pos = findPos(s, t, pf[i] - st);
    408 		
    409 		if(cc.empty()) {
    410 			ans[i] += t / g;
    411 			cc.insert(pt(pos, -i));
    412 		} else {
    413 			auto rg = cc.lower_bound(pt(pos, -i));
    414 			if(rg == cc.end()) {
    415 				ans[i] += t / g - pos;
    416 				rg = cc.begin();
    417 				ans[i] += rg->x;
    418 			} else
    419 				ans[i] += rg->x - pos;
    420 				
    421 			auto lf = cc.lower_bound(pt(pos, -i));
    422 			if(lf == cc.begin())
    423 				lf = --cc.end();
    424 			else
    425 				lf--;
    426 			ans[ -(lf->y) ] -= ans[i];
    427 			
    428 			cc.insert(pt(pos, -i));
    429 		} 
    430 	}
    431 	
    432 	forn(i, n)
    433 		printf("%d ", ans[i]);
    434 	puts("");
    435 }
    436 ```
    437 
    438 Tutorial is loading...
    439 
    440 **code**
    441 
    442 ```
    443 #include <bits/stdc++.h>
    444 
    445 using namespace std;
    446 
    447 using ll = long long;
    448 using ld = long double;
    449 using D = double;
    450 using uint = unsigned int;
    451 template<typename T>
    452 using pair2 = pair<T, T>;
    453 
    454 #ifdef WIN32
    455     #define LLD "%I64d"
    456 #else
    457     #define LLD "%lld"
    458 #endif
    459 
    460 #define pb push_back
    461 #define mp make_pair
    462 #define all(x) (x).begin(),(x).end()
    463 #define fi first
    464 #define se second
    465 
    466 const int maxn = 305;
    467 
    468 int pair3[maxn];
    469 int n;
    470 vector<vector<int>> answer;
    471 
    472 void add3(int a, int b, int c)
    473 {
    474     answer.pb({a, b, c});
    475 }
    476 
    477 void add4(int a, int b, int c, int d)
    478 {
    479     answer.pb({a, b, c, d});
    480 }
    481 
    482 int main()
    483 {
    484     cin >> n;
    485     if (n % 2 == 0)
    486     {
    487         pair3[0] = 3; // 0 1 3
    488         pair3[2] = 1; // 2 3 1
    489         add3(0, 1, 2);
    490         add3(2, 3, 0);
    491         for (int i = 4; i < n; i += 2)
    492         {
    493             add4(0, pair3[0], 1, i);
    494             add3(i, i + 1, 0);
    495             pair3[i] = 1;
    496             pair3[0] = i + 1;
    497             for (int j = 2; j < i; j += 2)
    498             {
    499                 add4(j, pair3[j], j + 1, i);
    500                 add4(j, i, j + 1, i + 1);
    501                 pair3[j] = i + 1;
    502             }
    503         }
    504         for (int i = 0; i < n; i += 2)
    505         {
    506             add3(i, i + 1, pair3[i]);
    507         }
    508     } else
    509     {
    510         pair3[1] = 0; // 1 2 0
    511         add3(0, 1, 2);
    512         for (int i = 3; i < n; i += 2)
    513         {
    514             add3(i, i + 1, 0);
    515             pair3[i] = 0;
    516             for (int j = 1; j < i; j += 2)
    517             {
    518                 add4(j, pair3[j], j + 1, i);
    519                 add4(j, i, j + 1, i + 1);
    520                 pair3[j] = i + 1;
    521             }
    522         }
    523         for (int i = 1; i < n; i += 2)
    524         {
    525             add3(i, i + 1, pair3[i]);
    526         }
    527     }
    528     printf("%d\n", (int)answer.size());
    529     for (auto &t : answer)
    530     {
    531         printf("%d", (int)t.size());
    532         for (auto t2 : t) printf(" %d", t2 + 1);
    533         printf("\n");
    534     }
    535     return 0;
    536 }
    537 ```