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

Điểm: 0,07 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

VOI 2008

Dạng bài

Ngôn ngữ cho phép

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

Copy

2
1 -2
2 3

Sample Output

Copy

Bình luận

Hãy đọc nội quy trước khi bình luận.

-5

truonghovuviet đã bình luận 2:23:19 ch, 19/12/2024 ← sửa 3 →

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

leminhhoang16112012 đã bình luận 3:36:24 ch, 08/12/2024

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; }

2

quanbao29060 đã bình luận 3:41:51 ch, 20/11/2024

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.

93

PDNAM đã bình luận 4:28:53 sa, 05/09/2023 ← sửa 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ả

-16

DTAN đã bình luận 6:06:29 sa, 10/10/2023

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

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

PDNAM đã bình luận 12:02:12 ch, 10/10/2023

:>>>

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-9

PDNAM đã bình luận 3:02:52 sa, 17/08/2023 ← chỉnh sửa →

yeah hết tle r

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-34

chonnhan123 đã bình luận 1:21:04 ch, 16/03/2023 ← sửa 4 →

help

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-28

hthai đã bình luận 4:20:34 ch, 14/08/2023

two pointers

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-73

Dannyplusplus đã bình luận 1:49:43 ch, 24/09/2022

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

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-84

minhphannq đã bình luận 5:57:42 sa, 17/09/2022

332321

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.