Cho xâu s dài vô hại được tạo thành bằng cách ghép liên tiếp các xâu "TINHOCTREQUANGNINH" và hai số tự nhiên a, b được nhập vào từ bàn phím:Yêu cầu: Đưa ra màn hình các kí tự từ vị trí a đến vị trí b của xâu sDữ liệu: Nhập vào từ bàn phím 2 số tự nhiên a, b mỗi só được viết trên một dòng (\(a\le b\le1000000000\); \(0\le b-a\le18\)).Kết quả: Đưa ra màn hình các ký tự từ vị trí a đến vị trí b của xâu s.Ví...
Đọc tiếp
Cho xâu s dài vô hại được tạo thành bằng cách ghép liên tiếp các xâu "TINHOCTREQUANGNINH" và hai số tự nhiên a, b được nhập vào từ bàn phím:
Yêu cầu: Đưa ra màn hình các kí tự từ vị trí a đến vị trí b của xâu s
Dữ liệu: Nhập vào từ bàn phím 2 số tự nhiên a, b mỗi só được viết trên một dòng (\(a\le b\le1000000000\); \(0\le b-a\le18\)).
Kết quả: Đưa ra màn hình các ký tự từ vị trí a đến vị trí b của xâu s.
Ví dụ:
| Nhập vào | Kết quả |
10 18 | QUANGNINH |
19 27 | TINHOCTRE |
Bạn tham khảo theo code C++ nhé!
Bài này khá hay nên mình sẽ giải thích 1 chút về thuật toán mà mình sử dụng.
Thường thì 1 số bạn sẽ nghĩ đến sử dụng vòng lặp, nhưng đối với bài với giá trị của a và b lớn thì dùng vòng lặp ở những Testcase ở 60% sẽ dễ bị quá thời gian không đạt được điểm tối đa.
Hướng giải quyết code của mình làm như sau:
Dãy TINHOCTREQUANGNINH là 1 dãy có 18 kí tự sẽ tạo 1 dãy vô hạn
=> Mỗi kí tự sẽ được gán 1 chỉ số chia lấy dư cho 18.
Ví dụ chuỗi s = "TINHOCTREQUANGNINH"
Ví dụ a = 19 khi thì a%18 = 1. Thì nó sẽ lấy kí tự đầu và b cũng tương tự. Đối với trường hợp a hoặc b %18=0 thì chỉ số đó cũng sẽ bằng 18 vì a%18=0 hoặc b%18=0 chỉ đến vị trí cuối của chuỗi.
Mình chia làm 3 trường hợp như sau:
- TH1: Lấy các kí tự từ 1 chuỗi gốc TINHOCTREQUANGNINH (a%18 < b%18)
-> Đối với trường hợp này thì chỉ cần in ra các kí tự từ a%18 đến b%18. Trong C++ chỉ số bắt đầu là 0 nên mình dùng a%18-1
-TH2: Cần ghép 2 chuỗi lại để lấy kí tự, ví dụ a = 15 và b = 21 => Kết quả là NINHTIN
Để dễ hình thì ta phải ghép 2 chuỗi s lại như sau: TINHOCTREQUANGNINHTINHOCTREQUANGNINH
Đối với trường hợp 2 này thì a%18 sẽ > b%18.
Do vậy mình sẽ in các kì tự từ a%18 đến 18 của chuỗi TINHOCTREQUANGNINH. Tiếp tục in tiếp từ vị trí đầu chuỗi đến b%18 của chuỗi. => Sẽ tạo ra được 1 chuỗi theo yêu cầu của Input
- TH3: a = b
Trường hợp này mình in ra kí tự thứ a hoặc b. Để tiết kiệm thời gian khi sử dụng vòng lặp thì sẽ tương ứng với s[a%18-1] . Vì trong C++ chỉ số chuỗi bắt đầu là 0 nên -1 để đúng với yêu cầu bài toán đặt ra.