ĐỀ ÔN TẬP XÂU

3. Bài tập chủ đề kiểu dữ liệu chuỗi

Bài 121: Ước chuỗi

Cho một chuỗi S tối đa 100 ký tự, chỉ gồm các chữ cái in thường.

Chuỗi X được gọi là ước của chuỗi S nếu chuỗi X có độ dài ngắn nhất và khi ghép một số lần X ta được chuỗi S.

Ví dụ:

S = "abababab" thì ước của nó là X = "ab".
S = "aaaaaa" thì ước của nó là X = "a".
S = "abc" thì ước của nó là X = "abc".

Cho trước một chuỗi S nhập từ bàn phím, hãy tìm chuỗi X là ước của chuỗi S.

Đầu vào

Một dòng duy nhất chứa chuỗi S.

Đầu ra

Chuỗi X là ước của chuỗi S.

Ví dụ

Đầu vào
abababab

Đầu ra
ab

Đầu vào
abc

Đầu ra
abc

Bài 122: Chuỗi k-string

Một chuỗi được gọi là k-string là chuỗi ký tự có dạng lặp lại k lần một chuỗi nào đó.

Ví dụ:

Chuỗi "hoahoa" được gọi là chuỗi 2-string vì nó là kết quả của việc viết lặp lại 2 lần chuỗi "hoa".
Chuỗi "abababab" vừa là chuỗi 2-string vừa là chuỗi 4-string.
Chuỗi "abc" chỉ là chuỗi 1-string.

Tất nhiên, một chuỗi bất kỳ luôn là chuỗi 1-string.

Cho số nguyên dương k và chuỗi ký tự s, hãy tìm cách sắp xếp lại thứ tự các ký tự trong s để chuỗi kết quả là một chuỗi k-string. Nếu không thể thực hiện được thì in ra số -1.

Đầu vào

Dòng đầu chứa số nguyên k (1 <= k <= 10^3).
Dòng thứ hai chứa chuỗi ký tự s khác rỗng và chỉ gồm các chữ cái tiếng Anh in thường. Độ dài chuỗi s không quá 10^4.

Đầu ra

Nếu có nhiều đáp án thỏa mãn yêu cầu bài toán thì chỉ cần in ra một đáp án bất kỳ.
Ngược lại, nếu không thực hiện được thì in ra số -1.

Ràng buộc

Có 60% số test ứng với 60% điểm với chuỗi s có độ dài không quá 200.

Ví dụ

Đầu vào
2
aabb

Đầu ra
abab

Đầu vào
2
abaa

Đầu ra
-1

Bài 123: Chuỗi dịch vòng

Bạn được cho một chuỗi:

S = S1S2...SN

gồm các chữ số, chữ cái tiếng Anh in thường và in hoa. Tất cả các chuỗi dịch vòng của chuỗi S được liệt kê theo bảng sau:

STT	Chuỗi dịch vòng
1	`S1S2S3...SN`
2	`S2S3...SNS1`
3	`S3...SNS1S2`
...	...
N	`SN...S1S2S3`

Nhiệm vụ của bạn là hãy đưa ra toàn bộ chuỗi dịch vòng của S theo thứ tự như bảng trên.

Đầu vào

Một dòng duy nhất chứa chuỗi S khác rỗng có độ dài không quá 100.

Đầu ra

In ra N dòng, trong đó N là độ dài chuỗi S.
Mỗi dòng ghi một chuỗi dịch vòng của S.

Ví dụ

Đầu vào
abC1

Đầu ra
abC1
bC1a
C1ab
1abC

Chú ý

Phải đưa ra kết quả theo đúng thứ tự, mọi thứ tự khác đưa ra đều không có điểm.

Ví dụ kết quả đưa ra như sau sẽ bị coi là sai:

abC1
C1ab
bC1a
1abC

Bài 124: Chuỗi con

Cho hai chuỗi X và Y chỉ chứa các ký tự chữ cái in hoa.

Trong đó chuỗi X là chuỗi vòng tròn, tức là sau ký tự X1 là X2, sau X2 là X3, ..., sau XN-1 là XN và sau XN là X1.

