Chắc hẳn ai cũng biết đến trò chơi billiard - một trò chơi mà người chơi sử dụng gậy để đẩy viên bi cái (thường có màu trắng) theo một hướng nào đó để viên bi cái đẩy các viên bi mục tiêu của người chơi đó xuống lỗ. Để chơi được billiard, ngoài kỹ thuật và sức khỏe ra, người chơi cần phải có đầu óc tính toán tốt về cả Toán học, Vật lý và Chiến thuật để có thể trở thành một người chơi giỏi.
Thay vì nghiên cứu trên bàn billiard chuẩn, thì trong bài toán này, chúng ta sẽ nghiên cứu trên bàn carom kích thước $$$M*N$$$. Bàn carom cũng giống với bàn bi-a thông thường, chỉ khác là bàn carom sẽ không có lỗ để bi rơi xuống. Một bàn carom như vậy thường dùng phục vụ chơi các thể thức như carom 1 băng, 3 băng, 6 băng - thể thức mà người chơi sẽ dành điểm khi đẩy viên bi của mình chạm băng (tường) đủ số lần, chạm viên bi mục tiêu và chạm viên bi cái của đối phương.
Để đơn giản hóa bài toán, chúng ta sẽ mô phỏng bàn carom trên hệ trục tọa độ $$$Oxy$$$. Bàn carom là một hình chữ nhật với góc trái dưới là điểm $$$(0, 0)$$$ và góc phải trên là điểm $$$(N, M)$$$. Trên bàn carom hiện tại chỉ có duy nhất một chất điểm để thể hiện một viên bi, nằm trên tọa độ $$$(x_0, y_0)$$$ ($$$0 \lt x_0 \lt N, 0 \lt y_0 \lt M$$$).
Mỗi giây, viên bi sẽ di chuyển một khoảng cách tương ứng với vector $$$(v_x, v_y)$$$. Khi chạm vào "tường" (khi vị trí chất điểm nằm trên cạnh của hình chữ nhật), viên bi sẽ thay đổi vận tốc theo những nguyên tắc sau:
- Nếu đang di chuyển với vận tốc $$$(v_1, v_2)$$$ mà va vào tường song song với trục Oy, vận tốc viên bi chuyển thành $$$(-v_1, v_2)$$$.
- Nếu đang di chuyển với vận tốc $$$(v_1, v_2)$$$ mà va vào tường song song với trục Ox, vận tốc viên bi chuyển thành $$$(v_1, -v_2)$$$.
- Nếu đang di chuyển với vận tốc $$$(v_1, v_2)$$$ mà va vào đúng vị trí góc của hình chữ nhật, vận tốc viên bi chuyển thành $$$(-v_1, -v_2)$$$ (Ta coi như cùng lúc va chạm với hai tường vuông góc nhau).
Giả sử viên bi có vận tốc vĩnh viễn không đổi (gia tốc bằng không) kể cả sau khi bật vào tường. Hãy tính chính xác vị trí của nó sau thời điểm bắt đầu di chuyển $$$S$$$ giây. Ta có thể chứng minh được với mọi $$$S$$$ nguyên, vị trí của viên bi sẽ luôn là số nguyên.
Dòng đầu chứa $$$T$$$ ($$$1 \le T \le 10^4$$$) - số bộ dữ liệu trong file input. Mỗi bộ dữ liệu sẽ có format như sau:
- Một dòng duy nhất chứa bảy số: $$$N$$$, $$$M$$$, $$$x_0$$$, $$$y_0$$$. $$$v_x$$$, $$$v_y$$$, $$$T$$$. ($$$2 \le N, M \le 10^9$$$, $$$0 \lt x_0 \lt N$$$, $$$0 \lt y_0 \lt M$$$, $$$-10^9 \le v_x, v_y \le 10^9$$$, $$$|v_x| + |v_y| \gt 0$$$, $$$1 \le S \le 10^9$$$). $$$N$$$, $$$M$$$ là kích thước của bàn carom, $$$x_0$$$, $$$y_0$$$ là vị trí ban đầu của viên bi, $$$v_x$$$, $$$v_y$$$ là vận tốc của viên bi, và bạn cần phải đưa ra vị trí chính xác tại thời điểm sau thời điểm bắt đầu di chuyển $$$S$$$ giây.
Với mỗi bộ test, in ra trên một dòng hai số: $$$x_S$$$, $$$y_S$$$ - vị trí của viên bi sau thời điểm bắt đầu di chuyển $$$S$$$ giây - cách nhau bởi một dấu cách.
10% số điểm ứng với $$$N=M=10^9$$$, $$$0 \lt x_0, y_0 \le 10^4$$$, $$$0 \le v_x, v_y \le 10^4$$$, $$$1 \le S \le 10^4$$$.
30% số điểm ứng với $$$1 \le T \le 10$$$, $$$2 \le N, M \le 100$$$, $$$-100 \le v_x, v_y \le 100$$$, $$$1 \le S \le 100$$$.
30% số điểm ứng với $$$M = 2$$$, $$$v_y = 0$$$, $$$y_0 = 1$$$.
30% số điểm ứng với giới hạn gốc.
3 3 5 2 2 2 1 3 6 8 3 2 5 1 1 100 200 13 45 -20 111 9969
2 5 4 3 33 196
Ví dụ 1: A0, A1, A2, A3, A4 ứng với vị trí của viên bi tại các thời điểm 0, 1, 2, 3, 4.
Hai thợ săn low_ và lantrungseo đi vào rừng bắt thỏ.
N con thỏ trong rừng đều xếp thành một hàng ngang (theo một cách không hề có sắp xếp trước). Chúng được đánh dấu từ $$$1$$$ đến $$$N$$$ theo thứ tự từ trái qua phải, và ở các vị trí, hai thợ săn đều biết con thỏ ở đó thuộc giống gì. Để cho buổi đi săn thú vị, low_ và lantrungseo đã đưa ra một trò chơi:
- Mỗi người chọn 2 số $$$l$$$ và $$$r$$$ ($$$l \le r$$$) và bắt tất cả các con thỏ trong đoạn đó. Số điểm nhận được của mỗi người chơi sẽ là số lượng giống thỏ khác nhau trong những chú thỏ mà người đó bắt được.
Trong khi low_ chỉ chăm chăm tìm cách để chiến thắng, lantrungseo quan tâm đến việc tính tổng số điểm của tất cả các đoạn có thể chọn. Nói cách khác, lantrungseo quan tâm đến tổng:
$$$$$$\sum_{1 \le l \le r \le N}f(l, r)$$$$$$
Với $$$f(l, r)$$$ là số lượng số giống thỏ khác nhau nằm trên đoạn $$$[l, r]$$$.
Hãy giúp lantrungseo tính ra tổng đó.
Dòng đầu tiên ở mỗi file input chứa $$$T$$$ ($$$1 \le T \le 10$$$) - số bộ test. Mỗi bộ test có format như sau:
- Dòng đầu tiên chứa $$$N$$$ ($$$1 \le N \le 10^6$$$).
- Dòng thứ hai chứa N số: $$$typ_1, typ_2,...,typ_N$$$ ($$$1 \le typ_i \le 10^9$$$) - số thể hiện giống của từng con thỏ. Hai con thỏ $$$i$$$, $$$j$$$, cùng giống khi và chỉ khi $$$typ_i=typ_j$$$.
- Tổng của $$$N$$$ trong tất cả các bộ test không vượt quá $$$2*10^6$$$.
Với mỗi bộ test, in ra trên một dòng duy nhất một số là kết quả bài toán.
40% số điểm ứng với $$$N \le 1000$$$.
2 3 1 2 3 4 1 2 2 3
10 16
Bộ test thứ hai:
$$$f(1, 1)=1$$$, $$$f(1, 2)=2$$$, $$$f(1, 3)=2$$$, $$$f(1, 4)=3$$$, $$$f(2, 2)=1$$$, $$$f(2, 3)=1$$$, $$$f(2, 4)=2$$$, $$$f(3, 3)=1$$$, $$$f(3, 4)=2$$$, $$$f(4, 4)=1$$$.
Mới đây, Riot vừa cho ra mắt chế độ chơi Đấu Trường Chân Lý. Chúng tôi tự hỏi, tại sao ta không tạo ra một trò chơi tương tự nhỉ.
Đấu Trường Phi Lý là chế độ chơi PvC (người đấu với máy) lai PvP (người đấu với người). Về cơ bản, bạn và một người chơi khác sẽ cầm hai con tướng ngẫu nhiên và được đặt lên hai đỉnh nào đó trên một đồ thị N đỉnh. Gọi hai đỉnh xuất phát của hai người chơi là $$$u$$$ và $$$v$$$, hai người chơi sẽ phải tìm đường đi đến đỉnh $$$f$$$ - vạch đích - nơi mà hai người chơi sẽ có một màn solo đẹp mắt để tìm ra xem ai là người chiến thắng trong trận đấu này. Nếu một trong hai người chơi không thể đi đến vạch đích do bị quái đánh chết hoặc cố tình thoát trò chơi, người còn lại sẽ nghiễm nhiên dành chiến thắng khi đã đến được vạch đích. Còn nếu hai người chơi đều không đến được vạch đích, cả hai đều bị coi như là thua.
Cụ thể hơn, bạn sẽ cầm một vị tướng ngẫu nhiên với lượng máu tối đa là $$$hp$$$. Mỗi lần đi qua một cạnh trên đồ thị để đến một đỉnh nào đó, bạn sẽ đánh nhau với một quái khác và mất lượng máu là $$$1$$$. Một số đỉnh trên bản đồ là bệ đá hồi sinh. Khi đến được tới một bệ đá nào đó, bạn sẽ được hồi lại toàn bộ lượng máu ban đầu, kể cả khi bạn vừa đánh với quái khiến cho lượng máu của bạn tụt xuống còn 0. Điều này đồng nghĩa với việc: bạn chỉ có thể chết trước khi đi tới vạch đích nếu như máu của bạn tụt xuống 0 và bạn đang không đứng ở một bệ đá hồi sinh.
Để giải quyết bài toán về tính "cân bằng", bạn tự đưa ra một bài toán: Đấu trường Phi Lý là một đồ thị có N đỉnh, M cạnh. Bạn cầm vị tướng tRuNgSeO, ban đầu đứng ở đỉnh u trên đồ thị. Bạn biết trước các đỉnh sạc năng lượng và đỉnh vạch đích, hãy tính $$$hp$$$ bé nhất có thể để tRuNgSeO đi được tới vạch đích mà không bị quái đánh đến chết.
Dòng đầu tiên chứa T ($$$1 \le T \le 10$$$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:
- Dòng đầu tiên chứa N, M, K ($$$2 \le K \le N \le 10^5, 1 \le M \le 10^5$$$) - lần lượt là số đỉnh trong đồ thị, số cạnh trong đồ thị, và số đỉnh trong đồ thị làm bệ đá hồi sinh.
- Dòng thứ hai chứa K số: $$$b_1, b_2,..., b_K$$$ ($$$1 \le b_1 \lt b_2 \lt ... \lt b_K \le N$$$) - các đỉnh làm bệ đá hồi sinh.
- Dòng thứ ba đến dòng M+2, mỗi dòng chứa 2 số u, v ($$$1 \le u, v \le N$$$). Mỗi dòng thể hiện một đường đi từ u đến v trong đấu trường.
- Dòng thứ M+3: chứa 2 số: u và f ($$$1 \le u, f \le N, u \neq f$$$). Dữ liệu đảm bảo cả hai đỉnh này đều là bệ đá hồi sinh.
- Dữ liệu đảm bảo đồ thị liên thông: Với mọi u, v, ta đều tìm được đường đi từ u đến v và ngược lại.
Trên mỗi dòng, in ra một số duy nhất là lượng máu tối đa $$$hp$$$ bé nhất sao cho tRuNgSeO có thể đi đến vạch đích.
2 6 6 3 1 3 6 1 2 2 3 4 2 5 6 4 5 3 4 1 6 6 5 3 1 5 6 1 2 2 3 3 4 4 5 6 3 1 5
3 3
30% số test thỏa mãn $$$N \le 1000$$$, $$$K \le 1000$$$.
Cánh đồng hoa ở Amsterdam được chia thành $$$N$$$ ô đất, mỗi ô đất được đánh số từ $$$1$$$ đến $$$N$$$.
Hai người làm vườn chăm chỉ low_ và lantrungseo được giao chăm sóc hoa trên những ô đất này. Vì là những người làm vườn yêu bộ môn giải thuật, đồng thời cũng vì có quá nhiều hoa màu, low_ và lantrungseo đã cùng đưa ra bài toán như sau:
Ban đầu trên ô đất thứ $$$i$$$ có $$$A_i$$$ bông hoa. Mỗi ngày, hai người làm vườn sẽ phải thực hiện một trong hai sự kiện sau theo danh sách cho trước:
"1": Chọn ra hai chỉ số $$$l, r$$$ ($$$1 \le l \le r \le N$$$). Với mỗi $$$i$$$ thuộc đoạn $$$[l, r]$$$, trồng trên ô đất thứ $$$i$$$ số lượng hoa là $$$i-l+1$$$. Ví dụ, nếu $$$N=5$$$ và chọn $$$l=2$$$ và $$$r=4$$$, thì trồng 1 bông trên ô đất 2, 2 bông trên ô đất 3, 3 bông trên ô đất 4.
"2": Hai người làm vườn chán trồng hoa (nên sẽ không trồng thêm bông nào ngày hôm đó). Thay vì đó, low_ đố lantrungseo tính tổng số bông hoa trên các ô đất thuộc đoạn $$$[u, v]$$$ ($$$1 \le u \le v \le N$$$).
Bạn có danh sách các sự kiện diễn ra trong $$$Q$$$ ngày. Hãy giúp lantrungseo trả lời các sự kiện "2".
Dòng đầu chứa $$$T$$$ ($$$1 \le T \le 4$$$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:
- Dòng đầu chứa $$$N$$$ ($$$1 \le N \le 10^5$$$) - số ô đất trên cánh đồng hoa.
- Dòng thứ hai chứa $$$N$$$ số: $$$A_1, A_2, ..., A_N$$$. ($$$0 \le A_i \le 10^6$$$) - số bông hoa trên từng cánh đồng.
- Dòng thứ 3 chứa $$$Q$$$ ($$$1 \le Q \le 10^5$$$) - số sự kiện diễn ra trên cánh đồng.
- $$$Q$$$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:
+ "1": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $$$l, r$$$ cách nhau bởi một dấu cách ($$$1 \le l \le r \le N$$$).
+ "2": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $$$u, v$$$ cách nhau bởi một dấu cách ($$$1 \le u \le v \le N$$$).
Với mỗi sự kiện "2", in ra một số duy nhất là kết quả của sự kiện.
20% số điểm ứng với $$$N \le 1000, Q \le 1000$$$.
40% số điểm ứng với $$$N \le 10^5, Q \le 10^5$$$. Trong mỗi bộ test, truy vấn "1" cuối cùng sẽ xuất hiện trước truy vấn "2" đầu tiên.
40% số điểm còn lại ứng với giới hạn gốc.
2 5 2 1 3 5 2 6 1 1 3 2 3 5 1 4 5 1 2 5 1 1 1 2 1 4 7 10 5 2 0 8 6 2 7 1 2 5 1 1 6 2 4 7 1 1 3 1 5 5 1 1 5 2 1 7
13 25 38 86
Bộ test thứ nhất:
Ban đầu: $$${2, 1, 3, 5, 2}$$$
Sau ngày đầu tiên: $$${3, 3, 6, 5, 2}$$$
Sau ngày thứ ba: $$${3, 3, 6, 6, 4}$$$
Sau ngày thứ tư: $$${3, 4, 8, 9, 8}$$$
Sau ngày thứ năm: $$${4, 4, 8, 9, 8}$$$