codeforces-scrape

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

1560.md (6416B)


      1 Source: https://codeforces.com/blog/entry/94009
      2 
      3 Ideas: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      4 
      5 [1560A - Dislike of Threes](/contest/1560/problem/A "Codeforces Round 739 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main()
     19 {
     20 	int t;
     21 	cin >> t;
     22 
     23 	while (t--)
     24 	{
     25 		int k;
     26 		cin >> k;
     27 
     28 		for (int i = 1; ; i++)
     29 		{
     30 			if (i % 3 == 0 || i % 10 == 3)
     31 				continue;
     32 			if (--k == 0)
     33 			{
     34 				cout << i << '\n';
     35 				break;
     36 			}
     37 		}
     38 	}
     39 }
     40 ```
     41 
     42 [1560B - Who's Opposite?](/contest/1560/problem/B "Codeforces Round 739 (Div. 3)")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 typedef long long ll;
     56 
     57 int main()
     58 {
     59 	int t;
     60 	cin >> t;
     61 
     62 	while (t--)
     63 	{
     64 		ll a, b, c;
     65 		cin >> a >> b >> c;
     66 
     67 		ll n = 2 * abs(a - b);
     68 		if (a > n || b > n || c > n)
     69 			cout << -1 << '\n';
     70 		else
     71 		{
     72 			ll d = n / 2 + c;
     73 			while (d > n) d -= n;
     74 			cout << d << '\n';
     75 		}
     76 	}
     77 	return 0;
     78 }
     79 ```
     80 
     81 [1560C - Infinity Table](/contest/1560/problem/C "Codeforces Round 739 (Div. 3)")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 int main()
     95 {
     96 	int t;
     97 	cin >> t;
     98 
     99 	while (t--)
    100 	{
    101 		int k;
    102 		cin >> k;
    103 
    104 		int a = 1;
    105 		int x = 1;
    106 		int i = 1;
    107 
    108 		while (k >= x + a)
    109 		{
    110 			x += a;
    111 			a += 2;
    112 			i += 1;
    113 		}
    114 
    115 		int m = k - x + 1;
    116 		if (m <= i)
    117 			cout << m << ' ' << i << '\n';
    118 		else
    119 			cout << i << ' ' << (i - (m - i)) << '\n';
    120 	}
    121 }
    122 ```
    123 
    124 [1560D - Make a Power of Two](/contest/1560/problem/D "Codeforces Round 739 (Div. 3)")
    125 
    126 **Tutorial**
    127 
    128 Tutorial is loading...
    129 
    130 **Solution**
    131 
    132 ```
    133 #include <bits/stdc++.h>
    134 
    135 using namespace std;
    136 
    137 typedef long long ll;
    138 
    139 const ll P2LIM = (ll)2e18;
    140 
    141 int solve(string s, string t)
    142 {
    143 	int tp = 0;
    144 	int sp = 0;
    145 	int taken = 0;
    146 
    147 	while (sp < s.length() && tp < t.length())
    148 	{
    149 		if(s[sp] == t[tp])
    150 		{
    151 			taken++;
    152 			tp++;
    153 		}
    154 		sp++;
    155 	}
    156 
    157 	return (int)s.length() - taken + (int)t.length() - taken;
    158 }
    159 
    160 vector<string> ts;
    161 
    162 int main()
    163 {
    164 	for (ll p2 = 1; p2 <= P2LIM; p2 *= 2)
    165 		ts.push_back(to_string(p2));
    166 
    167 	int t;
    168 	cin >> t;
    169 
    170 	while (t--)
    171 	{
    172 		string n;
    173 		cin >> n;
    174 
    175 		int ans = n.length() + 1;
    176 		for (auto p2 : ts)
    177 			ans = min(ans, solve(n, p2));
    178 		cout << ans << '\n';
    179 	}
    180 
    181 	return 0;
    182 }
    183 ```
    184 
    185 [1560E - Polycarp and String Transformation](/contest/1560/problem/E "Codeforces Round 739 (Div. 3)")
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Solution**
    192 
    193 ```
    194 #include <bits/stdc++.h>
    195 
    196 using namespace std;
    197 
    198 int cntsrc[26]; // don't forget to memset it but not cnt
    199 int* cnt = cntsrc - 'a'; // so cnt['a'] = cntsrc[0] and so on
    200 
    201 pair<string, string> decrypt(string s)
    202 {
    203 	string order;
    204 	reverse(s.begin(), s.end());
    205 	for (auto c : s)
    206 	{
    207 		if (!cnt[c])
    208 			order.push_back(c);
    209 		cnt[c]++;
    210 	}
    211 
    212 	int m = order.length();
    213 	int originalLength = 0;
    214 	for (int i = 0; i < m; i++)
    215 		originalLength += cnt[order[i]] / (m - i);
    216 
    217 	reverse(order.begin(), order.end());
    218 	return { string(s.rbegin(), s.rbegin() + originalLength), order };
    219 }
    220 
    221 string encrypt(pair<string, string> p)
    222 {
    223 	string result = p.first;
    224 
    225 	for (auto c : p.second)
    226 	{
    227 		string temp;
    228 		for (auto d : p.first)
    229 			if (d != c)
    230 			{
    231 				temp.push_back(d);
    232 				result.push_back(d);
    233 			}
    234 		p.first = temp;
    235 	}
    236 
    237 	return result;
    238 }
    239 
    240 int main()
    241 {
    242 	int t;
    243 	cin >> t;
    244 
    245 	while (t--)
    246 	{
    247 		memset(cntsrc, 0, sizeof(cntsrc));
    248 		string s;
    249 		cin >> s;
    250 
    251 		auto ans = decrypt(s);
    252 		auto check = encrypt(ans);
    253 
    254 		if (check == s)
    255 			cout << ans.first << ' ' << ans.second << '\n';
    256 		else
    257 			cout << "-1\n";
    258 	}
    259 
    260 	return 0;
    261 }
    262 ```
    263 
    264 [1560F1 - Nearest Beautiful Number (easy version)](/contest/1560/problem/F1 "Codeforces Round 739 (Div. 3)")
    265 
    266 **Tutorial**
    267 
    268 Tutorial is loading...
    269 
    270 **Solution**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 
    275 using namespace std;
    276 
    277 string solve1(string n)
    278 {
    279 	string res(n.length(), '9');
    280 	for (char c = '8'; c >= '0'; c--)
    281 	{
    282 		string t(n.length(), c);
    283 		if (t >= n)
    284 			res = t;
    285 	}
    286 
    287 	return res;
    288 }
    289 
    290 string solve2(string n)
    291 {
    292 	string res = solve1(n);
    293 
    294 	for(char a = '0'; a <= '9'; a++)
    295 		for (char b = a + 1; b <= '9'; b++)
    296 		{
    297 			bool n_ok = true;
    298 			for (int i = 0; i < n.length(); i++)
    299 			{
    300 				if (n[i] < b)
    301 				{
    302 					string t = n;
    303 					if (t[i] < a) t[i] = a;
    304 					else t[i] = b;
    305 					for (int j = i + 1; j < n.length(); j++)
    306 						t[j] = a;
    307 					if (res > t)
    308 						res = t;
    309 				}
    310 
    311 				if(n[i] != a && n[i] != b)
    312 				{
    313 					n_ok = false;
    314 					break;
    315 				}
    316 			}
    317 
    318 			if (n_ok) return n;
    319 		}
    320 
    321 	return res;
    322 }
    323 
    324 string solve()
    325 {
    326 	string n;
    327 	int k;
    328 	cin >> n >> k;
    329 
    330 	if (k == 1) return solve1(n);
    331 	else return solve2(n);
    332 }
    333 
    334 int main()
    335 {
    336 	int t;
    337 	cin >> t;
    338 
    339 	while (t--)
    340 		cout << solve() << '\n';
    341 
    342 	return 0;
    343 }
    344 ```
    345 
    346 [1560F2 - Nearest Beautiful Number (hard version)](/contest/1560/problem/F2 "Codeforces Round 739 (Div. 3)")
    347 
    348 **Tutorial**
    349 
    350 Tutorial is loading...
    351 
    352 **Short solution**
    353 
    354 ```
    355 #include <bits/stdc++.h>
    356 
    357 using namespace std;
    358 
    359 string solve()
    360 {
    361 	string n;
    362 	int k;
    363 	cin >> n >> k;
    364 
    365 	while (true)
    366 	{
    367 		set<char> s;
    368 		for (auto c : n) s.insert(c);
    369 		if (s.size() <= k) return n;
    370 
    371 		s.clear();
    372 		int ptr = 0;
    373 		for (; ; ptr++)
    374 		{
    375 			s.insert(n[ptr]);
    376 			if (s.size() > k)
    377 			{
    378 				while (n[ptr] == '9')
    379 					ptr--;
    380 				n[ptr]++;
    381 				for (int i = ptr + 1; i < n.size(); i++)
    382 					n[i] = '0';
    383 				break;
    384 			}
    385 		}
    386 	}
    387 }
    388 
    389 int main()
    390 {
    391 	int t;
    392 	cin >> t;
    393 
    394 	while (t--)
    395 		cout << solve() << '\n';
    396 	
    397 	return 0;
    398 }
    399 ```
    400 
    401 **Long solution**
    402 
    403 ```
    404 #include <bits/stdc++.h>
    405 
    406 using namespace std;
    407 
    408 string solveFillingSuffix(string& n, char d, int from)
    409 {
    410 	for (int i = from; i < n.length(); i++)
    411 		n[i] = d;
    412 	return n;
    413 }
    414 
    415 void decAt(map<char, int>& d, char c)
    416 {
    417 	if (d.count(c))
    418 	{
    419 		d[c]--;
    420 		if (d[c] == 0) d.erase(c);
    421 	}
    422 }
    423 
    424 string solve()
    425 {
    426 	string n;
    427 	int k;
    428 	cin >> n >> k;
    429 
    430 	map<char, int> d;
    431 	int pref = 0;
    432 
    433 	while (pref < n.length())
    434 	{
    435 		if (d.count(n[pref]))
    436 		{
    437 			d[n[pref++]]++;
    438 			continue;
    439 		}
    440 		if (d.size() == k) break;
    441 		d[n[pref++]]++;
    442 	}
    443 
    444 	if (pref == n.length())
    445 		return n;
    446 
    447 	while (true)
    448 	{
    449 		if (n[pref] == '9')
    450 		{
    451 			decAt(d, n[--pref]);
    452 			continue;
    453 		}
    454 
    455 		if (d.size() < k)
    456 		{
    457 			d[++n[pref]]++;
    458 			return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1);
    459 		}
    460 
    461 		auto it = d.upper_bound(n[pref]);
    462 		if (it == d.end())
    463 		{
    464 			decAt(d, n[--pref]);
    465 			continue;
    466 		}
    467 
    468 		n[pref] = it->first;
    469 		return solveFillingSuffix(n, d.begin()->first, pref + 1);
    470 	}
    471 }
    472 
    473 int main()
    474 {
    475 	int t;
    476 	cin >> t;
    477 
    478 	while (t--)
    479 		cout << solve() << '\n';
    480 	
    481 	return 0;
    482 }
    483 ```