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 ```