Chọn ĐTQG TPHCM 2023

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. Đường tròn tâm O

Cho $N$ điểm trên mặt phẳng tọa độ $Oxy$ , điểm thứ $i$ $(1 \leq i \leq N)$ có tọa độ là $(x i; y i)$ .

Yêu cầu : Hãy viết chương trình xác định số lượng lớn nhất các điểm cùng nằm trên một đường tròn nào đó có tâm là gốc tọa độ $O$ của hệ trục tọa độ.

Input

Dòng thứ nhất chứa số nguyên $N$ $(1 \leq N \leq 105)$ ;

Trên $N$ dòng tiếp theo, dòng thứ $i$ chứa $2$ số nguyên $x i, y i$ cho biết tọa độ của điểm thứ $i$ . Các số nguyên này có giá trị tuyệt đối không vượt quá $104$ . Các số cách nhau bởi ít nhất một khoảng trắng. Tọa độ của các điểm có thể trùng nhau.

Output

Ghi ra một số nguyên là số lượng lớn nhất các điểm cùng nằm trên một đường tròn có tâm là gốc $O$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$30%$	$1 \leq N \leq 1000$
2	$30%$	Tọa độ các điểm có giá trị tuyệt đối không vượt quá $100$
3	$40%$	$1000 < N \leq 105$

Sample Input 1

Sample Output 1

Notes

Có $4$ điểm cùng nằm trên đường tròn tâm $O$ bán kính $\sqrt(10)$ là: $C(3;1)$ , $F(1;3)$ , $G(-1;3)$ và $H(3;1)$ . Có thể kiểm tra được đây là số lượng lớn nhất các điểm cùng nằm trên một đường tròn tâm $O$ .

---

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. Giá trung bình

Để có thể đưa ra những quyết định mua vào, bán ra hợp lý của cổ phiếu thì nhà đầu tư chứng khoán cần phân tích tình hình thị trường thật kỹ lưỡng. Một trong những yếu tố quan trọng được nhiều nhà đầu tư quan tâm là giá bán trung bình của một cổ phiếu so với một mức giá tham chiếu.

Yêu cầu : Xét giá bán của một cổ phiếu trong $N$ phiên giao dịch và một mức giá tham chiếu $P$ . Hãy viết chương trình cho biết có bao nhiêu phiên giao dịch liên tiếp trong $N$ phiên trên có giá bán trung bình lớn hơn hoặc bằng giá tham chiếu $P$ . Cụ thể là nếu đánh số các phiên giao dịch từ $1$ đến $N$ thì có bao nhiêu cặp chỉ số $(L, R)$ để giá trung bình của các cổ phiếu trong phiên giao dịch từ $L$ đến $R$ là lớn hơn hoặc bằng giá $P$ .

Input

Dòng thứ nhất chứa số nguyên $N$ $(1 \leq N \leq 106)$ ;

Dòng thứ hai chứa $N$ số nguyên $G i$ $(0 \leq G i \leq 109)$ lần lượt cho biết giá bán của cổ phiếu trong $N$ phiên giao dịch;

Dòng thứ ba chứa số nguyên $P$ $(0 \leq P \leq 109)$ là mức giá tham chiếu.

Output

Ghi ra một số nguyên là số phiên giao dịch liên tiếp trong $N$ phiên được xét có giá bán trung bình lớn hơn hay bằng giá tham chiếu $P$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$30%$	$1 < N \leq 1000$
2	$20%$	$1000 < N \leq 104$
3	$50%$	$5 \cdot 105 < N \leq 106$

Sample Input 1

10
5 8 9 3 7 2 8 10 6 5
9

Sample Output 1

Notes

Các phiên giao dịch liên tiếp có giá trị trung bình lớn hơn hoặc bằng $9$ là: ${9}$ , ${8; 10}$ , ${10}$ .

---

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. Đường ống thoát nước

Trong một tòa nhà chung cư, người ta thiết kế một hệ thống thoát nước bao gồm $N$ chốt được đánh số $1, 2, \dots, N$ cùng với $N$ đường ống hai chiều nối giữa $N$ cặp chốt có dạng $(i, j)$ với $i \neq j$ và $1 \leq i, j \leq N$ . Hệ thống là đạt yêu cầu nếu như từ mỗi chốt, nước đều có thể chảy đến tất cả các chốt khác thông qua các đường ống. Nguyên tắc hoạt động của hệ thống là: ban đầu hệ thống sẽ không có nước, mỗi khi có nước chảy vào từ một chốt $X$ nào đó, nước sẽ thoát ra qua các chốt được nối trực tiếp với chốt $X$ thông qua các đường ống. Cứ tiếp tục như thế, nước sẽ chảy lan ra toàn hệ thống và có xu hướng chảy càng lúc càng xa chốt $X$ chứ không chảy ngược lại. Nếu nước chảy đến một chốt nào đó mà không chảy đi được nữa thì dừng lại tại đó.

