Tutorial
Tutorial is loading...
Solution (Vovuh)
n, k = map(int, input().split())
print((k + n - 1) // n)
Tutorial
Tutorial is loading...
Solution (Vovuh)
q = int(input())
for i in range(q):
n, m, k = map(int, input().split())
if (n < m): n, m = m, n
if (n % 2 != m % 2):
k -= 1
n -= 1
elif (n % 2 != k % 2):
k -= 2
n -= 1
m -= 1
print(-1 if k < n else k)
Tutorial
Tutorial is loading...
Solution with combinatorics (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long C[20][20];
long long pw[4];
long long cnk(int n, int k){
if (k < 0 || k > n) return 0;
return C[n][k];
}
long long get(int n, int lft){
long long tot = 0;
forn(i, lft + 1)
tot += cnk(n, i) * pw[i];
return tot;
}
long long calc(long long x){
string s = to_string(x);
long long res = 0;
int cur = 3;
int n = s.size();
forn(i, n){
if (s[i] == '0') continue;
res += get(n - i - 1, cur);
--cur;
if (cur == -1) break;
res += get(n - i - 1, cur) * (s[i] - '1');
}
return res;
}
int main() {
forn(i, 20){
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729;
int T;
scanf("%d", &T);
forn(i, T){
long long L, R;
scanf("%lld%lld", &L, &R);
printf("%lld\n", calc(R + 1) - calc(L));
}
return 0;
}
Solution with precalc (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
vector<long long> res;
void brute(int pos, int cnt, long long cur){
if (pos == 18){
res.push_back(cur);
return;
}
brute(pos + 1, cnt, cur * 10);
if (cnt < 3)
for (int i = 1; i <= 9; ++i)
brute(pos + 1, cnt + 1, cur * 10 + i);
}
int main() {
brute(0, 0, 0);
res.push_back(1000000000000000000);
int T;
scanf("%d", &T);
forn(i, T){
long long L, R;
scanf("%lld%lld", &L, &R);
printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L)));
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = 300 * 1000 + 9;
int n, m;
int a[N], b[N];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", a + i);
scanf("%d", &m);
for(int i = 0; i < m; ++i) scanf("%d", b + i);
long long sum = 0;
for(int i = 0; i < n; ++i) sum += a[i];
for(int i = 0; i < m; ++i) sum -= b[i];
if(sum != 0){
puts("-1");
return 0;
}
int posa = 0, posb = 0;
int res = 0;
while(posa < n){
++res;
long long suma = a[posa++], sumb = b[posb++];
while(suma != sumb){
if(suma < sumb) suma += a[posa++];
else sumb += b[posb++];
}
}
printf("%d\n", res);
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 1000 + 7;
struct seg{
int x1, y1, x2, y2;
seg(){};
};
struct line{
long long A, B, C;
line(){};
line(seg a){
A = a.y1 - a.y2;
B = a.x2 - a.x1;
C = -A * a.x1 - B * a.y1;
};
};
int n;
seg a[N];
int get(seg a){
int dx = a.x1 - a.x2;
int dy = a.y1 - a.y2;
return __gcd(abs(dx), abs(dy)) + 1;
}
long long det(long long a, long long b, long long c, long long d){
return a * d - b * c;
}
bool in(int x, int l, int r){
if (l > r) swap(l, r);
return (l <= x && x <= r);
}
bool inter(seg a, seg b, int& x, int& y){
line l1(a), l2(b);
long long dx = det(l1.C, l1.B, l2.C, l2.B);
long long dy = det(l1.A, l1.C, l2.A, l2.C);
long long d = det(l1.A, l1.B, l2.A, l2.B);
if (d == 0)
return false;
if (dx % d != 0 || dy % d != 0)
return false;
x = -dx / d;
y = -dy / d;
if (!in(x, a.x1, a.x2) || !in(y, a.y1, a.y2))
return false;
if (!in(x, b.x1, b.x2) || !in(y, b.y1, b.y2))
return false;
return true;
}
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
int ans = 0;
int x, y;
forn(i, n){
ans += get(a[i]);
set<pair<int, int>> pts;
forn(j, i)
if (inter(a[i], a[j], x, y))
pts.insert({x, y});
ans -= pts.size();
}
printf("%d\n", ans);
return 0;
}
1036F - Relatively Prime Powers
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int K = 100;
const int N = 100 * 1000 + 13;
const long long INF64 = 3e18;
int mu[K];
void precalc(){
static bool prime[K];
static int lst[K];
memset(prime, false, sizeof(prime));
forn(i, K) lst[i] = i;
for (int i = 2; i < K; ++i){
if (lst[i] == i) mu[i] = 1;
for (int j = 2 * i; j < K; j += i){
lst[j] = min(lst[j], lst[i]);
if (lst[j] == lst[i])
mu[j] = 0;
else
mu[j] = -mu[i];
}
}
}
int mx[K];
long long binpow(long long a, int b){
long long res = 1;
while (b){
if (b & 1){
if (res < INF64 / a) res *= a;
else return INF64;
}
if (b > 1){
if (a < INF64 / a) a *= a;
else return INF64;
}
b >>= 1;
}
return res;
}
long long calc(long long n){
int pw = 63 - __builtin_clzll(n);
for (int i = 3; i <= pw; ++i){
if (mu[i] == 0) continue;
while (binpow(mx[i], i) > n)
--mx[i];
}
long long res = n - 1;
for (int i = 2; i <= pw; ++i)
res -= mu[i] * (mx[i] - 1);
return res;
}
int get_sqrt(long long n){
int l = 1, r = 1000000000;
while (l < r - 1){
int m = (l + r) / 2;
if (m * 1ll * m <= n)
l = m;
else
r = m;
}
return (r * 1ll * r <= n ? r : l);
}
long long ans[N];
int main() {
precalc();
int T;
scanf("%d", &T);
vector<pair<long long, int>> q;
forn(i, T){
long long n;
scanf("%lld", &n);
q.push_back({n, i});
}
sort(q.begin(), q.end(), greater<pair<long long, int>>());
mx[3] = 1000000;
mx[4] = 31622;
mx[5] = 3981;
for (int i = 6; i < K; ++i)
mx[i] = 1000;
forn(z, T){
long long n = q[z].first;
mx[2] = get_sqrt(n);
ans[q[z].second] = calc(n);
}
forn(i, T)
printf("%lld\n", ans[i]);
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 1000043;
vector<int> g[N];
vector<int> gt[N];
vector<int> src;
vector<int> snk;
int reach[20];
int used[N];
void dfs(int x)
{
if(used[x]) return;
used[x] = 1;
for(auto y : g[x]) dfs(y);
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 0; i < n; i++)
{
if(g[i].empty())
snk.push_back(i);
if(gt[i].empty())
src.push_back(i);
}
int cnt = src.size();
for(int i = 0; i < cnt; i++)
{
memset(used, 0, sizeof used);
dfs(src[i]);
for(int j = 0; j < cnt; j++)
if(used[snk[j]])
reach[i] ^= (1 << j);
}
bool ok = true;
for(int mask = 0; mask < (1 << cnt); mask++)
{
int res = 0;
for(int j = 0; j < cnt; j++)
if(mask & (1 << j))
res |= reach[j];
int cnt1 = __builtin_popcount(mask);
int cnt2 = __builtin_popcount(res);
if(cnt2 < cnt1 || (cnt2 == cnt1 && cnt1 != 0 && cnt1 != cnt))
ok = false;
}
if(!ok)
puts("NO");
else
puts("YES");
}