Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
import kotlin.math.abs
fun sum(a1: Int, a2: Int, b1: Int, b2: Int) = abs(a1 - a2) + abs(b1 - b2)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
val b = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
var sum = 0L
for (i in 1 until n) {
if (sum(a[i - 1], a[i], b[i - 1], b[i]) > sum(a[i - 1], b[i], b[i - 1], a[i]))
a[i] = b[i].also { b[i] = a[i] }
sum += sum(a[i - 1], a[i], b[i - 1], b[i])
}
println(sum)
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
for (v in a) {
var ans = 20
for (cntAdd in 0..15) {
for (cntMul in 0..15) {
if (((v + cntAdd) shl cntMul) % 32768 == 0)
ans = minOf(ans, cntAdd + cntMul)
}
}
print("$ans ")
}
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
int main(){
int tc;
scanf("%d", &tc);
while (tc--) {
int n;
scanf("%d", &n);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
long long ans = 1e18;
int mx = *max_element(a.begin(), a.end());
for (int x : {mx, mx + 1}){
long long cnt1 = 0, cnt2 = 0;
forn(i, n){
cnt2 += (x - a[i]) / 2;
cnt1 += (x - a[i]) % 2;
}
long long dif = max(0ll, cnt2 - cnt1 - 1) / 3;
cnt1 += dif * 2;
cnt2 -= dif;
ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
if (cnt2 > 0){
cnt1 += 2;
--cnt2;
ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
}
}
printf("%lld\n", ans);
}
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
scanf("%d %d", &n, &k);
vector<long long> b(n);
for (auto &it : b) {
scanf("%lld", &it);
}
vector<long long> closed(n);
long long sum = 0, cnt = 0, ans = 0;
for (int i = n - 1; i >= 0; --i) {
sum -= cnt;
cnt -= closed[i];
b[i] -= sum;
if (b[i] <= 0) {
continue;
}
int el = min(i + 1, k);
long long need = (b[i] + el - 1) / el;
sum += need * el;
cnt += need;
ans += need;
if (i - el >= 0) {
closed[i - el] += need;
}
}
printf("%lld\n", ans);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
int main(){
cin.tie(0);
iostream::sync_with_stdio(false);
int n;
cin >> n;
vector<string> s(3);
forn(i, 3) cin >> s[i];
vector<int> pr(n + 1);
forn(i, n){
pr[i + 1] += pr[i];
forn(j, 3) pr[i + 1] += (s[j][i] == '1');
}
vector<int> p(3 * n), rk(3 * n, 1);
iota(p.begin(), p.end(), 0);
function<int(int)> getp;
getp = [&](int a) -> int {
return a == p[a] ? a : p[a] = getp(p[a]);
};
auto unite = [&](int a, int b) -> bool {
a = getp(a), b = getp(b);
if (a == b) return false;
if (rk[a] < rk[b]) swap(a, b);
p[b] = a;
rk[a] += rk[b];
return true;
};
vector<int> prhe(n + 1), prve(n + 1);
forn(j, n){
forn(i, 2) if (s[i][j] == '1' && s[i + 1][j] == '1' && unite(i * n + j, (i + 1) * n + j))
++prve[j + 1];
forn(i, 3) if (j > 0 && s[i][j] == '1' && s[i][j - 1] == '1' && unite(i * n + j, i * n + (j - 1)))
++prhe[j];
}
forn(i, n) prve[i + 1] += prve[i];
forn(i, n) prhe[i + 1] += prhe[i];
vector<int> nxt(n + 1, 0);
for (int i = n - 1; i >= 0; --i)
nxt[i] = (s[0][i] == '1' && s[1][i] == '0' && s[2][i] == '1' ? (nxt[i + 1] + 1) : 0);
int m;
cin >> m;
forn(_, m){
int l, r;
cin >> l >> r;
--l, --r;
int non101 = l + nxt[l];
if (non101 > r){
cout << "2\n";
continue;
}
int tot = pr[r + 1] - pr[non101];
int in = (prve[r + 1] - prve[non101]) + (prhe[r] - prhe[non101]);
int res = tot - in;
if (non101 != l){
if (s[0][non101] == '1' && s[1][non101] == '1' && s[2][non101] == '1');
else if (s[0][non101] == '0' && s[2][non101] == '0') res += 2;
else ++res;
}
cout << res << "\n";
}
return 0;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> lens;
long long sqr(int x)
{
return x * 1ll * x;
}
long long eval_split(int len, int k)
{
return sqr(len / k) * (k - len % k) + sqr(len / k + 1) * (len % k);
}
pair<int, long long> eval_segment(int len, long long bound)
{
// only take options with value >= bound
if(bound <= 2 || len == 1)
return make_pair(len - 1, len);
int lf = 0;
int rg = len - 1;
while(rg - lf > 1)
{
int mid = (lf + rg) / 2;
if(eval_split(len, mid) - eval_split(len, mid + 1) >= bound)
lf = mid;
else
rg = mid;
}
return make_pair(lf, eval_split(len, lf + 1));
}
pair<int, long long> eval_full(long long bound)
{
pair<int, long long> ans;
for(auto x : lens)
{
pair<int, long long> cur = eval_segment(x, bound);
ans.first += cur.first;
ans.second += cur.second;
}
return ans;
}
int main()
{
scanf("%d", &n);
int pr = 0;
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
lens.push_back(x - pr);
pr = x;
}
long long w;
scanf("%lld", &w);
long long lf = 0ll;
long long rg = (long long)(1e18) + 43;
if(eval_full(rg).second <= w)
{
cout << 0 << endl;
return 0;
}
while(rg - lf > 1)
{
long long mid = (lf + rg) / 2;
pair<int, long long> res = eval_full(mid);
if(res.second <= w)
lf = mid;
else
rg = mid;
}
pair<int, long long> resL = eval_full(lf);
pair<int, long long> resR = eval_full(rg);
assert(resL.second <= w && resR.second > w);
long long change = (resR.second - resL.second) / (resR.first - resL.first);
cout << resL.first + (w - resL.second) / change << endl;
}