Coin

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ả:
admin
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

An tự cho rằng mình có khả năng điều khiển các vật ở ngoài xa. Tuyên bố này khiến Na bị sốc, vốn là một người theo chủ nghĩa duy lý xác nhận, ngay lập tức Na muốn An phải chứng minh khả năng này.
An quyết định tung một đồng xu để biểu diễn khả năng của mình. An nói rằng mình có thể làm việc ấy theo cách như này: số mặt ngửa sẽ hơn số mặt sấp đúng \(k\) lần. Na đã viết ra kết quả của các lần tung đồng xu và bây giờ ông muốn tìm ra chuỗi dài nhất các lần tung xu liên tiếp mà số mặt ngửa gấp số mặt sấp đúng \(k\) lần.

Input

  • Dòng đầu tiên chứa 2 số nguyên \(n\) và \(k\) (\(3 \leq n \leq 10^6, 2 \leq k \leq n - 1\)), \(n\) cho biết số lần tung xu của An trong khi \(k\) đã được mô tả trong yêu cầu của bài.
  • Dòng thứ hai gồm một dãy \(n\) ký tự cho biết kết quả của các lần tung xu liên tiếp. Dãy này gồm các ký tự O và R biểu thị mặt ngửa hoặc mặt sấp.

Output

  • Chỉ có 1 dòng duy nhất chứa 1 số nguyên cho biết độ dài chuỗi dài nhất các lần tung xu liên tiếp mà trong đó số mặt ngửa gấp chính xác \(k\) lần số mặt sấp. Nếu không tồn tại chuỗi như thế thì xuất ra số 0.

Example

Test 1

Input 
17 3
OROOOOOROOOOORRRR
Output 
12

Bình luận


  • 4
    SPyofgame    9:53 a.m. 13 Tháng 6, 2020

    Spoiler Alert

    Hint 1

    • Cách đơn giản nhất là duyệt qua từng đoạn \(1 \leq i \leq j \leq n\)

    Gọi số lượng O trong đoạn là cntO

    Gọi số lượng R trong đoạn là cntR

    Chọn đoạn dài nhất thỏa cntO = cntR * k

    Hint 2

    • Dùng mảng cộng dồn ta có thể tính số lượng O, R trong \(O(1)\)

    Gọi f(n, c) là số lượng kí tự c trong đoạn [1, n]

    Có số lượng kí tự c trong đoạn [l, r] là f(r, c) - f(l - 1, c)

    Hint 3

    • Ta có thể tìm trước i một đoạn nào đó mà sau khi loại nó ra ta sẽ được kết quả cntO = cntR * k

    Gọi cntO là số lượng kí tự O tính từ 1 -> i

    Gọi cntR là số lượng kí tự R tính từ 1 -> i

    Nếu cntO = cntR * k sẵn rồi thì cập nhật res = i

    Nếu cntO - cntR * k tồn tại thì cập nhật res = max(res, vị trí hiện tại - vị trí cuối đoạn con đó)

    Nếu cntO - cntR * k không tồn tại, thì ta đánh dấu vị trí cuối của nó là i

    Reference AC code | O(n) time | O(1) auxiliary space | Online Solving, STL, Equalsum-problem ???

    C++
    int main()
{
    int n, k;
    cin >> n >> k;

    char c;
    while (c = getchar(), c != 'O' && c != 'R');

    unordered_map<long long, int> M;
    int res = 0;
    int cntO = 0, cntR = 0;
    for (int i = 1; i <= n; ++i, c = getchar())
    {
        (c == 'O') ? cntO++ : cntR++;
        long long t = 1LL * cntO - 1LL * cntR * k;

        if (t == 0) res = i;
        if (M[t] != 0)
            res = max(res, i - M[t]);
        else 
            M[t] = i;
    }

    cout << res;
}