HSG9 Cà Mau 2026 - Tham quan

Xem dạng PDF

Gửi bài giải

Điểm: 5,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trong quá trình tham gia hội trại, đoàn của An được đưa tới tham quan một khu di tích lịch sử. Tuy nhiên, do số lượng khách tham quan khá đông nên An phải xếp hàng chờ đến lượt vào cổng. Cũng may là có một số người soát vé riêng lẻ, nhưng cũng có nhóm soát vé chung lượt, vì vậy thời gian chờ cũng không quá lâu.

An nhận thấy là những người soát vé chung là cùng một đoàn và mặc áo nhóm với màu giống nhau, đứng liên tiếp trong hàng. Những người soát vé riêng có màu áo không giống người đứng trước (nếu có) và người đứng sau.

Yêu cầu: Từ những quan sát trên An nhẩm tính được lượt thanh toán của mình. Hãy xác định lượt thanh toán của An.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ – số người trong hàng trước An (~1 \le N \le 200~);

  • Dòng thứ ~2~ chứa một xâu chữ cái la tinh in hoa xác định màu áo của ~i~ người trong hàng.

Output

Một số nguyên xác định lượt soát vé của An.

Sample Input 1

6
CCPCZZ

Sample Output 1

5

Notes

Ta xác định lượt soát vé như sau:

  • CC: Lượt ~1~;

  • P: Lượt ~2~;

  • C: Lượt ~3~;

  • ZZ: Lượt ~4~.

Vậy An sẽ được soát vé ở lượt ~5~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    thinhphamminh274  đã bình luận lúc 10, Tháng 11, 2026, 5:27

    PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: THAM QUAN

    1. Phân tích bài toán

    • Đề bài:
      • Có $N$ người xếp hàng trước cổng khu di tích, được biểu diễn bằng một xâu ký tự in hoa $s$ có độ dài $N$. Mỗi ký tự đại diện cho màu áo của một người trong hàng.
      • Những người soát vé chung là cùng một đoàn, mặc áo nhóm cùng màu và đứng liên tiếp nhau trong hàng.
      • Những người soát vé riêng có màu áo khác với người đứng trước và người đứng sau.
      • Cần xác định lượt thanh toán (lượt soát vé) của An (vị trí của An là đứng ngay sau nhóm người cuối cùng trong hàng).
    • Quy luật nhóm soát vé:
      • Mỗi nhóm người có cùng màu áo đứng liên tiếp sẽ được tính là một lượt soát vé.
      • Khi màu áo thay đổi so với người đứng ngay trước đó, một nhóm mới (lượt soát vé mới) bắt đầu.
      • Vị trí (lượt) của An sẽ bằng tổng số các nhóm soát vé cộng thêm 1.

    2. Giải thuật chi tiết

    Bước 1: Đọc dữ liệu
    • Đọc số nguyên $N$ (số người trong hàng).
    • Đọc xâu ký tự $s$ biểu diễn màu áo của $N$ người.
    Bước 2: Khởi tạo và đếm số lượng nhóm
    • Khởi tạo biến kết quả res = 1 (vì ít nhất sẽ có 1 lượt soát vé đầu tiên hoặc tính vị trí của An bắt đầu từ 1 nhóm).
    • Duyệt qua các ký tự của xâu $s$ bằng vòng lặp for:
      • Tại mỗi vị trí $i$, so sánh ký tự hiện tại s[i] với ký tự đứng trước nó s[i-1].
      • Nếu s[i] != s[i-1] (tức là có sự thay đổi về màu áo, đánh dấu sự bắt đầu của một nhóm soát vé mới), ta tăng biến res lên 1 đơn vị (res++).
    Bước 3: In kết quả
    • Sau khi duyệt hết xâu, giá trị của res chính là lượt soát vé của An. In kết quả ra màn hình.

    3. Đánh giá độ phức tạp

    • Độ phức tạp thời gian: $O(N)$ do chỉ sử dụng một vòng lặp duyệt qua toàn bộ xâu có độ dài $N$. Với $N \le 200$, thuật toán chạy cực kỳ nhanh và tối ưu.
    • Độ phức tạp không gian: $O(N)$ để lưu trữ xâu ký tự $s$.
      #include <bits/stdc++.h>
      #define ll long long
      #define Sonic() cin.tie(NULL)->syncwithstdio(0);
      #define el '\n'
      using namespace std;
      
      
      

      int main(){ Sonic(); ll n;cin>>n; string s;cin>>s; ll res=1; for(ll i=0;i<s.size();i++){ if(s[i]!=s[i-1])res++; } cout<<res; return 0; }