codeforces-scrape

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

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