Alphabet

Xem PDF
Tác giả:
trannhutri , sonprao2211
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Thỏ thích làm các bài tập về xử lý chuỗi. Thỏ định nghĩa rằng một chuỗi được gọi là tốt
là một chuỗi mà tất cả các kí tự \(alphabet\) trong đó đều là kí tự hoa hoặc là kí tự thường

Ví dụ :

  • ABCDEF là một chuỗi tốt

  • xyabx@# là một chuỗi tốt

  • Xy3z5A là một chuỗi xấu

Trong khi đọc tài liệu, Thỏ cảm thấy có rất nhiều chuỗi xấu xuất hiện và Thỏ muốn chuyển tất cả
các chuỗi xấu này thành chuỗi tốt với số lượng thao tác là ít nhất có thể.

Trong một thao tác, Thỏ chỉ có thể thay đổi MỘT kí tự trong xâu S thành một kí tự bất kì nào đó.

Bạn hãy giúp Thỏ tìm số lượng thao tác nhỏ nhất có thể để chuyển chuỗi xấu thành chuỗi tốt nhé.

Input

  • Dòng đầu tiên là số \(T\) số lượng test case \((1 \leq T \leq 10)\).

  • \(T\) dòng tiếp theo , mỗi dòng chứa một xâu \(S\) là chuỗi cần phải chuyển \((1 \leq Len(S) \leq 100)\).

Output

  • Tương ứng với mỗi chuỗi \(S\), in ra số lượng thao tác để chuyển chuỗi \(S\) thành chuỗi tốt, nếu trong chuỗi
    không có kí tự alphabet nào, in ra Invalid Input.

Example

Test 1

Input 
3
abcEfg
!@6#2
123A
Output 
1
Invalid Input   
0

Bình luận


  • 0
    tk21ngocduongbao    9:53 p.m. 29 Tháng 3, 2022

    tăng thời gian cho scratch đi a, chứ 1s thì ...


    • 15
      dang7rickroll    9:45 p.m. 22 Tháng 11, 2021 ← chỉnh sửa 2

      Spoiler Alert

      Dựa theo định nghĩa, ta rút ra được nhận xét: chỉ cần 1 ký tự, hoặc là chữ cái hoa, hoặc là chữ cái thường trong bảng chữ cái Alphabet thì chuỗi đó là chuỗi tốt .Vì thế các chuỗi như a###*#& và V*&#&$*22 là các chuỗi tốt.

      Vì vậy:

      • Nếu trong chuỗi đều tồn tại cả chữ cái hoa và thường thì phải biến đổi các chữ cái thường về chữ cái hoa, hoặc các chữ cái hoa về chữ cái thường. Điều này phụ thuộc vào số lượng chữ cái thường và số lượng chữ cái hoa trong chuỗi đó.
      • Gọi \(d_1\) là biến lưu số lượng chữ cái thường, \(d_2\) là biến lưu số lượng chữ cái hoa. Nếu một trong hai biến \(= 0\) thì ta không phải biến đổi gì thêm nữa.
      • Ngược lại, nếu \(d_1 > d_2\) thì phải biến đổi \(d_2\) chữ cái hoa sang chữ cái thường. Còn nếu \(d_1 < d_2\) thì phải biến đổi \(d_1\) chữ cái thường sang chữ cái hoa (vì đề bài yêu cầu là số lần biến đổi ít nhất có thể).
      • Còn nếu \(d_1 = d_2\) thì bạn in số nào cũng được.
      • Nếu cả hai biến đều \(=0\) (không tồn tại chữ cái nào trong xâu) thì không thể biến đổi (Invalid Input)

      Vậy là bài toán đã được giải quyết xong.

      Các bạn có thể tham khảo code của mình ở đây. (\(\color{red}{\text{Không chép nha}}\))

      Nếu các bạn có gì thắc mắc hoặc không hiểu, các bạn cứ comment nhé ! Mình sẽ giải thích cặn kẽ cho các bạn.

      Update: Cho mình gửi lời cảm ơn tới các bạn/anh/chị/em upvote hướng dẫn của mình.

      4 phản hồi