Bạn được cung cấp một chuỗi s. Mỗi ký tự là 0 hoặc 1. Bạn muốn tất cả các số 1 trong chuỗi tạo thành một phân đoạn liền kề. Ví dụ: nếu chuỗi là 0, 1, 00111 hoặc 01111100, thì tất cả 1 đều tạo thành một phân đoạn liền kề và nếu chuỗi là 0101, 100001 hoặc 11111111111101 thì điều kiện này không được đáp ứng. Bạn có thể xóa một số 0 (có thể không cần xóa) khỏi chuỗi. Số 0 tối thiểu mà bạn phải xóa là bao nhiêu?

Đầu vào: Dòng đầu tiên chứa một số nguyên t (1≤t≤100) - số lượng trường hợp kiểm tra. Sau đó t dòng tiếp theo, mỗi dòng đại diện cho một trường hợp thử nghiệm. Mỗi dòng chứa một chuỗi s (1≤ | s |<=100); mỗi ký tự của s là 0 hoặc 1.

Đầu ra: In số nguyên t, trong đó số nguyên thứ i là câu trả lời cho mẫu thử thứ i (số tối thiểu là 0 mà bạn phải xóa khỏi s).

Input:

3
010011
0
1111000

Output:

2
0
0

Số điện thoại là một chuỗi có đúng 11 chữ số, trong đó chữ số đầu tiên là 8. Ví dụ: dãy 80011223388 là số điện thoại, nhưng các dãy 70011223388 và 80000011223388 thì không. Bạn được cung cấp một chuỗi s có độ dài n, bao gồm các chữ số. Trong một thao tác, bạn có thể xóa bất kỳ ký tự nào khỏi chuỗi s. Ví dụ: có thể lấy các chuỗi 112, 111 hoặc 121 từ chuỗi 1121. Bạn cần xác định xem có một chuỗi các hoạt động như vậy (có thể là không), sau đó chuỗi s trở thành số điện thoại.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên t (1≤t≤100) - số lượng trường hợp kiểm tra. Dòng đầu tiên của mỗi trường hợp chứa một số nguyên n (1≤n≤100) - độ dài của chuỗi s.
• Dòng thứ hai gồm n là độ dài chuỗi s và chuỗi số s.

Đầu ra:

• Đối với mỗi bài kiểm tra in một dòng.
• Nếu có một chuỗi các hoạt động, sau đó s trở thành một số điện thoại, in YES. Nếu không, in NO.

Input:

2
13
7818005553535
11
31415926535

Output:

YES
NO

Bạn được cung cấp một chuỗi s = s1 s2 …. sn có độ dài n, chỉ chứa các chữ số 1, 2, ..., 9. Một chuỗi con s [l...r] của s là một chuỗi liên tiếp bắt đầu từ vị trí l tới vị trí r ở trong chuỗi ban đầu. Một chuỗi con s[l … r] của s ngay cả khi nó là một chuỗi rỗng. Tìm số lượng các chuỗi con là số chẵn của s. Lưu ý rằng ngay cả khi một số chuỗi con giống nhau, nhưng có l và r khác nhau, chúng được tính là các chuỗi con khác nhau.

Đầu vào:

• Dòng đầu tiên chứa số nguyên n (1≤n≤65000) - độ dài của chuỗi s.
• Dòng thứ hai chứa một chuỗi s có độ dài n. Chuỗi s chỉ bao gồm các chữ số 1, 2, ..., 9.

Đầu ra: In số lượng các phần tử chẵn của s.

Input:

4
1234

Output:

6

Axe và Lina đang cố gắng đồng bộ hai chuỗi mật mã A và B sao cho chúng giống hệt nhau. Để làm được việc này, họ được cung cấp thêm một chuỗi mật mã thứ ba là C đóng vai trò là "chìa khóa hoán đổi". Cả 3 chuỗi này đều có cùng độ dài.

