codeforces-scrape

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

1950.md (6294B)


      1 Source: https://codeforces.com/blog/entry/127664
      2 
      3 We hope you enjoyed the contest!
      4 
      5 [1950A - Stair, Peak, or Neither?](/contest/1950/problem/A "Codeforces Round 937 (Div. 4)")
      6 
      7 Idea: [SlavicG](/profile/SlavicG "Master SlavicG")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <iostream>
     17 
     18 void solve() {
     19 	int a, b, c;
     20 	std::cin >> a >> b >> c;
     21 	if(a < b && b < c) std::cout << "STAIR"<< "\n";
     22 	else if(a < b && b > c) std::cout << "PEAK"<< "\n";
     23 	else std::cout << "NONE" << "\n";
     24 }
     25 
     26 int main() {
     27 	int tt; std::cin >> tt;
     28 	while(tt--) 
     29 	    solve();
     30 }
     31 ```
     32 
     33 [1950B - Upscaling](/contest/1950/problem/B "Codeforces Round 937 (Div. 4)")
     34 
     35 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 void solve() {
     49 	int n;
     50 	cin >> n;
     51 	for (int i = 0; i < 2 * n; i++) {
     52 		for (int j = 0; j < 2 * n; j++) {
     53 			cout << (i / 2 + j / 2 & 1 ? '.' : '#');
     54 		}
     55 		cout << '\n';
     56 	}	
     57 }
     58 
     59 int main() {
     60 	ios::sync_with_stdio(false);
     61 	cin.tie(nullptr);
     62 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     63 	// solve();
     64 }
     65 ```
     66 
     67 [1950C - Clock Conversion](/contest/1950/problem/C "Codeforces Round 937 (Div. 4)")
     68 
     69 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 void solve() {
     83     int h, m; char c;
     84     cin >> h >> c >> m;
     85     string am = (h < 12 ? " AM" : " PM");
     86     h = (h % 12 ? h % 12 : 12);
     87     cout << (h < 10 ? "0" : "") << h << c << (m < 10 ? "0" : "") << m << am << '\n';
     88 }
     89 
     90 int main() {
     91 	ios::sync_with_stdio(false);
     92 	cin.tie(nullptr);
     93 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     94 	// solve();
     95 }
     96 ```
     97 
     98 [1950D - Product of Binary Decimals](/contest/1950/problem/D "Codeforces Round 937 (Div. 4)")
     99 
    100 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110 
    111 using namespace std;
    112 
    113 const int MAX = 100'007;
    114 const int MOD = 1'000'000'007;
    115 
    116 vector<int> binary_decimals;
    117 
    118 bool ok(int n) {
    119 	if (n == 1) {return true;}
    120 	bool ans = false;
    121 	for (int i : binary_decimals) {
    122 		if (n % i == 0) {
    123 			ans |= ok(n / i);
    124 		}
    125 	}
    126 	return ans;
    127 }
    128 
    129 void solve() {
    130 	int n;
    131 	cin >> n;
    132 	cout << (ok(n) ? "YES\n" : "NO\n");	
    133 }
    134 
    135 int main() {
    136 	for (int i = 2; i < MAX; i++) {
    137 		int curr = i;
    138 		bool bad = false;
    139 		while (curr) {
    140 			if (curr % 10 > 1) {bad = true; break;}
    141 			curr /= 10;
    142 		}
    143 		if (!bad) {binary_decimals.push_back(i);}
    144 	}
    145 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    146 	// solve();
    147 }
    148 ```
    149 
    150 [1950E - Nearly Shortest Repeating Substring](/contest/1950/problem/E "Codeforces Round 937 (Div. 4)")
    151 
    152 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 using namespace std;
    163 
    164 void solve() {
    165     int n;
    166     cin >> n;
    167     string s;
    168     cin >> s;
    169     for(int i = 1; i <= n; i++)
    170     {
    171         if(n%i == 0)
    172         {
    173             int satisfy = 2;
    174             for(int j = 0; j < i; j++)
    175             {
    176                 for(int k = j+i; k < n; k+=i)
    177                 {
    178                     if(s[k] != s[j])
    179                     {
    180                         satisfy--;
    181                     }
    182                 }
    183             }
    184             if(satisfy > 0)
    185             {
    186                 cout << i << endl;
    187                 return;
    188             }
    189             satisfy = 2;
    190             for(int j = n-i; j < n; j++)
    191             {
    192                 for(int k = j-i; k >= 0; k-=i)
    193                 {
    194                     if(s[k] != s[j])
    195                     {
    196                         satisfy--;
    197                     }
    198                 }
    199             }
    200             if(satisfy > 0)
    201             {
    202                 cout << i << endl;
    203                 return;
    204             }
    205         }
    206     }
    207 }
    208 
    209 int32_t main(){
    210     int t = 1;
    211     cin >> t;
    212     while (t--) {
    213         solve();
    214     }
    215 }
    216 ```
    217 
    218 [1950F - 0, 1, 2, Tree!](/contest/1950/problem/F "Codeforces Round 937 (Div. 4)")
    219 
    220 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution**
    227 
    228 ```
    229 #include <bits/stdc++.h>
    230 
    231 using namespace std;
    232 
    233 void solve() {
    234 	int a, b, c;
    235 	cin >> a >> b >> c;
    236 	if (a + 1 != c) {cout << -1 << '\n'; return;}
    237 	if (a + b + c == 1) {cout << 0 << '\n'; return;}
    238 	int curr = 1, next = 0, res = 1;
    239 	for (int i = 0; i < a + b; i++) {
    240 		if (!curr) {
    241 	        swap(next, curr);
    242 	        res++;
    243 	    }
    244 	    curr--;
    245 	    next++;
    246 	    if (i < a) {next++;}
    247 	}
    248 	cout << res << '\n';
    249 }
    250 
    251 int main() {
    252 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    253 	// solve();
    254 }
    255 ```
    256 
    257 [1950G - Shuffling Songs](/contest/1950/problem/G "Codeforces Round 937 (Div. 4)")
    258 
    259 Idea: [SlavicG](/profile/SlavicG "Master SlavicG")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution**
    266 
    267 ```
    268 #include "bits/stdc++.h"
    269 using namespace std;
    270 
    271 #define all(x) x.begin(),x.end()
    272 
    273 void solve() {
    274     int n; cin >> n;
    275     vector<int> s(n), g(n);
    276     vector<string> aa(n), bb(n);
    277     vector<string> vals;
    278     for(int i = 0; i < n; ++i) {
    279         string a, b; cin >> a >> b;
    280         vals.push_back(a);
    281         vals.push_back(b);
    282         aa[i] = a, bb[i] = b;
    283     }
    284     sort(all(vals));
    285     vals.erase(unique(all(vals)), vals.end());
    286     for(int i = 0; i < n; ++i) {
    287         s[i] = lower_bound(all(vals), aa[i]) - vals.begin();
    288         g[i] = lower_bound(all(vals), bb[i]) - vals.begin();
    289     }
    290     vector<vector<int>> dp(1 << n, vector<int>(n, 0));
    291     for(int i = 0; i < n; ++i) dp[1 << i][i] = 1;
    292     for(int mask = 0; mask < (1 << n); ++mask) {
    293         for(int lst = 0; lst < n; ++lst) {
    294             if(!dp[mask][lst]) continue;
    295             for(int i = 0; i < n; ++i) {
    296                 if(mask >> i & 1) continue;
    297                 if(s[lst] == s[i] || g[lst] == g[i]) {
    298                     dp[mask | (1 << i)][i] |= dp[mask][lst];
    299                 }
    300             }
    301         }
    302     }
    303     int ans = 0;
    304     for(int mask = 0; mask < (1 << n); ++mask) {
    305         for(int i = 0; i < n; ++i) {
    306             if(dp[mask][i]) {
    307                 ans = max(ans, __builtin_popcount(mask));
    308             }
    309         }
    310     }
    311     cout << n - ans << "\n";
    312 }   
    313  
    314 main() {
    315     int t = 1; cin >> t;
    316     while(t--) {
    317         solve();
    318     }
    319 }
    320 ```