1933.md (8238B)
1 Source: https://codeforces.com/blog/entry/126560 2 3 [1933A - Turtle Puzzle: Rearrange and Negate](/contest/1933/problem/A "Codeforces Round 929 (Div. 3)") 4 5 Idea: [snowysecret](/profile/snowysecret "Master snowysecret"), prepared: [snowysecret](/profile/snowysecret "Master snowysecret") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 int t; 19 cin >> t; 20 while (t--) { 21 int n; 22 cin >> n; 23 vector<int> arr(n); 24 for (int i = 0; i < n; i++) { 25 cin >> arr[i]; 26 } 27 int sum = 0; 28 for (int i = 0; i < n; i++) { 29 sum += abs(arr[i]); 30 } 31 cout << sum << endl; 32 } 33 return 0; 34 } 35 ``` 36 37 [1933B - Turtle Math: Fast Three Task](/contest/1933/problem/B "Codeforces Round 929 (Div. 3)") 38 39 Idea: [snowysecret](/profile/snowysecret "Master snowysecret"), prepared: [snowysecret](/profile/snowysecret "Master snowysecret"), [erniepsycholone](/profile/erniepsycholone "Expert erniepsycholone") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include<bits/stdc++.h> 49 using namespace std; 50 51 int main(){ 52 int t; 53 cin>>t; 54 while(t--){ 55 int k; 56 cin>>k; 57 int ACC=0; 58 bool hv=false; 59 for(int i=0;i<k;i++){ 60 int x; 61 cin>>x; 62 ACC+=x; 63 if(x%3==1){ 64 hv=true; 65 } 66 } 67 if(ACC%3==0){ 68 cout<<0<<endl; 69 }else if(ACC%3==2){ 70 cout<<1<<endl; 71 }else{ 72 if(hv==true){ 73 cout<<1<<endl; 74 }else{ 75 cout<<2<<endl; 76 } 77 } 78 } 79 } 80 ``` 81 82 [1933C - Turtle Fingers: Count the Values of k](/contest/1933/problem/C "Codeforces Round 929 (Div. 3)") 83 84 Idea: [dbsbs](/profile/dbsbs "Pupil dbsbs"), prepared: [dbsbs](/profile/dbsbs "Pupil dbsbs"), [snowysecret](/profile/snowysecret "Master snowysecret") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <bits/stdc++.h> 94 #define int long long 95 using namespace std; 96 97 void solve(int tc){ 98 int a, b, l; 99 cin >> a >> b >> l; 100 set<int> ans; 101 for(int i = 0; i <= 34; ++i){ 102 int x = l; 103 bool fail = false; 104 for(int _ = 0; _ < i; ++_){ 105 if(x % a){ 106 fail = true; 107 break; 108 } 109 x /= a; 110 } 111 if(fail) break; 112 while(true){ 113 ans.insert(x); 114 if(x % b) break; 115 x /= b; 116 } 117 } 118 cout << ans.size(); 119 } 120 121 bool multi = true; 122 123 signed main() { 124 int t = 1; 125 if (multi)cin >> t; 126 for (int i = 1; i <= t; ++i) { 127 solve(i); 128 cout << "\n"; 129 } 130 return 0; 131 } 132 ``` 133 134 [1933D - Turtle Tenacity: Continual Mods](/contest/1933/problem/D "Codeforces Round 929 (Div. 3)") 135 136 Idea: [snowysecret](/profile/snowysecret "Master snowysecret"), [erniepsycholone](/profile/erniepsycholone "Expert erniepsycholone"), prepared: [snowysecret](/profile/snowysecret "Master snowysecret") 137 138 **Tutorial** 139 140 Tutorial is loading... 141 142 **Solution** 143 144 ``` 145 #include <bits/stdc++.h> 146 using namespace std; 147 148 int main() { 149 int t; 150 cin >> t; 151 while(t--) { 152 int n; 153 cin >> n; 154 int a[n]; 155 for(int i=0; i<n; i++) cin >> a[i]; 156 sort(a, a + n); 157 if(a[0] != a[1]) { 158 cout << "YES\n"; 159 } 160 else { 161 bool PASS = 0; 162 for(int i=1; i<n; i++) { 163 if(a[i] % a[0] != 0) PASS = 1; 164 } 165 if(PASS) cout << "YES\n"; 166 else cout << "NO\n"; 167 } 168 } 169 } 170 ``` 171 172 [1933E - Turtle vs. Rabbit Race: Optimal Trainings](/contest/1933/problem/E "Codeforces Round 929 (Div. 3)") 173 174 Idea: [snowysecret](/profile/snowysecret "Master snowysecret"), prepared: [snowysecret](/profile/snowysecret "Master snowysecret") 175 176 **Tutorial** 177 178 Tutorial is loading... 179 180 **Solution** 181 182 ``` 183 #include "bits/stdc++.h" 184 using namespace std; 185 #define int long long 186 #define double long double 187 188 void solve(int tc) { 189 int n; 190 cin >> n; 191 int a[n + 1]; 192 for(int i = 1; i <= n; i++) cin >> a[i]; 193 int ps[n + 1]; 194 ps[0] = 0; 195 for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i]; 196 int q; 197 cin >> q; 198 while(q--) { 199 int l, u; 200 cin >> l >> u; 201 int lb = l, rb = n; 202 while(lb < rb) { 203 int mid = (lb + rb + 1) >> 1; 204 if(ps[mid] - ps[l - 1] <= u) lb = mid; 205 else rb = mid - 1; 206 } 207 int maxu = -1e18, optid; 208 for(int i = max(l, lb - 2); i <= min(n, lb + 2); i++) { 209 int t = ps[i] - ps[l - 1]; 210 int ut = (u + (u - t + 1)) * t / 2; 211 if(ut > maxu) { 212 maxu = ut; 213 optid = i; 214 } 215 } 216 cout << optid << " "; 217 } 218 } 219 220 signed main() { 221 int t = 1; cin >> t; 222 for(int i = 1; i <= t; i++){ 223 solve(i); 224 cout << "\n"; 225 } 226 } 227 ``` 228 229 [1933F - Turtle Mission: Robot and the Earthquake](/contest/1933/problem/F "Codeforces Round 929 (Div. 3)") 230 231 Idea: [erniepsycholone](/profile/erniepsycholone "Expert erniepsycholone"), prepared: [erniepsycholone](/profile/erniepsycholone "Expert erniepsycholone") 232 233 **Hint** 234 235 View the task in a relative perspective, with robot RT and the ending location moving downwards instead of rocks moving upwards. 236 237 **Tutorial** 238 239 Tutorial is loading... 240 241 **Solution** 242 243 ``` 244 #include<bits/stdc++.h> 245 #define int long long 246 using namespace std; 247 248 signed main(){ 249 int t; 250 cin >> t; 251 while (t--){ 252 int n, m; 253 cin >> n >> m; 254 bool a[n][m + 1]; 255 for (int i = 0; i < n; i++) { 256 for (int j = 1; j <= m; j++) { 257 cin >> a[i][j]; 258 } 259 } 260 int dp[n][m + 1]; 261 for (int i = 0; i < n; i++) { 262 for (int j = 0; j <= m; j++) { 263 dp[i][j] = INT_MAX; 264 } 265 } 266 dp[0][1] = 0; 267 for (int i = 1; i <= m; i++) { 268 for (int j = 0; j < n; j++) { 269 if (a[j][i]){ 270 continue; 271 } 272 dp[j][i] = min(dp[j][i], dp[(j - 1 + n) % n][i - 1] + 1); 273 } 274 for (int j = 0; j < 3 * n; j++) { 275 if (a[j % n][i] || a[(j - 1 + n) % n][i]){ 276 continue; 277 } 278 dp[j % n][i] = min(dp[j % n][i], dp[(j - 2 + n) % n][i] + 1); 279 } 280 } 281 int ans = INT_MAX; 282 for (int i = 0; i < n; i++) { 283 if (dp[i][m] == INT_MAX){ 284 continue; 285 } 286 int npos = ((n - 1) + dp[i][m]) % n; 287 if (npos < i) npos += n; 288 int cur = dp[i][m] + min(npos - i, n - (npos - i)); 289 ans = min(ans, cur); 290 } 291 if(ans == INT_MAX){ 292 cout << -1 << endl; 293 }else{ 294 cout << ans << endl; 295 } 296 } 297 } 298 ``` 299 300 [1933G - Turtle Magic: Royal Turtle Shell Pattern](/contest/1933/problem/G "Codeforces Round 929 (Div. 3)") 301 302 Idea: [snowysecret](/profile/snowysecret "Master snowysecret"), [jerryliuhkg](/profile/jerryliuhkg "Expert jerryliuhkg"), prepared: [snowysecret](/profile/snowysecret "Master snowysecret") 303 304 **Tutorial** 305 306 Tutorial is loading... 307 308 **Solution** 309 310 ``` 311 #include "bits/stdc++.h" 312 using namespace std; 313 314 void solve(int tc) { 315 int n, m, q; 316 cin >> n >> m >> q; 317 bool b[8] = {1, 1, 1, 1, 1, 1, 1, 1}; 318 int ans = 8; 319 cout << ans << '\n'; 320 while(q--) { 321 int r, c; 322 cin >> r >> c; 323 string shape; 324 cin >> shape; 325 if((r + (c+1) / 2) % 2) { 326 b[0] &= (shape == "circle"); 327 b[1] &= (shape == "square"); 328 } 329 else { 330 b[0] &= (shape == "square"); 331 b[1] &= (shape == "circle"); 332 } 333 if((r + c / 2) % 2) { 334 b[2] &= (shape == "circle"); 335 b[3] &= (shape == "square"); 336 } 337 else { 338 b[2] &= (shape == "square"); 339 b[3] &= (shape == "circle"); 340 } 341 342 if((c + (r+1) / 2) % 2) { 343 b[4] &= (shape == "circle"); 344 b[5] &= (shape == "square"); 345 } 346 else { 347 b[4] &= (shape == "square"); 348 b[5] &= (shape == "circle"); 349 } 350 if((c + r / 2) % 2) { 351 b[6] &= (shape == "circle"); 352 b[7] &= (shape == "square"); 353 } 354 else { 355 b[6] &= (shape == "square"); 356 b[7] &= (shape == "circle"); 357 } 358 ans = 0; 359 for(int i = 0; i < 8; i++) ans += b[i]; 360 cout << ans << '\n'; 361 } 362 } 363 364 int main() { 365 int t; 366 cin >> t; 367 for(int i = 1; i <= t; i++) solve(i); 368 } 369 ``` 370 371 Hope the contest was in some way helpful in improving your skills, and that you all had fun! 372 373 *“If you only do what you can do, you will never be more than you are now.”* – Master Oogway