codeforces-scrape

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

977.md (4217B)


      1 Source: https://codeforces.com/blog/entry/59281
      2 
      3 [977A - Wrong Subtraction](/contest/977/problem/A "Codeforces Round 479 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 
     22 	int n, k;
     23 	cin >> n >> k;
     24 	
     25 	for (int i = 0; i < k; ++i) {
     26 		if (n % 10 == 0) n /= 10;
     27 		else n--;
     28 	}
     29 	
     30 	cout << n << endl;
     31 	
     32 	return 0;
     33 }
     34 ```
     35 
     36 [977B - Two-gram](/contest/977/problem/B "Codeforces Round 479 (Div. 3)")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution (Vovuh)**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50 #ifdef _DEBUG
     51 	freopen("input.txt", "r", stdin);
     52 //	freopen("output.txt", "w", stdout);
     53 #endif
     54 
     55 	int n;
     56 	cin >> n;
     57 	string s;
     58 	cin >> s;
     59 	
     60 	int res = 0;
     61 	string ans;
     62 	for (int i = 0; i < n - 1; ++i) {
     63 		int cur = 0;
     64 		for (int j = 0; j < n - 1; ++j)
     65 			if (s[j] == s[i] && s[j + 1] == s[i + 1])
     66 				++cur;
     67 		if (res < cur) {
     68 			res = cur;
     69 			ans = string(1, s[i]) + string(1, s[i + 1]);
     70 		}
     71 	}
     72 	
     73 	cout << ans << endl;
     74 	
     75 	return 0;
     76 }
     77 ```
     78 
     79 [977C - Less or Equal](/contest/977/problem/C "Codeforces Round 479 (Div. 3)")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution (Vovuh)**
     86 
     87 ```
     88 #include <bits/stdc++.h>
     89 
     90 using namespace std;
     91 
     92 int main() {
     93 #ifdef _DEBUG
     94 	freopen("input.txt", "r", stdin);
     95 //	freopen("output.txt", "w", stdout);
     96 #endif
     97 	
     98 	int n, k;
     99 	scanf("%d %d", &n, &k);
    100 	
    101 	vector<int> a(n);
    102 	for (int i = 0; i < n; ++i)
    103 		scanf("%d", &a[i]);
    104 	
    105 	sort(a.begin(), a.end());
    106 	
    107 	int ans;
    108 	
    109 	if (k == 0) {
    110 		ans = a[0] - 1;
    111 	} else {
    112 		ans = a[k - 1];
    113 	}
    114 	
    115 	int cnt = 0;
    116 	
    117 	for (int i = 0; i < n; ++i)
    118 		if (a[i] <= ans) ++cnt;
    119 	
    120 	if (cnt != k || !(1 <= ans && ans <= 1000 * 1000 * 1000)) {
    121 		puts("-1");
    122 		return 0;
    123 	}
    124 	
    125 	printf("%d\n", ans);
    126 	
    127 	return 0;
    128 }
    129 ```
    130 
    131 [977D - Divide by three, multiply by two](/contest/977/problem/D "Codeforces Round 479 (Div. 3)")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Solution (eddy1021)**
    138 
    139 ```
    140 #include <bits/stdc++.h>
    141 using namespace std;
    142 typedef long long LL;
    143 int count3(LL x){
    144   int ret=0;
    145   while(x % 3 == 0){
    146     ret++;
    147     x /= 3;
    148   }
    149   return ret;
    150 }
    151 int n;
    152 vector<pair<int,LL>> v;
    153 int main(){
    154   cin>>n;
    155   v.resize(n);
    156   for(int i=0; i<n; i++){
    157     cin>>v[i].second;
    158     v[i].first=-count3(v[i].second);
    159   }
    160   sort(v.begin(), v.end());
    161   for(int i=0; i<n; i++)
    162     printf("%lld%c", v[i].second, " \n"[i + 1 == n]);
    163 }
    164 ```
    165 
    166 [977E - Cyclic Components](/contest/977/problem/E "Codeforces Round 479 (Div. 3)")
    167 
    168 **Tutorial**
    169 
    170 Tutorial is loading...
    171 
    172 **Solution (Vovuh)**
    173 
    174 ```
    175 #include <bits/stdc++.h>
    176 
    177 using namespace std;
    178 
    179 const int N = 200 * 1000 + 11;
    180 
    181 int n, m;
    182 int deg[N];
    183 bool used[N];
    184 vector<int> comp;
    185 vector<int> g[N];
    186 
    187 void dfs(int v) {
    188 	used[v] = true;
    189 	comp.push_back(v);
    190 	
    191 	for (auto to : g[v])
    192 		if (!used[to])
    193 			dfs(to);
    194 }
    195 
    196 int main() {
    197 #ifdef _DEBUG
    198 	freopen("input.txt", "r", stdin);
    199 //	freopen("output.txt", "w", stdout);
    200 #endif
    201 
    202 	scanf("%d %d", &n, &m);
    203 	for (int i = 0; i < m; ++i) {
    204 		int x, y;
    205 		scanf("%d %d", &x, &y);
    206 		--x, --y;
    207 		g[x].push_back(y);
    208 		g[y].push_back(x);
    209 		++deg[x];
    210 		++deg[y];
    211 	}
    212 	
    213 	int ans = 0;
    214 	for (int i = 0; i < n; ++i) {
    215 		if (!used[i]) {
    216 			comp.clear();
    217 			dfs(i);
    218 			bool ok = true;
    219 			for (auto v : comp) ok &= deg[v] == 2;
    220 			if (ok) ++ans;
    221 		}
    222 	}
    223 	
    224 	printf("%d\n", ans);
    225 	
    226 	return 0;
    227 }
    228 ```
    229 
    230 [977F - Consecutive Subsequence](/contest/977/problem/F "Codeforces Round 479 (Div. 3)")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution (Vovuh)**
    237 
    238 ```
    239 #include <bits/stdc++.h>
    240 
    241 using namespace std;
    242 
    243 int main() {
    244 #ifdef _DEBUG
    245 	freopen("input.txt", "r", stdin);
    246 //	freopen("output.txt", "w", stdout);
    247 #endif
    248 
    249 	int n;
    250 	scanf("%d", &n);
    251 	vector<int> a(n);
    252 	for (int i = 0; i < n; ++i)
    253 		scanf("%d", &a[i]);
    254 	
    255 	map<int, int> dp;
    256 	
    257 	int ans = 0;
    258 	int lst = 0;
    259 	for (int i = 0; i < n; ++i) {
    260 		int x = a[i];
    261 		dp[x] = dp[x - 1] + 1;
    262 		if (ans < dp[x]) {
    263 			ans = dp[x];
    264 			lst = x;
    265 		}
    266 	}
    267 	
    268 	vector<int> res;
    269 	for (int i = n - 1; i >= 0; --i) {
    270 		if (a[i] == lst) {
    271 			res.push_back(i);
    272 			--lst;
    273 		}
    274 	}
    275 	reverse(res.begin(), res.end());
    276 	
    277 	printf("%d\n", ans);
    278 	for (auto it : res)
    279 		printf("%d ", it + 1);
    280 	puts("");
    281 	
    282 	return 0;
    283 }
    284 ```