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