codeforces-scrape

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

1692.md (9223B)


      1 Source: https://codeforces.com/blog/entry/103883
      2 
      3 Thanks for participating!
      4 
      5 [1692A - Marathon](/contest/1692/problem/A "Codeforces Round 799 (Div. 4)")
      6 
      7 Idea: [mesanu](/profile/mesanu "Expert mesanu")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 t = int(input())
     17 for test in range(t):
     18     a,b,c,d = map(int, input().split())
     19     rs = (b > a) + (c > a) + (d > a)
     20     print(rs)
     21 ```
     22 
     23 [1692B - All Distinct](/contest/1692/problem/B "Codeforces Round 799 (Div. 4)")
     24 
     25 Idea: [mesanu](/profile/mesanu "Expert mesanu")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 typedef long long  ll;
     36 using namespace std;
     37 
     38 void solve()
     39 {
     40 	int n, x;
     41 	cin >> n;
     42 	set<int> a;
     43 	for(int i = 0; i < n; i++)
     44 	{
     45 		cin >> x;
     46 		a.insert(x);
     47 	}
     48 	if((n-a.size())%2 == 0)
     49 	{
     50 		cout << a.size() << endl;
     51 	}
     52 	else
     53 	{
     54 		cout << a.size()-1 << endl;
     55 	}
     56 }
     57 
     58 int32_t main(){
     59 	int t = 1;
     60 	cin >> t;
     61 	while (t--) {
     62 		solve();
     63 	}
     64 }
     65 ```
     66 
     67 [1692C - Where's the Bishop?](/contest/1692/problem/C "Codeforces Round 799 (Div. 4)")
     68 
     69 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
     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 	char g[9][9];
     84 	for (int i = 1; i <= 8; i++) {
     85 		for (int j = 1; j <= 8; j++) {
     86 			cin >> g[i][j];
     87 		}
     88 	}
     89 	for (int i = 2; i <= 7; i++) {
     90 		for (int j = 2; j <= 7; j++) {
     91 			if (g[i][j] == '#' && g[i - 1][j - 1] == '#' && g[i - 1][j + 1] == '#' && g[i + 1][j - 1] == '#' && g[i + 1][j + 1] == '#') {
     92 				cout << i << ' ' << j << '\n'; return;
     93 			}
     94 		}
     95 	}
     96 }
     97 
     98 int main() {
     99     ios::sync_with_stdio(false);
    100     cin.tie(nullptr);
    101     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    102     // solve();
    103 }
    104 ```
    105 
    106 [1692D - The Clock](/contest/1692/problem/D "Codeforces Round 799 (Div. 4)")
    107 
    108 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG")
    109 
    110 **Tutorial**
    111 
    112 Tutorial is loading...
    113 
    114 **Solution**
    115 
    116 ```
    117 #include <bits/stdc++.h>
    118 
    119 using namespace std;
    120 
    121 int a[5] = {600, 60, 0, 10, 1};
    122 int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412};
    123 
    124 void solve() {
    125 	string s;
    126 	cin >> s;
    127 	int x;
    128 	cin >> x;
    129 	int tot = 0;
    130 	for (int i = 0; i < 5; i++) {
    131 		tot += (int)(s[i] - '0') * a[i];
    132 	}
    133 	set<int> t;
    134 	for (int i = 0; i < 2022; i++) {
    135 		t.insert(tot);
    136 		tot += x;
    137 		tot %= 1440;
    138 	}
    139 	int res = 0;
    140 	for (int i : t) {
    141 		for (int j = 0; j < 16; j++) {
    142 			if (good[j] == i) {res++;}
    143 		}
    144 	}
    145 	cout << res << '\n';
    146 }
    147 
    148 int main() {
    149     ios::sync_with_stdio(false);
    150     cin.tie(nullptr);
    151     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    152     // solve();
    153 }
    154 ```
    155 
    156 [1692E - Binary Deque](/contest/1692/problem/E "Codeforces Round 799 (Div. 4)")
    157 
    158 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution**
    165 
    166 ```
    167 #include "bits/stdc++.h"
    168 using namespace std;
    169  
    170 #define ll long long
    171  
    172 #define       forn(i,n)              for(int i=0;i<n;i++)
    173 #define          all(v)              v.begin(), v.end()
    174 #define         rall(v)              v.rbegin(),v.rend()
    175  
    176 #define            pb                push_back
    177 #define          sz(a)               (int)a.size()
    178 
    179 ll query(int l, int r, vector<ll>& p) {
    180     return p[r] - (l ? p[l - 1] : 0);
    181 }
    182 
    183 void solve() {  
    184     int n, s; cin >> n >> s;
    185     vector<ll> a(n), p(n);
    186     forn(i, n) {
    187         cin >> a[i];
    188         p[i] = a[i];
    189         if(i) p[i] += p[i - 1];
    190     }
    191 
    192     int ans = INT_MAX;
    193 
    194     for(int i = 0; i < n; ++i) {
    195         int l = i, r = n - 1, pos = -1;
    196         while(l <= r) {
    197             int mid = l + r >> 1;
    198             if(query(i, mid, p) <= s) {
    199                 pos = mid;
    200                 l = mid + 1;
    201             } else r = mid - 1;
    202         }
    203         if(pos == -1 || query(i, pos, p) != s) continue;
    204         ans = min(ans, n - (pos - i + 1));
    205     }
    206 
    207     cout << (ans == INT_MAX ? -1 : ans) << "\n";
    208 } 
    209      
    210 int32_t main() {
    211     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    212     int t = 1;
    213     cin >> t;
    214     while(t--) {
    215         solve();
    216     }
    217 }
    218 ```
    219 
    220 [1692F - 3SUM](/contest/1692/problem/F "Codeforces Round 799 (Div. 4)")
    221 
    222 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    223 
    224 **Tutorial**
    225 
    226 Tutorial is loading...
    227 
    228 **Solution**
    229 
    230 ```
    231 #include <bits/stdc++.h>
    232 
    233 using namespace std;
    234 
    235 void solve() {
    236 	int n;
    237 	cin >> n;
    238 	int cnt[10] = {};
    239 	for (int i = 0; i < n; i++) {
    240 		int x;
    241 		cin >> x;
    242 		cnt[x % 10]++;
    243 	}
    244 	vector<int> v;
    245 	for (int i = 0; i < 10; i++) {
    246 		for (int j = 0; j < min(cnt[i], 3); j++) {
    247 			v.push_back(i);
    248 		}	
    249 	}
    250 	int m = v.size();
    251 	for (int i = 0; i < m; i++) {
    252 		for (int j = i + 1; j < m; j++) {
    253 			for (int k = j + 1; k < m; k++) {
    254 				if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;}
    255 			}
    256 		}
    257 	}
    258 	cout << "NO\n";
    259 }
    260 
    261 int main() {
    262     ios::sync_with_stdio(false);
    263     cin.tie(nullptr);
    264     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    265     // solve();
    266 }
    267 ```
    268 
    269 [1692G - 2^Sort](/contest/1692/problem/G "Codeforces Round 799 (Div. 4)")
    270 
    271 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    272 
    273 **Tutorial**
    274 
    275 Tutorial is loading...
    276 
    277 **Solution**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 
    282 using namespace std;
    283 
    284 const int MAX = 200007;
    285 const int MOD = 1000000007;
    286 
    287 void solve() {
    288 	int n, k;
    289 	cin >> n >> k;
    290 	int a[n];
    291 	for (int i = 0; i < n; i++) {
    292 		cin >> a[i];
    293 	}
    294 	int ok[n];
    295 	for (int i = 0; i < n - 1; i++) {
    296 		ok[i] = (a[i] < 2 * a[i + 1]);
    297 	}
    298 	int tot = 0;
    299 	for (int i = 0; i < k; i++) {
    300 		tot += ok[i];
    301 	}
    302 	int res = 0;
    303 	if (tot == k) {res++;}
    304 	for (int i = k; i < n - 1; i++) {
    305 		tot += ok[i];
    306 		tot -= ok[i - k];
    307 		if (tot == k) {res++;}
    308 	}
    309 	cout << res << '\n';
    310 }
    311 
    312 int main() {
    313     ios::sync_with_stdio(false);
    314     cin.tie(nullptr);
    315     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    316     // solve();
    317 }
    318 ```
    319 
    320 [1692H - Gambling](/contest/1692/problem/H "Codeforces Round 799 (Div. 4)")
    321 
    322 Idea: [mesanu](/profile/mesanu "Expert mesanu")
    323 
    324 **Tutorial**
    325 
    326 Tutorial is loading...
    327 
    328 **Solution**
    329 
    330 ```
    331 #include "bits/stdc++.h"
    332 using namespace std;
    333  
    334 #define ll long long
    335  
    336 #define       forn(i,n)              for(int i=0;i<n;i++)
    337 #define          all(v)              v.begin(), v.end()
    338 #define         rall(v)              v.rbegin(),v.rend()
    339  
    340 #define            pb                push_back
    341 #define          sz(a)               (int)a.size()
    342  
    343 struct DynamicMaxSubarraySum {
    344     struct node {
    345         ll pref, suf, val, sum;
    346     };  
    347     int N;
    348     ll neutral;
    349     vector<node> t;
    350     DynamicMaxSubarraySum(int _N, ll assign_value) {
    351         neutral = assign_value;
    352         N = _N;
    353         t.resize(4 * N);
    354         forn(i, 4 * N) t[i] = {0, 0, 0, 0};
    355         build(1, 0, N - 1); 
    356     }
    357     void build(int i, int l, int r) {
    358         if(l == r) {
    359             t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral;
    360             return;
    361         }
    362         int mid = (l + r) >> 1;
    363         build(2 * i, l, mid);
    364         build(2 * i + 1, mid + 1, r);
    365         t[i] = merge(t[2 * i], t[2 * i + 1]);
    366     }
    367     node merge(node a, node b) {
    368         node c;
    369         c.pref = max(a.pref, a.sum + b.pref);
    370         c.suf = max(b.suf, b.sum + a.suf);
    371         c.val = max({a.val, b.val, a.suf + b.pref});
    372         c.sum = a.sum + b.sum;
    373         return c;
    374     }
    375  
    376     void modif(int i, int l, int r, int pos, ll val) {
    377         if(l > pos || r < pos) return;
    378         if(l == pos && r == pos) {
    379             t[i].pref = t[i].suf = t[i].val = t[i].sum = val;
    380             return;
    381         }
    382         int mid = (l + r) >> 1;
    383         modif(2 * i, l, mid, pos, val);
    384         modif(2 * i + 1, mid + 1, r, pos, val);
    385         t[i] = merge(t[2 * i], t[2 * i + 1]);
    386     }
    387     node query(int i, int l, int r, int tl, int tr) {
    388         if(l > tr || r < tl) return {0, 0, 0, 0};
    389         if(l >= tl && r <= tr) return t[i];
    390         int mid = (l + r) >> 1;
    391         return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
    392     }
    393  
    394     void modif(int pos, int val) {
    395         modif(1, 0, N - 1, pos, val);
    396     }
    397     node query(int l, int r) {
    398         return query(1, 0, N - 1, l, r);
    399     }
    400     node query(int pos) {
    401         return query(1, 0, N - 1, pos, pos);
    402     }
    403 };
    404  
    405 void solve() {  
    406     int n; cin >> n;
    407     vector<int> a(n);
    408     forn(i, n) cin >> a[i];
    409     map<int, vector<int>> vv;
    410     forn(i, n) {
    411         vv[a[i]].pb(i);
    412     }
    413     DynamicMaxSubarraySum st(n, -1);
    414  
    415     ll mx = 0, ans = -1;
    416     for(auto i: vv) {
    417         vector<int> v = i.second;
    418         for(auto x: v) st.modif(x, 1);
    419         if(mx < st.query(0, n - 1).val) {
    420             ans = i.first;
    421             mx = st.query(0, n - 1).val;
    422         }
    423         for(auto x: v) st.modif(x, -1);
    424     }  
    425     int ansl = -1, ansr = -1;
    426     for(int i = 0; i < n; ++i) {
    427         if(a[i] == ans) a[i] = 1;
    428         else a[i] = -1;
    429     }
    430     ll sum = 0, lastl = 0;
    431     mx = 0;
    432     for(int i = 0; i < n; ++i) {
    433         sum += a[i];
    434         if(sum > mx) {
    435             mx = sum;
    436             ansr = i;
    437             ansl = lastl;
    438         }
    439         if(sum <= 0) {
    440             lastl = i + 1;
    441             sum = 0;
    442         }
    443     }
    444  
    445     cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n"; 
    446 }   
    447      
    448 int32_t main() {
    449     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    450     int t = 1;
    451     cin >> t;
    452     while(t--) {
    453         solve();
    454     }
    455 }
    456 ```