Tutorial is loading...
Code (by arsijo)
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
cout << min(a + 2, min(b + 1, c)) * 3 - 3;
}
Tutorial is loading...
Code
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
int main() {
int N; cin >> N;
vector<pii> O(N), T(N);
for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;
for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;
sort(O.begin(),O.end());
sort(T.begin(),T.end());
reverse(T.begin(),T.end());
vector<pii> Ans(N);
for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};
sort(Ans.begin(),Ans.end());
cout << Ans[0].x << ' ' << Ans[0].y << endl;
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
ll N; cin >> N;
vector<ll> ans;
for (ll i = 1; i*i <= N; ++i) {
if (N%i==0) {
ans.push_back(N*(i-1)/2 + i);
if (i*i!=N) {
ans.push_back(N*(N/i-1)/2 + N/i);
}
}
}
sort(ans.begin(),ans.end());
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " \n"[i==ans.size()-1];
}
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
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;}
inline ui inv(ui a){return pow(a,N-2);}
public:
inline Field(int x = 0) : v(x) {}
inline Field<N> pow(int p){return (*this)^p; }
inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
inline bool operator==(const Field<N>&o) const { return o.v==v; }
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
inline explicit operator ui() const { return v; }
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;}
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;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}
typedef Field<998244353> FF;
int main(int argc, char* argv[]) {
int n; cin >> n;
auto F = FF::fact(n);
auto I = FF::invfact(n);
FF ans = n * F[n];
for (int i = 1; i < n; ++i) ans -= F[n]*I[i];
cout << ans << endl;
}
Tutorial is loading...
Code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 500000
int N;
int A[MAXN];
long long sum;
#define TOO_SMALL -1
#define OK 0
#define TOO_BIG 1
int is_score(int value) {
vector<int> C(N+1,0);
for (int i = 0; i < N; ++i) ++C[A[i]];
++C[value];
int less = 0;
long long left = 0, right = 0;
for (int k = 0, i = 0; k <= N; k++) {
int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];
left += val;
--C[val];
right -= min(val, k);
less += C[k];
right += N-k-less;
if (left > right + (long long)(k+1)*k) {
return (i == k) ? TOO_BIG : TOO_SMALL;
}
}
return OK;
}
int main(int,char**) {
ios_base::sync_with_stdio(false);
scanf("%d", &N);
sum = 0;
for (int i = 0; i < N; i++) {
scanf("%d", A + i);
sum += A[i];
}
sort(A,A+N,greater<int>());
int parity = sum & 1;
int lo = 0, hi = (N - parity) / 2, lores = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_SMALL) {
lo = mid + 1;
} else {
lores = mid;
hi = mid - 1;
}
}
lo = lores;
hi = (N - parity) / 2;
int hires = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_BIG) {
hi = mid - 1;
} else {
hires = mid;
lo = mid + 1;
}
}
if (lores == -1 || hires == -1) printf("-1\n");
else {
for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);
printf("\n");
}
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <string>
typedef long long ll;
using namespace std;
int main() {
int N; cin >> N;
vector<ll> L(N);
for (ll &l: L) cin >> l;
string T; cin >> T;
bool hadWater = false;
ll time = 0, stamina = 0, twiceGrass = 0;
for (int i = 0; i < N; ++i) {
if (T[i] == 'L') {
time += L[i];
stamina -= L[i];
if (stamina < 0) {
/* not enough stamina, walk or swim "in place" to gain it */
time -= stamina * (hadWater ? 3 : 5);
stamina = 0;
}
} else if (T[i] == 'W') {
hadWater = true;
stamina += L[i];
time += 3 * L[i];
} else {
stamina += L[i];
time += 5 * L[i];
twiceGrass += 2*L[i];
}
/* no more than stamina/2 of walking can be converted to flying to save time,
* otherwise there would not be enough stamina at this point */
twiceGrass = min(twiceGrass, stamina);
}
if (stamina > 0) {
// convert walking to flying
time -= (5-1) * twiceGrass/2;
// convert swimming to flying
time -= (3-1) * (stamina - twiceGrass)/2;
}
cout << time << endl;
}
Tutorial is loading...
Code (by winger)
import random
def isPrime(n):
"""
Miller-Rabin primality test.
A return value of False means n is certainly not prime. A return value of
True means n is very likely a prime.
"""
if n!=int(n):
return False
n=int(n)
#Miller-Rabin test for prime
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:
return False
if n==2 or n==3 or n==5 or n==7:
return True
s = 0
d = n-1
while d%2==0:
d>>=1
s+=1
assert(2**s * d == n-1)
def trial_composite(a):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
return False
return True
for i in range(20):#number of trials
a = random.randrange(2, n)
if trial_composite(a):
return False
return True
def gcd(x, y):
return x if y == 0 else gcd(y, x % y)
n = int(input())
divs = [n]
def split(parts):
global divs
divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]
while not all([isPrime(x) for x in divs]):
x = random.randint(0, n - 1)
g = gcd(n, x)
if gcd(n, x) != 1:
split([g, n // g])
continue
y = int(input('sqrt {}\n'.format(x * x % n)))
if x == y:
continue
a, b = abs(x - y), x + y
g = gcd(x, y)
split([a // g, b // g, g])
print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))
Tutorial is loading...
Code
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
struct Sieve : public std::vector<bool> {
// ~10ns * n
explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {
at(0) = false;
if (n!=0) at(1) = false;
for (ui i = 2; i*i <= n; ++i) {
if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;
}
}
vector<int> primes() const {
vector<int> ans;
for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);
return ans;
}
private:
int n;
};
constexpr int M = 2e5;
auto P = Sieve{M}.primes();
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
vector<int> G(M, 0);
int Q = P.size();
for (int i = 0; i < Q; ++i) {
for (int j = i; j < Q; ++j) {
if (ll(P[i])*P[j] >= M) break;
P.push_back(P[i]*P[j]);
}
}
bitset<M> PB;
for (int p : P) PB[p] = true;
int N, F; cin >> N >> F;
PB[F] = false;
vector<bitset<M>> W(100);
W[0] = PB;
for (int i = 1; i < M; ++i) {
while (W[G[i]][i]) G[i]++;
W[G[i]] |= PB << i;
}
cerr << *max_element(G.begin(),G.end()) << endl;
int g = 0;
for (int i = 0; i < N; i++) {
int r,w,b;
cin >> r >> w >> b;
g ^= G[w-r-1];
g ^= G[b-w-1];
}
if (g == 0) {
cout << "Bob\nAlice\n";
} else {
cout << "Alice\nBob\n";
}
}