Hãy đưa ra tất cả các vị trí của chuỗi Y xuất hiện trong chuỗi X.

Đầu vào

Dòng 1 chứa chuỗi X khác rỗng, có độ dài không quá 100.
Dòng 2 chứa chuỗi Y khác rỗng, có độ dài không quá 100.

Đầu ra

In ra tất cả các vị trí xuất hiện chuỗi Y trong chuỗi X.
Các vị trí được in ra theo thứ tự tăng dần trên một dòng.

Ví dụ

Đầu vào
ABCCABC
CAB

Đầu ra
4 7

Bài 125: Chuỗi con đối xứng

Một chuỗi được gọi là đối xứng nếu nó có ít nhất một kí tự và nếu ta đọc từ trái sang phải hay từ phải sang trái đều giống nhau.

Ví dụ:

"A", "TET", "CAOOAC" là các chuỗi đối xứng.
"ABC", "BHABHDC" là các chuỗi không đối xứng.

Cho chuỗi kí tự S, có chiều dài n (1 <= n <= 1000). Hãy tìm chiều dài chuỗi con đối xứng dài nhất của S.

Chuỗi con của S là dãy các ký tự liên tiếp nhau trong S.

Đầu vào

Dòng đầu ghi giá trị n là độ dài chuỗi S.
Dòng sau gồm n kí tự liên tiếp, các ký tự chỉ gồm các chữ cái tiếng Anh in hoa.

Đầu ra

In ra một số nguyên duy nhất là độ dài chuỗi con đối xứng dài nhất.

Ví dụ

Đầu vào
18
IKACOBEGIGEBOCAHTM

Đầu ra
13

Đầu vào
19
IKACOBEGIGEMHBEGIGE

Đầu ra
5

Bài 126: Chuỗi Fibonacci

Chuỗi Fibonacci được định nghĩa như sau:

F1 = x
F2 = y
Fi = Fi-1 + Fi-2

Trong đó x, y là hai ký tự được cho trước, phép toán cộng được hiểu là phép toán ghép chuỗi.

Ví dụ: nếu x = 'A' và y = 'B' thì khi đó ta có dãy gồm 6 chuỗi Fibonacci như sau:

i	Chuỗi Fibonacci thứ i
1	`F1 = "A"`
2	`F2 = "B"`
3	`F3 = "BA"`
4	`F4 = "BAB"`
5	`F5 = "BABBA"`
6	`F6 = "BABBABAB"`

Cho biết hai ký tự x, y và số nguyên dương n. Hãy in ra chuỗi Fibonacci thứ n.

Đầu vào

Dòng đầu tiên là hai kí tự x và y, cách nhau 1 dấu cách.
Dòng tiếp theo là số nguyên dương n.

Đầu ra

In ra chuỗi Fibonacci thứ n.

Ví dụ

Đầu vào
A B
6

Đầu ra
BABBABAB

Bài 127: Toán tử

Buổi học thứ 2 về lập trình C++, các bạn học sinh được giới thiệu một số phép toán. Trong đó có 2 phép toán cơ bản nhất là:

Phép toán ++ sẽ tăng giá trị của biến X lên 1 đơn vị.
Phép toán -- sẽ giảm giá trị của biến X đi 1 đơn vị.

Cô giáo có một bài tập nhỏ như sau: cho biến X khởi tạo bằng 0 và một dãy các toán tử như trên, các bạn hãy tính giá trị của biến X sau khi thực hiện hết chuỗi lệnh đó.

Đầu vào

Dòng đầu tiên là số nguyên n (0 < n <= 150) là số lượng câu lệnh trong chương trình.
Dòng thứ i trong n dòng tiếp theo chứa câu lệnh với biến X.

Có 4 dạng câu lệnh là:

++X
X++
--X
X--

Đầu ra

In ra giá trị của biến X sau khi thực hiện xong chương trình.

Ví dụ

Đầu vào
4
X++
--X
X++
++X

Đầu ra
2

Giải thích

Ban đầu X = 0, sau câu lệnh thứ 1, X = 1.
Sau câu lệnh thứ 2, X = 0.
Sau câu lệnh thứ 3, X = 1.
Sau câu lệnh thứ 4, X = 2.