Ban quản lý muốn bỏ bớt đúng một đường ống để hệ thống vẫn đạt yêu cầu và ứng với cách bỏ đó, tồn tại cách chọn chốt $X$ thích hợp để mỗi khi có nước chảy vào $X$ thì ở mọi chốt trong hệ thống, nước sẽ đều chảy đến được và sẽ thoát ra từ chốt đó bằng không quá $K$ chốt khác.

Yêu cầu : Hãy viết chương trình xác định số cách chọn bỏ đi một đường ống nào đó để hệ thống còn lại vẫn đảm bảo các yêu cầu trên.

Input

Dòng thứ nhất chứa số $N, K$ với $1 \leq K < N \leq 105$ ;

Trên $N$ dòng tiếp theo, mỗi dòng chứa một cặp số $i, j$ cho biết có đường ống nước nối giữa chốt $i$ và chốt $j$ . Hệ thống sẽ đảm bảo đạt yêu cầu và các cặp $(i, j)$ phân biệt nhau giữa các dòng.

Output

Ghi ra một số nguyên là số cách bỏ đường ống.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$1 \leq K < N \leq 10$
2	$20%$	$N - 2 \leq K < N \leq 104$
3	$20%$	$K = 1$ và $2 \leq N \leq 104$
4	$40%$	$1 \leq K < N \leq 105$

Sample Input 1

Sample Output 1

Notes

Ta có $1$ cách bỏ đường ống như sau: bỏ đường ống nối $(2, 3)$ và chọn chốt $X$ là $7$ . Khi đó, nước sẽ chảy từ chốt $7$ đến $2$ , từ đây thoát ra chốt $1$ và $8$ ; tiếp theo, từ chốt $1$ chảy đến $3$ ; từ chốt $3$ chảy đến chốt $4$ và $6$ ; cuối cùng là từ chốt $4$ đến $5$ .

Nếu bỏ đường ống nối chốt $(1, 2)$ thì cho dù chọn chốt $X$ là chốt nào thì khi đến chốt $3$ , nước sẽ thoát ra theo ít nhất $3$ chốt khác (tức là lớn hơn $K$ ). Tương tự nếu bỏ đường ống $(1, 3)$ thì cho dù chọn chốt $X$ là chốt nào thì khi đến $2$ , nước sẽ thoát ra theo ít nhất $3$ chốt khác.

Ngoài ra, nếu bỏ bất kỳ đường ống nào khác thì hệ thống sẽ không còn đạt yêu cầu nữa.

---

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. Các loại đồng xu

Ở ngôi làng Olympic thần tiên, người dân sống trong các nông trại rộng lớn giữa các ngọn núi. Họ dùng hệ thống tiền xu riêng và di chuyển bằng thảm bay. Vào một ngày hội đặc biệt của năm, Trưởng làng Triết tổ chức bán các nông trại và các thảm bay với mức giá ưu đãi cho người dân: mỗi nông trại có giá tiền là $N$ đồng và mỗi thảm bay có giá tiền là $M$ đồng, trong đó $N$ và $M$ là các số nguyên dương.

Hệ thống tiền có nhiều mệnh giá khác nhau là các số nguyên dương, mỗi mệnh giá có số lượng xu không giới hạn. Thú vị là với mỗi mệnh giá của hệ thống tiền ở đây, người dân có thể dùng một hoặc nhiều xu cùng loại để có được số tiền vừa đúng $N$ đồng, đủ mua một nông trại. Trưởng làng đã tính toán rằng không có mệnh giá nào khác với các xu có trong làng mà cũng có tính chất thú vị như nêu trên.

Yêu cầu: Tính số lượng xu ít nhất (có thể cùng loại hoặc khác loại, với số lượng tùy ý) để đổi ra được đúng $M$ đồng, là số tiền vừa đủ mua được một cái thảm bay.

Input

Dòng duy nhất chứa hai số nguyên dương $N$ và $M$ với $1 \leq N \leq 1010$ , $1 \leq M \leq 105$ .

Output

Một số nguyên là số lượng xu ít nhất cần sử dụng để có thể mua được một cái thảm bay.

Subtasks

50% số điểm ứng với $1 \leq N \leq 100$ , $1 \leq M \leq 1000$ .

50% số điểm ứng với $1 \leq N \leq 1010$ , $1 \leq M \leq 105$ .

4 10

---

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. Cửa hàng trà sữa

