Chọn ĐTQG Quảng Trị 2024

Chọn ĐTQG Quảng Trị 2024

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Xâu đối xứng đôi

Việt Anh định nghĩa xâu đối xứng đôi PADBLE là xâu gồm các kí tự in thường'a'..'z'trong bảng mã ASCII có độ dài chẵn được ghép thành từ hai xâu con đối xứng có độ dài bằng nhau và có ít nhất hai kí tự khác nhau. Ví dụ xâu"abacdc","ab","aabb"là các xâu đối xứng đôi, nhưng xâu"aaaaabbb"không phải là xâu đối xứng đôi.

Yêu cầu : Cho xâu S chỉ chứa các kí tự'a'và'b', em hãy lập trình giúp Việt Anh tìm độ dài xâu PADBLE lớn nhất và có bao nhiêu xâu con có cùng độ dài lớn nhất đó trong xâu S?

Input

Chứa xâu S gồm các kí tự'a'và'b'.

Output

Gồm hai số nguyên là độ dài xâu đối xứng đôi lớn nhất và số xâu có độ dài lớn nhất, cách nhau dấu cách. Nếu không có xâu nào thỏa mãn thì in ra -1.

Scoring

Sample Input 1

aaabbaabbbaa

Sample Output 1

4 4

Sample Input 2

aaabbaabbbaaaa

Sample Output 2

6 1

Sample Input 3

aaaaaaaaaa

Sample Output 3

-1

Notes

Ví dụ 1 xâu đối xứng đôi có độ dài lớn nhất là 4 và có 4 xâu con thỏa mãn xâu PADBLE là"aabb"bắt đầu vị trí số 2,"bbaa"bắt đầu vị trí số 4,"aabb"bắt đầu vị trí số 6,"bbaa"bắt đầu vị trí số 9.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Tổng GCDS dãy số

Cho dãy số nguyên dương a₁, a₂, ⋯, a_N có N phần tử. Việt Anh định nghĩa hàm f(i,j) là tổng của tất cả giá trị (a_i · a_j)/d² với d là một ước chung của a_i và a_j. Ước chung của hai số nguyên dương x, y là số tự nhiên d mà x, y đều chia hết cho d.

Ví dụ dãy A = {2, 1, 4} thì f(1,3) = (2 · 4)/1² + (2 · 4)/2² = 10 với {1,2} là các ước chung của 2 và 4, f(1,2) = (2 · 1)/1² = 2 và f(2,3) = (1 · 4)/1² = 4.

Tổng GCDS của dãy số chính là tổng tất cả các f(i,j) định nghĩa ở trên sao cho 1 ≤ i < j ≤ N. Dãy A = {2, 1, 4} tổng GCDS của dãy số là f(1,2) + f(1,3) + f(2,3) = 16.

Việt Anh biết các bạn trường THPT Chuyên Lê Quý Đôn học lập trình rất tốt nên đưa ra bài toán như sau: Cho dãy số nguyên dương a₁, a₂, ⋯, a_N có N phần tử cần tính tổng GCDS của dãy số. Ngoài ra, Việt Anh còn thực hiện thêm Q truy vấn, với mỗi truy vấn cho hai số (x,y) gán phần tử a_x = y. Hãy tính tổng GCDS của dãy số mới.

Yêu cầu : Cho dãy số nguyên dương a₁, a₂, ⋯, a_N có N phần tử, thực hiện:

• Tính tổng GCDS của dãy số;

• Trả lời Q truy vấn, với mỗi truy vấn (x,y) hãy tính tổng GCDS của dãy số sau khi dãy đã được thay đổi.

Input

• Dòng đầu tiên chứa hai số nguyên dương N và Q (1 ≤ N,Q ≤ 5 · 10⁵);

• Dòng thứ 2 ghi dãy a₁, a₂, ⋯, a_N (1 ≤ a_i ≤ 5 · 10⁵);

• Q dòng tiếp theo mỗi dòng ghi lần lượt hai số x và y biểu thị truy vấn này gán a_x = y (1 ≤ x ≤ N, 1 ≤ y ≤ 5 · 10⁵).

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

Output

• Dòng đầu tiên ghi phần dư của tổng GCDS của dãy số ban đầu khi chia 10⁹ + 7;

