2024 · HSG THPT · Quảng Trị

Ở một vương quốc xa xôi, có một trò chơi rất được ưa chuộng tại cung điện Hoàng gia. Trò chơi này được gọi là "Tung đồng xu may mắn". Mỗi lần chơi, họ sẽ tung một số đồng xu và ghi lại kết quả của mỗi lần tung. Nếu đồng xu có mặt sấp thì họ sẽ ghi lại ký tự '~S~', còn nếu có mặt ngửa thì họ sẽ ghi lại ký tự '~N~' và kết quả thu được một chuỗi ký tự ~P~.

Sau mỗi ván chơi, nhà vua thường yêu cầu các quan thần tính toán tỷ lệ giữa số lần xuất hiện của mặt sấp và mặt ngửa để đánh giá vận may của mình. Tuy nhiên, không phải ai cũng nhanh nhạy trong việc tính toán tỷ lệ này. Vì vậy, nhà vua đã yêu cầu bạn - một vị cố vấn thông minh – viết một chương trình tự động tính toán tỷ lệ này dưới dạng một phân số tối giản. Ví dụ: ~P=~ '~SSNSN~' thì tỉ lệ sấp và ngửa là ~3/2~.

Yêu cầu: Cho một chuỗi kết quả ~P~ từ trò chơi, in ra tỷ lệ giữa số lần xuất hiện của mặt sấp và mặt ngửa dưới dạng phân số tối giản.

Input

Vào từ file văn bản COINLK.INP:

• Dòng đầu tiên gồm số nguyên dương ~T~ ~(1\leq T\leq 10)~ là số lượng chuỗi kết quả ~P~.
• ~T~ dòng tiếp theo: mỗi dòng chứa một chuỗi ký tự ~P~ ~(2\leq \lvert{P}\rvert\leq 100000)~ chỉ bao gồm hai ký tự '~S~' và '~N~' (ký hiệu ~\lvert{P}\rvert~ là độ dài của chuỗi ký tự ~P~).

Output

Ghi ra file văn bản COINLK.OUT: Gồm ~T~ dòng theo thứ tự các chuỗi trong tệp dữ liệu vào. Mỗi dòng gồm hai số nguyên ~A, B~ được viết dưới dạng ~A/B~.

Scoring

• Subtask ~1~ ~(30\%)~: ~2\leq \lvert{P}\rvert \leq255~.
• Subtask ~2~ ~(70\%)~: Không có ràng buộc gì thêm.

Example input 1

3
SNSSSS
SNSSNNSSN
SNN

Example output 1

5/1
5/4
1/2

Mình rất thích những số có ~3~ ước. Một hôm, Mình đố Bảo rằng: Mình cho Bảo ~2~ số nguyên dương ~L~ và ~R~ ~(L ≤ R)~, hỏi trong đoạn nguyên ~[L, R]~ có bao nhiêu số có ~3~ ước?

Input

Vào từ file văn bản NUMBER.INP: Gồm một dòng chứa hai số nguyên ~L~ và ~R~, cách nhau một dấu cách.

Output

Ghi ra file văn bản NUMBER.OUT: Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask ~1~ ~(60\%)~: ~1\leq L\leq R\leq 10^6~.
• Subtask ~2~ ~(20\%)~: ~1\leq L\leq R\leq 10^9~.
• Subtask ~3~ ~(20\%)~: ~1\leq L\leq R\leq 10^{14}~.

Example input 1

1 30

Example output 1

3

Example input 2

12 100

Example output 2

2

Minh và Bảo đang đi du lịch tại nước Pháp. Ở đây có ~n~ thành phố, tất cả nằm dọc theo một con đường cao tốc. Các thành phố được đánh số liên tiếp bắt đầu từ ~1~ đến ~n~. Khoảng cách từ thành phố thứ ~i~ đến vị trí bắt đầu con đường cao tốc (điểm gốc) là ~d_i~ ~(i = 1, 2, …, n)~.

Minh đang ở thành phố ~x~, Bảo ở thành phố ~y~ ~(1\leq x, y\leq n)~. Hai bạn muốn tìm một thành phố ~z~ để gặp nhau sao cho ~MAX~{~\lvert{d_x - d_z}\rvert,\lvert{d_y-d_z}\rvert~} là nhỏ nhất.

Yêu cầu: Cho ~d_1, d_2,...,d_n~ và ~x, y~. Hãy tìm giá trị nhỏ nhất của ~MAX~{~\lvert{d_x - d_z}\rvert,\lvert{d_y-d_z}\rvert~}.

Input

Vào từ file văn bản TRAVEL.INP:

• Dòng đầu tiên chứa ~2~ số nguyên ~n, Q~ ~(2\leq n\leq 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2,..., d_n~ ~(d_1, d_2,..., d_n\leq 10^9)~.

• ~Q~ dòng sau, mỗi dòng chứa hai số ~x, y,~ mô tả cho một câu hỏi ~(1\leq x, y\leq n)~.

Các số trên cùng một dòng được viết cách nhau bởi một dấu cách.

Output

Ghi ra file văn bản TRAVEL.OUT: Gồm ~Q~ dòng, mỗi dòng là một giá trị ~MAX~{~\lvert{d_x - d_z}\rvert,\lvert{d_y-d_z}\rvert~} nhỏ nhất tìm được với một câu hỏi theo thứ tự trong tệp dữ liệu vào.

Scoring

• Subtask ~1~ ~(40\%)~: ~n, Q\leq 100~.
• Subtask ~2~ ~(30\%)~: ~n, Q\leq 10^5~ và ~d_1<d_2<...<d_n~.</li>
• Subtask ~3~ ~(30\%)~: ~n, Q\leq 10^5~.

Example input 1

5 2
1 2 3 4 5
1 5
2 3

Example output 1

2
1

Example input 2

5 2
15 28 48 56 100
1 5
2 4

Example output 2

44
20

Bạn là một kỹ sư phần mềm tại một công ty chuyên phát triển hệ thống gửi email tự động. Hệ thống này cần gửi đi hàng triệu email mỗi ngày, nhiều email chứa các chuỗi ký tự dài lặp lại. Việc gửi những chuỗi dài như vậy làm tăng đáng kể chi phí băng thông và thời gian xử lý.

Bạn quyết định áp dụng một thuật toán nén đơn giản để giảm độ dài chuỗi: Tìm kiếm các đoạn lặp lại trong chuỗi và thay thế chúng bằng một biểu diễn ngắn hơn. Phương pháp nén này sử dụng các số đếm độ lặp lại, kèm theo đoạn lặp được đặt trong dấu ngoặc đơn.

Ví dụ: Chuỗi "~abababaaaaa~" có thể nén thành "~3(ab)5(a)~", trong đó "~3(ab)~" biểu thị đoạn "~ab~" được lặp lại ~3~ lần, "~5(a)~", biểu thị ký tự '~a~' xuất hiện ~5~ lần liên tiếp.

Định nghĩa cú pháp nén:

• <~L~> là một ký tự thường trong khoảng từ '~a~' đến '~z~'.

• <~D~> là một số nguyên lớn hơn hoặc bằng ~2~, biểu thị số lần lặp lại của chuỗi con bên trong dấu ngoặc đơn.

• <~R~> có thể là:

  • Một ký tự <~A~> duy nhất, hoặc một chuỗi nén bằng cách sử dụng một số nguyên <~D~> và một phần tử <~R~> khác.

  • <~S~> biểu diễn một chuỗi ký tự đã nén, có thể bao gồm một hoặc nhiều phần tử <~R~>.

Yêu cầu: Cho một chuỗi ~A~, hãy xác định cách nén chuỗi ~A~ sao cho độ dài biểu diễn của nó là ngắn nhất có thể. Biểu diễn độ dài của chuỗi nén nếu có nhiều cách nén có độ dài ngắn nhất thì chọn cách nào xuất hiện đầu tiên từ trái sang phải trong chuỗi gốc ~A~.

Input

Vào từ file văn bản WSTRING.INP:

• Dòng đầu tiên gồm một số nguyên ~N~ ~(1\leq N\leq 200)~ là độ dài của chuỗi đầu vào ~A~.
• Dòng thứ hai ghi chuỗi đầu vào ~A~, chỉ gồm các ký tự Latin thường.

Output

Ghi ra file văn bản WSTRING.OUT: Một chuỗi ký tự ~S~, là chuỗi đã được nén sao cho độ dài là ngắn nhất.

Scoring

• Subtask ~1~ ~(60\%)~: ~1\leq N\leq 10~.
• Subtask ~2~ ~(20\%)~: ~5\leq N\leq 25~ và chuỗi ~A~ chỉ gồm các chữ cái ~a~ và ~b~.
• Subtask ~3~ ~(20\%)~: Không có ràng buộc gì thêm.

Example input 1

15
zzzzzzzzzzzzzzz

Example output 1

15(z)

Example input 2

4
aaaa

Example output 2

4(a)

Note 2

Có ~2~ cách biểu diễn ngắn nhất là "~aaaa~" và "~4(a)~", đều dài ~4~ ký tự. Tuy nhiên, "~4(a)~" được ưu tiên vì có thứ tự từ điển bé hơn.

Example input 3

3
bbb

Example output 3

bbb

Note 3

Chúng ta giữ nguyên chuỗi thì sẽ có độ dài là ~3~ còn nếu chúng ta nén thành "~3(b)~" thì sẽ có độ dài là ~4~.

Example input 4

7
abcdefg

Example output 4

abcdefg

Example input 5

22
ababbaaaaaaaahabbabcaaan

Example output 5

2(3(ab)5(a))

Example input 6

11
ahbabaaaaaa

Example output 6

3(ab)5(a)