Bài 128: Mật khẩu

Trong bài toán này, một chuỗi mật khẩu được gọi là an toàn nếu chuỗi đó thỏa mãn:

Có độ dài ít nhất bằng 6.
Chứa ít nhất một chữ cái in hoa ('A'..'Z').
Chứa ít nhất một chữ cái in thường ('a'..'z').
Chứa ít nhất một chữ số ('0'..'9').

Ví dụ:

"a1B2C3", "tinHoc6" là các chuỗi mật khẩu an toàn.
"a1B2C", "abc123", "A1B2C3", "tinHoc" không là chuỗi mật khẩu an toàn.

Một lần, Bình nhìn thấy một chuỗi ký tự S, chỉ gồm các loại kí tự: chữ cái in hoa, chữ cái in thường và chữ số. Bình muốn tính số lượng đoạn con liên tiếp của chuỗi S là mật khẩu an toàn.

Cụ thể, Bình cần đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện:

1 <= i <= j <= |S|, với |S| là độ dài chuỗi S.
Chuỗi con gồm các ký tự liên tiếp trong S từ i đến j là mật khẩu an toàn.

Yêu cầu

Cho chuỗi S, tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện nêu trên.

Đầu vào

Gồm một dòng chứa chuỗi ký tự S.

Ràng buộc

50% số test đầu tiên có chuỗi S có độ dài không quá 50.
25% số test tiếp theo có chuỗi S có độ dài không quá 300.
25% số test cuối cùng có chuỗi S có độ dài không quá 1000.

Đầu ra

In ra một số nguyên là số lượng cặp chỉ số (i, j) thỏa mãn đề bài.

Ví dụ

Đầu vào
abc3456789PQ

Đầu ra
6

Đầu vào
abc123

Đầu ra
0

Bài 129: Trò chơi Đá - Giấy - Kéo

Cậu bé phù thủy Harry Potter và cô bé phù thủy Hermione cùng chơi trò chơi Đá - Giấy - Kéo (Rock-Paper-Scissors - RPS).

Có tất cả n lượt chơi, và Hermione với bùa phép bí mật nên luôn biết trước Harry sẽ đưa ra thao tác gì trước khi cậu ta thực hiện trong mỗi lượt chơi.

Tuy nhiên, bùa phép cũng cho hạn chế với Hermione, đó là cô bé phải sử dụng đúng a lần biểu tượng hòn đá/nắm đấm, b lần biểu tượng tờ giấy/bàn tay xòe, và c lần biểu tượng cái kéo/hai ngón tay xòe, đồng thời a + b + c = n.

Hermione sẽ thắng nếu cô bé đánh bại Harry ít nhất ceil(n / 2) lần.

Luật trò chơi RPS:

Đá (R) đập được Kéo (S).
Giấy (P) bọc được Đá (R).
Kéo (S) cắt được Giấy (P).

Cho biết chuỗi mô tả động tác mà Harry sẽ chơi và các giá trị n, a, b, c. Hãy xác định xem Hermione có thể giành chiến thắng hay không, và nếu có, hãy in chuỗi mô tả động tác mà Hermione cần thực hiện để giành chiến thắng. Nếu có nhiều câu trả lời, chỉ cần in ra một câu trả lời bất kỳ.

Đầu vào

Dòng đầu chứa số nguyên T (1 <= T <= 100) là số bộ dữ liệu test.
Theo sau là mô tả của T bộ dữ liệu. Mỗi bộ dữ liệu gồm 3 dòng:
- Dòng thứ 1 chứa lần lượt 4 số nguyên n, a, b, c (1 <= n <= 100, 0 <= a, b, c <= n, a + b + c = n). Các số nguyên cách nhau một dấu cách.
- Dòng thứ 2 chứa chuỗi n ký tự chỉ gồm các chữ cái 'R', 'P', 'S' với ý nghĩa như đã nói trong đề bài. Chuỗi này mô tả các thao tác tay mà Harry sẽ thực hiện trong n ván chơi, theo đúng thứ tự chơi.

Đầu ra

Ứng với mỗi bộ dữ liệu, chương trình cần in ra:

Nếu Hermione thua Harry thì in ra một dòng chứa thông báo NO.
Nếu Hermione thắng Harry thì in ra:
- Dòng đầu chứa thông báo YES.
- Dòng sau chứa chuỗi n ký tự mô tả thao tác tay mà Hermione thực hiện thì sẽ giành chiến thắng. Chuỗi thao tác này có thể không duy nhất.

Ví dụ

Đầu vào
2
3 1 1 1
RPS
3 3 0 0
RPS

Đầu ra
YES
PSR
NO

Giải thích

Trong bộ dữ liệu thứ nhất:
- Lượt 1, Hermione ra giấy (P) và Harry ra đá (R), Hermione thắng.
- Lượt 2, Hermione ra kéo (S) và Harry ra giấy (P), Hermione thắng.
- Lượt 3, Hermione ra đá (R) và Harry ra kéo (S), Hermione thắng.
- Hermione thắng Harry 3 lần và 3 >= ceil(3/2), vì vậy Hermione chiến thắng trong trò chơi.
Trong bộ dữ liệu thứ hai, Hermione chỉ có thể ra đá (R) trong cả 3 lần chơi. Hermione chỉ thắng trong lần cuối cùng, vì Harry ra kéo (S). Vì vậy Hermione chỉ thắng 1 lần, mà 1 < ceil(3/2), nên Hermione thua Harry.

Bài 130: Tìm số tối thiểu

Cho số nguyên dương S gồm n chữ số, không có chữ số 0 thừa ở tận cùng bên trái, và số nguyên dương k.

Hãy tìm cách thay thế tối đa k chữ số bất kỳ trong S để thu được số nhỏ nhất có n chữ số và số thu được cũng không có chữ số 0 thừa ở tận cùng bên trái.

Chú ý: Một số có chữ số 0 thừa ở tận cùng bên trái nếu có ít nhất hai chữ số và chữ số đầu tiên của nó là 0. Ví dụ: các số 00, 00069 và 0101 có các số 0 thừa ở tận cùng bên trái, còn các số 0, 3000 và 1010 không có các số 0 ở tận cùng bên trái.

Đầu vào

Dòng đầu chứa số nguyên T là số bộ dữ liệu vào (1 <= T <= 100).
Tiếp theo là T bộ dữ liệu, mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa hai số nguyên n và k cách nhau một dấu cách (1 <= n <= 2 * 10^3, 0 <= k <= n) với ý nghĩa như đã nêu trong đề bài.
- Dòng thứ hai chứa chuỗi S có n chữ số thập phân mô tả số nguyên, chuỗi S không chứa chữ số 0 ở tận cùng bên trái.

Đầu ra

In ra số S gồm n chữ số sau khi đã thay thế không quá k chữ số như đã yêu cầu.

Ví dụ

Đầu vào
3
5 3
51428
3 2
102
1 1
1

Đầu ra
10028
100
0

Bài 131: Chuỗi tốt

Một chuỗi nhị phân chỉ gồm các chữ số 0 và 1 là một chuỗi tốt nếu số lượng các chữ số 0 và 1 khác nhau.

Ví dụ:

"1", "101", "0000" là chuỗi tốt.
"01", "1001", "1000" không phải là chuỗi tốt.

Bạn được biết một chuỗi nhị phân S. Hãy tìm cách cắt chuỗi S thành một số ít nhất các chuỗi con sao cho tất cả các chuỗi con này đều là chuỗi tốt.

Ví dụ, một cách cắt chuỗi S = "110010" thành các chuỗi "110" và "010" hoặc thành các chuỗi "11" và "0010" là hợp lệ; còn cách cắt thành "1100" và "10" thì không hợp lệ vì cả hai chuỗi con đều không phải chuỗi tốt. Ngoài ra, việc cắt S thành các chuỗi con "1", "1", "0010" cũng là không hợp lệ, vì cách cắt này không phải là cách cắt tối thiểu, mặc dù cả 3 chuỗi con đều là chuỗi tốt.

Biết rằng lời giải luôn tồn tại. Bạn hãy tìm một cách cắt thỏa mãn yêu cầu và chỉ cần cho biết số chuỗi con ít nhất là bao nhiêu.

Đầu vào