• Q dòng tiếp theo mỗi dòng ghi một số là phần dư của tổng GCDS của dãy khi chia 10⁹ + 7 tương ứng với thứ tự truy vấn trong tệp dữ liệu vào.

Scoring

Sample Input 1

2 2
2 4
1 4
1 3

Sample Output 1

10
21
12

Sample Input 2

4 3
462955 253652 126897 278176
2 5432
1 2314
3 2

Sample Output 2

57273948
41211035
109845881
827916911

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Hệ thống tính điểm GSCORES

Nhân dịp khánh thành siêu thị VINCOMPLAZA tại Đông Hà, Việt Anh được bố mẹ dẫn đi chơi tại khu vui chơi có trong siêu thị. Bạn ấy rất thích thú với các trò chơi ở đây, đặc biệt là trò chơi mang tên"G_SCORES"với hệ thống tính điểm vô cùng thú vị.

G_SCORESlà trò chơi mới được các nhà phát triển tạo ra N màn chơi, màn chơi thứ i có cấp độ là i. Hệ thống điểm thưởng cho các cấp độ của trò chơi được thiết lập như sau:

• Cấp độ i có điểm thưởng là số nguyên dương s_i có giá trị từ 1 đến N. Các cấp độ được sắp xếp theo độ khó tăng dần (s₁ ≤ s₂ ≤ ⋯ ≤ s_N);

• Để đảm bảo người chơi vượt qua nhiều cấp độ sẽ được xếp hạng cao hơn, các nhà phát triển thiết lập quy tắc: Với một số k (2 ≤ k ≤ N) bất kỳ, tổng số điểm của k màn chơi phải lớn hơn tổng số điểm của mọi lần mà có số màn chơi ít hơn k.

Yêu cầu : Cho N màn chơi, hỏi có bao nhiêu cách thiết lập hợp lệ để các nhà phát triển thiết lập hệ thống điểm cho các cấp độ thỏa mãn những điều kiện nêu trên?

Input

• Dòng đầu tiên chứa một số nguyên T (1 ≤ T ≤ 5) là số lượng bộ tests;

• T dòng tiếp theo, dòng thứ i chứa số nguyên N (2 ≤ N ≤ 5000) là số màn chơi.

Output

Gồm có T dòng, dòng thứ i theo thứ tự ghi phần dư của số cách thiết lập hệ thống điểm hợp lệ khi chia 10⁹ + 7.

Scoring

Sample Input 1

3
2
3
4

Sample Output 1

3
7
16

Notes

Ở ví dụ trên với N = 3 ta có 7 dãy s_i tương ứng như sau:

1 1 1
1 2 2
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Trao đổi

An rất thích sưu tập tem và An đã sưu tập được nhiều con tem quý. Tại một buổi trưng bày các con tem cổ của những người sưu tập tem trong thành phố. An phát hiện ra một con tem cổ mà An rất thích và đã mất rất nhiều công sức tìm kiếm lâu nay. An muốn mua lại con tem đó nhưng chủ nhân của con tem không bán mà chỉ đồng ý trao đổi bằng những con tem mà An đang có.

Bộ sưu tập của An có N con tem, đánh số từ 1 đến N. Con tem thứ i có giá trị C_i với i = 1, 2, ⋯, N. Các con tem có giá trị bằng nhau được xem là cùng một loại. Chủ nhân của con tem mà An muốn đổi yêu cầu An phải đổi bằng một số con tem và tổng giá trị của các con tem đó phải lớn hơn hoặc bằng P.

An rất muốn sở hữu con tem cổ nhưng cũng cân nhắc cách đổi sao cho giữ lại cho mình nhiều loại tem khác nhau nhất và tổng giá trị các con tem đem trao đổi càng nhỏ càng tốt.

Yêu cầu : Bạn hãy tìm cách trao đổi giúp An có được con tem như mong muốn.

Input

• Dòng đầu tiên chứa hai số nguyên N, P (1 ≤ N,P ≤ 6 · 10⁴);

• Dòng tiếp theo chứa N số nguyên không âm C₁, C₂, ⋯, C_N, và P ≤ C₁ + C₂ + ⋯ + C_N ≤ 2 · P.