Luật chơi như sau:

• Bạn sẽ đi dọc theo các chuỗi từ trái sang phải. Tại mỗi vị trí, bạn BẮT BUỘC phải lấy ký tự của chuỗi C để tráo đổi với ký tự của chuỗi A HOẶC tráo đổi với ký tự của chuỗi B.

(Lưu ý: Không được phép giữ nguyên, bắt buộc phải tráo C với A hoặc tráo C với B).

Yêu cầu: Sau khi đi hết toàn bộ chuỗi và thực hiện xong các phép tráo đổi, liệu bạn có thể làm cho chuỗi A và chuỗi B trở nên giống y hệt nhau được không?

Dữ liệu vào (Input):

• Dòng đầu tiên chứa số nguyên T (1 <= T <= 100) – số lượng câu hỏi.

• Mỗi câu hỏi gồm 3 dòng, lần lượt là 3 chuỗi A, B, C (chỉ gồm các chữ cái in thường, độ dài tối đa 100 ký tự).

Dữ liệu ra (Output):

• In ra YES nếu có cách tráo đổi để chuỗi A giống hệt chuỗi B.

• Nếu không có cách nào, in ra NO.

Ví dụ minh họa:

Input:

2
abc
bca
bca
imi
mii
iim

Output:

YES
NO

Nikolay có một chuỗi s có độ dài bằng n, chỉ bao gồm các chữ cái Latinh viết thường 'a' và 'b'. Vị trí của nó được đánh số từ 1 đến n. Anh ta muốn sửa đổi chuỗi của mình sao cho mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau. Để đạt được điều đó, Nikolay có thể thực hiện thao tác sau tùy ý số lần (có thể là cần thực hiện thao tác nào):

Chọn một số vị trí trong chuỗi của mình và thay thế chữ cái trên vị trí này bằng chữ cái khác (nghĩa là thay 'a' bằng 'b' hoặc thay thế ' b 'với' a ').

Nikolay không thể sử dụng chữ cái nào ngoại trừ 'a' và 'b'. Tiền tố của chuỗi s có độ dài l (1≤l≤n) là một chuỗi s [1..l].

Ví dụ: đối với chuỗi s = "abba", có hai tiền tố có độ dài chẵn. Đầu tiên là s [1..2] = "ab" và s thứ hai [1...4] = "abba". Cả hai đều có cùng số 'a' và 'b'.

Nhiệm vụ của bạn là tính toán số lượng hoạt động tối thiểu Nikolay phải thực hiện với chuỗi s để sửa đổi nó để mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau.

Đầu vào:

• Dòng đầu tiên của đầu vào chứa một số nguyên n chẵn (2≤n≤2⋅10^5) - độ dài của chuỗi s.
• Dòng thứ hai của đầu vào chứa chuỗi s có độ dài n, chỉ bao gồm các chữ cái Latinh viết thường 'a' và 'b'.

Đầu ra:

• Trong dòng đầu tiên, số lượng hoạt động tối thiểu Nikolay phải thực hiện với chuỗi s để sửa đổi nó để mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau.
• Trong dòng thứ hai in chuỗi Nikolay có được sau khi áp dụng tất cả các thao tác. Nếu có nhiều câu trả lời, bạn có thể in bất kỳ câu trả lời nào.

Input:

4
bbbb

Output:

2
abab

Trong vũ trụ siêu anh hùng, một người có tên là S muốn sử dụng phép thuật để biến hình, giả dạng thành một siêu anh hùng khác có tên là T. Tuy nhiên, phép biến hình này phải tuân thủ nghiêm ngặt Quy luật Cấu trúc Ký tự.

Trong thế giới này, các chữ cái được chia làm 2 hệ:

• Hệ Nguyên âm: Bao gồm 5 chữ cái a, e, i, o, u.

• Hệ Phụ âm: Bao gồm tất cả các chữ cái tiếng Anh in thường còn lại.

