let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

Codechef July 17 - Chef and Sign Sequences

solution.md

Tóm tắt đề

Cho dãy các dấu >, <, =, tìm số P nhỏ nhất sao cho ta có thể điền các số nguyên trong đoạn [1, P] vào dãy dấu trên sao cho mỗi dấu đều có 2 số kề bên, và dãy số được điền vào là dãy đúng. Ví dụ:

  • Dãy dấu: <<<, dãy số sau khi điền: 1<2<3<4, P = 4
  • <=>, 1<2=2>1, P = 2

Cách giải

Đầu tiên ta cần loại hết các dấu = để dễ xử lí. Sau đó đếm các dấu < liên tiếp, các dấu > liên tiếp rồi xuất kết quả dựa trên mảng đếm.

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        vector<char> a;
        for (auto c: s) if (c != '=') a.push_back(c);
        int n = (int)a.size();
        if (n == 0) cout << "1\n";
        else {
            vector<int> l(n);
            l[0] = 2;
            for (int i=1; i<n; i++) {
                if (a[i] == a[i-1]) l[i] = l[i-1] + 1;
                else l[i] = 2;
            }
            cout << *max_element(l.begin(), l.end()) << '\n';
        }
    }
    return 0;
}
Comments