Dòng đầu tiên của đầu vào chứa số nguyên q (1 <= q <= 100) là số truy vấn.
Tiếp theo là q dòng, mỗi dòng chứa một truy vấn gồm một chuỗi nhị phân s khác rỗng có độ dài không quá 100.

Đầu ra

Chương trình cần in ra q dòng, trong đó dòng thứ i ghi câu trả lời của truy vấn thứ i, là số lượng ít nhất các chuỗi con tốt có thể cắt ra từ s.

Ví dụ

Đầu vào
2
110010
100

Đầu ra
2
1

Bài 132: Bàn phím hỏng

Bình đang học thực hành gõ văn bản trên phòng máy nhà trường. Thật không may, bàn phím của Bình có một số phím bị hỏng, do đó, khi Bình nhấn vào một phím hỏng một lần thì ký tự tương ứng trên phím đó có thể xuất hiện nhiều lần trên màn hình soạn thảo; trong khi, nếu Bình nhấn một phím bình thường, sẽ chỉ có một ký tự tương ứng hiện trên màn hình.

Ví dụ: Bình gõ từ "hello", trên màn hình có thể xuất hiện một trong các từ sau: "hello", "hhhhello", "hhhheeeellllooo", nhưng sẽ không thể xuất hiện các từ sau: "hell", "helo", "hhllllooo".

Lưu ý rằng, khi Bình nhấn một phím, ký tự tương ứng phải xuất hiện một trong cùng một nhóm trên màn hình; ký tự tương ứng có thể nhận xuất hiện với số lần khác nhau.

Với mỗi từ trong văn bản của Bình, thầy giáo đã đoán được từ mà Bình thực sự muốn gõ, nhưng ông không chắc chắn, vì vậy thầy giáo yêu cầu bạn giúp đỡ.

Bạn được biết một danh sách các cặp từ. Trong mỗi cặp từ, từ đầu tiên là dự đoán của thầy giáo, từ thứ hai là do Bình gõ, và bạn cần xác định xem từ thứ hai có thể đúng là từ thứ nhất hay không.

Đầu vào

Dòng đầu tiên của đầu vào chứa một số nguyên n (1 <= n <= 1000) là số lượng cặp từ cần kiểm tra.
Mỗi cặp từ nằm trên 2 dòng, trong đó:
- Dòng 1 chứa một chuỗi ký tự s không rỗng chỉ gồm các chữ cái tiếng Anh in thường, mô tả từ mà thầy giáo đoán nội dung Bình gõ.
- Dòng 2 chứa một chuỗi ký tự t không rỗng chỉ gồm các chữ cái tiếng Anh in thường, mô tả từ mà Bình gõ bằng bàn phím bị hỏng.

Độ dài của s và t không lớn hơn 10^5. Dữ liệu đảm bảo rằng tổng độ dài của tất cả các chuỗi s và tổng độ dài của tất cả các chuỗi t trong đầu vào đều không lớn hơn 10^5.

Đầu ra

Chương trình cần in ra n dòng. Trong đó, dòng thứ i in ra câu trả lời YES hoặc NO tương ứng với cặp từ thứ i từ đầu vào.

Ví dụ

Đầu vào
4
hello
hello
hello
helloo
hello
hllllooo
hello
helo

Đầu ra
YES
YES
NO
NO

Bài 133: Ký tự duy nhất đầu tiên

Một chuỗi ký tự S gồm toàn chữ cái tiếng Anh in thường. Hãy tìm vị trí đầu tiên của ký tự xuất hiện duy nhất một lần trong S.

Các ký tự trong chuỗi được đánh thứ tự từ 1, 2, .... Nếu không có ký tự nào như vậy thì in ra số -1.

Đầu vào

Dòng đầu tiên của đầu vào chứa số nguyên q (1 <= q <= 100) là số truy vấn.
Tiếp theo là q dòng, mỗi dòng chứa một truy vấn là một chuỗi ký tự S có độ dài không quá 200.

Đầu ra

Chương trình của bạn cần in ra q dòng, trong đó dòng thứ i ghi câu trả lời của truy vấn thứ i theo yêu cầu đề bài.

Ví dụ