Để biến hình thành công từ tên S sang tên T, hai cái tên này bắt buộc phải thỏa mãn 2 điều kiện sau:

1. Khớp độ dài: Tên S và tên T phải có số lượng chữ cái bằng nhau.

2. Khớp hệ ký tự: Tại bất kỳ vị trí tương ứng nào, một Nguyên âm chỉ có thể biến thành một Nguyên âm (hoặc giữ nguyên), và một Phụ âm chỉ có thể biến thành một Phụ âm (hoặc giữ nguyên). Tuyệt đối không thể biến Nguyên âm thành Phụ âm hoặc ngược lại.

Yêu cầu: Cho trước hai cái tên S và T. Hãy kiểm tra xem phép biến hình này có thể thành công hay không?

Dữ liệu vào (Input):

• Dòng 1: Chứa chuỗi S (độ dài từ 1 đến 1000 ký tự).

• Dòng 2: Chứa chuỗi T (độ dài từ 1 đến 1000 ký tự). (Đảm bảo hai chuỗi luôn khác nhau và chỉ chứa các chữ cái in thường).

Dữ liệu ra (Output):

• In ra Yes nếu phép biến hình hợp lệ.

• In ra No nếu phép biến hình thất bại.

Ví dụ minh họa:

Input:

abc
ukm

Output:

Yes

Alice có một chuỗi s. Cô ấy thực sự thích chữ "a". Cô gọi một chuỗi là tốt nếu hơn một nửa số ký tự trong chuỗi đó là "a". Ví dụ: "aaabb", "axaa" là các chuỗi tốt và "baca", "awwwa", "" (chuỗi trống) thì không. Alice có thể xóa một số ký tự khỏi chuỗi s của mình. Cô ấy muốn biết chuỗi dài nhất còn lại là gì sau khi xóa một số ký tự (có thể bằng 0) để có được chuỗi được coi là tốt. Nó được đảm bảo rằng chuỗi có ít nhất một "a" trong đó, vì vậy câu trả lời luôn tồn tại.

Đầu vào: Nhập vào một chuỗi s (1≤ | s |<= 50) bao gồm các chữ cái tiếng Anh viết thường. Nó được đảm bảo rằng có ít nhất một "a" trong s.

Đầu ra: In một số nguyên duy nhất, độ dài của chuỗi tốt nhất dài nhất mà Alice có thể nhận được sau khi xóa một số ký tự khỏi s.

Input:

xaxxxxa

Output:

3

Keanu Reeves đang mắc kẹt trong thế giới ảo Ma Trận. Để chứng minh mình đang ở trong thế giới ảo, anh cần giải quyết một bài toán với chuỗi mật mã chỉ gồm các chữ số 0 và 1.

Trong thế giới này, một chuỗi mật mã được gọi là "Chuỗi An Toàn" nếu số lượng chữ số 0 và số lượng chữ số 1 trong chuỗi đó KHÁC NHAU. Ví dụ: Các chuỗi 1, 101, 0000 là an toàn. Các chuỗi 01, 1001, 111000 không an toàn (vì số lượng chữ số 0 bằng với số lượng chữ số 1).

Nhiệm vụ của bạn: Bạn được cấp một chuỗi mật mã S ban đầu. Bạn hãy cắt chuỗi S này thành ÍT ĐOẠN NHẤT có thể, sao cho TẤT CẢ các đoạn sau khi cắt đều là "Chuỗi An Toàn".

Lưu ý:

• Nếu chuỗi S ban đầu đã an toàn sẵn, bạn không cần cắt (tức là số đoạn cắt được k = 1).

• Nếu có nhiều cách cắt tạo ra số đoạn tối thiểu giống nhau, bạn có thể in ra bất kỳ cách nào.

Dữ liệu vào (Input):

• Dòng 1: Chứa một số nguyên N (1 <= N <= 100) là độ dài của chuỗi S.

