Dịch đề nhé:
(Bản dịch chỉ mang tính chất tham khảo, nhiều lần thi Codeforces em bị hiểu nhầm đề rồi nên nếu sai chỗ nào (đặc biệt là bài 5) thì các anh, chị, em bỏ qua cho và comment lỗi + cách sửa phía dưới (gửi tin nhắn cũng được))
Nhấn chữ "Hiện bản gốc" để lấy link đề gốc :D
Bài 4: Ngựa
Mansur thích nuôi ngựa, giống như tổ tiên xưa của anh. Anh hiện đang có đàn gia súc lớn nhất của Ka-dắc-tan. Điều đáng ngạc nhiên là năm trước, Mansur chỉ là một dzgidit (tiếng Ka-dắc-tan nghĩa là một người đàn ông trẻ) và anh chỉ có một con ngựa. Anh mơ anh kiếm được nhiều tiền và cuối cùng trở thành một bai (tiếng Ka-dắc-tan nghĩa là một người rất giàu có)
Hãy đánh số các năm từ \(0\) đến \(N-1\) theo thứ tự thời gian (ví dụ, năm \(N-1\) là năm gần đây nhất). Thời tiết mỗi năm ảnh hưởng đến tốc độ sinh trưởng của đàn gia súc.Với mỗi năm \( i\), Mansur nhớ được chỉ số sinh trưởng \(X[i]\). Nếu đầu năm \(i\) anh có \(h\) con ngựa thì cuối năm anh có \(h.X[i]\) con ngựa.
Ngựa chỉ có thể bán vào cuối năm. Với mỗi năm, Mansur lại nhớ một số nguyên dương \(Y[i]\): mức giá mà anh có thể bán một con ngựa vào cuối năm. Sau mỗi năm, anh có thể bán bao nhiêu con ngựa cũng được, nhưng phải cùng mức giá \(Y[i]\)
Mansur tự hỏi số tiền lớn nhất anh có thể có được bây giờ nếu ông bán ngựa của mình một cách tối ưu nhất trong những năm qua. Bạn có vinh dự là một khách mời trong toi của Mansur (tiếng Ka-dắc-tan là kì nghỉ của Mansur), và anh ấy nhờ bạn trả lời câu hỏi này.
Trí nhớ của Mansur được cải thiện vào mỗi buổi tối, vì vậy anh cập nhập dữ liệu của mình M lần. Mỗi lần cập nhập sẽ thay đổi một giá trị \(X[i]\) hoặc \(Y[i]\). Sau mỗi lần cập nhập anh ta lại hỏi số tiền lớn nhất anh ta có thể kiếm được là bao nhiêu. Bạn chỉ cần xuất ra một số là tổng của các câu trả lời đó (?) (câu gốc là Mansur’s updates are cumulative: each of your answers should take into account all of the previous updates.) Lưu ý rằng mỗi giá trị \(X[i]\) và \( Y[i]\) có thể được cập nhập nhiều lần.
Câu trả lời thật cho câu hỏi của Mansur có thể rất lớn. Để tránh làm việc với số lớn, bạn chỉ cần xuất ra kết quả đã modulo cho \(10^9+7\)
Input
Dòng 1: \(N\)
Dòng 2: \(X[0] ... X[N-1]\)
Dòng 3: \(Y[0] ... Y[N-1]\)
Dòng 4: \(M\)
Dòng \(5, ...,M+4\): ba số \(type\) \(pos\) \(val\), trong đó
\(type\): cập nhập dãy \(X\) nếu \(type=1\), cập nhập dãy \(Y\) nếu \(type = 2\)
\(pos\): vị trí cập nhập
\(val\): giá trị cập nhập vào
Bài 5: Sắp xếp
Aizhan có \(N\) số nguyên \(S[0], S[1],...,S[N-1]\). Dãy này gồm các số từ \(0\) đến \(N-1\) Cô đang cố gắng sắp xếp lại dãy này theo trình tự tăng dần bằng cách đổi chỗ một số cặp số. Người bạn của cô Ermek cũng đổi chỗ một số cặp số – không nhất thiết là phải theo cách tối ưu.
Ermek và Aizhan sẽ chỉnh sửa dãy này nhiều vòng. Mỗi vòng, đầu tiên Ermek sẽ đổi chổ hai phần tử và sau đó Aizhan lại đổi chổ một lần nữa. Chính xác hơn, mỗi người nói hai vị trí cần đổi chỗ và đổi chỗ chúng. Lưu ý rằng giá trị của hai vị trí không cần phải khác nhau. Nếu giá trị của chúng bằng nhau, hiển nhiên là dãy vẫn không thay đổi.
Aizhan biết Ermek không thực sự quan tâm đến việc sắp xếp lại dãy \(S\). Cô còn biết chính xác những cặp phần tử mà Ermek sẽ đổi chỗ. Ermek sẽ tham gia \(M\) vòng đổi chỗ. Ta đánh số những vòng này từ \(0\) đến \(M-1\). Với mỗi \(i\) trong khoảng từ \(0\) đến \(M-1\), Ermek sẽ chọn hai vị trí \(X[i]\) và \(Y[i]\) ở vòng \( i\).
Aizhan muốn sắp xếp lại dãy \(S\). Trước mỗi vòng, nếu Aizhan thấy dãy đã được sắp xếp theo trình tự tăng dần, cô và Ermek sẽ dừng đổi chỗ. Cho dãy \(S\) và những phần tử mà Ermek sẽ chọn, nhiệm vụ của bạn là tìm mỗi dãy các lượt đổi chỗ theo cách tối ưu. Dữ liệu đề bài luôn đảm bảo bạn có thể sắp xếp dãy \(S\) trong \(M\) vòng.
Lưu ý rằng nếu Aizhan thấy rằng dãy \(S\) đã được sắp xếp sau lượt của Ermek, cô sẽ chọn đổi chỗ hai phần tử bằng nhau. Kết quả là dãy đã được sắp xếp sau vòng đó. Ngoài ra nếu dãy \(S\) đã được sắp xếp, số vòng cần thiết để sắp xếp dãy là \(0 \)
Input
Dòng \(1\): \(N\)
Dòng \(2\): \(S[0] ... S[N-1]\)
Dòng \(3\): \(M\)
Dòng \(4,...,M+3\): \(X[i]\) \(Y[i]\)
Output
Dòng \(1\): \(R\) (số vòng đổi chỗ ít nhất để sắp xếp dãy)
Dòng \(2+i\), với \(0 \leq i < R\): \(P[i]\) \(Q[i]\)
Bài 6: Thị trấn
Có \(N\) thị trấn nhỏ ở Ka-dắc-tan, được đánh số từ \(0\) đến \(N-1\). Ngoài ra còn có một số lượng không biết trước thành phố lớn. Các thành phố nhỏ và thành phố lớn được gọi chung là các khu định cư.
Tất cả các khu định cư của Ka-dắc-tan được kết nối với nhau trong một mạng bằng các đường cao tốc hai chiều. Mỗi đường cao tốc nối liền hai khu định cư khác nhau, và mỗi cặp khu định cư được kết nối trực tiếp bằng nhiều nhất một đường cao tốc. Đối với mỗi cặp khu định cư bất kì \(a\) và \(b\) đều có một đường đi duy nhất có thể đi từ \(a\) đến \(b\) bằng đường cao tốc mà mỗi đường cao tốc chỉ được sử dụng một lần
Hình sau cho biết một mạng gồm \(11\) thị trấn nhỏ và \(7\) thị trấn lớn. Thị trấn nhỏ là hình tròn được đánh số nguyên, còn thị trấn lớn là hình vuông được đánh số bằng chữ cái in thường
Mỗi đường cao tốc có độ dài là một số nguyên dương. Khoảng cách giữa hai khu định cư là giá trị nhỏ nhất của độ dài các đường đi từ khu định cư này sang khu định cư khác.
Với mỗi thành phố lớn \(C\) ta có thể đo khoảng cách \( r(C)\) đến thị trấn nhỏ ở xa nó nhất. Một thành phố lớn \(C\) là một trung tâm hoạt động nếu \(r(C)\) của nó là nhỏ nhất trong số các thành phố lớn. Khoảng cách giữa trung tâm hoạt động đến thị trấn nhỏ ở xa nhất là \(R\). Vì vậy, \(R\) là giá trị nhỏ nhất trong các giá trị \(r(C)\).
Trong ví dụ trên thị trấn xa nhất từ thị trấn lớn \(a\) là thị trấn \(8\) và khoảng cách giữa chúng là \(r(a)=1+4+12=17\). Với thị trấn \(g\) ta có \(r(g)=17\) (thị trấn nhỏ xa thị trấn \(g\) nhất là thị trấn \(6\)). Trung tâm hoạt động duy nhất của mạng trên là \(f\) với \(r(f)=16\). Vì vậy \(R=16\)
Bỏ một trung tâm hoạt động làm mạng chia thành nhiều thành phần được kết nối. Một trung tâm hoạt đông cân nếu mỗi phần đều có nhiều nhất \([\frac{N}{2}]\) thị trấn nhỏ (không tính thị trấn lớn). Lưu ý rằng \([x]\) là số nguyên lớn nhất không lớn hơn \(x\).
Ở ví dụ trên, thành phố \(f\) là một trung tâm hoạt động. Nếu ta bỏ thành phố \(f\), mạng sẽ bị chia thành bốn phần được kết nối. \(4\) phần này là {\(0, 1, 10\)}, {\(2, 3\)}, {\(4, 5, 6, 7\)} và {\(8, 9\)}. Không có phần nào có quá \([\frac{11}{2}]=5\) thị trấn nhỏ, vì vậy thành phố \(f\) là một trung tâm hoạt động cân.
Nhiệm vụ
- Tìm \(R\)
- Tìm các trung tâm hoạt động cân
Subtask
Ở subtask \(1, 2\): Bạn chỉ cần phải xuất ra \(R\) đúng
Từ subtask \(3\) đến subtask \(6\): Bạn phải xuất ra cả \(R\) lẫn các trung tâm hoạt động cân
Bạn được cung cấp hai thủ tục \(hubDistance\) để tìm \(R\) và thủ tục \(getDistance\) để lấy dữ liệu (cách dùng vui lòng xem ở bản tiếng Anh, mình không hiểu rõ lắm), số lần gọi các thủ tục này ở mỗi subtask được cho ở cột "number of queries" ở bảng dưới đây.
Thông tin thêm ở subtask \(4\): Mỗi thành phố lớn kết nối đến đúng \(3\) khu định cư
Input
Dòng \(1\): Số thứ tự của subtask và số lượng test trong subtask
Dòng \(2\): \(N_1\), số lượng thị trấn nhỏ trong test thứ nhất
\(N_1\) dòng sau: số thứ \(j\)\((1 \leq j \leq N_1)\) ở dòng \(i\)\((1 \leq i \leq N_1)\) là khoảng cách giữa thị trấn nhỏ \(i-1\) và \(j-1\)
Các test sau tương tự ở đằng sau.
Ví dụ test \(1\) trông như sau:
Thí sinh không được đọc trực tiếp file input này mà phải truy cập thông qua một thư viện được cung cấp sẵn