Đầu vào
4
abcdbc
abcdefabcde
ababab
a

Đầu ra
1
6
-1
1

Bài 134: Di chuyển robot

Giáo sư Vova đang thử nghiệm một robot đi bộ. Giả sử sân chơi là mặt phẳng tọa độ Oxy. Ban đầu robot đứng tại điểm (0, 0).

Chuỗi hướng dẫn di chuyển của robot là s bao gồm các ký tự 'L', 'R', 'U' và 'D'. Nếu robot đang ở trong ô (x, y), nó có thể di chuyển đến một trong các ô liền kề tùy thuộc vào hướng dẫn hiện tại:

Nếu hướng dẫn hiện tại là chữ 'L', robot di chuyển sang trái đến điểm (x - 1, y).
Nếu hướng dẫn hiện tại là chữ 'R', robot di chuyển sang phải đến điểm (x + 1, y).
Nếu hướng dẫn hiện tại là chữ 'U', robot di chuyển lên trên đến điểm (x, y + 1).
Nếu hướng dẫn hiện tại là chữ 'D', robot di chuyển xuống dưới đến điểm (x, y - 1).

Giáo sư Vova không muốn robot đi qua điểm nào đó quá 1 lần, trừ điểm (0, 0).

Vì vậy, một chuỗi hướng dẫn là hợp lệ nếu robot xuất phát từ ô (0, 0), di chuyển theo các hướng dẫn đã cho, và không đi qua điểm nào đó quá 1 lần. Do đó, chỉ có điểm (0, 0) là robot đến 2 lần: xuất phát và kết thúc. Tất nhiên, nếu chuỗi hướng dẫn là rỗng thì điểm (0, 0) chỉ được thăm một lần, vì ban đầu robot đã ở đó.

Ví dụ:

Các chuỗi hướng dẫn sau là hợp lệ: "UD", "RL", "UURULLDDDDLLDDRRUU".
Các chuỗi sau là không hợp lệ:
- "U" vì điểm cuối không phải là (0, 0).
- "UUDD" vì đến điểm (0, 1) hai lần.

Tuy nhiên, vì lý do nào đó mà chuỗi hướng dẫn có thể không hợp lệ. Vova muốn lập trình lại chuỗi hướng dẫn theo cách sau: xóa đi một số ký tự hướng dẫn, có thể xóa tất cả hoặc không xóa ký tự nào, sau đó sắp xếp các ký tự còn lại theo ý muốn và cho robot đi chuyển.

Nhiệm vụ của bạn là giúp giáo sư Vova loại bỏ càng ít càng tốt các ký tự hướng dẫn khỏi chuỗi hướng dẫn ban đầu và sắp xếp các ký tự còn lại để được chuỗi hướng dẫn hợp lệ, đồng thời cho biết độ dài tối đa của chuỗi hướng dẫn hợp lệ bạn có thể thu được. Bạn phải trả lời q truy vấn độc lập.

Đầu vào

Dòng đầu tiên của đầu vào chứa số nguyên q (1 <= q <= 10^4) là số truy vấn.
Dòng thứ i trong q dòng tiếp theo chứa truy vấn thứ i được cho dưới dạng một chuỗi s bao gồm ít nhất 1 và không quá 10^5 ký tự 'L', 'R', 'U' và 'D', mô tả chuỗi hướng dẫn ban đầu.
Dữ liệu vào đảm bảo tổng độ dài chuỗi s trong tất cả các truy vấn không quá 10^5.

Đầu ra

Ứng với mỗi truy vấn theo thứ tự đầu vào, chương trình của bạn cần in ra câu trả lời tương ứng gồm 2 dòng:

Dòng 1: In ra độ dài tối đa k của chuỗi hướng dẫn robot sau khi đã chỉnh sửa theo yêu cầu.
Dòng 2: In ra chuỗi đã chỉnh sửa gồm k ký tự hướng dẫn. Nếu có nhiều chuỗi thỏa mãn, chỉ cần in ra một chuỗi bất kỳ trong số đó.
Nếu không có phương án thỏa mãn, dòng 1 in ra số 0 và dòng 2 in ra một dòng trống.

Ví dụ