Sau những ngày chinh chiến cùng các kỳ thi lập trình thi đấu, Tài đã về nhà mở một cửa hàng trà sữa của riêng mình. Cửa hàng có 3 loại trà đặc biệt là: trà sữa hạnh nhân, trà sữa sen vàng và trà sữa gừng. Các loại trà sữa này được pha chế theo cách rất đặc biệt làm người thưởng thức có trải nghiệm khó quên. Nhân dịp khai trương, cửa hàng xếp các ký tự H, S và G đại diện cho các loại trà sữa trên thành một dãy có độ dài $N$ và mỗi khách đến mua có thể tham gia một chương trình khuyến mãi như sau: khách chọn ra dãy các ký tự liên tiếp tương ứng với các loại trà mà mình muốn mua; Tài sẽ đếm số lượng các ký tự H, S, G có trong dãy đã chọn và nhân các giá trị này lại với nhau; nếu kết quả thu được là một lũy thừa của 2 thì khách hàng sẽ nhận được phiếu giảm giá.

Yêu cầu: Đếm số cặp chỉ số $(L, R)$ với $1 \leq L \leq R \leq N$ sao cho nếu gọi $a, b, c$ lần lượt là số lượng ký tự H, S, G có trong đoạn dãy con liên tiếp từ $L$ đến $R$ thì tích $a \times b \times c$ là một lũy thừa của 2.

Input

Dòng duy nhất chứa $N$ ký tự thuộc {H, S, G} viết liên tiếp nhau không dấu cách, trong đó $1 \leq N \leq 105$ .

Output

Một số nguyên là số cách để nhận được khuyến mãi, cũng chính là số chuỗi con thỏa mãn yêu cầu đã nêu.

Subtasks

20% số điểm ứng với $N \leq 102$ .

40% số điểm ứng với $102 < N \leq 103$ .

40% số điểm ứng với $103 < N \leq 105$ .

HHSSGG

---

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. Thẻ xe buýt miễn phí

Với thành tích học tập xuất sắc trong lớp chuyên Tin, bạn Hùng được nhà tài trợ tặng thưởng một thẻ đi xe buýt miễn phí. Thành phố có $N$ trạm xe buýt, được đánh số từ 1 đến $N$ và có $M$ tuyến xe vận chuyển hành khách giữa các trạm, được đánh số từ 1 đến $M$ . Tuyến xe thứ $i$ sẽ di chuyển hai chiều giữa trạm $A i$ và $B i$ với tiền vé là $C i$ . Hệ thống các tuyến xe được thiết kế để đảm bảo rằng khi đi xe buýt từ một trạm, ta đều có thể đến được một trạm bất kỳ khác. Nhà của Hùng ở gần trạm $S$ còn trường học thì ở gần trạm $T$ . Với thẻ xe buýt miễn phí, Hùng được chọn đúng một hành trình mà tổng tiền vé ít nhất để đi từ trạm $S$ đến trạm $T$ . Có thể có nhiều hành trình khác nhau để đi từ $S$ đến $T$ với cùng tổng tiền vé ít nhất như thế, nhưng Hùng chỉ được chọn ra đúng một hành trình.

Lúc đó, Hùng sẽ được miễn giá vé cho tất cả các tuyến xe thuộc hành trình đã chọn. Ngoài ra, Hùng cũng thường hay đi đến hai nhà sách ở gần trạm $U$ và $V$ . Khi di chuyển bằng xe buýt từ $U$ đến $V$ , Hùng không cần phải trả tiền vé cho những tuyến xe buýt được miễn giá vé. Một hành trình miễn giá vé được gọi là tối ưu khi số tiền Hùng phải trả để mua vé đi từ $U$ đến $V$ là nhỏ nhất.

Yêu cầu: Tính tổng tiền vé ít nhất mà Hùng phải trả để đi từ $U$ đến $V$ nếu Hùng chọn được một hành trình miễn giá vé tối ưu.

Input

Dòng thứ nhất chứa hai số nguyên $N$ và $M$ ( $2 \leq N \leq 105$ , $1 \leq M \leq 2 \times 105$ ).

Dòng thứ hai chứa hai số nguyên $S$ và $T$ ( $1 \leq S, T \leq N$ ; $S \neq T$ ).

Dòng thứ ba chứa hai số nguyên $U$ và $V$ ( $1 \leq U, V \leq N$ ; $U \neq V$ ; cặp $(S, T)$ khác cặp $(U, V)$ ).

Trên $M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $A i, B i, C i$ ( $1 \leq A i, B i \leq N$ ; $1 \leq C i \leq 109$ ; $A i \neq B i$ ).

Output

Một số nguyên là tổng tiền vé ít nhất Hùng phải trả theo yêu cầu trên.

Subtasks

30% số điểm ứng với $S = U$ .

30% số điểm ứng với $N \leq 300$ .

40% số điểm ứng với $2 \leq N \leq 105$ , $1 \leq M \leq 2 \times 105$ .

5 7 1 3 4 5 1 2 10 1 3 30 1 4 15 2 3 10 4 3 5 3 5 10 4 5 12

---

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 trúc đề và tiến độ