Các số trên cùng một dòng cách nhau dấu cách.

Output

• Dòng thứ nhất ghi hai số nguyên dương D, S (S ≥ P) với D là số lượng loại tem khác nhau còn lại sau khi trao đổi và S là tổng giá trị các con tem đem ra trao đổi;

• Dòng thứ hai ghi K số nguyên C_i1, C_i2, ⋯, C_iK là giá trị các con tem đem ra trao đổi theo thứ tự không giảm.

Các số trên một dòng ghi cách nhau dấu cách.

Nếu chỉ đúng giá trị D thì được 20% số điểm của test đó.

Scoring

Sample Input 1

8 21
5 5 5 0 7 4 7 9

Sample Output 1

4 21
5 7 9

Sample Input 2

7 100
90 2 2 3 3 6 6

Sample Output 2

3 101
2 3 6 90

Notes

Ví dụ 1:

• Có 4 loại tem khác nhau trong số các con tem còn lại {0, 4, 5, 5, 7};

• Có thể dùng các con tem {4, 5, 5, 7} để đổi.

Ví dụ 2, để còn lại 3 loại tem {2, 3, 6}, cần phải đổi các con tem với tổng 101.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Phủ điểm

Trong thời gian chờ vào tiết học, An và Lạc cùng nhau chơi một trò chơi đơn giản. An lấy một tờ giấy vở học sinh hình chữ nhật kẻ ô vuông có chiều rộng W, chiều cao H và vẽ một số điểm lên tờ giấy đó. Có thể xem góc dưới bên trái của tờ giấy có tọa độ (0, 0) và góc trên bên phải có tọa độ (W, H). Các điểm có thể vẽ trùng nhau nhưng được tính như các điểm phân biệt. Lạc lấy ra một mảnh giấy hình chữ nhật có chiều rộng w, chiều cao h và hai bạn cùng tìm cách đặt mảnh giấy này lên tờ giấy sao cho các cạnh của mảnh giấy song song với các biên của tờ giấy đã vẽ các điểm, chiều rộng và chiều cao mảnh giấy tương ứng với chiều rộng, chiều cao của tờ giấy và mảnh giấy phủ được nhiều điểm nhất có thể. Các điểm nằm trên biên của mảnh giấy cũng được xem là bị phủ.

An, Lạc đã vào lớp. Bạn hãy tiếp tục trò chơi khi tờ giấy và mảnh giấy có kích thước lớn hơn.

Yêu cầu : Cho n điểm và kích thước w, h của mảnh giấy, hãy tìm số điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật đó.

Input

• Dòng đầu chứa ba số nguyên n, w, h (1 ≤ n ≤ 10⁵, 1 ≤ w, h ≤ 10⁸);

• n dòng tiếp theo, dòng thứ i chứa hai số nguyên x_i và y_i là tọa độ của điểm thứ i được vẽ trên tờ giấy (1 ≤ x_i, y_i ≤ 10⁸).

Các số trên một dòng cách nhau dấu cách.

Output

Gồm một dòng ghi một số là số lượng điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật.

Scoring

Sample Input 1

6 2 3
1 1
3 1
2 2
3 3
5 3
3 5

Sample Output 1

4

Sample Input 2

10 8 8
8 9
20 14
3 9
7 8
3 4
7 8
10 19
6 11
5 10
8 2

Sample Output 2

7

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. Kết nối

Quốc gia Byteland xinh đẹp có N thành phố đánh số từ 1 đến N. Có M tuyến đường một chiều nối giữa hai thành phố khác nhau, đánh số từ 1 đến M. Có thể có nhiều hơn một tuyến đường cùng một chiều nối giữa hai thành phố.

Chính quyền Byteland chuẩn bị kế hoạch sửa chữa các tuyến đường. Tuyến đường trong thời gian sửa chữa sẽ dừng hoạt động. Một câu hỏi đặt ra cho chính quyền lúc này là: "Có thể đi từ thành phố A đến thành phố B và từ B quay lại thành phố A được hay không khi dừng hoạt động của một trong các tuyến đường của quốc gia?". Bởi sẽ có nhiều cặp thành phố cần có sự kết nối giao thông giữa chúng trong thời gian thi công các tuyến đường, bạn hãy giúp chính quyền Byteland trả lời các câu hỏi đó.