Đầu vào
6
LRU
DURLDRUDRULRDURDDL
LRUDDLRUDRUL
LLLLRRRR
URDUR
LLL

Đầu ra
2
LR
14
RUURDDDDLLLLUR
12
ULDDDRRRUULL
2
LR
2
UD
0

Bài 135: Số Ebne

Một số được gọi là số Ebne nếu và chỉ nếu tổng các chữ số của nó chia hết cho 2 nhưng bản thân số đó không chia hết cho 2.

Ví dụ: 13, 1227, 185217 là các số Ebne, còn 12, 2, 177013, 265918 thì không phải.

Cho một số nguyên không âm gồm n chữ số. Bạn có thể xóa một số chữ số, không nhất thiết liên tiếp, để số đã cho trở thành số Ebne. Bạn được thay đổi thứ tự của các chữ số còn lại. Số kết quả không được chứa chữ số 0 ở đầu. Bạn có thể xóa bất kỳ số chữ số nào, hoặc có thể không cần xóa chữ số nào.

Bất kỳ số kết quả nào hợp lệ đều được chấp nhận. Nếu không thể thực hiện được yêu cầu thì in ra số -1.

Đầu vào

Dòng đầu tiên chứa một số nguyên T (1 <= T <= 1000) là số bộ dữ liệu kiểm tra.
Theo sau là các bộ dữ liệu kiểm tra, mỗi bộ gồm 2 dòng:
- Dòng đầu chứa một số nguyên N (1 <= N <= 3000) là số chữ số của số ban đầu S.
- Dòng thứ hai chứa một số nguyên không âm S, gồm N chữ số.

Dữ liệu đảm bảo S không chứa chữ số 0 ở đầu và tổng của N trên tất cả bộ dữ liệu kiểm tra không vượt quá 3000.

Đầu ra

Với mỗi bộ dữ liệu kiểm tra từ đầu vào, in ra một dòng chứa câu trả lời theo định dạng sau: nếu không thể tạo được số Ebne thì in ra -1; ngược lại, in ra số kết quả bất kỳ mà bạn cho là hợp lệ.

Ví dụ

Đầu vào
4
4
1227
1
0
6
177013
24
222373204424185217171912

Đầu ra
1227
-1
17703
2237344218521717191

Giải thích

Bộ dữ liệu 1: Số 1227 đã là số Ebne vì 1 + 2 + 2 + 7 = 12, 12 chia hết cho 2, trong khi đó 1227 không chia hết cho 2. Vì vậy ta không cần xóa bất kỳ chữ số nào. Các câu trả lời như 127 hoặc 17 cũng sẽ được chấp nhận.
Bộ dữ liệu 2: Không thể tạo số Ebne từ số đã cho.
Bộ dữ liệu 3: Có thể tạo nhiều số Ebne từ số 177013, ví dụ xóa 1 chữ số để có: 17703, 77013 hoặc 17013. Câu trả lời 1701 hoặc 770 không được chấp nhận vì chúng không phải là số Ebne. Câu trả lời 013 không được chấp nhận vì nó chứa các số 0 đứng đầu.
Bộ dữ liệu 4: Có nhiều câu trả lời có thể được chấp nhận. Một trong số đó có thể là: 222373204424185217171912 -> 22237320442418521717191 bằng cách xóa chữ số cuối cùng.

Bài 136: Xóa các chữ số 0

Cho một chuỗi nhị phân S chỉ gồm các ký tự 0 và 1. Người ta muốn tạo một chuỗi mới gồm toàn các chữ số 1 liên tiếp trong chuỗi S.

Ví dụ:

Nếu chuỗi S là: 0, 1, 00111 hoặc 01111100, thì tất cả chữ số 1 sẽ tạo thành một đoạn liền tiếp.
Nếu chuỗi S là: 0101, 100001 hoặc 1111111111011, thì điều kiện này không được đáp ứng.

Bạn được phép xóa một số tối thiểu các chữ số 0 trong S hoặc có thể không xóa để các chữ số 1 trong S tạo thành một đoạn liên tiếp. Hãy thực hiện điều này.

Đầu vào

