codeforces-scrape

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

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 ![](https://espresso.codeforces.com/b70d9507011b4794910ebe8899d07c67f6260cd6.png) 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*.