codeforces-scrape

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

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