codeforces-scrape

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

1703.md (6253B)


      1 Source: https://codeforces.com/blog/entry/104786
      2 
      3 Thanks for participating!
      4 
      5 [1703A - YES или YES?](/contest/1703/problem/A "Codeforces Round 806 (Div. 4)")
      6 
      7 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера 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 	string s;
     25 	cin >> s;
     26 	if (s[0] != 'y' && s[0] != 'Y') {cout << "NO\n";}
     27 	else if (s[1] != 'e' && s[1] != 'E') {cout << "NO\n";}
     28 	else if (s[2] != 's' && s[2] != 'S') {cout << "NO\n";}
     29 	else {cout << "YES\n";}
     30 }
     31 
     32 int main() {
     33 	ios::sync_with_stdio(false);
     34 	cin.tie(nullptr);
     35 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     36 	// solve();
     37 }
     38 ```
     39 
     40 [1703B - ICPC шарики](/contest/1703/problem/B "Codeforces Round 806 (Div. 4)")
     41 
     42 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера flamestorm")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52  
     53 using namespace std;
     54  
     55 const int MAX = 200007;
     56 const int MOD = 1000000007;
     57  
     58 void solve() {
     59 	int n;
     60 	cin >> n;
     61 	string s;
     62 	cin >> s;
     63 	bool vis[26] = {};
     64 	int res = 0;
     65 	for (char c : s) {
     66 		if (!vis[c - 'A']) {res += 2; vis[c - 'A'] = true;}
     67 		else {res++;}
     68 	}
     69 	cout << res << '\n';
     70 }
     71  
     72 int main() {
     73 	ios::sync_with_stdio(false);
     74 	cin.tie(nullptr);
     75 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     76 	// solve();
     77 }
     78 ```
     79 
     80 [1703C - Шифр](/contest/1703/problem/C "Codeforces Round 806 (Div. 4)")
     81 
     82 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 using namespace std;
     93  
     94 void solve()
     95 {
     96     int n;
     97     cin >> n;
     98     int a[n];
     99     for(int i = 0; i < n; i++)
    100     {
    101         cin >> a[i];
    102     }
    103     for(int i = 0; i < n; i++)
    104     {
    105         int b;
    106         cin >> b;
    107         if(b == 0)
    108         {
    109             continue;
    110         }
    111         string now;
    112         cin >> now;
    113         for(int j = 0; j < b; j++)
    114         {
    115             if(now[j] == 'U'){a[i]--;}
    116             else if(now[j] == 'D'){a[i]++;}
    117             if(a[i] < 0){a[i]+=10;}
    118             if(a[i] > 9){a[i]-=10;}
    119         }
    120     }
    121     for(int i = 0; i < n; i++)
    122     {
    123         cout << a[i] << " ";
    124     }
    125     cout << endl;
    126 }
    127  
    128 int main(){
    129     int t;
    130     cin>> t;
    131     while(t--)
    132     {
    133         solve();
    134     }
    135     return 0;
    136 }
    137 ```
    138 
    139 [1703D - Двойные строки](/contest/1703/problem/D "Codeforces Round 806 (Div. 4)")
    140 
    141 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151  
    152 using namespace std;
    153  
    154 const int MAX = 200007;
    155 const int MOD = 1000000007;
    156  
    157 void solve() {
    158 	int n;
    159 	cin >> n;
    160 	string s[n];
    161 	map<string, bool> mp;
    162 	for (int i = 0; i < n; i++) {
    163 		cin >> s[i];
    164 		mp[s[i]] = true;
    165 	}
    166 	for (int i = 0; i < n; i++) {
    167 		bool ok = false;
    168 		for (int j = 1; j < s[i].length(); j++) {
    169 			string pref = s[i].substr(0, j), suff = s[i].substr(j, s[i].length() - j);
    170 			if (mp[pref] && mp[suff]) {ok = true;}	
    171 		}
    172 		cout << ok;
    173 	}
    174 	cout << '\n';
    175 }
    176  
    177 int main() {
    178 	ios::sync_with_stdio(false);
    179 	cin.tie(nullptr);
    180 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    181 	// solve();
    182 }
    183 ```
    184 
    185 [1703E - Симметричная решётка](/contest/1703/problem/E "Codeforces Round 806 (Div. 4)")
    186 
    187 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    188 
    189 **Tutorial**
    190 
    191 Tutorial is loading...
    192 
    193 **Solution**
    194 
    195 ```
    196 #include <bits/stdc++.h>
    197 using namespace std;
    198  
    199 void solve()
    200 {
    201     int n;
    202     cin >> n;
    203     int a[n][n];
    204     for(int i = 0; i < n; i++)
    205     {
    206         for(int j = 0; j < n; j++)
    207         {
    208             char c;
    209             cin >> c;
    210             a[i][j] = c-'0';
    211         }
    212     }
    213     int ans = 0;
    214     for(int i = 0; i < (n+1)/2; i++)
    215     {
    216         for(int j = 0; j < n/2; j++)
    217         {
    218             int nowi = i, nowj = j;
    219             int oldnowj = nowj;
    220             int sum = a[nowi][nowj];
    221             nowj = n-nowi-1;
    222             nowi = oldnowj;
    223             sum+=a[nowi][nowj];
    224             oldnowj = nowj;
    225             nowj = n-nowi-1;
    226             nowi = oldnowj;
    227             sum+=a[nowi][nowj];
    228             oldnowj = nowj;
    229             nowj = n-nowi-1;
    230             nowi = oldnowj;
    231             sum+=a[nowi][nowj];
    232             ans+=min(sum, 4-sum);
    233         }
    234     }
    235     cout << ans << endl;
    236 }
    237  
    238 int main(){
    239     int t;
    240     cin>> t;
    241     while(t--)
    242     {
    243         solve();
    244     }
    245     return 0;
    246 }
    247 ```
    248 
    249 [1703F - Очередная задача про пары, удовлетворяющие неравенству](/contest/1703/problem/F "Codeforces Round 806 (Div. 4)")
    250 
    251 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера flamestorm")
    252 
    253 **Tutorial**
    254 
    255 Tutorial is loading...
    256 
    257 **Solution**
    258 
    259 ```
    260 #include <bits/stdc++.h>
    261  
    262 using namespace std;
    263  
    264 const int MAX = 200007;
    265 const int MOD = 1000000007;
    266  
    267 void solve() {
    268 	int n;
    269 	cin >> n;
    270 	int a[n + 1];
    271 	for (int i = 1; i <= n; i++) {
    272 		cin >> a[i];
    273 	}
    274 	long long res = 0;
    275 	vector<int> v;
    276 	for (int i = 1; i <= n; i++) {
    277 		if (a[i] >= i) {continue;}
    278 		res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
    279 		v.push_back(i);
    280 	}
    281 	cout << res << '\n';
    282 }
    283  
    284 int main() {
    285 	ios::sync_with_stdio(false);
    286 	cin.tie(nullptr);
    287 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    288 	// solve();
    289 }
    290 ```
    291 
    292 [1703G - Хороший ключ, плохой ключ](/contest/1703/problem/G "Codeforces Round 806 (Div. 4)")
    293 
    294 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Solution**
    301 
    302 ```
    303 #include <bits/stdc++.h>
    304 using namespace std;
    305  
    306 void solve()
    307 {
    308     int n, k;
    309     cin >> n >> k;
    310     int a[n];
    311     for(int i = 0; i < n; i++)
    312     {
    313         cin >> a[i];
    314     }
    315     long long ans = 0;
    316     long long sum = 0;
    317     for(int i = -1; i < n; i++)
    318     {
    319         long long now = sum;
    320         for(int j = i+1; j < min(n, i+32); j++)
    321         {
    322             int copy = a[j];
    323             copy>>=j-i;
    324             now+=copy;
    325         }
    326         ans = max(ans, now);
    327         if(i+1 != n)
    328         {
    329             sum+=a[i+1]-k;
    330         }
    331     }
    332     cout << ans << endl;
    333 }
    334  
    335 int main(){
    336     int t;
    337     cin >> t;
    338     while(t--)
    339     {
    340         solve();
    341     }
    342     return 0;
    343 }
    344 ```