codeforces-scrape

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

1352.md (4936B)


      1 Source: https://codeforces.com/blog/entry/77161
      2 
      3 All problem ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). And he prepared all problems himself. I just helped with testing, reviewing and tutorial writing.
      4 
      5 [1352A - Sum of Round Numbers](/contest/1352/problem/A "Codeforces Round 640 (Div. 4)")
      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 	int t;
     20 	cin >> t;
     21 	while (t--) {
     22 		int n;
     23 		cin >> n;
     24 		vector<int> ans;
     25 		int power = 1;
     26 		while (n > 0) {
     27 			if (n % 10 > 0) {
     28 				ans.push_back((n % 10) * power);
     29 			}
     30 			n /= 10;
     31 			power *= 10;
     32 		}
     33 		cout << ans.size() << endl;
     34 		for (auto number : ans) cout << number << " ";
     35 		cout << endl;
     36 	}
     37 }
     38 ```
     39 
     40 [1352B - Same Parity Summands](/contest/1352/problem/B "Codeforces Round 640 (Div. 4)")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int main() {
     54 	int t;
     55 	cin >> t;
     56 	while (t--) {
     57 		int n, k;
     58 		cin >> n >> k;
     59 		int n1 = n - (k - 1);
     60 		if (n1 > 0 && n1 % 2 == 1) {
     61 			cout << "YES" << endl;
     62 			for (int i = 0; i < k - 1; ++i) cout << "1 ";
     63 			cout << n1 << endl;
     64 			continue;
     65 		}
     66 		int n2 = n - 2 * (k - 1);
     67 		if (n2 > 0 && n2 % 2 == 0) {
     68 			cout << "YES" << endl;
     69 			for (int i = 0; i < k - 1; ++i) cout << "2 ";
     70 			cout << n2 << endl;
     71 			continue;
     72 		}
     73 		cout << "NO" << endl;
     74 	}
     75 }
     76 ```
     77 
     78 [1352C - K-th Not Divisible by n](/contest/1352/problem/C "Codeforces Round 640 (Div. 4)")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution**
     85 
     86 ```
     87 #include <bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 int main() {
     92 	int t;
     93 	cin >> t;
     94 	while (t--) {
     95 		int n, k;
     96 		cin >> n >> k;
     97 		int need = (k - 1) / (n - 1);
     98 		cout << k + need << endl;
     99 	}
    100 }
    101 ```
    102 
    103 [1352D - Alice, Bob and Candies](/contest/1352/problem/D "Codeforces Round 640 (Div. 4)")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution in O(n)**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 
    116 int main() {
    117 	int t;
    118 	cin >> t;
    119 	while (t--) {
    120 		int n;
    121 		cin >> n;
    122 		vector<int> a(n);
    123 		for (auto &it : a) cin >> it;
    124 		int l = 0, r = n - 1;
    125 		int suml = 0, sumr = 0;
    126 		int cnt = 0, ansl = 0, ansr = 0;
    127 		while (l <= r) {
    128 			if (cnt % 2 == 0) {
    129 				int nsuml = 0;
    130 				while (l <= r && nsuml <= sumr) {
    131 					nsuml += a[l++];
    132 				}
    133 				ansl += nsuml;
    134 				suml = nsuml;
    135 			} else {
    136 				int nsumr = 0;
    137 				while (l <= r && nsumr <= suml) {
    138 					nsumr += a[r--];
    139 				}
    140 				ansr += nsumr;
    141 				sumr = nsumr;
    142 			}
    143 			++cnt;
    144 		}
    145 		cout << cnt << " " << ansl << " " << ansr << endl;
    146 	}
    147 }
    148 ```
    149 
    150 **Solution in O(n^2)**
    151 
    152 ```
    153 // Author: Ivan Kazmenko ([email protected])
    154 import std.algorithm;
    155 import std.conv;
    156 import std.range;
    157 import std.stdio;
    158 import std.string;
    159 
    160 void main ()
    161 {
    162 	auto tests = readln.strip.to !(int);
    163 	foreach (test; 0..tests)
    164 	{
    165 		auto n = readln.strip.to !(int);
    166 		auto a = readln.splitter.map !(to !(int)).array;
    167 		int [2] total;
    168 		int prev = 0;
    169 		int moves = 0;
    170 		while (!a.empty)
    171 		{
    172 			moves += 1;
    173 			int cur = 0;
    174 			while (!a.empty && cur <= prev)
    175 			{
    176 				cur += a[0];
    177 				a = a[1..$];
    178 			}
    179 			total[moves % 2] += cur;
    180 			prev = cur;
    181 			reverse (a);
    182 		}
    183 		writeln (moves, " ", total[1], " ", total[0]);
    184 	}
    185 }
    186 ```
    187 
    188 [1352E - Special Elements](/contest/1352/problem/E "Codeforces Round 640 (Div. 4)")
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution**
    195 
    196 ```
    197 #include <bits/stdc++.h>
    198 
    199 using namespace std;
    200 
    201 int main() {
    202 	int t;
    203 	cin >> t;
    204 	while (t--) {
    205 		int n;
    206 		cin >> n;
    207 		vector<int> a(n);
    208 		vector<int> cnt(n + 1);
    209 		int ans = 0;
    210 		for (auto &it : a) {
    211 			cin >> it;
    212 			++cnt[it];
    213 		}
    214 		for (int l = 0; l < n; ++l) {
    215 			int sum = 0;
    216 			for (int r = l; r < n; ++r) {
    217 				sum += a[r];
    218 				if (l == r) continue;
    219 				if (sum <= n) {
    220 					ans += cnt[sum];
    221 					cnt[sum] = 0;
    222 				}
    223 			}
    224 		}
    225 		cout << ans << endl;
    226 	}
    227 }
    228 ```
    229 
    230 [1352F - Binary String Reconstruction](/contest/1352/problem/F "Codeforces Round 640 (Div. 4)")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution**
    237 
    238 ```
    239 #include <bits/stdc++.h>
    240 
    241 using namespace std;
    242 
    243 int main() {
    244 	int t;
    245 	cin >> t;
    246 	while (t--) {
    247 		int n0, n1, n2;
    248 		cin >> n0 >> n1 >> n2;
    249 		if (n1 == 0) {
    250 			if (n0 != 0) {
    251 				cout << string(n0 + 1, '0') << endl;
    252 			} else {
    253 				cout << string(n2 + 1, '1') << endl;
    254 			}
    255 			continue;
    256 		}
    257 		string ans;
    258 		for (int i = 0; i < n1 + 1; ++i) {
    259 			if (i & 1) ans += "0";
    260 			else ans += "1";
    261 		}
    262 		ans.insert(1, string(n0, '0'));
    263 		ans.insert(0, string(n2, '1'));
    264 		cout << ans << endl;
    265 	}
    266 }
    267 ```
    268 
    269 [1352G - Special Permutation](/contest/1352/problem/G "Codeforces Round 640 (Div. 4)")
    270 
    271 **Tutorial**
    272 
    273 Tutorial is loading...
    274 
    275 **Solution**
    276 
    277 ```
    278 #include <bits/stdc++.h>
    279 
    280 using namespace std;
    281 
    282 int main() {
    283 	int t;
    284 	cin >> t;
    285 	while (t--) {
    286 		int n;
    287 		cin >> n;
    288 		if (n < 4) {
    289 			cout << -1 << endl;
    290 			continue;
    291 		}
    292 		for (int i = n; i >= 1; --i) {
    293 			if (i & 1) cout << i << " ";
    294 		}
    295 		cout << 4 << " " << 2 << " ";
    296 		for (int i = 6; i <= n; i += 2) {
    297 			cout << i << " ";
    298 		}
    299 		cout << endl;
    300 	}
    301 }
    302 ```