691.md (7957B)
1 Source: https://codeforces.com/blog/entry/46075 2 3 ### [691A - Fashion in Berland](/contest/691/problem/A "Educational Codeforces Round 14") 4 5 The problem was suggested and prepared by Arthur Jaworski [KingArthur](/profile/KingArthur "Expert KingArthur"). 6 7 In this problem you should simply check the conditions from the problem statement. 8 9 **С++ solution** 10 11 ``` 12 const int N = 1010; 13 14 int n, a[N]; 15 16 bool read() { 17 if (!(cin >> n)) return false; 18 forn(i, n) assert(cin >> a[i]); 19 return true; 20 } 21 22 void solve() { 23 int cnt = accumulate(a, a + n, 0); 24 if (n == 1) puts(cnt == 1 ? "YES" : "NO"); 25 else puts(cnt == n - 1 ? "YES" : "NO"); 26 } 27 ``` 28 29 Complexity: *O*(*n*). 30 31 ### [691B - s-palindrome](/contest/691/problem/B "Educational Codeforces Round 14") 32 33 The problem was suggested by Nikita Melnikov [nickmeller](/profile/nickmeller "Pupil nickmeller"). 34 35 In this problem you should simply find the symmetric letters by picture and also observe that the pairs (*b*, *d*) and (*p*, *q*) is the symmteric reflections. 36 37 **C++ solution** 38 39 ``` 40 string s; 41 42 bool read() { 43 return !!getline(cin, s); 44 } 45 46 string symmetric = "AHIMOoTUVvWwXxY"; 47 map<char, char> opposite = {{'p', 'q'}, {'q', 'p'}, {'d', 'b'}, {'b', 'd'}}; 48 49 void solve() { 50 forn(i, sz(s)) { 51 if (symmetric.find(s[i]) != string::npos) { 52 if (s[sz(s) - 1 - i] != s[i]) { 53 puts("NIE"); 54 return; 55 } 56 } else if (opposite.count(s[i])) { 57 if ((sz(s) & 1) && i == (sz(s) >> 1)) { 58 puts("NIE"); 59 return; 60 } 61 if (s[sz(s) - 1 - i] != opposite[s[i]]) { 62 puts("NIE"); 63 return; 64 } 65 } else { 66 puts("NIE"); 67 return; 68 } 69 } 70 puts("TAK"); 71 } 72 ``` 73 74 Complexity: *O*(*n*). 75 76 ### [691C - Exponential notation](/contest/691/problem/C "Educational Codeforces Round 14") 77 78 The problem was suggsted by user [blowUpTheStonySilence](/profile/blowUpTheStonySilence "Expert blowUpTheStonySilence"). 79 80 This is an implementation problem. You should do exactly what is written in the problem statement. On my mind the simplest way is to find the position of the first not zero digit and the position of the dot. The difference between that positions is the value of *b* (if the value is positive you should also decrease it by one). 81 82 **C++ solution** 83 84 ``` 85 string s; 86 87 bool read() { 88 return !!getline(cin, s); 89 } 90 91 void solve() { 92 int pos = int(find_if(all(s), [](char c) { return c != '0' && c != '.'; }) - s.begin());; 93 size_t dot_pos = s.find('.'); 94 if (dot_pos == string::npos) { 95 dot_pos = s.size(); 96 } else { 97 s.erase(dot_pos, 1); 98 } 99 100 int expv = (int) dot_pos - pos; 101 if (expv > 0) expv--; 102 forn(t, 2) { 103 while (s.back() == '0') s.pop_back(); 104 reverse(all(s)); 105 } 106 if (sz(s) > 1) s.insert(1, "."); 107 if (expv == 0) printf("%s\n", s.c_str()); 108 else printf("%sE%d\n", s.c_str(), expv); 109 } 110 ``` 111 112 Complexity: *O*(*n*). 113 114 ### [691D - Swaps in Permutation](/contest/691/problem/D "Educational Codeforces Round 14") 115 116 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 117 118 Consider a graph with *n* vertices whose edges is the pairs from the input. It's possible to swap any two values with the positions in some connected component in that graph. So we can sort the values from any component in decreasing order. Easy to see that after sorting the values of each component we will get the lexicographically maximal permutation. 119 120 **C++ solution** 121 122 ``` 123 const int N = 1200300; 124 125 int n, m; 126 int p[N]; 127 pti a[N]; 128 129 bool read() { 130 if (!(cin >> n >> m)) return false; 131 forn(i, n) { 132 assert(scanf("%d", &p[i]) == 1); 133 p[i]--; 134 } 135 forn(i, m) { 136 assert(scanf("%d%d", &a[i].x, &a[i].y) == 2); 137 a[i].x--, a[i].y--; 138 } 139 return true; 140 } 141 142 bool used[N]; 143 vector<int> g[N]; 144 vector<int> perm, pos; 145 146 void dfs(int v) { 147 if (used[v]) return; 148 used[v] = true; 149 pos.pb(v); 150 perm.pb(p[v]); 151 152 for (auto to : g[v]) dfs(to); 153 } 154 155 int ans[N]; 156 157 void solve() { 158 forn(i, n) { 159 g[i].clear(); 160 used[i] = false; 161 } 162 163 forn(i, m) { 164 g[a[i].x].pb(a[i].y); 165 g[a[i].y].pb(a[i].x); 166 } 167 168 int cnt = 0; 169 forn(i, n) 170 if (!used[i]) { 171 cnt++; 172 pos.clear(); 173 perm.clear(); 174 dfs(i); 175 sort(all(pos)); 176 sort(all(perm), greater<int>()); 177 forn(j, sz(perm)) 178 ans[pos[j]] = perm[j]; 179 } 180 181 forn(i, n) { 182 if (i) putchar(' '); 183 printf("%d", ans[i] + 1); 184 } 185 puts(""); 186 } 187 ``` 188 189 Complexity: *O*(*n* + *m*). 190 191 ### [691E - Xor-sequences](/contest/691/problem/E "Educational Codeforces Round 14") 192 193 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 194 195 Let *z**ij* be the number of xor-sequences of length *i* with the last element equal to *a**j*. Let *g**ij* be equal to one if  contains the number of ones in binary presentation that is multiple of three. Otherwise let *g**ij* be equal to zero. Consider a vectors *z**i* = {*z**ij*}, *z**i* - 1 = {*z**i* - 1, *j*} and a matrix *G* = {*g**ij*}. Easy to see that *z**i* = *G* × *z**i* - 1. So *z**n* = *G**n**z*0. Let's use the associative property of matrix multiplication: at first let's calculate *G**n* with binary matrix exponentiation and then multiply it to the vector *z*0. 196 197 **C++ solution** 198 199 ``` 200 const int N = 101; 201 202 int n; 203 li k; 204 li a[N]; 205 206 bool read() { 207 if (!(cin >> n >> k)) return false; 208 forn(i, n) assert(cin >> a[i]); 209 return true; 210 } 211 212 const int mod = 1000 * 1000 * 1000 + 7; 213 214 inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } 215 inline void inc(int& a, int b) { a = add(a, b); } 216 inline int mul(int a, int b) { return int(a * 1ll * b % mod); } 217 218 int count(li x) { 219 int ans = 0; 220 while (x) { 221 ans++; 222 x &= x - 1; 223 } 224 return ans; 225 } 226 227 void mul(int a[N][N], int b[N][N], int n) { 228 static int c[N][N]; 229 forn(i, n) 230 forn(j, n) { 231 c[i][j] = 0; 232 forn(k, n) inc(c[i][j], mul(a[i][k], b[k][j])); 233 } 234 forn(i, n) forn(j, n) a[i][j] = c[i][j]; 235 } 236 237 void bin_pow(int a[N][N], li b, int n) { 238 static int ans[N][N]; 239 forn(i, n) forn(j, n) ans[i][j] = i == j; 240 241 while (b) { 242 if (b & 1) mul(ans, a, n); 243 mul(a, a, n); 244 b >>= 1; 245 } 246 247 forn(i, n) forn(j, n) a[i][j] = ans[i][j]; 248 } 249 250 void solve() { 251 static int a[N][N]; 252 memset(a, 0, sizeof(a)); 253 forn(i, n) { 254 forn(j, n) 255 a[i][j] = count(::a[i] ^ ::a[j]) % 3 == 0; 256 a[i][n] = 1; 257 } 258 259 //forn(i, n + 1) clog << mp(a[i], n + 1) << endl; 260 261 bin_pow(a, k, n + 1); 262 263 int ans = 0; 264 forn(i, n + 1) inc(ans, a[i][n]); 265 cout << ans << endl; 266 } 267 ``` 268 269 Complexity: *O*(*n*3*logk*). 270 271 ### [691F - Couple Cover](/contest/691/problem/F "Educational Codeforces Round 14") 272 273 The problem was suggested by Michael Kirsche [mkirsche](/profile/mkirsche "Grandmaster mkirsche"). 274 275 Let's count the number of pairs with multiple less than *p*. To get the number of not less pairs we should sumply subtract from *n*·(*n* - 1) the number of less pairs. Let *cnt**i* be the number of values in *a* equal to *i* and *z**j* be the number of pairs from *a* with the multiple equal to *j*. To calculate the values from *z* we can use something like Eratosthenes sieve: let's iterate over the first multiplier *a* and the multiple of it *b* = *ka* and increment *z**b* by the value *cnt**a*·*cnt**k*. After calculating the array *z* we should calculate the array of its partial sums and find the number of less pairs in *O*(1) time. 276 277 **C++ solution** 278 279 ``` 280 const int N = 3100300; 281 282 int n, m; 283 int a[N], p[N]; 284 285 bool read() { 286 if (!(cin >> n)) return false; 287 forn(i, n) assert(scanf("%d", &a[i]) == 1); 288 assert(cin >> m); 289 forn(i, m) assert(scanf("%d", &p[i]) == 1); 290 return true; 291 } 292 293 int cnt[N]; 294 li z[N]; 295 296 void solve() { 297 memset(cnt, 0, sizeof(cnt)); 298 299 forn(i, n) cnt[a[i]]++; 300 301 fore(a, 1, N) { 302 if (!cnt[a]) continue; 303 for (int b = a; b < N; b += a) { 304 if (b / a != a) z[b] += li(cnt[a]) * cnt[b / a]; 305 else z[b] += li(cnt[a]) * (cnt[a] - 1); 306 } 307 } 308 309 fore(i, 1, N) z[i] += z[i - 1]; 310 311 forn(i, m) { 312 li ans = li(n) * (n - 1) - z[p[i] - 1]; 313 printf("%lld\n", ans); 314 } 315 } 316 ``` 317 318 Complexity: *O*(*n* + *XlogX*), where *X* is the maximal value in *p*.