roseKindergarten

NHÀ TRẺ HOA HỒNG PHIÊU LƯU KÝ – PHẦN 1

“Trừ các bài khó ra, bài nào cũng dễ.” – Nhà giáo thông thái NVL

 Là một nhà giáo thông thái, thầy NVL luôn tập trung vào việc tuyển sinh những nhân tài trẻ của đất nước, và đưa họ tới ngôi trường cổ tích – Nhà trẻ Hoa Hồng. Hàng năm, có hàng trăm sĩ tử muốn đến thử sức xem bản thân có thể nhập học vào trường hay không, khiến thầy vô cùng đau đầu khi phải xem hết một đống bài thi. Vì vậy thầy quyết định, thay vì kiểm tra tự luận như các trường khác, thầy sẽ cho các thí sinh làm trắc nghiệm. Vì trắc nghiệm của thầy toàn những câu hỏi hóc búa, mà thầy chỉ thích bài đúng trọn vẹn, nên nhiều thí sinh quen biết đã hợp tác với nhau để làm bài. Vì rất ghét việc chép bài, thầy đưa ra một hệ thống gọi là “Chỉ số quen biết”. Chỉ số quen biết là một hệ thống vô cùng phức tạp, được biểu thị bằng 2 mã:

• Nếu bạn thứ i quen biết bạn thứ i+1 thì chỉ số quen biết của i là 1.
• Ngược lại, nếu bạn thứ i không quen biết bạn thứ i+1 thì chỉ số quen biết của i là 0.

Nếu hai thí sinh i và i+1 đều ra đáp án đúng mà i quen biết i+1, cả hai bạn đều sẽ bị loại khỏi kì thi, vì thầy cho rằng hai bạn có hành vi gian lận.

Cho đáp án của bài thi là 1 chuỗi x. Cho 1 tập ans có n phiếu trả lời của các thí sinh dưới dạng 1 chuỗi các chữ cái biểu diễn đáp án, và 1 tập relationship có n-1 phần tử là chỉ số quen biết giữa 2 bạn a[i] và a[i+1]. Hãy giúp nhà giáo thông thái NVL biết có bao nhiêu người đã vượt qua kì thi một cách công bằng nhất.

Ví dụ:

• Với đáp án gốc x = "ACBDA", đáp án của thí sinh ans = {"ACBDA","CDABD","ACBDA","ACBDA","ACBDA"}, chỉ số quen biết relationship = {0,1,1,0} thì output RoseKindergarten = 2.
  Bạn 1 có câu trả lời đúng nên được qua.
  Bạn 2 có câu trả lời sai.
  Bạn 3 và 4 có câu trả lời đúng, tuy nhiên vì hai bạn quen biết nhau nên bị loại vì gian lận.
  Bạn 5 có câu trả lời như bạn 4, nhưng vì bạn 4 không quen bạn 5 nên bạn 5 qua.

Đầu vào/Đầu ra:

• [Thời gian] 0.2s với C++, 1.2s với Java và C#, 1.6s với Python, Go và JavaScript.
• [Đầu vào] String x
  Đáp án đúng của bài thi.
  1 ≤ x.length() ≤ 10000
  [Đầu vào] Array of Strings ans
  Đáp án của các thí sinh. Đảm bảo tất cả các đáp án đều trả lời đủ số câu hỏi.
  0 ≤ ans.size() ≤ 10000
ans[i].length() = x.length()
  [Đầu vào] Array of Integers relationship
  Chỉ số quen biết của các thí sinh.
  relationship.size() = ans.size()
0 ≤ relationship[i] ≤ 1
• [Đầu ra] Integer
  Số thí sinh vượt qua bài kiểm tra.