VOI 08 Bài 1 - Trò chơi với dãy số

Points: 0.07 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

VOI 2008

Problem types

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm ~n~ số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:

~b_1, b_2, \dots, b_n~

còn dãy số mà bạn thứ hai chọn là:

~c_1, c_2, \dots, c_n~

Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng ~b_{i}~ ~(1 \leq i \leq n)~, còn bạn thứ hai đưa ra số hạng ~c_{j}~ ~(1 \leq j \leq n)~ thì giá của lượt chơi đó sẽ là ~|b_{i} + c_{j}|~.

Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \leq 10^{5})~
Dòng thứ hai chứa dãy số nguyên ~b_1, b_2, \dots, b_n~ ~(|b_{i}| \leq 10^{9}, i = 1, 2, ..., n)~
Dòng thứ ba chứa dãy số nguyên ~c_1, c_2, \dots, c_n~ ~(|c_{i}| \leq 10^{9}, i = 1, 2, ..., n)~

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra giá nhỏ nhất tìm được.

Giới hạn

60% số tests ứng với 60% số điểm của bài có ~(1 \leq n \leq 1000)~.

Sample Input

2
1 -2
2 3

Sample Output

Comments

Please read the guidelines before commenting.

-4

ngoccaidu2008 commented on Oct. 29, 2025, 2:36 p.m.

Bài cũng khá cơ bản:

code tham khảo:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int maxn=5+1e5;
int n,ans=LLONG_MAX;
int a[maxn],b[maxn];
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for (int i=1;i<=n;i++)
    {
        auto k=lower_bound(b+1,b+n+1,-a[i]);
        if (k==b+n+1) ans=min(ans,abs(a[i]+b[n]));
        else if (k!=b+1) ans=min(ans,min(abs(a[i]+b[k-b]),abs(a[i]+b[k-b-1])));
        else ans=min(ans,abs(a[i]+b[1]));
    }cout<<ans;
}

-7

dothupcb commented on Oct. 16, 2025, 3:02 p.m.

de vai cut

This comment is hidden due to too much negative feedback. Show it anyway.

6

NguyenQuyK58A commented on Sept. 12, 2025, 2:05 p.m.

Bạn nào bị sai 1 test thì dùng long long nha

3

thaihsgserk60 commented on Aug. 20, 2025, 2:26 p.m.

include <bits/stdc++.h>

using namespace std; int main(){ int n;cin >>n; int a[n]; int b[n]; for(int i=0;i<n;i++) cin >>a[i]; for(int j=0;j<n;j++) cin >>b[j]; sort(b,b+n); int MIN=1e9; for(int i=0;i<n;i++){ auto it=lower_bound(b,b+n,-a[i]); if(it!=b+n){ MIN=min(MIN,abs(it+a[i])); } if(it!=b){ it-=1; MIN=min(MIN,abs(it+a[i])); } } cout <<MIN<<'\n'; return 0; } an 14/15 test sai o dau a

-10

THPTHD_Hieu commented on May 13, 2025, 8:10 a.m.

trò chơi với số dãy

This comment is hidden due to too much negative feedback. Show it anyway.

-12

RussVN123 commented on May 13, 2025, 12:10 p.m.

Trời cho với sãy dố !!

This comment is hidden due to too much negative feedback. Show it anyway.

-9

phunguyengia0809 commented on July 23, 2025, 4:20 a.m.

aothatday

This comment is hidden due to too much negative feedback. Show it anyway.

-18

truonghovuviet commented on Dec. 19, 2024, 2:23 p.m. ← edit 3 →

This comment is hidden due to too much negative feedback. Show it anyway.

-11

leminhhoang16112012 commented on Dec. 8, 2024, 3:36 p.m.

include <bits/stdc++.h>

using namespace std;

define ll long long

ll cs10[18]; ll f[18]; int len(ll x) { int ans = 0; while (x) { ans++; x = x / 10; } return ans; } ll cut(ll x) { int l = len(x); for(int i = 1; i<= l/2; i++) x = x/10; return x; } ll dx(int l, ll x) { int ld = len(x), cuoi=x; while(ld> l/2) { cuoi = cuoi/10; ld--; } while(cuoi) { x = x * 10 + cuoi %10; cuoi= cuoi/10; } return x; } int main() { f[1]=9; f[2]=9; cs10[0]=1; cs10[1]=10; for(int i =2; i <= 18; i++) { f[i] =f[i-2]10; cs10[i] = cs10[i-1]10; } ll x = 123456789; ll l = len(x); ll ans =0; for(int i = 1; i <=n-1; i++) ans = ans+f[i]; ll dau = cut(x), cuoi = dau; ll dxx = dx(l, x); if(dxx <= x) ans = ans + (dau - cs10[len(dau)]+1); else ans = ans + (dau - cs10[len(dau)]) cout << ans; return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

5

quanbao29060 commented on Nov. 20, 2024, 3:41 p.m.

Hướng giải của mình thì các bạn sort thằng a sau đó với mỗi b tìm tổng nhỏ nhất bằng lower_bound. Mình chỉ gợi ý thế thôi mn tham khảo.

126

PDNAM commented on Sept. 5, 2023, 4:28 a.m. ← edit 2 →

Đây là hướng giải của mình bằng c++,thấy hay cho xin ^ nha:

ta thấy đối với b[i] thì |b[i]+c[j]| bé nhất là khi c[j] là phần tử bé nhất trong mảng c mà => -(b[i]) hoặc số lớn nhất trong mảng c mà < -(b[i])

vậy nên ta chỉ cần sort b và c ,rồi tìm giá trị |b[i]+c[j]| bằng hai con trỏ vì với mọi c[j]lớn hơn b[i] thì cũng sẽ lớn hơn b[i-1]

đặt j=n rồi for(i=n->1){ tìm c[j]đầu tiên mà <=b[i];tính kết quả = max của kết quả và max(abs(b[i]-c[j],abs(b[i]-c[j+1]) } nếu kết quả =0 thì break;

cuối cùng là in ra kết quả

-27

DTAN commented on Oct. 10, 2023, 6:06 a.m.

Bạn pro quá không biết bạn còn nhận đệ tử không. :))

This comment is hidden due to too much negative feedback. Show it anyway.

-22

PDNAM commented on Oct. 10, 2023, 12:02 p.m.

:>>>

This comment is hidden due to too much negative feedback. Show it anyway.

-6

PDNAM commented on Aug. 17, 2023, 3:02 a.m. ← edited →

yeah hết tle r

This comment is hidden due to too much negative feedback. Show it anyway.

-41

chonnhan123 commented on March 16, 2023, 1:21 p.m. ← edit 4 →

help

This comment is hidden due to too much negative feedback. Show it anyway.

-37

hthai commented on Aug. 14, 2023, 4:20 p.m.

two pointers

This comment is hidden due to too much negative feedback. Show it anyway.

-82

Dannyplusplus commented on Sept. 24, 2022, 1:49 p.m.

Sai 1 test 12 :( bác nào biết không cứu em

This comment is hidden due to too much negative feedback. Show it anyway.

-97

minhphannq commented on Sept. 17, 2022, 5:57 a.m.

332321

This comment is hidden due to too much negative feedback. Show it anyway.