Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бодолт илгээх Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

ULB201501 - Блок

 

Бат Болд хоёр блокоор байшин барьж тоглож байгаа ба ингэхдээ тэр хоёр хоёулаа тус тусдаа сондгой тооны N ширхэг байшин цувуулан барив. Батын барьж байгаа байшингуудыг эхнээс нь mi гэж дугаарлаад мөн Болдын байшингуудыг si гэж дугаарлая (1 <= i <= N).


            Тэр хоёр өөрсдийн барьсан байшингуудаа бүгдийг нь харгалзан si болон miнь тэнцүү өндөртэй болгохоор шийдэв. Ингэхдээ дараах дүрмийг барина:


            Байшингуудын зүүн талаас эхлэх ба эхлээд бүх байшингуудын өндрүүдийг эрс буурах байдлаар болгоод хамгийн голын байшин хүрсний дараа дараачийн байшингуудын өндрийг эрс өсөх байдлаар өөрчлөхөөр болов. Ингэхдээ мөн дурын дараалсан хоёр байшингийн өндрийн зөрөөг 1 байлгана. Доорх зургаас тодорхой харна уу.




            Ямар нэгэн байшингийн өндрийг өөрчлөхдөө тухайн байшингийн дээрээс нь нэг блок аваад хаяж болно (үүнийгээ дахин ашиглахгүй) эсвэл уутнаас шинэ блок гаргаж тухайн байшингийн дээр нь давхарлаж тавих гэсэн 2 үйлдэл зөвшөөрөгдсөн (саванд хангалттай тооны блок байгаа гэж үз).


            Таны даалгавар бол Бат Болд хоёрын тус тусдаа барьсан байшингуудын өндрүүд өгөгдсөн (хамгийн зүүн талаасаа) бол дээр дурьдсан байдлаар байшингуудаа өөржлөхөд хийгдэх хамгийн бага үйлдлийн тоог олох явдал юм.


 


Оролт:


Оролтын файлын эхний мөрөнд сондгой N (1 <= N <= 300 000) буюу Бат Болд хоёрын тус тусдаа барьж буй байшингуудын тоо.


Дараачийн хоёр мөрт тус бүр N тоо байх ба энэ нь эхлээд Батын барьсан байшингуудын өндрүүд зүүн талаасаа эхлэн өгөгдөнө mi. Дараа нь Болдын барьсан байшингуудын өндрүүд мөн зүүн талаасаа эхлэн өгөгдөнө si.


(0 <= mi<= 1012) (0 <= si<= 1012).


Гаралт:


Бодлогын хариу болох ганц тоо.


 


Жишээнүүд:








Оролт




Оролт








3


1 2 3


3 2 2




5


2   3 0 1 4


3   3 2 3 1


 








Гаралт




Гаралт








3




10








 


Тайлбар:


1-р жишээн дээр Бат эхний байшин дээрээ 2 блок тавина харин Болд 3 дахь байшин дээрээ нэг блок тавихад адилхан болно.
Submit solution!
Нэмсэн:munkhbat
Огноо:2016-04-14
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:Бүгд дараах хэлүүдээс бусад: ASM64 NCSHARP GOSU JS-MONKEY JULIA PYPY3
hide comments
2024-02-11 10:43:08
#include <bits/stdc++.h>
using namespace std;

long long count(long long n, vector<long long>& a, vector<long long>& b, long long m) {
int mid = n / 2;
long long c = abs(m - a[mid]) + abs(m - b[mid]);
int L = mid - 1;
int R = mid + 1;
m++;
while (L >= 0) {
c += abs(m - a[L]);
c += abs(m - a[R]);
c += abs(m - b[L]);
c += abs(m - b[R]);
L--; m++;
R++;
}
return c;
}

int main() {
int n;
cin >> n;
vector<long long> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
long long L = 0;
long long R = 1e13;
while (L < R - 2) {
long long k = (R - L) / 3;
long long m1 = L + k;
long long m2 = L + 2 * k;
long long v1 = count(n, a, b, m1);
long long v2 = count(n, a, b, m2);
if (v1 == v2) {
L = m1;
R = m2;
} else if (v1 < v2) {
R = m2;
} else {
L = m1;
}
}
long long ans = count(n, a, b, L);
for(int i = L + 1; i <= R; i++) {
ans = min(count(n, a, b, i), ans);
}
cout << ans;
}
2024-01-28 15:43:31
#include <bits/stdc++.h>
using namespace std;

long long count(long long n, vector<long long>& a, vector<long long>& b, long long m) {
int mid = n / 2;
long long c = abs(m - a[mid]) + abs(m - b[mid]);
int L = mid - 1;
int R = mid + 1;
m++;
while (L >= 0) {
c += abs(m - a[L]);
c += abs(m - a[R]);
c += abs(m - b[L]);
c += abs(m - b[R]);
L--; m++;
R++;
}
return c;
}

int main() {
int n;
cin >> n;
vector<long long> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
long long L = 0;
long long R = 1e13;
while (L < R - 2) {
long long k = (R - L) / 3;
long long m1 = L + k;
long long m2 = L + 2 * k;
long long v1 = count(n, a, b, m1);
long long v2 = count(n, a, b, m2);
if (v1 == v2) {
L = m1;
R = m2;
} else if (v1 < v2) {
R = m2;
} else {
L = m1;
}
}
long long ans = count(n, a, b, L);
for(int i = L + 1; i <= R; i++) {
ans = min(count(n, a, b, i), ans);
}
cout << ans;
}
2019-06-19 13:10:29
ternary search

Last edit: 2019-08-28 10:49:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.