codeforces-scrape

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

1742.md (7045B)


      1 Source: https://codeforces.com/blog/entry/107962
      2 
      3 Thanks for participating!
      4 
      5 [1742A - Sum](/contest/1742/problem/A "Codeforces Round 827 (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, b, c;
     25 	cin >> a >> b >> c;
     26 	cout << ((a + b == c || c + a == b || b + c == a) ? "YES\n" : "NO\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 [1742B - Increasing](/contest/1742/problem/B "Codeforces Round 827 (Div. 4)")
     38 
     39 Idea: [mesanu](/profile/mesanu "Expert mesanu")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 using namespace std;
     50 
     51 void solve()
     52 {
     53     int n;
     54     cin >> n;
     55     int x[n];
     56     set<int> a;
     57     for(int i = 0; i < n; i++)
     58     {
     59         cin >> x[i];
     60     }
     61     for(int i = 0; i < n; i++)
     62     {
     63         if(a.find(x[i]) != a.end())
     64         {
     65             cout << "NO" << endl;
     66             return;
     67         }
     68         a.insert(x[i]);
     69     }
     70     cout << "YES" << endl;
     71 }
     72 
     73 int main()
     74 {
     75     int t;
     76     cin >> t;
     77     while(t--)
     78     {
     79         solve();
     80     }
     81 }
     82 ```
     83 
     84 [1742C - Stripes](/contest/1742/problem/C "Codeforces Round 827 (Div. 4)")
     85 
     86 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm")
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Bonus**
     93 
     94 How do you write a validator for this problem? (Given a grid, check if it is a valid input.)
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 const int MAX = 200007;
    104 const int MOD = 1000000007;
    105 
    106 void solve() {
    107 	char g[8][8];
    108 	vector<int> r;
    109 	for (int i = 0; i < 8; i++) {
    110 		for (int j = 0; j < 8; j++) {
    111 			cin >> g[i][j];
    112 			if (g[i][j] == 'R') {r.push_back(i);}
    113 		}
    114 	}
    115 	for (int i : r) {
    116 	    bool ok = true;
    117 	    for (int j = 0; j < 8; j++) {
    118 	        if (g[i][j] != 'R') {ok = false; break;}
    119 	    }
    120 	    if (ok) {cout << "R\n"; return;}
    121 	}
    122 	cout << "B\n";
    123 }
    124 
    125 int main() {
    126 	ios::sync_with_stdio(false);
    127 	cin.tie(nullptr);
    128 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    129 	// solve();
    130 }
    131 ```
    132 
    133 [1742D - Coprime](/contest/1742/problem/D "Codeforces Round 827 (Div. 4)")
    134 
    135 Idea: [badlad](/profile/badlad "Expert badlad"), [SlavicG](/profile/SlavicG "Expert SlavicG")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution**
    142 
    143 ```
    144 #include "bits/stdc++.h"
    145 using namespace std;
    146  
    147 #define ll long long
    148  
    149 #define       forn(i,n)              for(int i=0;i<n;i++)
    150 #define          all(v)              v.begin(), v.end()
    151 #define         rall(v)              v.rbegin(),v.rend()
    152  
    153 #define            pb                push_back
    154 #define          sz(a)               (int)a.size()
    155 
    156 vector<int> pairs[1001];
    157 void solve() {
    158     int n; cin >> n;
    159     vector<int> id[1001];
    160     for(int i = 1; i <= n; ++i) {
    161         int x; cin >> x;
    162         id[x].push_back(i);
    163     }
    164     int ans = -1;
    165     for(int i = 1; i <= 1000; ++i) {
    166         for(int j: pairs[i]) {
    167             if(!id[i].empty() && !id[j].empty()) {
    168                 ans = max(ans, id[i].back() + id[j].back());
    169             }
    170         }
    171     }
    172     cout << ans << "\n";
    173 }   
    174  
    175 int32_t main() {
    176     for(int i = 1; i <= 1000; ++i) {
    177         for(int j = 1; j <= 1000; ++j) {
    178             if(__gcd(i, j) == 1) {
    179                 pairs[i].push_back(j);
    180             }
    181         }
    182     }
    183     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    184     int t = 1;
    185     cin >> t;
    186     while(t--) {
    187         solve();
    188     }
    189 }
    190 ```
    191 
    192 [1742E - Scuza](/contest/1742/problem/E "Codeforces Round 827 (Div. 4)")
    193 
    194 Idea: [mesanu](/profile/mesanu "Expert mesanu")
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 
    205 using namespace std;
    206 
    207 void solve()
    208 {
    209     int n, q;
    210     cin >> n >> q;
    211     vector<long long> pref;
    212     pref.push_back(0);
    213     vector<int> prefmax;
    214     for(int i = 0; i < n; i++)
    215     {
    216         int x;
    217         cin >> x;
    218         pref.push_back(pref.back()+x);
    219         if(i == 0)
    220         {
    221             prefmax.push_back(x);
    222         }
    223         else
    224         {
    225             prefmax.push_back(max(prefmax.back(), x));
    226         }
    227     }
    228     for(int i = 0; i < q; i++)
    229     {
    230         int k;
    231         cin >> k;
    232         int ind = upper_bound(prefmax.begin(), prefmax.end(), k)-prefmax.begin();
    233         cout << pref[ind] << " ";
    234     }
    235     cout << endl;
    236 }
    237 
    238 int main()
    239 {
    240     int t;
    241     cin >> t;
    242     while(t--)
    243     {
    244         solve();
    245     }
    246 }
    247 ```
    248 
    249 [1742F - Smaller](/contest/1742/problem/F "Codeforces Round 827 (Div. 4)")
    250 
    251 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG")
    252 
    253 **Tutorial**
    254 
    255 Tutorial is loading...
    256 
    257 **Solution**
    258 
    259 ```
    260 #include "bits/stdc++.h"
    261 using namespace std;
    262  
    263 #define ll long long
    264  
    265 #define       forn(i,n)              for(int i=0;i<n;i++)
    266 #define          all(v)              v.begin(), v.end()
    267 #define         rall(v)              v.rbegin(),v.rend()
    268  
    269 #define            pb                push_back
    270 #define          sz(a)               (int)a.size()
    271 
    272 void solve() {
    273     int q; cin >> q;
    274     bool otherA = false, otherB = false;
    275     ll cntA = 0, cntB = 0;
    276     while(q--) {
    277         ll d, k; string x; cin >> d >> k >> x;
    278         for(auto c: x) {
    279             if(d == 1) {
    280                 if(c != 'a') otherA = 1;
    281                 else cntA += k;
    282             } else {
    283                 if(c != 'a') otherB = 1;
    284                 else cntB += k;
    285             } 
    286         }
    287         if(otherB) {
    288             cout << "YES\n";
    289         } else if(!otherA && cntA < cntB) {
    290             cout << "YES\n";
    291         } else {
    292             cout << "NO\n";
    293         }
    294     }
    295 }   
    296  
    297 int32_t main() {
    298     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    299     int t = 1;
    300     cin >> t;
    301     while(t--) {
    302         solve();
    303     }
    304 }
    305 ```
    306 
    307 [1742G - Orray](/contest/1742/problem/G "Codeforces Round 827 (Div. 4)")
    308 
    309 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG")
    310 
    311 **Tutorial**
    312 
    313 Tutorial is loading...
    314 
    315 **Solution**
    316 
    317 ```
    318 #include "bits/stdc++.h"
    319 using namespace std;
    320  
    321 #define ll long long
    322  
    323 #define       forn(i,n)              for(int i=0;i<n;i++)
    324 #define          all(v)              v.begin(), v.end()
    325 #define         rall(v)              v.rbegin(),v.rend()
    326  
    327 #define            pb                push_back
    328 #define          sz(a)               (int)a.size()
    329 
    330 void solve() {
    331     int n; cin >> n;
    332     vector<int> a(n);
    333     forn(i, n) cin >> a[i];
    334     //we care at most about first log2(a) values
    335     int cur_or = 0;
    336     vector<bool> vis(n, false);
    337     for(int i = 0; i < min(31, n); ++i) {
    338         int mx = 0, idx = -1;
    339         for(int j = 0; j < n; ++j) {
    340             if(vis[j]) continue;
    341             if((cur_or | a[j]) > mx) {
    342                 mx = (cur_or | a[j]);
    343                 idx = j;
    344             }
    345         }
    346         vis[idx] = true;
    347         cout << a[idx] << " ";
    348         cur_or |= a[idx];
    349     }
    350     forn(i, n) if(!vis[i]) cout << a[i] << " ";
    351     cout << '\n';
    352 }   
    353  
    354 int32_t main() {
    355     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    356     int t = 1;
    357     cin >> t;
    358     while(t--) {
    359         solve();
    360     }
    361 }
    362 ```