codeforces-scrape

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

1760.md (6996B)


      1 Source: https://codeforces.com/blog/entry/109348
      2 
      3 We hope you enjoyed the contest! Sorry for the late editorial.
      4 
      5 [1760A - Medium Number](/contest/1760/problem/A "Codeforces Round 835 (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 = 200007;
     21 const int MOD = 1000000007;
     22 
     23 void solve() {
     24 	int a[3];
     25 	cin >> a[0] >> a[1] >> a[2];
     26 	sort(a, a + 3);
     27 	cout << a[1] << '\n';	
     28 }
     29 
     30 int main() {
     31 	ios::sync_with_stdio(false);
     32 	cin.tie(nullptr);
     33 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     34 	// solve();
     35 }
     36 ```
     37 
     38 [1760B - Atilla's Favorite Problem](/contest/1760/problem/B "Codeforces Round 835 (Div. 4)")
     39 
     40 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include "bits/stdc++.h"
     50 using namespace std;
     51  
     52 using ll = long long;
     53  
     54 #define       forn(i,n)              for(int i=0;i<n;i++)
     55 #define          all(v)              v.begin(), v.end()
     56 #define         rall(v)              v.rbegin(),v.rend()
     57  
     58 #define            pb                push_back
     59 #define          sz(a)               (int)a.size()
     60 
     61 void solve() {
     62     int n; string s; cin >> n >> s;
     63     sort(all(s));
     64     cout << s.back() - 'a' + 1 << "\n";
     65 }   
     66  
     67 int32_t main() {
     68     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
     69     int t = 1;
     70     cin >> t;
     71     while(t--) {
     72         solve();
     73     }
     74 }
     75 ```
     76 
     77 [1760C - Advantage](/contest/1760/problem/C "Codeforces Round 835 (Div. 4)")
     78 
     79 Idea: [Errichto](/profile/Errichto "International Grandmaster Errichto")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution**
     86 
     87 ```
     88 #include <bits/stdc++.h>
     89 
     90 using namespace std;
     91 
     92 #define forn(i, n) for (int i = 0; i < int(n); i++)
     93 
     94 int main() {
     95     int t;
     96     cin >> t;
     97     forn(tt, t) {
     98         int n;
     99         cin >> n;
    100         vector<int> a(n);
    101         forn(i, n)
    102             cin >> a[i];
    103         vector<int> b(a);
    104         sort(b.begin(), b.end());
    105         forn(i, n) {
    106             if (a[i] == b[n - 1])
    107                 cout << a[i] - b[n - 2] << " ";
    108             else
    109                 cout << a[i] - b[n - 1] << " ";
    110         }
    111         cout << endl;
    112    }
    113 }
    114 ```
    115 
    116 [1760D - Challenging Valleys](/contest/1760/problem/D "Codeforces Round 835 (Div. 4)")
    117 
    118 Idea: [mesanu](/profile/mesanu "Expert mesanu")
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution**
    125 
    126 ```
    127 #include <bits/stdc++.h>
    128 using namespace std;
    129 void solve()
    130 {
    131     int n;
    132     cin >> n;
    133     vector<int> a;
    134     for(int i = 0; i < n; i++)
    135     {
    136         int x;
    137         cin >> x;
    138         if(i == 0 || x != a.back())
    139         {
    140             a.push_back(x);
    141         }
    142     }
    143     int num_valley = 0;
    144     for(int i = 0; i < a.size(); i++)
    145     {
    146         if((i == 0 || a[i-1] > a[i]) && (i == a.size()-1 || a[i] < a[i+1]))
    147         {
    148             num_valley++;
    149         }
    150     }
    151     if(num_valley == 1)
    152     {
    153         cout << "YES" << endl;
    154     }
    155     else
    156     {
    157         cout << "NO" << endl;
    158     }
    159 }
    160 
    161 int32_t main(){
    162     int t = 1;
    163     cin >> t;
    164     while (t--) {
    165         solve();
    166     }
    167 }
    168 ```
    169 
    170 [1760E - Binary Inversions](/contest/1760/problem/E "Codeforces Round 835 (Div. 4)")
    171 
    172 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution**
    179 
    180 ```
    181 #include "bits/stdc++.h"
    182 using namespace std;
    183  
    184 using ll = long long;
    185  
    186 #define       forn(i,n)              for(int i=0;i<n;i++)
    187 #define          all(v)              v.begin(), v.end()
    188 #define         rall(v)              v.rbegin(),v.rend()
    189  
    190 #define            pb                push_back
    191 #define          sz(a)               (int)a.size()
    192 
    193 ll calc(vector<int>& a) {
    194     ll zeroes = 0, ans = 0;
    195     for(int i = sz(a) - 1; i >= 0; --i) {
    196         if(a[i] == 0) ++zeroes;
    197         else ans += zeroes;
    198     }
    199     return ans;
    200 }
    201 void solve() {
    202     int n; cin >> n;
    203     vector<int> a(n);
    204     forn(i, n) cin >> a[i];
    205     ll ans = calc(a);
    206     forn(i, n) {
    207         if(a[i] == 0) {
    208             a[i] = 1;
    209             ans = max(ans, calc(a));
    210             a[i] = 0;
    211             break;
    212         }
    213     }
    214     for(int i = n - 1; i >= 0; --i) {
    215         if(a[i] == 1) {
    216             a[i] = 0;
    217             ans = max(ans, calc(a));
    218             a[i] = 1;
    219             break;
    220         }
    221     }
    222     cout << ans << "\n";
    223 }   
    224  
    225 int32_t main() {
    226     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    227     int t = 1;
    228     cin >> t;
    229     while(t--) {
    230         solve();
    231     }
    232 }
    233 ```
    234 
    235 [1760F - Quests](/contest/1760/problem/F "Codeforces Round 835 (Div. 4)")
    236 
    237 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm")
    238 
    239 **Tutorial**
    240 
    241 Tutorial is loading...
    242 
    243 **Solution**
    244 
    245 ```
    246 #include <bits/stdc++.h>
    247 
    248 using namespace std;
    249 
    250 const int MAX = 200007;
    251 const int MOD = 1000000007;
    252 
    253 void solve() {
    254 	int n, d;
    255 	long long c;
    256 	cin >> n >> c >> d;
    257 	long long a[n];
    258 	for (int i = 0; i < n; i++) {
    259 		cin >> a[i];
    260 	}
    261 	sort(a, a + n, greater<long long>());
    262 	int l = 0, r = d + 2;
    263 	while (l < r) {
    264 		int m = l + (r - l + 1) / 2;
    265 		long long tot = 0;
    266 		int curr = 0;
    267 		for (int i = 0; i < d; i++) {
    268 			if (i % m < n) {tot += a[i % m];}
    269 		}
    270 		if (tot >= c) {
    271 			l = m;
    272 		}
    273 		else {
    274 			r = m - 1;
    275 		}
    276 	}
    277 	if (l == d + 2) {cout << "Infinity\n"; return;}
    278 	if (l == 0) {cout << "Impossible\n"; return;}
    279 	cout << l - 1 << '\n';
    280 }
    281 
    282 int main() {
    283 	ios::sync_with_stdio(false);
    284 	cin.tie(nullptr);
    285 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    286 	// solve();
    287 }
    288 ```
    289 
    290 [1760G - SlavicG's Favorite Problem](/contest/1760/problem/G "Codeforces Round 835 (Div. 4)")
    291 
    292 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
    293 
    294 **Tutorial**
    295 
    296 Tutorial is loading...
    297 
    298 **Solution**
    299 
    300 ```
    301 #include "bits/stdc++.h"
    302 using namespace std;
    303  
    304 using ll = long long;
    305  
    306 #define       forn(i,n)              for(int i=0;i<n;i++)
    307 #define          all(v)              v.begin(), v.end()
    308 #define         rall(v)              v.rbegin(),v.rend()
    309  
    310 #define            pb                push_back
    311 #define          sz(a)               (int)a.size()
    312 
    313 const int N = 1e5 + 10;
    314 vector<pair<int, int>> adj[N];
    315 set<int> s;
    316 bool ok = true;
    317 int n, a, b;
    318 void dfs1(int u, int par, int x) {
    319     if(u == b) return;
    320     s.insert(x);
    321     for(auto e: adj[u]) {
    322         int v = e.first, w = e.second;
    323         if(v == par) continue;
    324         dfs1(v, u, x ^ w);
    325     }
    326 }
    327 
    328 bool dfs2(int u, int par, int x) {
    329     if(u != b && s.count(x)) return true;
    330     for(auto e: adj[u]) {
    331         int v = e.first, w = e.second;
    332         if(v == par) continue;
    333         if(dfs2(v, u, w ^ x)) return true;
    334     } 
    335     return false;
    336 }
    337 
    338 void solve() {
    339     s.clear();
    340     cin >> n >> a >> b; --a, --b;
    341     forn(i, n) adj[i].clear();
    342     for(int i = 0; i < n - 1; ++i) {
    343         int u, v, w; cin >> u >> v >> w; --u, --v;
    344         adj[u].pb({v, w});
    345         adj[v].pb({u, w});
    346     }
    347     dfs1(a, -1, 0);
    348     if(dfs2(b, -1, 0)) cout << "YES\n";
    349     else cout << "NO\n";
    350 }   
    351  
    352 int32_t main() {
    353     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    354     int t = 1;
    355     cin >> t;
    356     while(t--) {
    357         solve();
    358     }
    359 }
    360 ```