1915.md (6681B)
1 Source: https://codeforces.com/blog/entry/123952 2 3 We hope you enjoyed the contest! 4 5 [1915A - Odd One Out](/contest/1915/problem/A "Codeforces Round 918 (Div. 4)") 6 7 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const int MAX = 200'007; 21 const int MOD = 1'000'000'007; 22 23 void solve() { 24 int a, b, c; 25 cin >> a >> b >> c; 26 cout << (a ^ b ^ c) << '\n'; 27 } 28 29 int main() { 30 ios::sync_with_stdio(false); 31 cin.tie(nullptr); 32 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 33 // solve(); 34 } 35 ``` 36 37 [1915B - Not Quite Latin Square](/contest/1915/problem/B "Codeforces Round 918 (Div. 4)") 38 39 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 const int MAX = 200'007; 53 const int MOD = 1'000'000'007; 54 55 void solve() { 56 int cnt[3] = {}; 57 for (int i = 0; i < 9; i++) { 58 char c; 59 cin >> c; 60 if (c != '?') {cnt[c - 'A']++;} 61 } 62 for (int i = 0; i < 3; i++) { 63 if (cnt[i] < 3) {cout << (char)('A' + i) << '\n';} 64 } 65 } 66 67 int main() { 68 ios::sync_with_stdio(false); 69 cin.tie(nullptr); 70 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 71 // solve(); 72 } 73 ``` 74 75 [1915C - Can I Square?](/contest/1915/problem/C "Codeforces Round 918 (Div. 4)") 76 77 Idea: [SlavicG](/profile/SlavicG "Master SlavicG") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 **Solution** 84 85 ``` 86 #include "bits/stdc++.h" 87 using namespace std; 88 89 #define ll long long 90 91 #define all(v) v.begin(), v.end() 92 #define rall(v) v.rbegin(),v.rend() 93 94 #define pb push_back 95 #define sz(a) (int)a.size() 96 97 bool is_square(ll x) { 98 ll l = 1, r = 1e9; 99 while(l <= r) { 100 ll mid = l + (r - l) / 2; 101 if(mid * mid == x) return true; 102 if(mid * mid > x) r = mid - 1; 103 else l = mid + 1; 104 } 105 return false; 106 } 107 void solve() { 108 ll n; cin >> n; 109 ll s = 0; 110 for(int i = 0, x; i < n; ++i) { 111 cin >> x; s += x; 112 } 113 if(is_square(s)) cout << "YES\n"; 114 else cout << "NO\n"; 115 } 116 117 int32_t main() { 118 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 119 int t = 1; 120 cin >> t; 121 while(t--) { 122 solve(); 123 } 124 } 125 ``` 126 127 [1915D - Unnatural Language Processing](/contest/1915/problem/D "Codeforces Round 918 (Div. 4)") 128 129 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Solution** 136 137 ``` 138 #include <bits/stdc++.h> 139 140 using namespace std; 141 142 const int MAX = 200'007; 143 const int MOD = 1'000'000'007; 144 145 void solve() { 146 int n; 147 cin >> n; 148 string s; 149 cin >> s; 150 string res = ""; 151 while (!s.empty()) { 152 int x; 153 if (s.back() == 'a' || s.back() == 'e') {x = 2;} 154 else {x = 3;} 155 156 while (x--) { 157 res += s.back(); 158 s.pop_back(); 159 } 160 res += '.'; 161 } 162 res.pop_back(); 163 reverse(res.begin(), res.end()); 164 cout << res << '\n'; 165 } 166 167 int main() { 168 ios::sync_with_stdio(false); 169 cin.tie(nullptr); 170 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 171 // solve(); 172 } 173 ``` 174 175 [1915E - Romantic Glasses](/contest/1915/problem/E "Codeforces Round 918 (Div. 4)") 176 177 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 178 179 **Tutorial** 180 181 Tutorial is loading... 182 183 **Solution** 184 185 ``` 186 #include "bits/stdc++.h" 187 using namespace std; 188 189 #define ll long long 190 191 #define all(v) v.begin(), v.end() 192 #define rall(v) v.rbegin(),v.rend() 193 194 #define pb push_back 195 #define sz(a) (int)a.size() 196 197 void solve() { 198 int n; cin >> n; 199 vector<int> a(n); 200 for(int i = 0; i < n; ++i) cin >> a[i]; 201 map<ll, ll> m; 202 ll s = 0; 203 m[0] = 1; 204 for(int i = 0; i < n; ++i) { 205 a[i] *= ((i % 2) ? -1 : 1); 206 s += a[i]; 207 if(m[s]) { 208 cout << "YES\n"; 209 return; 210 } 211 ++m[s]; 212 } 213 cout << "NO\n"; 214 } 215 216 int32_t main() { 217 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 218 int t = 1; 219 cin >> t; 220 while(t--) { 221 solve(); 222 } 223 } 224 ``` 225 226 [1915F - Greetings](/contest/1915/problem/F "Codeforces Round 918 (Div. 4)") 227 228 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution** 235 236 ``` 237 #include <bits/stdc++.h> 238 239 using namespace std; 240 241 #include <ext/pb_ds/assoc_container.hpp> 242 #include <ext/pb_ds/tree_policy.hpp> 243 244 typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set; 245 246 int t, n; 247 248 vector<pair<int, int>> arr; 249 250 long long ans; 251 252 ordered_set st; 253 254 void solve(){ 255 cin >> n; 256 257 arr.assign(n, {}); 258 259 for(auto &p : arr) cin >> p.second >> p.first; 260 261 sort(arr.begin(), arr.end()); 262 263 ans = 0; 264 st.clear(); 265 266 for(auto p : arr){ 267 ans += st.size() - st.order_of_key(p.second); 268 269 st.insert(p.second); 270 } 271 272 cout << ans << "\n"; 273 } 274 275 int main(){ 276 ios_base::sync_with_stdio(false);cin.tie(NULL); 277 278 cin >> t; 279 280 while(t--){ 281 solve(); 282 } 283 } 284 ``` 285 286 [1915G - Bicycles](/contest/1915/problem/G "Codeforces Round 918 (Div. 4)") 287 288 Idea: [SlavicG](/profile/SlavicG "Master SlavicG") 289 290 **Tutorial** 291 292 Tutorial is loading... 293 294 **Solution** 295 296 ``` 297 #include "bits/stdc++.h" 298 299 const int64_t inf = 1e18; 300 301 void solve() { 302 int n, m; std::cin >> n >> m; 303 std::vector<std::pair<int, int>> adj[n]; 304 for(int i = 0; i < m; ++i) { 305 int u, v, w; std::cin >> u >> v >> w; --u, --v; 306 adj[u].emplace_back(v, w); 307 adj[v].emplace_back(u, w); 308 } 309 std::vector<int> s(n); 310 for(int& i: s) std::cin >> i; 311 312 std::vector<std::vector<int64_t>> dist(n, std::vector<int64_t>(1001, inf)); 313 std::vector<std::vector<bool>> vis(n, std::vector<bool>(1001, false)); 314 315 dist[0][s[0]] = 0; 316 std::priority_queue<std::array<int64_t, 3>> q; 317 q.push({0, 0, s[0]}); 318 while(!q.empty()) { 319 int u = q.top()[1], k = q.top()[2]; 320 q.pop(); 321 if(vis[u][k] || dist[u][k] == inf) continue; 322 vis[u][k] = true; 323 for(auto x: adj[u]) { 324 int v = x.first, w = x.second; 325 int c = std::min(s[v], k); 326 if(dist[v][c] > dist[u][k] + 1LL * w * k) { 327 dist[v][c] = dist[u][k] + 1LL * w * k; 328 q.push({-dist[v][c], v, c}); 329 } 330 } 331 } 332 int64_t ans = inf; 333 for(int k = 1; k <= 1000; ++k) 334 ans = std::min(ans, dist[n - 1][k]); 335 std::cout << ans << "\n"; 336 } 337 338 int main() { 339 std::ios_base::sync_with_stdio(0);std::cin.tie(0); 340 int t = 1; std::cin >> t; 341 while(t--) { 342 solve(); 343 } 344 } 345 ```