VOI 08 Bài 1 - Trò chơi với dãy số
Xem dạng PDFHai 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
0
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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; }
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.
Đây là hướng giải của mình bằng c++,thấy hay cho xin ^ nha:
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.