USACO 2022 December Contest, Platinum, Palindromes

Xem PDF

Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Liên Hiệp Bò của Farmer John (UCFJ) đang tham gia giải vô địch hoofball hàng năm! Đội UCFJ gồm \(N\) bò (\(1 \le N \le 7500\)) đã giành được huy chương vàng trong môn hoofball, vượt qua đội của Farmer Nhoj một cách sát sao.

Các con bò đã sắp xếp hàng để chuẩn bị cho buổi lễ trao giải. Chúng muốn John chụp \(\frac{N(N+1)}{2}\) bức ảnh nhóm, một bức cho mỗi chuỗi con liên tiếp trong đội hình.

Tuy nhiên, John, với tư cách là huấn luyện viên của đội, rất kén chọn về cách mà các con bò nên được xếp hàng. Cụ thể, ông từ chối chụp ảnh cho một chuỗi con trừ khi nó tạo thành một palindrome, có nghĩa là giống bò của con bò thứ \(i\) từ đầu chuỗi con phải giống với giống bò của con bò thứ \(i\) từ cuối chuỗi con đối với tất cả các số nguyên dương \(i\) nhỏ hơn hoặc bằng độ dài của chuỗi con. Mỗi giống bò có thể là Guernsey hoặc Holstein.

Đối với mỗi một trong \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình, hãy đếm số lần hoán đổi tối thiểu cần thiết để sắp xếp chuỗi con đó thành một palindrome (hoặc \(-1\) nếu không thể làm được). Một lần hoán đổi đơn giản là việc lấy hai con bò kề nhau trong chuỗi con và hoán đổi vị trí của chúng. Xuất ra tổng số lần hoán đổi của tất cả các chuỗi con này.

Lưu ý rằng số lần hoán đổi cần thiết được tính độc lập cho mỗi chuỗi con (các con bò quay trở lại vị trí ban đầu giữa các bức ảnh).

Input

  • Đội hình, được biểu diễn bằng một chuỗi gồm các ký tự G và H có độ dài \(N\).

Output

  • Tổng số lần hoán đổi được đề cập trên đối với tất cả \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình.

Scoring

  • Subtask 1: \(N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]\).

Example

Test 1

Input
GHHGGHHGH
Output
12
Note

Bốn chuỗi con liên tiếp đầu tiên là G, GH, GHH và GHHG. Cả G và GHHG đều đã là palindrome, vì vậy chúng đóng góp \(0\) vào tổng. GHH có thể được sắp xếp thành một palindrome bằng một lần hoán đổi, vì vậy nó đóng góp \(1\) vào tổng. GH không thể được sắp xếp thành palindrome bằng bất kỳ số lần hoán đổi nào, vì vậy nó đóng góp \(-1\) vào tổng.

Một chuỗi con liên tiếp khác đóng góp vào tổng là HHGG. Chuỗi này có thể được sắp xếp thành một palindrome bằng hai lần hoán đổi.


Bình luận

Không có bình luận nào.