CANDY BOXES

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
dang7rickroll
Dạng bài
Điểm: 250 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn Lan có vô tận những viên kẹo. Các viên kẹo được đánh số \(1,2,...\).

Sau đó, Lan lần lượt bỏ các viên kẹo vào \(n\) hộp kẹo, sao cho hộp thứ \(i\) chứa được \(a_i\) viên kẹo.

Yêu cầu: Có \(Q\) truy vấn, mỗi truy vấn sẽ đặt ra một số nguyên \(k\) là thứ tự của \(1\) viên kẹo. Hãy cho biết viên kẹo thứ \(k\) này đang nằm trong hộp nào?

Input

  • Dòng đầu ghi \(n\) không quá \(10^5\).
  • Dòng thứ hai ghi \(n\) số nguyên dương \(a_1,a_2,...,a_n\) được sắp xếp tăng dần.
  • Dòng thứ ba ghi số nguyên dương \(Q\) không quá \(10^5\).
  • \(Q\) dòng tiếp theo, mỗi dòng ghi số nguyên \(k\) không quá \((1+2...+n)\)

Output

  • Ứng với truy vấn thứ \(x\), in ra thứ tự của hộp kẹo đang chứa viên kẹo thứ \(x\).

Example

Test 1

Input 
3
1 2 3
2
1
5
Output 
1
3

Bình luận


  • 23
    Who_you_knows_Who    9:19 a.m. 23 Tháng 1, 2022 ← chỉnh sửa 6

    Spoiler Alert

    Hình ảnh minh họa thuật toán:

    Hint 1: < Cày trâu >

    • Vì các viên kẹo được đánh số 1, 2, ... nên ta có thể đơn giản hóa bài toán như sau:
    • k là số viên kẹo.
    • Bỏ kẹo lần lượt vào các hộp kẹo từ 1 -> n đến khi kẹo hết.
    • Thứ tự của hộp kẹo cuối cùng được bỏ sẽ là kết quả.
      if(k > a[i]) k -= a[i];
      else {
      cout << i << endl;
      break;
      }
      Full Code
      | O(N * Q) | 70% - 80% Test | TLE
      #include<bits/stdc++.h>
      using namespace std;
      long long a[1000000];
      int main ()
      {
      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
      long long n, q, k;
      cin >> n;
      for(int i = 1; i <= n; i ++) cin >> a[i];
      cin >> q;
      while(q --)
      {
      cin >> k;
      for(int i = 1; i <= n; i ++)
      {
      if (k > a[i]) k -= a[i];
      else
      {
      cout << i << endl;
      break;
      }
      }
      }
      }

    Hint 2: < Chặt nhị phân >
    - Tương tự việc bỏ kẹo vào các hộp kẹo như cày trâu.
    - Tạo một mảng tổng lưu giá trị tổng số viên kẹo từ hộp kẹo thứ 1 -> i.
    - Chặt nhị phân mảng tổng để tìm vị trí.

    Nếu các bạn chưa biết thuật toán chặt nhị phân, các bạn có thể tham khảo: Tại đây.

    Minh họa giữa chặt nhị phân và cày trâu:

    Full code
    | O (Q * (log(2, N) | 100% Test | AC
    #include<bits/stdc++.h>
    using namespace std;
    long long a[1000000];
    long long s[1000000];
    int main ()
    {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long n, q, k;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
    cin >> q;
    while(q --)
    {
    cin >> k;
    long long l = 1, r = n;
    while (l <= r)
    {
    long long g = (l + r) / 2;
    if (k <= s[g]) r = g - 1;
    else l = g + 1;
    }
    cout << l << endl;
    }
    }

    Nếu các bạn có thắc mắc gì thì có thể ib riêng cho mình: Tại đây