• Dòng 2: Chứa chuỗi S có độ dài N (chỉ gồm các ký tự 0 và 1).

Dữ liệu ra (Output):

• Dòng 1: In ra số nguyên K là số lượng đoạn ít nhất mà bạn cắt được.

• Dòng 2: In ra K đoạn mật mã đó, mỗi đoạn cách nhau một khoảng trắng (dấu cách).

Ví dụ:

Input:

6 
100011

Output:

2 
100 011

Giải thích ví dụ: Chuỗi 100011 có 3 số '0' và 3 số '1' (không an toàn). Ta cắt thành 2 đoạn là 100 (có 2 số '0', 1 số '1') và 011 (có 1 số '0', 2 số '1'). Cả 2 đoạn này đều an toàn và đây là cách cắt tạo ra ít đoạn nhất.

Bạn được cung cấp một chuỗi mật mã S có độ dài N. Chuỗi này chỉ chứa K loại chữ cái viết hoa đầu tiên trong bảng chữ cái tiếng Anh (ví dụ: nếu K = 3, chuỗi sẽ chỉ chứa 3 loại chữ cái là A, B và C).

Từ chuỗi S ban đầu, bạn có thể rút trích ra một "chuỗi con" bằng cách chọn ra một số chữ cái và giữ nguyên thứ tự ban đầu của chúng (nói cách khác, bạn được quyền xóa bớt một số chữ cái bị thừa). Ví dụ: Với chuỗi gốc là "ABCDE", bạn có thể tạo ra chuỗi con "ADE" hoặc "BD", nhưng không thể tạo ra chuỗi "DEA" vì nó bị ngược thứ tự.

Một chuỗi con được gọi là "Đội Hình Cân Bằng" nếu số lượng của TẤT CẢ K loại chữ cái trong chuỗi đó là HOÀN TOÀN BẰNG NHAU.

Nhiệm vụ của bạn: Hãy tìm cách xóa bớt ký tự sao cho phần còn lại tạo thành một "Đội Hình Cân Bằng" dài nhất có thể. In ra độ dài lớn nhất đó.

Dữ liệu vào (Input):

• Dòng 1: Chứa hai số nguyên N (1 <= N <= 10^5) là độ dài của chuỗi S, và K (1 <= K <= 26) là số loại chữ cái.

• Dòng 2: Chứa chuỗi S có độ dài N (chỉ gồm K loại chữ cái viết hoa đầu tiên).

Dữ liệu ra (Output):

• In ra một số nguyên duy nhất là độ dài của "Đội Hình Cân Bằng" dài nhất tìm được.

Ví dụ:

Input:

9 3 
ACAABCCAB

Output:

6

Vasya mới tập làm quen với bàn phím máy tính và vừa tham gia vào một phòng chat trực tuyến. Cậu ấy muốn gõ từ "hello" để chào mọi người. Tuy nhiên, do luống cuống, ngón tay của Vasya cứ bấm nhầm và lặp phím lung tung, tạo ra một xâu ký tự S lộn xộn.

Mọi người trong phòng chat rất thông cảm và quy ước với nhau rằng: Vasya sẽ được coi là đã "nói xin chào" thành công nếu ta có thể xóa đi một vài ký tự trong xâu S (hoặc không xóa ký tự nào) sao cho các ký tự còn lại ghép thành đúng từ "hello" (lưu ý: không được thay đổi thứ tự trước sau của các ký tự còn lại).

Yêu cầu: Cho xâu ký tự S mà Vasya vừa gõ, hãy kiểm tra xem cậu ấy có "nói xin chào" thành công hay không.

Dữ liệu vào (Input):

• Gồm một dòng duy nhất chứa xâu S mà Vasya đã gõ. Xâu chỉ bao gồm các chữ cái in thường, độ dài tối thiểu là 1 và tối đa là 100 ký tự.

Dữ liệu ra (Output):

• In ra YES nếu Vasya nói xin chào thành công.