Dòng đầu chứa một số nguyên T (1 <= T <= 100) là số bộ dữ liệu kiểm tra.
Tiếp theo là T bộ dữ liệu, mỗi bộ dữ liệu gồm một dòng chứa một chuỗi nhị phân S khác rỗng và có độ dài không quá 100 ký tự.

Đầu ra

Ứng với mỗi bộ dữ liệu vào, chương trình của bạn cần in ra một số nguyên là số lượng tối thiểu các chữ số 0 cần xóa khỏi S.
Bài 137: Đổi chuỗi

Cho ba chuỗi a, b và c có cùng độ dài n.
Các chuỗi chỉ bao gồm các chữ cái tiếng Anh thường.

Chữ cái thứ i của a là a[i], của b là b[i], và của c là c[i].

Với mỗi i (1 ≤ i ≤ n), bạn phải đổi c[i] với a[i] hoặc với b[i].

Hãy cho biết sau khi thực hiện các phép đổi, có thể làm cho chuỗi a trở nên giống hệt chuỗi b hay không.

Đầu vào

Dòng đầu tiên chứa số nguyên T (1 ≤ T ≤ 100) là số bộ dữ liệu.
Mỗi bộ dữ liệu gồm 3 dòng:
- Dòng 1: chuỗi a
- Dòng 2: chuỗi b
- Dòng 3: chuỗi c

Ba chuỗi có cùng độ dài và không vượt quá 100.

Đầu ra

Với mỗi bộ dữ liệu, in ra:

YES nếu có thể.
NO nếu không thể.

Ví dụ

Input

4
aaa
bbb
ccc
abc
bca
bca
aabb
bbaa
baba
imi
mii
iim

Output

NO
YES
YES
NO

Bài 138: Số đẹp

Cho một số nguyên x gồm n chữ số a[1], a[2], ..., a[n] và một số nguyên dương k < n.

Số nguyên y gồm m chữ số b[1], b[2], ..., b[m] được gọi là số đẹp nếu:

b[i] = b[i + k] với mọi 1 ≤ i ≤ m-k

Hãy tìm số nguyên y đẹp và nhỏ nhất không vượt quá x.

Đầu vào

Dòng đầu tiên chứa hai số nguyên n, k
Dòng thứ hai chứa chuỗi số a

Điều kiện:

2 ≤ n ≤ 2×10^5
1 ≤ k < n

Đầu ra

Dòng đầu tiên in ra số chữ số của y
Dòng thứ hai in ra số y

Ví dụ

Input

3 2
353

Output

3
353

Input

4 2
1234

Output

4
1313

Bài 139: Các từ quá dài

Đôi khi một số từ như "localization" hoặc "internationalization" quá dài nên khó viết nhiều lần.

Ta thay thế các từ có độ dài lớn hơn 10 bằng:

chữ cái đầu
số lượng ký tự ở giữa
chữ cái cuối

Ví dụ:

"localization" → "l10n"
"internationalization" → "i18n"

Các từ không quá dài thì giữ nguyên.

Đầu vào

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 100)
n dòng tiếp theo, mỗi dòng chứa một từ

Đầu ra

In ra dạng rút gọn tương ứng.

Ví dụ

Input

4
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis

Output

word
l10n
i18n
p43s

Bài 140: Thao tác chuỗi

Cho hai chuỗi khác nhau s và t có cùng độ dài n, chỉ gồm các chữ cái tiếng Anh thường.

An được phép thực hiện đúng một thao tác:

Chọn hai vị trí i và j (1 ≤ i, j ≤ n)
Hoán đổi s[i] và s[j]

Hỏi có thể làm cho chuỗi s trở thành t sau đúng một thao tác hay không.

Đầu vào

Dòng đầu tiên chứa số nguyên q (1 ≤ q ≤ 100) là số bộ dữ liệu.
Mỗi bộ dữ liệu gồm:
- Dòng 1: số nguyên n
- Dòng 2: chuỗi s
- Dòng 3: chuỗi t

Điều kiện:

2 ≤ n ≤ 10^4

Đầu ra

Với mỗi bộ dữ liệu, in ra:

Yes nếu có thể
No nếu không thể

Ví dụ

Input

4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca

Output

Yes
No
No
No