Lũy thừa cơ số 2 - LCOJ: Luyện Code Online Judge

PTIT036 - Lũy thừa cơ số 2

Điểm: 1,00 (OI)

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

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

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một mảng ~a~ gồm ~n~ số nguyên dương được sắp xếp không giảm, và một mảng ~b~ gồm ~m~ số nguyên dương (có thể không được sắp xếp).

Cho biết ~f(i)~ (~1 \le i \le m~) là vị trí tương ứng của phần tử ~b_i~ trên mảng ~a~ (số thứ tự trên các mảng đều đếm từ ~1~, nếu ~b_i~ không xuất hiện ở ~a~ thì ~f(i) = -1~, nếu ~b_i~ xuất hiện nhiều lần trên ~a~ thì lấy số thứ tự nhỏ nhất).

Đặt ~X = \sum_{i=1}^{m} f(i) \mod 30~, yêu cầu của chúng ta là tính ~\lfloor 2^X \rfloor~.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ là kích thước mảng ~a~ (~1 \le n \le 10^5~).
Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~0 \le a_1 \le a_2 \le \ldots \le a_n \le 10^9~).
Dòng thứ ba gồm số nguyên dương ~m~ là kích thước mảng ~b~ (~1 \le m \le 10^5~).
Dòng thứ tư gồm ~m~ số nguyên dương ~b_1, b_2, \ldots, b_m~ (~0 \le b_i \le 10^9~).

Output

In ra một số nguyên duy nhất là kết quả tìm được.

Sample

Input #1

6
1 5 6 7 9 44
2
5 6

Output #1

Input #2

7
1 2 55 487 489 665 687
3
687 666 489

Output #2

Hint

Giải thích test 1: ~5~ là ở vị trí số ~2~ nên ~f(1) = 2~, ~6~ là vị trí số ~3~ nên ~f(2) = 3~. -> kết quả là ~2^{2+3} = 32~.
Giải thích test 2: ~687~ ở vị trí ~7~ nên ~f(1) = 7~, ~666~ không có nên ~f(2) = -1~, ~489~ ở vị trí ~5~ nên ~f(3) = 5~. -> kết quả là ~2^{7-1+5} = 2048~.

Problem source: CLB Lập Trình PTIT

Bình luận

Please read the guidelines before commenting.

hàm có sẵn lower_bound đã giải quyết điều kiện lấy thứ tự nhỏ nhất nếu đúng giá trị; chỉ có khi x < 0 kết quả là phân số, nên nó cũng về 0 thôi ta in ra 0 nếu x < 0;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int maxn = 5e6 + 5;
int n, m; 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n; vector<ll> a(n);
    for (ll &x : a) cin >> x;
    cin >> m; vector<ll> b(m);
    for (ll &x : b) cin >> x;
    auto f = [&](ll i) -> ll {
        ll x = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        if (x >= a.size() || a[x] != b[i]) return -1;
        return x + 1;
    };
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        ans += f(i);
        ans %= 30;
    }
    ll res = (ans >= 0 ? 1 << ans : 0);
    cout << res;
}

6

dinhvantung0611 đã bình luận lúc 11, Tháng 1, 2024, 11:20

Chú ý trường hợp: 0 < 2^(X) < 1 (X < 0): in ra 0 luôn

Và chú ý ra điều kiện đoạn tìm địa chỉ nhỏ nhất của phần tử (binary_search):

i = A[mid]

while (A[i] == A[mid] && i >= 0)

i -= 1;

return i + 2 (do địa chỉ của mảng bắt đầu từ 1)