Xâu luỹ thừa bậc K của một xâu S là một xâu T mà T được tạo thành bằng cách viết K lần xâu S liên tiếp nhau.

Ví dụ: xâu luỹ thừa bậc 3 của xâu "abc" là xấu "abcabcabc".

Yêu cầu: Cho hai số nguyên K và 2 xâu S,T. Yêu cầu kiểm tra xem xâu T có phải xâu luỹ thừa bậc K của xâu S hay không ?

Dữ liệu vào: • Gồm 3 dòng: 2 dòng đầu lần lượt chứa xâu S và xâu T, dòng cuối chứa số nguyên K.

Kết quả:

• Nếu xâu T là xâu luỹ thừa bậc K của xâu S in ra " YES " ngược lại in ra " NO "

Giới hạn:

• Hai xâu S ,T chỉ chứa các kí tự latin in thường. Độ dài mỗi xâu không ra 1000 kí tự 

1.Khái niệm về xâu và kiểu string.

-Xâu kí tự là một dãy gồm nhiều kí tự đặt cạnh nhau và được đánh các số phần tử theo chỉ số;ví dụ”Toan Tin”,phần tử thứ I là s[i].

-Như vậy xét về bản chất xâu kí tự giống như một  mảng kí tự.

-Ta đặt xâu kí tự trong dấu nháy kép,còn mỗi kí tự ta đặt trong dấu nháy đơn.

Đề bài: có 13 đồng tiền trong đó có 1 đồng bị lỗi không biết nặng hơn hay nhẹ hơn đồng tiền còn lại qua 3 lần cân thăng bằng tìm gia đồng bị lỗi. Lời giải:
Ta đánh đấu từng đồng bằng các số từ 1 đến 13 , ta chia thành 3 nhóm nhóm A là nhóm có số đồng từ số 1 đến số 4 , nhóm B có số đồng từ 5 đến 8 , nhóm C có số đồng từ 9 đến 13 , lần cân thứ nhất: ta cho nhóm A cân với nhóm B nếu cân thằng bằng thì nhóm C sẽ có 1 đồng bị lỗi , ta cho đồng 12 , 13 gia ngoài, cho thêm đồng số 1 vào cùng với đồng số 9 cho lên cân vơi đồng số 11 và đồng số 10 nếu cân thăng bằng thì đồng số 1 2 và đồng số 13 có 1 đồng bị lỗi . Ta cân 1 trong 2 đồng trên vơi bất kể đồng còn lại nào thì có thể tìm gia được đồng bị lỗi, nếu cân lệnh ta gi nhớ xem nhóm nào nặng hơn , vậy là trong 3 đồng 9, 10, 11 có 1 đồng bị lỗi , lần cân thứ 3 ta cho đồng số 10 cân với đồng số 11 nếu cân thăng bằng thì đồng số 9 bị lỗi còn cân lệch thì đồng số 11 và 10 có 1 đồng bị lỗi ta lấy 2 đồng cân vơi nhau và để ý xem đồng nào cùng nặng hoặc cùng nhẹ như nhóm này ở lần cân số 2 là đồng bị lỗi.
Quay chở lại trường hợp cân nhóm A với Nhóm B nếu cân không thăng bằng ta gi nhớ xem nhóm nào nặng hơn. Ta bỏ đồng số 4 của nhóm A và đồng số 7,8 của nhóm B gia ngoài. Cho đồng số 3 sang nhóm B đồng số 6 sang nhóm A . Vậy nhóm A có đồng 1 ,2 ,6 nhóm B có đồng 3 ,5 và đồng số 9 cho thêm vào không bị lỗi. Nếu cân thăng bằng thì 3 đồng 4 ,7,8 có đồng lỗi, ta lấy đồng 7 cân với đồng 8 cũng suy luận như nhóm C là tìm đc đồng bị lỗi. Nếu cân đảo chiều thì đồng 3 hoặc đồng 6 bị lỗi, còn lần cân còn lại tìm gia được đồng nào bị lỗi. Nếu cân vẫn lệch như lần cân số 1 thì 3 đồng 1,2,5 có đồng bị lỗi ta cũng cân đồng số 1 với đồng số 2 như cách cân ở nhóm C có thể tìm gia đồng bị lỗi. dưới là lick chi tiết video giải bài toán:https://www.youtube.com/watch?v=JwPzm0ya0ug&t=33s

Chung  minh rằng :  , ta gọi x là số lần cân ( cân thằng bằng) , x là số tự nhiên ≥  3 ,   , ta luôn tìm 1 đồng bị lỗi qua số  qua số lân cân là x và số đồng tối đa là:   

2.(3^x-2+ 3^x-3+3^x-4...+3^x-x) +(3^x-2+ 3^x-3^x-4...+3^x-x)+ 4-x

trong đó luôn tìm được 1 đồng tiền bị lỗi .

bài toán  có 13 đồng tiền trong đó có 1 đồng bị lỗi không biết nặng hơn hay nhẹ hơn đồng tiền còn lại qua 3 lần cân thăng bằng tìm gia đồng bị lỗi. Lời giải:

Ta đánh đấu từng đồng bằng các số từ 1 đến 13 , ta chia thành 3 nhóm nhóm A là nhóm có số đồng từ số 1 đến số 4 , nhóm B có số đồng từ 5 đến 8 , nhóm C có số đồng từ 9 đến 13 , lần cân thứ nhất: ta cho nhóm A cân với nhóm B nếu cân thằng bằng thì nhóm C sẽ có 1 đồng bị lỗi , ta cho đồng 12 , 13 gia ngoài, cho thêm đồng số 1 vào cùng với đồng số 9 cho lên cân vơi đồng số 11 và đồng số 10 nếu cân thăng bằng thì đồng số 1 2 và đồng số 13 có 1 đồng bị lỗi . Ta cân 1 trong 2 đồng trên vơi bất kể đồng còn lại nào thì có thể tìm gia được đồng bị lỗi, nếu cân lệnh ta gi nhớ xem nhóm nào nặng hơn , vậy là trong 3 đồng 9, 10, 11 có 1 đồng bị lỗi , lần cân thứ 3 ta cho đồng số 10 cân với đồng số 11 nếu cân thăng bằng thì đồng số 9 bị lỗi còn cân lệch thì đồng số 11 và 10 có 1 đồng bị lỗi ta lấy 2 đồng cân vơi nhau và để ý xem đồng nào cùng nặng hoặc cùng nhẹ như nhóm này ở lần cân số 2 là đồng bị lỗi.
Quay chở lại trường hợp cân nhóm A với Nhóm B nếu cân không thăng bằng ta gi nhớ xem nhóm nào nặng hơn. Ta bỏ đồng số 4 của nhóm A và đồng số 7,8 của nhóm B gia ngoài. Cho đồng số 3 sang nhóm B đồng số 6 sang nhóm A . Vậy nhóm A có đồng 1 ,2 ,6 nhóm B có đồng 3 ,5 và đồng số 9 cho thêm vào không bị lỗi. Nếu cân thăng bằng thì 3 đồng 4 ,7,8 có đồng lỗi, ta lấy đồng 7 cân với đồng 8 cũng suy luận như nhóm C là tìm đc đồng bị lỗi. Nếu cân đảo chiều thì đồng 3 hoặc đồng 6 bị lỗi, còn lần cân còn lại tìm gia được đồng nào bị lỗi. Nếu cân vẫn lệch như lần cân số 1 thì 3 đồng 1,2,5 có đồng bị lỗi ta cũng cân đồng số 1 với đồng số 2 như cách cân ở nhóm C có thể tìm gia đồng bị lỗi.

từ dữ niệu bài toán ta có :

 Với 3 lần cân ta cân được tối đa 13 đồng tiền , 

 Với 4 lần cân ta cân được tối đa là 39 đồng tiền ( 1 tuần trc mình nhầm to cái này) vì đơn giản là 39 đông chia thành 13 cân vơi13 , nếu thăng bằng thì 13 đồng còn lại bị lỗi và với 3 lần cân còn lại tìm đc đồng bị lỗi trong 13 đồng như là làm, còn cân lệch thì chia thành 3 nhóm 9,9,8 lấy ghép mỗi bên bên này 4 thì bên kia 5  có 3 khả năng xẩy ra ứng với 3 nhóm có số đồng là 9 hoặc 9, hoặc 8 bị lỗi , nếu 9 đồng bị lỗi thì lại chị làm 3,3,3 khác với bài toán 13 đông xu ta chia đc 3,3,2 do khi cân 2 nhóm số đồng xu cộng lại không thể lẻ đc nhầm tổng quát ở chỗ này

Với 5 lần cân thì ta được số đồng tối đa là 119 , lấy 40 đồng cân với 40 đông , cân thằng bằng thì 39 đông còn lại bị lỗi với 4 lần cân còn lại tìm đc 1 đồng bị lỗi như trên

Với 6 lần cân ta đc số đồng tối đa là 361 đồng lấy 121 cân với 121 đồng nếu cân thằng bằng thì 119 đồng còn lại bị lỗi còn cân lệch thì 242 đồng bị  lỗi cho thêm 1  đồng  không bị lỗi vào ta chia thành 3 nhóm mỗi nhóm có 81 đồng sắp xếp sao cho mỗi bên có 40 hoặc 41 đồng của của lần lượt 2 nhóm trên .

Với 7 lần ta có số đồng tối đa xác định đc là 364+364+361 tổng số là 1089

 với 8 lần cân ta có số đồng tối đa xác định được 1 đồng bị lỗi là : 1093+1093+1089=3275

với 9 lần cân ta luôn được số đồng xu tối đa để tìm được 1 đồng xu bị lỗi là : 3280+3280+3275=9835

Tổng hợp lại bài toán với x là số lần cân     x là số tự nhiên x≥  3ta luôn có số đồng tiền tối đa xác định đc qua x lần cân là:  . Thì tìm đc 1 đồng tiền bị lỗi. 2.(3^x-2+ 3^x-3+3^x-4...+3^x-x) +(3^x-2+ 3^x-3^x-4...+3^x-x)+ 4-x