HSG9 Cà Mau 2026 - Tham quan
Xem dạng PDFTrong 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
PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: THAM QUAN
1. Phân tích bài toán
2. Giải thuật chi tiết
Bước 1: Đọc dữ liệu
Bước 2: Khởi tạo và đếm số lượng nhóm
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).for:s[i]với ký tự đứng trước nós[i-1].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ếnreslên 1 đơn vị (res++).Bước 3: In kết quả
reschí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