codeforces-scrape

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

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