codeforces-scrape

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

1194.md (10320B)


      1 Source: https://codeforces.com/blog/entry/68405
      2 
      3 [1194A - Remove a Progression](/contest/1194/problem/A "Educational Codeforces Round 68 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main(args: Array<String>) {
     15     val T = readLine()!!.toInt()
     16     for (t in 1..T) {
     17         val (n, x) = readLine()!!.split(' ').map { it.toLong() }
     18         println(x * 2)
     19     }
     20 }
     21 ```
     22 
     23 [1194B - Yet Another Crosses Problem](/contest/1194/problem/B "Educational Codeforces Round 68 (Rated for Div. 2)")
     24 
     25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (PikMike)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 
     36 #define forn(i, n) for (int i = 0; i < int(n); i++)
     37 
     38 using namespace std;
     39 
     40 int main() {
     41 	int q;
     42 	cin >> q;
     43 	forn(_, q){
     44 		int n, m;
     45 		cin >> n >> m;
     46 		vector<string> s(n);
     47 		forn(i, n)
     48 			cin >> s[i];
     49 		vector<int> cntn(n), cntm(m);
     50 		forn(i, n) forn(j, m){
     51 			cntn[i] += (s[i][j] == '.');
     52 			cntm[j] += (s[i][j] == '.');
     53 		}
     54 		int ans = n + m;
     55 		forn(i, n) forn(j, m){
     56 			ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
     57 		}
     58 		cout << ans << "\n";
     59 	}
     60 	return 0;
     61 }
     62 ```
     63 
     64 [1194C - From S To T](/contest/1194/problem/C "Educational Codeforces Round 68 (Rated for Div. 2)")
     65 
     66 Idea: [Roms](/profile/Roms "Master Roms")
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution (Roms)**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 
     77 using namespace std;
     78 
     79 int q;
     80 string s, t, p;
     81 int cnt[30];
     82 
     83 int main() {
     84 	cin >> q;
     85 	for(int iq = 0; iq < q; ++iq){
     86 		cin >> s >> t >> p;
     87 		memset(cnt, 0, sizeof cnt);
     88 		for(auto x : p)
     89 			++cnt[x - 'a'];
     90 
     91 		bool ok = true;
     92 		int is = 0, it = 0;
     93 		while(is < s.size()){
     94 			if(it == t.size()){
     95 				ok = false;
     96 				break;
     97 			}
     98 			
     99 			if(s[is] == t[it]){
    100 				++is, ++it;
    101 				continue;
    102 			}
    103 			
    104 			--cnt[t[it] - 'a'];
    105 			++it;
    106 		}
    107         while(it < t.size()){
    108             --cnt[t[it] - 'a'];
    109 			++it;
    110         }
    111         
    112 		if(*min_element(cnt, cnt + 30) < 0)
    113 			ok = false;
    114 
    115 		if(ok) cout << "YES\n";
    116 		else cout << "NO\n";
    117 	}		
    118 	return 0;
    119 }                             	
    120 
    121 }                             	
    122 ```
    123 
    124 [1194D - 1-2-K Game](/contest/1194/problem/D "Educational Codeforces Round 68 (Rated for Div. 2)")
    125 
    126 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    127 
    128 **Tutorial**
    129 
    130 Tutorial is loading...
    131 
    132 **Solution (adedalic)**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136 using namespace std;
    137 
    138 int n, k;
    139 
    140 inline bool read() {
    141 	if(!(cin >> n >> k))
    142 		return false;
    143 	return true;
    144 }
    145 
    146 void solve() {
    147 	bool win = true;
    148 	if(k % 3 == 0) {
    149 		int np = n % (k + 1);
    150 		if(np % 3 == 0 && np != k)
    151 			win = false;
    152 	} else {
    153 		int np = n % 3;
    154 		if(np == 0)
    155 			win = false;
    156 	}
    157 	
    158 	puts(win ? "Alice" : "Bob");
    159 }
    160 
    161 int main(){
    162 	int T; cin >> T;
    163 	while(T--) {
    164 		read();
    165 		solve();
    166 	}
    167 	return 0;
    168 }
    169 ```
    170 
    171 [1194E - Count The Rectangles](/contest/1194/problem/E "Educational Codeforces Round 68 (Rated for Div. 2)")
    172 
    173 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    174 
    175 **Tutorial**
    176 
    177 Tutorial is loading...
    178 
    179 **Solution (Roms)**
    180 
    181 ```
    182 #include <bits/stdc++.h>
    183 
    184 using namespace std;
    185 
    186 #define mp make_pair
    187 
    188 const int N = 10009;
    189 const int INF = 1000000009;
    190  
    191 int n;
    192 vector <pair<int, int> > vs[N], hs[N];
    193 int f[N];
    194 vector <int> d[N];
    195 
    196 void upd(int pos, int x){
    197 	for(; pos < N; pos |= pos + 1)
    198 		f[pos] += x;
    199 }
    200 
    201 int get(int pos){
    202 	int res = 0;
    203 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    204 		res += f[pos];
    205 	return res;
    206 }
    207 
    208 int get(int l, int r){
    209 	return get(r) - get(l - 1);
    210 }
    211 
    212 const int D = 5000;
    213 
    214 int main() {
    215 	cin >> n;
    216 	for(int i = 0; i < n; ++i){
    217 		int x1, y1, x2, y2;
    218 		cin >> x1 >> y1 >> x2 >> y2;
    219 		x1 += D, y1 += D, x2 += D, y2 += D; 
    220 		if(y1 == y2) 
    221 			hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) );	
    222 		else 
    223 			vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) );	
    224 	}
    225 
    226 	long long res = 0;
    227 	for(int y = 0; y < N; ++y) for(auto s : hs[y]){
    228 		for(int i = 0; i < N; ++i) d[i].clear();
    229 		memset(f, 0, sizeof f);
    230 
    231 		int l = s.first, r = s.second;
    232 		for(int x = l; x <= r; ++x) for(auto s2 : vs[x])
    233 			if(s2.first <= y && s2.second > y) {
    234 				d[s2.second].push_back(x);
    235 				upd(x, 1);
    236 			}
    237 
    238 		for(int y2 = y + 1; y2 < N; ++y2){
    239 			for(auto s2 : hs[y2]){			
    240 				int cur = get(s2.first, s2.second);
    241 				res += cur * (cur - 1) / 2;
    242 			}
    243 			for(auto x : d[y2]) upd(x, -1);
    244 		}
    245 	}
    246 
    247 	cout << res << endl;
    248 	return 0;
    249 }                             	
    250 ```
    251 
    252 [1194F - Crossword Expert](/contest/1194/problem/F "Educational Codeforces Round 68 (Rated for Div. 2)")
    253 
    254 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    255 
    256 **Tutorial**
    257 
    258 Tutorial is loading...
    259 
    260 **Solution (adedalic)**
    261 
    262 ```
    263 #include<bits/stdc++.h>
    264 
    265 using namespace std;
    266 
    267 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    268 #define sz(a) int((a).size())
    269 
    270 #define x first
    271 #define y second
    272 
    273 typedef long long li;
    274 typedef pair<int, int> pt;
    275 
    276 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    277     return out << "(" << p.x << ", " << p.y << ")";
    278 }
    279 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    280     fore(i, 0, sz(v)) {
    281         if(i) out << " ";
    282         out << v[i];
    283     }
    284     return out;
    285 }
    286 
    287 const int MOD = int(1e9) + 7;
    288 
    289 inline int norm(int a) {
    290     if(a >= MOD) a -= MOD;
    291     if(a < 0) a += MOD;
    292     return a;
    293 }
    294 inline int mul(int a, int b) {
    295     return int(a * 1ll * b % MOD);
    296 }
    297 inline int binPow(int a, int k) {
    298     int ans = 1;
    299     while(k > 0) {
    300         if(k & 1) ans = mul(ans, a);
    301         a = mul(a, a);
    302         k >>= 1;
    303     }
    304     return ans;
    305 }
    306 inline int inv(int a) {
    307     return binPow(a, MOD - 2);
    308 }
    309 
    310 int n;
    311 li T;
    312 vector<li> t;
    313 
    314 inline bool read() {
    315     if(!(cin >> n >> T))
    316         return false;
    317     t.resize(n);
    318     fore(i, 0, n)
    319         cin >> t[i];
    320     return true;
    321 }
    322 
    323 vector<int> f, inf;
    324 
    325 int C(int n, li k) {
    326     if(k > n || k < 0)
    327         return 0;
    328     return mul(f[n], mul(inf[k], inf[n - k]));
    329 }
    330 
    331 inline void solve() {
    332     f.resize(n + 5);
    333     inf.resize(n + 5);
    334     f[0] = inf[0] = 1;
    335     fore(i, 1, sz(f)) {
    336         f[i] = mul(i, f[i - 1]);
    337         inf[i] = mul(inf[i - 1], inv(i));
    338     }
    339 
    340     int sumC = 1;
    341     li bd = T;
    342     int pw2 = 1, i2 = (MOD + 1) / 2;
    343 
    344     vector<int> p(n + 1, 0);
    345     fore(i, 0, n) {
    346         pw2 = mul(pw2, i2);
    347 
    348         sumC = norm(mul(2, sumC) - C(i, bd));
    349         li need = t[i];
    350         if(bd > i + 1) {
    351             li sub = min(bd - i - 1, need);
    352             bd -= sub, need -= sub;
    353         }
    354         li rem = min(bd + 1, need);
    355         fore(k, 0, rem)
    356             sumC = norm(sumC - C(i + 1, bd - k));
    357         bd -= rem;
    358 
    359         p[i] = mul(sumC, pw2);
    360     }
    361 
    362     int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD);
    363     cout << ans << endl;
    364 //    cerr << mul(ans, binPow(2, n)) << endl;
    365 }
    366 
    367 int main() {
    368 #ifdef _DEBUG
    369     freopen("input.txt", "r", stdin);
    370     int tt = clock();
    371 #endif
    372     cout << fixed << setprecision(15);
    373 
    374     if(read()) {
    375         solve();
    376 
    377 #ifdef _DEBUG
    378         cerr << "TIME = " << clock() - tt << endl;
    379         tt = clock();
    380 #endif
    381     }
    382     return 0;
    383 }
    384 ```
    385 
    386 [1194G - Another Meme Problem](/contest/1194/problem/G "Educational Codeforces Round 68 (Rated for Div. 2)")
    387 
    388 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    389 
    390 **Tutorial**
    391 
    392 Tutorial is loading...
    393 
    394 **Solution (BledDest)**
    395 
    396 ```
    397 #include<bits/stdc++.h>
    398 
    399 using namespace std;
    400 
    401 const int N = 105;
    402 
    403 int a[N];
    404 int n;
    405 int numPos[10], denPos[10];
    406 int num, den;
    407 const int MOD = 998244353;
    408 
    409 struct halfState
    410 {
    411 	int carry;
    412 	int mask;
    413 	bool comp;
    414 	
    415 	halfState() {};
    416 	halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {};
    417 };
    418 
    419 bool operator <(const halfState& x, const halfState& y)
    420 {
    421 	if(x.carry != y.carry) return x.carry < y.carry;
    422 	if(x.mask != y.mask) return x.mask < y.mask;
    423 	return x.comp < y.comp;
    424 }
    425 
    426 bool operator ==(const halfState& x, const halfState& y)
    427 {
    428 	return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp;
    429 }
    430 
    431 bool operator !=(const halfState& x, const halfState& y)
    432 {
    433 	return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp;
    434 }
    435 
    436 halfState go(const halfState& s, int pos, int digit, bool isNum)
    437 {
    438 	int newDigit = digit * (isNum ? num : den) + s.carry;
    439 	int newCarry = newDigit / 10;
    440 	newDigit %= 10;
    441 	int newMask = s.mask;
    442 	int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]);
    443 	if(maskPos != -1) newMask |= (1 << maskPos);
    444 	bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp);
    445 	return halfState(newCarry, newMask, newComp);
    446 }
    447 
    448 struct state
    449 {
    450 	halfState numState;
    451 	halfState denState;
    452 	
    453 	state() {};
    454 	state(halfState numState, halfState denState) : numState(numState), denState(denState) {};
    455 	
    456 	void norm()
    457 	{
    458 		if(numState.mask & denState.mask)
    459 			numState.mask = denState.mask = 1;
    460 	};
    461 	
    462 	bool valid()
    463 	{
    464 		return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0);
    465 	};
    466 };
    467 
    468 bool operator <(const state& x, const state& y)
    469 {
    470 	if(x.numState != y.numState) return x.numState < y.numState;
    471 	return x.denState < y.denState;
    472 }
    473 
    474 state go(const state& s, int pos, int digit)
    475 {
    476 	halfState newNum = go(s.numState, pos, digit, true);
    477 	halfState denNum = go(s.denState, pos, digit, false);
    478 	state res(newNum, denNum);
    479 	res.norm();
    480 	return res;
    481 }
    482 
    483 int add(int x, int y)
    484 {
    485 	return (x + y) % MOD;
    486 }
    487 
    488 int ans = 0;
    489 
    490 void calcFixed(int x, int y)
    491 {
    492 	num = x;
    493 	den = y;
    494 	for(int i = 0; i <= 9; i++)
    495 		numPos[i] = denPos[i] = -1;
    496 	int cnt = 0;
    497 	for(int i = 1; i <= 9; i++)
    498 		for(int j = 1; j <= 9; j++)
    499 			if(i * y == j * x)
    500 			{
    501 				numPos[i] = denPos[j] = cnt++;
    502 			}
    503 	vector<map<state, int> > dp(102);
    504 	dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1;
    505 	for(int i = 0; i <= 100; i++)
    506 		for(auto x : dp[i])
    507 		{
    508 			state curState = x.first;
    509 			int curCount = x.second;
    510 			for(int j = 0; j <= 9; j++)
    511 			{
    512 				state newState = go(curState, i, j);
    513 				dp[i + 1][newState] = add(dp[i + 1][newState], curCount);
    514 			}
    515 		}
    516 	for(auto x : dp[101])
    517 	{
    518 		state curState = x.first;
    519 		int curCount = x.second;
    520 		if(curState.valid())
    521 			ans = add(ans, curCount);
    522 	}
    523 }
    524 
    525 int main()
    526 {
    527 	string s;
    528 	cin >> s;
    529 	int len = s.size();
    530 	reverse(s.begin(), s.end());
    531 	for(int i = 0; i < len; i++)
    532 	{
    533 		a[i] = s[i] - '0';
    534  	}
    535  	for(int i = 1; i <= 9; i++)
    536  		for(int j = 1; j <= 9; j++)
    537  			if(__gcd(i, j) == 1)
    538  				calcFixed(i, j);
    539  	cout << ans << endl;
    540 }
    541 ```