• Ngược lại, in ra NO.

Ví dụ 1:

Input:

ahhellllloou

Output:

YES

Ví dụ 2:

Input:

hlelo

Output:

NO

Việc dịch thuật từ tiếng Berland sang tiếng Birland thực ra lại vô cùng thú vị. Hai ngôn ngữ này có một sợi dây liên kết rất đặc biệt: một từ trong tiếng Birland chính là cách viết đảo ngược hoàn toàn của từ đó trong tiếng Berland!

Ví dụ: Từ code trong tiếng Berland khi dịch sang tiếng Birland sẽ được đánh vần ngược lại thành edoc.

Tuy quy tắc cực kỳ đơn giản, nhưng gõ phím nhanh thì vẫn rất dễ mắc lỗi. Vasya vừa dịch một từ S (tiếng Berland) thành từ T (tiếng Birland). Bạn hãy lập trình giúp Vasya kiểm tra xem cậu ấy đã dịch chính xác 100% hay chưa nhé.

Yêu cầu: Cho hai xâu ký tự S và T. Hãy kiểm tra xem T có phải là xâu đảo ngược hoàn toàn của S hay không.

Dữ liệu vào (Input):

• Dòng đầu tiên chứa từ S (từ gốc tiếng Berland).

• Dòng thứ hai chứa từ T (bản dịch tiếng Birland).

• Cả hai từ chỉ bao gồm các chữ cái in thường, không chứa dấu cách thừa. Độ dài mỗi từ tối thiểu là 1 và tối đa là 100 ký tự.

Dữ liệu ra (Output):

• In ra YES nếu từ T chính xác là từ S viết ngược lại.

• Nếu sai dù chỉ một ký tự hoặc sai độ dài, in ra NO.

Ví dụ 1:

Input:

code
edoc

Output:

YES

Ví dụ 2: Input:

#

abb
aba

Output:

NO

Anton và cậu bạn thân Danik đều là những người đam mê cờ vua mãnh liệt. Trong một buổi giao lưu, họ đã chơi liên tục n ván cờ (với trình độ một chín một mười, không có ván cờ nào kết thúc với tỉ số hòa).

Sau một chuỗi trận đấu trí căng thẳng, cả hai đều hoa mắt chóng mặt và không nhớ rõ ai đang dẫn trước. Bạn được cung cấp một cuốn sổ ghi chép lại kết quả của từng ván đấu. Hãy lập trình để thống kê và phân định xem ai mới là nhà vô địch thực sự nhé!

Yêu cầu: Đếm số lượng ván thắng của mỗi người và đưa ra kết quả chung cuộc.

Dữ liệu vào (Input):

Dòng đầu tiên chứa một số nguyên dương n (1 <= n <= 100000) — tổng số ván cờ đã chơi.

Dòng thứ hai chứa một xâu ký tự S bao gồm đúng n chữ cái in hoa (chỉ gồm các ký tự 'A' và 'D').

Ký tự 'A' có nghĩa là Anton thắng ván đó.

Ký tự 'D' có nghĩa là Danik thắng ván đó.

Dữ liệu ra (Output):

In ra Anton nếu Anton giành được nhiều ván thắng hơn Danik.

In ra Danik nếu Danik giành được nhiều ván thắng hơn Anton.

In ra Friendship (Tình bạn) nếu hai người có số ván thắng bằng nhau.

Ví dụ 1:

Input:

5
AAADD

Output:

Anton

(Giải thích: Trong 5 ván cờ, Anton thắng 3 ván, Danik chỉ thắng 2 ván. Chung cuộc Anton là người chiến thắng).

Ví dụ 2:

Input:

6
ADAAAA

Output:

Anton

Ví dụ 3:

Input:

6
DADADA

Output:

Friendship

(Giải thích: Mỗi người đều giành được đúng 3 ván thắng, kết quả chung cuộc là hòa).