Bedao Grand Contest 16
Points: 100
Khoa là một kẻ cuồng với những viên đá quý, đặc biệt là kim cương. Hiện tại Khoa có một danh sách ~N~ mỏ kim cương được đặt ở đâu đó trên trục tọa độ. Khoa muốn khai thác nhiều nhất kim cương từ các mỏ đã biết trước. Phạm vi khai thác của Khoa cũng kì hoặc như cách anh ấy thích kim cương, gọi ~(u, v)~ là tâm điểm của phạm vi mà Khoa khai thác, thì Khoa sẽ khai thác được các ô ~(u - 1, v - 1)~, ~(u - 1, v)~, ~(u - 1, v + 1)~, ~(u, v - 2)~, ~(u, v - 1)~, ~(u, v)~ ~(u, v + 1)~, ~(u, v + 2)~, ~(u + 1, v - 1)~, ~(u + 1, v)~, ~(u + 1, v + 1)~, ~(u + 2, v)~.
Hình minh họa:
Vì toàn ngỗng trong bộ môn hình học giải tích, nên Khoa quyết định nhờ bạn giúp anh ấy thõa sức với đam mê kim cương của mình.
Input
Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) – Số lượng mỏ kim cương.
~N~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x, y, w~ (~1 \leq x, y, w \leq 10^9~) biểu diễn một mỏ kim cương trên trục tọa độ – ~x, y~ đại diện cho tọa độ của mỏ, ~w~ là số viên kim cương trong mỏ.
Output
Một dòng duy nhất là số lượng kim cương tối đa mà Khoa có thể khai thác được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~50~ | ~1 \leq x, y \leq 10^3~ |
2 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5
1 1 5
1 2 3
1 3 9
2 3 4
2 2 4
Sample Output 1
25
Notes
Chọn tâm điểm khai thác là ~(2, 2)~, Khoa sẽ khai thác được cả ~5~ mỏ kim cương, lấy được tổng cộng ~25~ kim cương.
Points: 100
Trung là một thầy thuốc có tiếng bởi tài năng và lòng nhân từ của mình.
Sau kì thi VOI vừa rồi, nhiều bạn trẻ cưỡi VOI lần đầu đã tạch ngã
rất đau, vì vậy thầy thuốc Trung cần một lượng lớn nguyên liệu để bào
chế ra thuốc để chữa cho các bạn.
Vùng Trung ở có ~n~ ngọn núi, được kết nối bởi ~m~ con đường một chiều, trên con đường thứ ~i~ ban đầu có các cây thuốc cho sản lượng ~w_i~. Sau khi hái thuốc ở trên một con đường, các cây thuốc trên con đường này sẽ dần mọc lại nhưng sản lượng sẽ giảm đi một nửa (làm tròn xuống số nguyên gần nhất). Nhà của Trung ở ngọn núi ~1~, tìm lộ trình đi hái được nhiều thuốc nhất (có thể kết thúc ở một ngọn núi bất kì).
Input
Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(1 \leq n, m \leq 2 \times 10^5)~.
~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~ ~(1 \leq u, v \leq n; 1 \leq w \leq 10^9)~ mô tả một con đường nối giữa hai ngọn núi.
Output
- In ra số lượng thuốc tối đa Trung có thể thu thập được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~30~ | ~n, m \leq 15; w_i = 1~ ~\forall{i} = 1, 2, \ldots, m~ |
2 | ~30~ | ~u_i \leq v_i~ |
3 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
5 5
1 3 2
3 4 1
4 2 1
2 1 2
3 5 6
Sample Output 1
14
Sample Input 2
6 7
1 4 3
4 5 2
5 1 5
5 2 8
2 3 3
3 6 4
6 2 1
Sample Output 2
35
Notes
Trong ví dụ, lộ trình Trung có thể đi là ~1 \to 3 \to 4 \to 2 \to 1 \to 3 \to 4 \to 2 \to 1 \to 3 \to 5~ với lượng thuốc thu thập được là ~2 + 1 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 6 = 14~.
Points: 100
Cho ~n~ con ếch ngồi ở trên một đĩa tròn khổng lồ được biểu diễn dưới dạng một mặt phẳng hai chiều, ban đầu con ếch thứ ~i~ ở vị trí có tọa độ là ~(x_i,y_i)~. Có thể có nhiều con ếch ở cùng vị trí trong một thời điểm.
Có ~m~ sự kiện sẽ lần lượt diễn ra, mỗi sự kiện thuộc một trong bốn dạng như sau:
~\texttt{cw}~: Xoay đĩa tròn theo chiều kim đồng hồ. Vị trí của các con ếch được xoay theo chiều kim đồng hồ một góc 90 độ quanh gốc tọa độ.
~\texttt{ccw}~: Xoay đĩa tròn ngược chiều kim đồng hồ. Vị trí của các con ếch được xoay ngược chiều kim đồng hồ một góc 90 độ quanh gốc tọa độ.
~\texttt{xflip k}~: Các con ếch nhảy sang vị trí đối xứng với vị trí ban đầu qua đường thẳng ~x=k~.
~\texttt{yflip k}~: Các con ếch nhảy sang vị trí đối xứng với vị trí ban đầu qua đường thẳng ~y=k~.
Cho ~q~ truy vấn, mỗi truy vấn gồm hai số ~a~ và ~b~, bạn hãy tìm vị trí của con ếch thứ ~a~ ngay sau sự kiện thứ ~b~.
Input
Dòng đầu gồm ba số nguyên ~n, m, q~ lần lượt là số lượng ếch, số lượng sự kiện và số lượng truy vấn ~(1 \leq n,m,q \leq 2 \times 10^5)~.
Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm hai số nguyên ~x_i~ và ~y_i~ mô tả vị trí ban đầu của con ếch thứ ~i~ ~(-10^9 \leq x_i, y_i \leq 10^9)~.
Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm một chuỗi kí tự ~\texttt{event}_i \in \{\texttt{cw, ccw, xflip, yflip}\}~. Nếu ~\texttt{event}_i \in \{\texttt{xflip, yflip}\}~ thì có thêm số nguyên ~k_i~ ~(-10^9 \leq k_i \leq 10^9)~.
Dòng thứ ~i~ trong ~q~ dòng tiếp theo gồm hai số nguyên ~a_i~ và ~b_i~ (~1 \le a_i \le n~, ~1 \le b_i \le m~) mô tả truy vấn thứ ~i~.
Các số hoặc chữ trên cùng một dòng cách nhau bởi dấu cách.
Output
Dòng thứ ~i~ trong ~q~ dòng gồm một số nguyên là câu trả lời cho truy vấn thứ ~i~ (thứ tự như trong phần input).
Scoring
Subtask | Điểm | Ràng buộc |
---|---|---|
~1~ | ~10\%~ | ~1 \leq n, m, q \leq 2\times 10^3~ |
~2~ | ~20\%~ | Các sự kiện chỉ gồm dạng ~\texttt{cw, ccw}~ |
~3~ | ~30\%~ | Các sự kiện chỉ gồm dạng ~\texttt{xflip, yflip}~ |
~4~ | ~40\%~ | Không có ràng buộc gì thêm |
Sample Input 1
3 5 9
3 1
5 3
9 5
cw
xflip 7
ccw
yflip 8
ccw
1 1
2 1
1 2
1 3
3 3
1 4
2 4
1 5
3 5
Sample Output 1
1 -3
3 -5
13 -3
3 13
9 9
3 3
5 5
-3 3
-7 9
Sample Input 2
5 10 10
9 7
3 6
10 4
1 4
8 9
cw
ccw
ccw
xflip 10
xflip 4
yflip 7
yflip 6
yflip 8
cw
ccw
2 1
4 5
5 3
1 3
3 9
4 8
2 2
2 9
2 4
5 1
Sample Output 2
6 -3
-16 1
-9 8
-7 9
8 16
-16 17
3 6
15 18
26 3
9 -8
Notes
Giải thích test ví dụ đầu tiên:
Vị trí ban đầu của ~3~ con ếch:
Sau thao tác đầu tiên, vị trí của ~3~ con ếch là:
Vị trí ếch ~1~ sau thao tác ~1~ là (~1, -3~) nên nên truy vấn đầu tiên (~1, 1~) trả ra đáp án là (~1, -3~). Tương tự đáp án của truy vấn thứ hai (~2, 1~) trả ra (~3, -5~).
Sau thao tác thứ hai, vị trí của ~3~ con ếch là:
Đáp án của truy vấn (~1, 2~) là (~13, -3~).
Sau thao tác thứ ba, vị trí của ~3~ con ếch là:
Đáp án của truy vấn (~1, 3~) là (~3, 13~).
Đáp án của truy vấn (~3, 3~) là (~9, 9~).
Sau thao tác thứ tư, vị trí của ~3~ con ếch là:
Đáp án của truy vấn (~1, 4~) là (~3, 3~).
Đáp án của truy vấn (~2, 4~) là (~5, 5~).
Sau thao tác thứ năm, vị trí của ~3~ con ếch là:
Đáp án của truy vấn (~1, 5~) là (~-3, 3~).
Đáp án của truy vấn (~3, 4~) là (~-7, 9~).
Points: 100
Hôm nay trên đường đi học, Naot vô tình nhặt được trên đường một mảnh giấy chứa ~2~ mảng số nguyên ~a~ và ~b~ có độ dài ~n~. Phía sau mặt giấy có ghi một câu đố với nội dung như sau:
Gọi số nguyên thứ ~i~ ~(0 \le i < n)~ (của mảng ~a~ và mảng ~b~ là ~a_i~ và ~b_i~. Cho hàm ~f~ được định nghĩa như sau:
float f(float x, int a[], int b[], int n) {
float res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i != j) {
int da = a[i] - a[j];
int db = b[i] - b[j];
res = max(res, da * cos(x) + db * sin(x));
}
}
}
return res;
}
Hãy tìm giá trị nhỏ nhất của hàm ~f~ với ~2~ mảng số được cho trước. Kết quả được chấp nhận với sai số ~10^{-6}~.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ (~2 \leq n \leq 10^6~).
Dòng tiếp theo chứa ~n~ số nguyên ~a_0, a_1, ..., a_{n - 1}~ (~|a_i| \leq 10^5~).
Dòng tiếp theo chứa ~n~ số nguyên ~b_0, b_1, ..., b_{n - 1}~ (~|b_i| \leq 10^5~).
Output
- Xuất ra giá trị nhỏ nhất mà hàm ~f~ có thể đạt được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20~ | ~n \le 10~ |
2 | ~30~ | ~n \le 1000~ |
3 | ~50~ | ~n \le 10^6~ |
Sample Input 1
5
3 2 9 3 2
5 5 5 5 5
Sample Output 1
0.0000000000
Sample Input 2
4
1 0 1 2
0 -1 -2 -1
Sample Output 2
1.4142135624
Sample Input 3
5
3 1 5 3 4
7 2 9 3 5
Sample Output 3
1.6712580436
Notes
Ở trong ví dụ thứ nhất, giá trị ~x~ để hàm ~f~ đạt giá trị nhỏ nhất là ~x = \frac{\pi}{2}~.
Ở trong ví dụ thứ hai, giá trị ~x~ để hàm ~f~ đạt giá trị nhỏ nhất là ~x = \frac{\pi}{4}~.
Points: 100
Độ Mixi, tên thật là Phùng Thanh Độ, là một streamer, youtuber người Việt Nam, sở hữu kênh Youtube Mixigaming với 7,35 triệu người đăng ký. Tuy nhiên vào rạng sáng ngày 02/04/2024, máy tính của anh bất ngờ bị tin tặc xâm nhập, chiếm đoạt trái phép tất cả các thông tin tài khoản trong máy. Để lấy lại, Hacker đã yêu cầu anh trả 2500\$, hoặc trả lời bài toán sau đây:
Cho ba số nguyên dương ~n,c,s~ (~n\le 1000~, ~c\le 100~, ~n\cdot c\le s\le 10^9~). Tìm dãy số thực ~a_1,a_2,\ldots,a_n~ sao cho:
~a_i\ge c~ với mọi ~1\le i\le n~.
~a_1+a_2+\ldots+a_n=s~.
~\displaystyle\sum_{i=1}\sum_{j=i+1} \frac{a_i}{a_j}~ đạt giá trị nhỏ nhất.
Dù đã tốt nghiệp khoa Công Nghệ Thông Tin, Độ Mixi vẫn không thể tìm được dãy số thỏa mãn. Hãy giúp anh ấy!
Input
Một dòng duy nhất là ba số nguyên dương ~n, c, s~ (~n\le 1000~, ~c\le 100~, ~n\cdot c\le s\le 10^9~).
Output
Một dòng duy nhất gồm ~n~ số thực ~a_1,a_2,\ldots,a_n~ thỏa mãn các điều kiện trên. Câu trả lời sẽ được chấp nhận khi sai số giữa ~\displaystyle\sum_{i=1}\sum_{j=i+1} \frac{a_i}{a_j}~ trong câu trả lời của bạn so với đáp án không vượt quá ~10^{-6}~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~30~ | ~n = 3~ |
2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
3 2 10
Sample Output 1
2 2.472136 5.527864
Sample Input 2
5 2 20
Sample Output 2
2 2 2.839904 4.856167 8.303929
Sample Input 3
10 50 600
Sample Output 3
50 50 50 50 50 50 56.762135 67.501934 80.273780 95.462151
Notes
Ở trong ví dụ thứ nhất, đáp án trên là dãy tối ưu với ~\displaystyle\sum_{i=1}\sum_{j=i+1} \frac{a_i}{a_j}~ ~=~ ~\displaystyle\frac{a_1}{a_2} + \frac{a_1}{a_3} + \frac{a_2}{a_3}~ ~=~ ~1.618034~
Points: 100
Tập đoàn XYZ bao gồm một chủ tịch và ~n~ nhân viên, được đánh số từ ~1~ đến ~n~. Tập đoàn hoạt động theo mô hình cấp trên — cấp dưới, cấp trên trực tiếp của nhân viên ~i~ là ~p_i~ (nếu ~p_i = 0~ thì cấp trên trực tiếp chính là chủ tịch). Theo đó nếu ~p_i \neq 0~ thì nhân viên ~i~ cũng được coi là cấp dưới trực tiếp của nhân viên ~p_i~. Năng suất lao động của nhân viên ~i~ được đánh giá bằng điểm số ~a_i~, năng suất càng cao thì điểm càng cao.
Năm mới sắp đến, chủ tịch tập đoàn chuẩn bị thưởng Tết cho các nhân viên. Nhân viên ~i~ sẽ hài lòng với mức thưởng Tết của mình nếu không có nhân viên nào khác là cấp trên trực tiếp hay cấp dưới trực tiếp của nhân viên ~i~ (trừ chủ tịch) có năng suất thấp hơn mà nhận được mức thưởng Tết cao hơn nhân viên ~i~.
Để tránh hiện tượng nhảy việc sau Tết, chủ tịch quyết định mức thưởng Tết để làm hài lòng tất cả các nhân viên. Vì ngân sách có hạn, mức thưởng của nhân viên ~i~ là một số nguyên dương không vượt quá ~m~, và không có hai nhân viên nào khác nhau mà có mức thưởng giống nhau. Chủ tịch tập đoàn muốn biết: có bao nhiêu cách thưởng Tết cho nhân viên mà tất cả đều hài lòng? Hai cách thưởng Tết được coi là khác nhau nếu có một nhân viên nhận được hai mức thưởng khác nhau trong hai cách.
Gọi ~S~ là số cách thưởng Tết cho nhân viên thỏa mãn các điều kiện trên. Vì ~S~ có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~998244353~.
Input
Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 3000, n \leq m \leq 10 ^ 6~) lần lượt là số nhân viên trong tập đoàn và giới hạn mức thưởng Tết của từng người.
Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, ..., p_n~ (~0 \leq p_i < i~) mô tả cấp trên trực tiếp của từng nhân viên.
Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq n~) mô tả điểm số của từng nhân viên. Không có hai nhân viên nào khác nhau có cùng điểm số.
Output
In ra một số nguyên duy nhất là phần dư của ~S~ khi chia cho ~998244353~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10\%~ | ~n, m \le 9~. |
2 | ~10\%~ | ~p_i = 0~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~. |
3 | ~20\%~ | ~p_i = i - 1~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~. |
4 | ~20\%~ | ~a_i = i~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~. |
5 | ~20\%~ | ~n \le 200~. |
6 | ~20\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
5 5
0 1 2 3 2
2 5 3 1 4
Sample Output 1
12
Sample Input 2
5 5
0 1 2 0 4
2 1 3 5 4
Sample Output 2
20
Notes
Ở test ví dụ thứ nhất:
Một số cách thưởng Tết cho nhân viên thỏa mản các điều kiện:
(2, 5, 3, 1, 4)
(1, 5, 4, 2, 3)
(3, 5, 4, 2, 1)
...
Ở test ví dụ thứ hai:
Một số cách thưởng Tết cho nhân viên thỏa mản các điều kiện:
(2, 1, 3, 5, 4)
(2, 1, 5, 4, 3)
(4, 1, 2, 5, 3)
(4, 2, 3, 5, 1)
(5, 1, 4, 3, 2)
...