1141.md (5260B)
1 Source: https://codeforces.com/blog/entry/66062 2 3 Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round! 4 5 Tutorial is loading... 6 7 **Code** 8 9 ``` 10 int n, m; 11 cin >> n >> m; 12 int result = -1; 13 if (m % n == 0) { 14 result = 0; 15 int d = m / n; 16 while (d % 2 == 0) 17 d /= 2, result++; 18 while (d % 3 == 0) 19 d /= 3, result++; 20 if (d != 1) 21 result = -1; 22 } 23 cout << result << endl; 24 ``` 25 26 Tutorial is loading... 27 28 **Code** 29 30 ``` 31 int n; 32 cin >> n; 33 vector<int> a(n); 34 for (int i = 0; i < n; i++) 35 cin >> a[i]; 36 int result = 0; 37 int len = 0; 38 for (int i = 0; i < 2 * n; i++) { 39 if (a[i % n] == 1) { 40 len++; 41 result = max(result, len); 42 } else { 43 len = 0; 44 } 45 } 46 cout << result << endl; 47 ``` 48 49 Tutorial is loading... 50 51 **Code** 52 53 ``` 54 int n; 55 cin >> n; 56 vector<int> q(n - 1); 57 long long sum = 0; 58 long long min_val = 0; 59 for (int i = 0; i + 1 < n; i++) { 60 cin >> q[i]; 61 sum += q[i]; 62 if (sum < min_val) 63 min_val = sum; 64 } 65 vector<long long> p(n); 66 p[0] = 1 - min_val; 67 forn(i, n - 1) 68 p[i + 1] = p[i] + q[i]; 69 bool ok = true; 70 for (int i = 0; i < n; i++) 71 if (p[i] < 1 || p[i] > n) 72 ok = false; 73 if (ok) 74 ok = set<long long>(p.begin(), p.end()).size() == n; 75 if (ok) { 76 forn(i, n) 77 cout << p[i] << " "; 78 } else 79 cout << -1 << endl; 80 ``` 81 82 Tutorial is loading... 83 84 **Code** 85 86 ``` 87 #define forn(i, n) for (int i = 0; i < int(n); i++) 88 const int A = 26; 89 ... 90 int n; 91 cin >> n; 92 string l; 93 cin >> l; 94 vector<vector<int>> left(A); 95 vector<int> wl; 96 forn(i, n) 97 if (l[i] != '?') 98 left[l[i] - 'a'].push_back(i); 99 else 100 wl.push_back(i); 101 string r; 102 cin >> r; 103 vector<vector<int>> right(A); 104 vector<int> wr; 105 forn(i, n) 106 if (r[i] != '?') 107 right[r[i] - 'a'].push_back(i); 108 else 109 wr.push_back(i); 110 vector<pair<int,int>> p; 111 vector<int> cl(A), cr(A); 112 forn(i, A) { 113 forn(j, min(left[i].size(), right[i].size())) 114 p.push_back(make_pair(left[i][j] + 1, right[i][j] + 1)); 115 cl[i] = cr[i] = min(left[i].size(), right[i].size()); 116 } 117 forn(i, A) 118 while (cl[i] < left[i].size() && !wr.empty()) { 119 p.push_back(make_pair(left[i][cl[i]] + 1, wr[wr.size() - 1] + 1)); 120 cl[i]++; 121 wr.pop_back(); 122 } 123 forn(i, A) 124 while (cr[i] < right[i].size() && !wl.empty()) { 125 p.push_back(make_pair(wl[wl.size() - 1] + 1, right[i][cr[i]] + 1)); 126 wl.pop_back(); 127 cr[i]++; 128 } 129 forn(j, min(wl.size(), wr.size())) 130 p.push_back(make_pair(wl[j] + 1, wr[j] + 1)); 131 cout << p.size() << endl; 132 for (auto pp: p) 133 cout << pp.first << " " << pp.second << endl; 134 ``` 135 136 Tutorial is loading... 137 138 **Code** 139 140 ``` 141 long long H; 142 int n; 143 cin >> H >> n; 144 vector<long long> a(n); 145 long long sum = 0; 146 long long gap = 0; 147 long long h = H; 148 for (int i = 0; i < n; i++) { 149 cin >> a[i]; 150 sum -= a[i]; 151 h += a[i]; 152 if (h <= 0) { 153 cout << i + 1 << endl; 154 return 0; 155 } 156 gap = max(gap, sum); 157 } 158 if (sum <= 0) { 159 cout << -1 << endl; 160 return 0; 161 } 162 163 long long whole = (H - gap) / sum; 164 H -= whole * sum; 165 long long result = whole * n; 166 167 for (int i = 0;; i++) { 168 H += a[i % n]; 169 result++; 170 if (H <= 0) { 171 cout << result << endl; 172 break; 173 } 174 } 175 ``` 176 177 Tutorial is loading... 178 179 Tutorial is loading... 180 181 **Code** 182 183 ``` 184 int n; 185 cin >> n; 186 vector<int> a(n); 187 for (int i = 0; i < n; i++) 188 cin >> a[i]; 189 map<int, vector<pair<int,int>>> segs; 190 for (int r = 0; r < n; r++) { 191 int sum = 0; 192 for (int l = r; l >= 0; l--) { 193 sum += a[l]; 194 segs[sum].push_back({l, r}); 195 } 196 } 197 int result = 0; 198 vector<pair<int,int>> best; 199 for (const auto& p: segs) { 200 const vector<pair<int,int>>& pp = p.second; 201 int cur = 0; 202 int r = -1; 203 vector<pair<int,int>> now; 204 for (auto seg: pp) 205 if (seg.first > r) { 206 cur++; 207 now.push_back(seg); 208 r = seg.second; 209 } 210 if (cur > result) { 211 result = cur; 212 best = now; 213 } 214 } 215 cout << result << endl; 216 for (auto seg: best) 217 cout << seg.first + 1 << " " << seg.second + 1 << endl; 218 ``` 219 220 Tutorial is loading... 221 222 **Code** 223 224 ``` 225 int n, k, r; 226 vector<vector<pair<int,int>>> g; 227 int D; 228 vector<int> col; 229 230 void dfs(int u, int p, int f) { 231 int color = 0; 232 for (auto e: g[u]) 233 if (p != e.first) { 234 if (color == f) { 235 color = (color + 1) % D; 236 f = -1; 237 } 238 col[e.second] = color; 239 dfs(e.first, u, color); 240 color = (color + 1) % D; 241 } 242 } 243 244 int main() { 245 cin >> n >> k; 246 g.resize(n); 247 vector<int> d(n); 248 for (int i = 0; i + 1 < n; i++) { 249 int x, y; 250 cin >> x >> y; 251 x--, y--; 252 g[x].push_back({y, i}); 253 g[y].push_back({x, i}); 254 d[x]++, d[y]++; 255 } 256 map<int,int> cnt; 257 for (int dd: d) 258 cnt[dd]++; 259 260 int kk = n; 261 D = 0; 262 for (auto p: cnt) 263 if (kk > k) 264 D = p.first, 265 kk -= p.second; 266 else 267 break; 268 col = vector<int>(n - 1); 269 dfs(0, -1, -1); 270 cout << D << endl; 271 for (int i = 0; i + 1 < n; i++) 272 cout << col[i] + 1 << " "; 273 } 274 ```