Yêu cầu : Cho sơ đồ giao thông của quốc gia Byteland, hãy trả lời Q câu hỏi như đã nêu.

Input

• Dòng đầu chứa hai số nguyên N, M (2 ≤ N ≤ 2000, 1 ≤ M ≤ 10⁵);

• M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N) mô tả một tuyến đường một chiều nối từ thành phố u đến thành phố v;

• Dòng tiếp theo chứa số nguyên Q (0 ≤ Q ≤ 10⁵):Nếu Q ≠ 0 thì Q dòng tiếp theo mỗi dòng chứa hai số nguyên A, B (1 ≤ A, B ≤ N) mô tả một câu hỏi như trên;Nếu Q = 0 thì không chứa gì thêm, khi đó bạn sẽ trả lời tất cả các câu hỏi tương ứng với các cặp có thứ tự: (1,1); (1,2); (1,3); ⋯; (1,N); (2,2); (2,3); ⋯; (2,N); (3,3); ⋯; (3,N); ⋯; (N,N).

Các số trên một dòng cách nhau dấu cách.

Output

Với mỗi câu hỏi tương ứng với một cặp thành phố A, B, bạn trả lời theo một trong các giá trị sau:

• 0: Trong trường hợp không dừng hoạt động tuyến đường nào mà vẫn không có đường đi cho ít nhất của một trong hai hướng (từ A đến B hoặc từ B đến A);

• M + 1: Trong trường hợp nếu dừng hoạt động của bất kỳ tuyến đường nào thì cũng có đường đi từ A đến B và từ B quay lại A;

• E: Là một số trong khoảng từ 1 đến M là số hiệu tuyến đường mà khi dừng hoạt động tuyến đường đó thì sẽ không có đường đi cho ít nhất một trong hai hướng. Nếu có nhiều tuyến đường như vậy thì ghi ra tuyến đường có số hiệu nhỏ nhất.

Để ghi ra các giá trị này bạn thực hiện theo yêu cầu sau:

• Gọi r₁, r₂, ⋯, r_K là các giá trị trả lời cho Q câu hỏi (K = Q) trong trường hợp Q ≠ 0, nếu Q = 0 thì K = N × (N+1)2;

• Kết quả gồm một dòng ghi một số là phần dư của số nguyên P khi chia cho 10⁹ + 7 với: P = r₁ × B^K-1 + r₂ × B^K-2 + r₃ × B^K-3 + ⋯ + r_K × B⁰, trong đó B = 2 × 10⁵.

Scoring

Sample Input 1

6 11
1 4
4 3
3 5
5 1
1 3
3 6
5 6
6 2
4 2
5 1
3 5
0

Sample Output 1

575589257

Sample Input 2

8 17
5 2
6 5
4 6
4 8
4 3
3 1
2 7
7 4
5 4
8 7
8 3
3 6
6 1
2 4
1 5
1 5
5 2
4
4 6
8 1
5 2
6 7

Sample Output 2

995598902

Notes

Trong ví dụ thứ nhất:

• Câu hỏi (1,6): Không có đường đi từ 6 về 1 trong khi không dừng hoạt động tuyến đường nào;

• Câu hỏi (1,3): Dừng hoạt động bất kỳ tuyến đường nào thì cũng có đường đi theo cả hai hướng giữa 1 và 3;

• Câu hỏi (4,5): Khi dừng hoạt động tuyến đường từ 1 đến 4 (số hiệu 1) thì sẽ không có đường đi từ 5 đến 4.

Dãy kết quả tương ứng là 12, 0, 12, 1, 12, 0, 12, 0, 0, 0, 0, 12, 1, 12, 0, 12, 1, 0, 12, 0, 12.

Trong ví dụ thứ hai:

• Câu hỏi (8,1): Nếu dừng hoạt động tuyến đường từ 4 đến 8 thì sẽ không có đường đi từ 1 đến 8;

• Câu hỏi (6,7): Nếu dừng hoạt động tuyến đường từ 7 đến 4 thì sẽ không có đường đi từ 7 đến 6.

Dãy kết quả tương ứng là 18, 4, 18, 8.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.