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 ```