1091.md (10387B)
1 Source: https://codeforces.com/blog/entry/64196 2 3 Tutorial is loading... 4 5 **Code (by arsijo)** 6 7 ``` 8 #include <bits/stdc++.h> 9 using namespace std; 10 11 int main(){ 12 int a, b, c; 13 cin >> a >> b >> c; 14 cout << min(a + 2, min(b + 1, c)) * 3 - 3; 15 } 16 ``` 17 18 Tutorial is loading... 19 20 **Code** 21 22 ``` 23 #include <vector> 24 #include <algorithm> 25 #include <iostream> 26 27 using namespace std; 28 29 typedef pair<int,int> pii; 30 31 #define x first 32 #define y second 33 34 int main() { 35 int N; cin >> N; 36 vector<pii> O(N), T(N); 37 for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y; 38 for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y; 39 sort(O.begin(),O.end()); 40 sort(T.begin(),T.end()); 41 reverse(T.begin(),T.end()); 42 43 vector<pii> Ans(N); 44 for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y}; 45 sort(Ans.begin(),Ans.end()); 46 cout << Ans[0].x << ' ' << Ans[0].y << endl; 47 } 48 ``` 49 50 Tutorial is loading... 51 52 **Code** 53 54 ``` 55 #include <iostream> 56 #include <vector> 57 #include <algorithm> 58 59 using namespace std; 60 61 typedef long long ll; 62 63 int main() { 64 ll N; cin >> N; 65 vector<ll> ans; 66 67 for (ll i = 1; i*i <= N; ++i) { 68 if (N%i==0) { 69 ans.push_back(N*(i-1)/2 + i); 70 if (i*i!=N) { 71 ans.push_back(N*(N/i-1)/2 + N/i); 72 } 73 } 74 } 75 sort(ans.begin(),ans.end()); 76 77 for (int i = 0; i < ans.size(); ++i) { 78 cout << ans[i] << " \n"[i==ans.size()-1]; 79 } 80 81 } 82 ``` 83 84 Tutorial is loading... 85 86 **Code** 87 88 ``` 89 #include <iostream> 90 #include <vector> 91 92 using namespace std; 93 94 template <unsigned int N> class Field { 95 typedef unsigned int ui; 96 typedef unsigned long long ull; 97 inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;} 98 inline ui inv(ui a){return pow(a,N-2);} 99 public: 100 inline Field(int x = 0) : v(x) {} 101 inline Field<N> pow(int p){return (*this)^p; } 102 inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};} 103 inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; } 104 inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; } 105 inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; } 106 inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); } 107 inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;} 108 inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;} 109 inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;} 110 inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;} 111 inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};}; 112 inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; } 113 inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; } 114 inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; } 115 inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; } 116 inline bool operator==(const Field<N>&o) const { return o.v==v; } 117 inline bool operator!=(const Field<N>&o) const { return o.v!=v; } 118 inline explicit operator ui() const { return v; } 119 inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;} 120 inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;} 121 private: ui v; 122 }; 123 template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;} 124 template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;} 125 template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;} 126 template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;} 127 template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;} 128 template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;} 129 130 typedef Field<998244353> FF; 131 132 int main(int argc, char* argv[]) { 133 int n; cin >> n; 134 auto F = FF::fact(n); 135 auto I = FF::invfact(n); 136 FF ans = n * F[n]; 137 for (int i = 1; i < n; ++i) ans -= F[n]*I[i]; 138 cout << ans << endl; 139 } 140 ``` 141 142 Tutorial is loading... 143 144 **Code** 145 146 ``` 147 #include <iostream> 148 #include <algorithm> 149 #include <vector> 150 using namespace std; 151 152 #define MAXN 500000 153 154 int N; 155 int A[MAXN]; 156 long long sum; 157 158 #define TOO_SMALL -1 159 #define OK 0 160 #define TOO_BIG 1 161 162 int is_score(int value) { 163 vector<int> C(N+1,0); 164 for (int i = 0; i < N; ++i) ++C[A[i]]; 165 ++C[value]; 166 167 int less = 0; 168 long long left = 0, right = 0; 169 for (int k = 0, i = 0; k <= N; k++) { 170 int val = (i == k && (i == N || A[i] < value)) ? value : A[i++]; 171 left += val; 172 --C[val]; 173 right -= min(val, k); 174 less += C[k]; 175 right += N-k-less; 176 if (left > right + (long long)(k+1)*k) { 177 return (i == k) ? TOO_BIG : TOO_SMALL; 178 } 179 } 180 return OK; 181 } 182 183 int main(int,char**) { 184 ios_base::sync_with_stdio(false); 185 186 scanf("%d", &N); 187 sum = 0; 188 for (int i = 0; i < N; i++) { 189 scanf("%d", A + i); 190 sum += A[i]; 191 } 192 193 sort(A,A+N,greater<int>()); 194 int parity = sum & 1; 195 int lo = 0, hi = (N - parity) / 2, lores = -1; 196 while (lo <= hi) { 197 int mid = (lo + hi) / 2; 198 if (is_score(2*mid + parity) == TOO_SMALL) { 199 lo = mid + 1; 200 } else { 201 lores = mid; 202 hi = mid - 1; 203 } 204 } 205 206 lo = lores; 207 hi = (N - parity) / 2; 208 int hires = -1; 209 while (lo <= hi) { 210 int mid = (lo + hi) / 2; 211 if (is_score(2*mid + parity) == TOO_BIG) { 212 hi = mid - 1; 213 } else { 214 hires = mid; 215 lo = mid + 1; 216 } 217 } 218 219 if (lores == -1 || hires == -1) printf("-1\n"); 220 else { 221 for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity); 222 printf("\n"); 223 } 224 } 225 ``` 226 227 Tutorial is loading... 228 229 **Code** 230 231 ``` 232 #include <iostream> 233 #include <vector> 234 #include <string> 235 236 typedef long long ll; 237 using namespace std; 238 239 int main() { 240 int N; cin >> N; 241 vector<ll> L(N); 242 for (ll &l: L) cin >> l; 243 string T; cin >> T; 244 bool hadWater = false; 245 ll time = 0, stamina = 0, twiceGrass = 0; 246 for (int i = 0; i < N; ++i) { 247 if (T[i] == 'L') { 248 time += L[i]; 249 stamina -= L[i]; 250 if (stamina < 0) { 251 /* not enough stamina, walk or swim "in place" to gain it */ 252 time -= stamina * (hadWater ? 3 : 5); 253 stamina = 0; 254 } 255 } else if (T[i] == 'W') { 256 hadWater = true; 257 stamina += L[i]; 258 time += 3 * L[i]; 259 } else { 260 stamina += L[i]; 261 time += 5 * L[i]; 262 twiceGrass += 2*L[i]; 263 } 264 /* no more than stamina/2 of walking can be converted to flying to save time, 265 * otherwise there would not be enough stamina at this point */ 266 twiceGrass = min(twiceGrass, stamina); 267 } 268 269 if (stamina > 0) { 270 // convert walking to flying 271 time -= (5-1) * twiceGrass/2; 272 273 // convert swimming to flying 274 time -= (3-1) * (stamina - twiceGrass)/2; 275 } 276 277 cout << time << endl; 278 } 279 ``` 280 281 Tutorial is loading... 282 283 **Code (by winger)** 284 285 ``` 286 import random 287 288 def isPrime(n): 289 """ 290 Miller-Rabin primality test. 291 292 A return value of False means n is certainly not prime. A return value of 293 True means n is very likely a prime. 294 """ 295 if n!=int(n): 296 return False 297 n=int(n) 298 #Miller-Rabin test for prime 299 if n==0 or n==1 or n==4 or n==6 or n==8 or n==9: 300 return False 301 302 if n==2 or n==3 or n==5 or n==7: 303 return True 304 s = 0 305 d = n-1 306 while d%2==0: 307 d>>=1 308 s+=1 309 assert(2**s * d == n-1) 310 311 def trial_composite(a): 312 if pow(a, d, n) == 1: 313 return False 314 for i in range(s): 315 if pow(a, 2**i * d, n) == n-1: 316 return False 317 return True 318 319 for i in range(20):#number of trials 320 a = random.randrange(2, n) 321 if trial_composite(a): 322 return False 323 324 return True 325 326 def gcd(x, y): 327 return x if y == 0 else gcd(y, x % y) 328 329 n = int(input()) 330 331 divs = [n] 332 333 def split(parts): 334 global divs 335 divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1] 336 337 while not all([isPrime(x) for x in divs]): 338 x = random.randint(0, n - 1) 339 g = gcd(n, x) 340 if gcd(n, x) != 1: 341 split([g, n // g]) 342 continue 343 y = int(input('sqrt {}\n'.format(x * x % n))) 344 if x == y: 345 continue 346 a, b = abs(x - y), x + y 347 g = gcd(x, y) 348 split([a // g, b // g, g]) 349 350 print('!', len(divs), ' '.join(str(d) for d in sorted(divs))) 351 ``` 352 353 Tutorial is loading... 354 355 **Code** 356 357 ``` 358 #include <vector> 359 #include <stack> 360 #include <iostream> 361 #include <algorithm> 362 #include <bitset> 363 using namespace std; 364 365 typedef unsigned int ui; 366 typedef long long ll; 367 368 struct Sieve : public std::vector<bool> { 369 // ~10ns * n 370 explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) { 371 at(0) = false; 372 if (n!=0) at(1) = false; 373 for (ui i = 2; i*i <= n; ++i) { 374 if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false; 375 } 376 } 377 378 vector<int> primes() const { 379 vector<int> ans; 380 for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i); 381 return ans; 382 } 383 384 private: 385 int n; 386 }; 387 388 constexpr int M = 2e5; 389 auto P = Sieve{M}.primes(); 390 391 int main() { 392 ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 393 394 vector<int> G(M, 0); 395 int Q = P.size(); 396 for (int i = 0; i < Q; ++i) { 397 for (int j = i; j < Q; ++j) { 398 if (ll(P[i])*P[j] >= M) break; 399 P.push_back(P[i]*P[j]); 400 } 401 } 402 403 bitset<M> PB; 404 for (int p : P) PB[p] = true; 405 406 int N, F; cin >> N >> F; 407 PB[F] = false; 408 409 vector<bitset<M>> W(100); 410 W[0] = PB; 411 for (int i = 1; i < M; ++i) { 412 while (W[G[i]][i]) G[i]++; 413 W[G[i]] |= PB << i; 414 } 415 cerr << *max_element(G.begin(),G.end()) << endl; 416 417 int g = 0; 418 for (int i = 0; i < N; i++) { 419 int r,w,b; 420 cin >> r >> w >> b; 421 g ^= G[w-r-1]; 422 g ^= G[b-w-1]; 423 } 424 if (g == 0) { 425 cout << "Bob\nAlice\n"; 426 } else { 427 cout << "Alice\nBob\n"; 428 } 429 } 430 ```