Cho dãy \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\).

Hàm \(f(l,\ r)\ \)được định nghĩa như sau:

\(f(l,\ r) = min(a_{l},\ a_{l + 1},\ \ldots,\ a_{r})*max(a_{l},\ a_{l + 1},\ \ldots,\ a_{r})*(r - l + 1)\).

Yêu cầu: Hãy tính tổng \(f(l,\ r)\ \)với mọi cặp \(l,\ r\ \)thỏa mãn \(1 \leq l \leq r \leq n\).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n;\)

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1 \leq a_{i} \leq 10^{8},\forall\ i \in \lbrack 1,\ n\rbrack)\).

Kết quả: Ghi một số nguyên dương duy nhất là tổng tìm được theo modulo \(\mathbf{10}^{\mathbf{9}}\mathbf{+ 7}\).

Ví dụ:

Chú ý:

Bạn cần Đăng nhập để nộp bài

Nông sản (nongsan.*)

Trung tâm phân phối S là nơi tập kết rất nhiều nông sản. Mỗi ngày, trung tâm cần cử các xe giao hàng để vận chuyển nông sản đến các thành phố/điểm bán lẻ khác nhau. Mỗi xe đi đến một địa điểm riêng biệt. Các thành phố được kết nối với nhau và với trung tâm bằng những tuyến đường. Mỗi tuyến đường có một thời gian di chuyển nhất định.

Hãy tìm ra thời gian di chuyển ngắn nhất từ trung tâm phân phối (\(S\)) đến tất cả các thành phố/điểm bán lẻ khác trong mạng lưới. Việc này giúp tài xế giao hàng hiệu quả nhất, đảm bảo nông sản tươi ngon đến tay khách hàng nhanh chóng.

Dữ liệu vào:

• Dòng 1: Ba số nguyên \(N,\ M,\ S\).

  • \(N\): Tổng số địa điểm (bao gồm Trung tâm phân phối và các thành phố/điểm bán lẻ), được đánh số từ 1 đến \(N\).

  • \(M\): Số lượng tuyến đường kết nối các địa điểm.

  • \(S\): Trung tâm phân phối nông sản.

• M dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U,V,W\).

  • \(U,\ V\): Hai địa điểm được kết nối bởi một tuyến đường.

  • \(W\): Thời gian di chuyển giữa \(U\) và \(V\).

Kết quả: ghi \(N\) dòng, trong đó dòng thứ \(i\) in ra thời gian di chuyển ngắn nhất từ Trung tâm phân phối \(S\) đến địa điểm \(i\). Nếu không có đường đi đến một địa điểm nào đó, in ra \(- 1\)

Ràng buộc:

• \(1\ \ \leq \ \ N\ \ \leq \ \ 10^{3}\)

• \(1\ \ \leq \ \ S\ \ \leq \ \ 10^{3}\)

• \(1\ \ \leq \ \ M\ \ \leq \ \ N \times (N - 1)/2\ \)

• \(1\ \ \leq \ \ W\ \ \leq \ \ 10^{9}\)

Bạn cần Đăng nhập để nộp bài

Logistics (logistics.*)

Công ty Logistics Abela là một công ty thương mại điện tử lớn, chịu trách nhiệm tối ưu hóa các tuyến đường giao hàng phức tạp. Mỗi kiện hàng cần được vận chuyển từ kho chính (S) của công ty. Tuy nhiên, trước khi đến tay khách hàng cuối cùng (T), kiện hàng này bắt buộc phải ghé qua một trung tâm kiểm định (X) để kiểm tra chất lượng của sản phẩm.

Mạng lưới giao thông của thành phố rất rộng lớn, bao gồm nhiều tuyến đường nối các địa điểm quan trọng. Mỗi tuyến đường có một thời gian di chuyển cụ thể. Hãy tính toán thời gian di chuyển ngắn nhất cho toàn bộ quy trình giao nhận này. Điều đó có nghĩa là bạn cần tìm lộ trình nhanh nhất từ kho S đến trung tâm X, sau đó tiếp tục tìm lộ trình nhanh nhất từ trung tâm X đến điểm giao hàng T. Tổng thời gian của hai chặng đường này sẽ là tiêu chí then chốt để đảm bảo khách hàng nhận được hàng nhanh nhất và hiệu quả nhất.

Dữ liệu vào:

• Dòng 1: Năm số nguyên \(N,\ M,\ S,\ X,\ T\).

  • \(N\): Tổng số địa điểm trong mạng lưới giao hàng (đánh số từ 1 đến \(N\)).

  • \(M\): Số lượng tuyến đường kết nối các địa điểm.

  • \(S\): điểm xuất phát của kiện hàng.

  • \(X\): điểm dừng bắt buộc để xử lý hàng.

  • \(T\): điểm giao hàng cuối cùng.

• \(M\) dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U,\ V,\ W\).

  • \(U,\ V\): Hai địa điểm được kết nối bởi một tuyến đường.

  • \(W\): Thời gian di chuyển (trọng số) giữa \(U\) và \(V\).

Kết quả:

In ra tổng thời gian di chuyển ngắn nhất cho toàn bộ hành trình từ \(S \rightarrow X \rightarrow T\). Nếu không có đường đi hợp lệ nào để hoàn thành nhiệm vụ (ví dụ: không thể đến \(X\) từ \(S\), hoặc không thể đến \(T\) từ \(X\)), in ra \(- 1\).

Ràng buộc:

• \(1\ \leq \ N\ \leq \ 10^{3}\)

• \(1\ \leq \ S,\ T,\ X,\ U,\ V\ \leq \ N\)

• \(1\ \leq \ M\ \leq \ N \times (N - 1)/2\)

• \(1\ \leq \ W\ \leq \ 10^{9}\ \)

Bạn cần Đăng nhập để nộp bài

Graph_hp

Trên bản đồ thành phố HP có \(n\) địa điểm chiến lược (đánh số từ 1 đến \(n)\) và \(m\) con đường hai chiều (đánh số từ 1 đến \(m)\), con đường \(i\ (1 \leq i \leq m)\) nối giữa hai địa điểm \(x_{i}\) và \(y_{i}\ (1 \leq x_{i},y_{i} \leq n)\).

Có \(q\) truy vấn, truy vấn thứ \(i\ (1 \leq i \leq q)\) cho hai số \(l\) và \(r\), bạn hãy cho biết mọi cặp địa điểm chiến lược có thể di chuyển được với nhau không nếu chỉ dùng các con đường \(l,l + 1,\ldots,r.\)

Dữ liệu:

+ Dòng đầu tiên gồm hai số nguyên dương \(n,m\ (2 \leq n \leq 100;1 \leq m \leq 100.000);\)

+ \(m\) dòng sau, dòng thứ \(i\ (1 \leq i \leq m)\) gồm hai số nguyên dương \(x_{i},y_{i}\) \((1 \leq x_{i},y_{i} \leq n)\) mô tả một con đường nối giữa hai địa điểm \(x_{i}\) và \(y_{i}\);

+ Dòng tiếp theo chứa số nguyên dương \(q\ (1 \leq q \leq 100.000)\);

+ \(q\) dòng sau, dòng thứ \(i\ (1 \leq i \leq q)\) gồm hai số nguyên \(l\) và \(r\) mô tả truy vấn \(i\) \((1 \leq l \leq r \leq m)\);

Kết quả: Ghi \(q\) dòng, dòng thứ \(i\) in ra “Yes” nếu mọi cặp địa điểm chiến lược có thể đến được nhau và “No” nếu ngược lại.

Ràng buộc:

+ 20% số điểm thoả mãn: \(m,q \leq 100\);

+ 20% số điểm tiếp theo thoả mãn: \(l = 1,\ \forall i \in \lbrack 1;q\rbrack\);

+ 20% số điểm tiếp theo thoả mãn: \(l \leq 50,\ \forall i \in \lbrack 1;q\rbrack\);

+ 40% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Cứu hỏa (cuuhoa.*)

Đội phòng cháy chữa cháy AS làm nhiệm vụ chữa cháy, hoả hoạn cho tất cả các địa điểm trong thành phố \(X\). Với phương châm “Tốc độ cứu hộ, quyết định tất cả”, họ phải xây dựng sẵn lộ trình đến các vị trí để khi cần là sẵn sàng lên đường. Khi có một đám cháy xảy ra tại một khu vực nhất định (\(\mathbf{D}\)), xe cứu hỏa cần được cử đi từ vị trí S. Mỗi con đường giữa các khu vực/trạm cứu hỏa có một thời gian di chuyển nhất định.

Để đảm bảo hiệu quả chữa cháy tối đa, hãy:

• Xác định thời gian di chuyển ngắn nhất để xe cứu hỏa đến được khu vực cháy \(D\).

• Đếm số lượng các tuyến đường khác nhau có cùng thời gian di chuyển ngắn nhất đó. Việc này cực kỳ quan trọng để đội cứu hỏa có các phương án dự phòng nhanh chóng nếu một tuyến đường chính bị tắc nghẽn hoặc không thể đi qua do sự cố bất ngờ.

Dữ liệu vào:

• Dòng 1: Bốn số nguyên \(N,\ M,\ S,\ D\).

  • \(N\): Tổng số địa điểm cần cứu hộ, được đánh số từ 1 đến \(N\).

  • \(M\): Số lượng tuyến đường kết nối các địa điểm.

  • \(S\): vị trí xuất phát

  • \(D\): vị trí xảy ra đám cháy

• \(M\) dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U,\ V,\ W\).

  • \(U,\ V\): Hai địa điểm được kết nối bởi một tuyến đường.

  • \(W\): Thời gian di chuyển (trọng số) giữa \(U\) và \(V\).

Kết quả:

• Dòng 1: In ra thời gian di chuyển ngắn nhất từ trạm cứu hỏa \(S\) đến khu vực cháy \(D\).

• Dòng 2: In ra số lượng các tuyến đường khác nhau có cùng thời gian di chuyển ngắn nhất đó.

• Nếu không có đường đi từ \(S\) đến \(D\), in ra -1 trên cả hai dòng

Ràng buộc:

• \(1\ \leq \ N\ \leq \ 10^{3}\)

• \(1\ \leq \ S,\ D\ \leq \ N\)

• \(1\ \leq \ M\ \leq \ N \times (N - 1)/2\)

• \(1\ \leq \ W\ \leq \ 10^{9}\)

Bạn cần Đăng nhập để nộp bài

Chi phí phát sinh (chiphips.*)

Đất nước Anpha có \(n\) thành phố được đánh số \(1,2,3,\ \ldots,n\). Giữa các thành phố này có \(m\) tuyến đường hai chiều đảm bảo kết nối giữa \(n\) thành phố. Mỗi tuyến đường thứ \((1 \leq i \leq n)\)được mô tả bởi cặp số \(\left( u_{i},v_{i} \right)\) kết nối trực tiếp hai thành phố \(u_{i}\) và \(v_{i}\) \(\left( u_{i} ≠ v_{i} \right)\) và được gán hai số nguyên dương \(c_{i}\), \(d_{i}\), trong đó \(c_{i}\) là độ đẹp và \(d_{i}\)là chi phí phát sinh khi đi qua tuyến đường.

Giả sử \(s\) và \(t\) là hai thành phố của đất nước Anpha. Một công ty ABC đang cần vận chuyển một chuyến hàng có trọng lượng 𝑊 từ thành phố 𝑠 tới thành phố 𝑡. Ta gọi một đường đi từ \(s\) đến \(t\) là một dãy \(z_{0},z_{1},z_{2},....,z_{k - 1},z_{k}\), trong đó \(z_{0} = s,\ z_{k} = t,\ \left( z_{i - 1},\ z_{i} \right)\)là tuyến đường với \(i = 1,2,...,k\). Chi phí cần vận chuyển một chuyến hàng có trọng lượng 𝑊 từ thành phố \(s\) đến thành phố \(t\) theo đường đi nói trên là:

\[d\left( z_{0},z_{1} \right) + d\left( z_{1},z_{2} \right) + ... + d\left( z_{k - 1},z_{k} \right) + \frac{W}{C_{\min}}\]

Trong đó \(d\left( z_{i - 1},\ z_{i} \right)\)là chi phí phát sinh của tuyến đường \(\left( z_{i - 1},\ z_{i} \right)\), \(C_{\min}\) là độ đẹp nhỏ nhất trong các tuyến đường trên đường đi mà xe hàng đi qua.

Yêu cầu: Cho trước hai thành phố s và t. Hãy tìm đường đi để vận chuyển một chuyến hàng có trọng lượng \(W\)với chi phí nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n,\ m\ (2 \leq n \leq 150,\text{ 1} \leq m \leq 5000)\), mỗi số cách nhau một khoảng trắng;

• Dòng thứ hai chứa ba số nguyên dương \(s,\ t,\ W\ (1 \leq s,t \leq n;\ 1 \leq W \leq 10^{4})\), mỗi số cách nhau một khoảng trắng;

• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa bốn số nguyên dương \(u_{i},v_{i},c_{i},d_{i}\ \)mô tả thông tin về con đường thứ \(i\ \left( 1 \leq u_{i},\ v_{i} \leq n;\text{ 1} \leq c_{i},\ d_{i} \leq 10000,\ i = \ 1,2,\ .\ .\ .\ ,\ m \right)\), mỗi số cách nhau một khoảng trắng.

Kết quả: Ghi một số duy nhất là chi phí nhỏ nhất để vận chuyển chuyến hàng (kết quả làm tròn đến hai chữ số sau dấu thập phân).

Ví dụ:

Ràng buộc:

+ Subtask1. Có 40% số test ứng với 40% số điểm của bài thỏa mãn \(\mathbf{c}_{\mathbf{i}}\mathbf{=}\mathbf{d}_{\mathbf{i}}\mathbf{= 1\ (\forall i = 1,2,3,...,m)}\);

+ Subtask2. Có 30% số test ứng với 30% số điểm của bài thỏa mãn \(\mathbf{c}_{\mathbf{i}}\mathbf{= 1\ (\forall i = 1,2,3,...,m)}\);

+ Subtask3. Có 20% số test ứng với 20% số điểm của bài thỏa mãn \(\mathbf{m = n - 1}\);

+ Subtask4. Có 10% số test ứng với 10% số điểm của bài không có ràng buộc bổ sung.

Bạn cần Đăng nhập để nộp bài

A và B là hai người chơi vào vòng chung kết một cuộc thi và được nhận các phần thưởng do công ty AZ tài trợ. Vòng chung kết sẽ diễn ra trong \(M\) ngày. Ban đầu, ban tổ chức sẽ chuẩn bị trước \(N\) món quà. Các phần quà được đánh số từ \(1\) đến \(N\), phần quà thứ \(i\) từ trái sang phải có giá trị là \(a_{i}\). Mỗi ngày thi sẽ diễn ra như sau, ban tổ chức sẽ chọn ra một phần quà, và thay thế nó bằng một phần quà mới. Cụ thể hơn, vào ngày thứ \(i\), ban tổ chức sẽ chọn ra hai số \(x_{i}\), \(v_{i}\) và thay phần quà ở vị trí \(x_{i}\) thành một phần quà mới có giá trị là \(v_{i}\). Sau đó, \(A\) và \(B\) sẽ luân phiên nhau chọn quà. \(A\) đi trước và cả hai người đều muốn tối ưu tổng giá trị của các phần quà mình nhận được.

Yêu cầu: Tính xem ở mỗi ngày chơi, \(A\ \)sẽ nhận được tối đa tổng giá trị của các phần quà là bao nhiêu nếu cả \(A\) và \(B\) đều chơi tối ưu.

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên dương \(N,\ M\ (1 \leq N,\ M \leq 10^{5})\);

• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(a_{i}\ \left( 1 \leq a_{i} \leq 10^{6};i = 1,\ 2,\ \ \ldots,\ \ N \right)\);

• Dòng thứ i trong số M dòng tiếp theo chứa hai số nguyên dương \(x_{i},\ v_{i}\ \left( 1 \leq x_{i} \leq N;1 \leq v_{i} \leq 10^{6} \right)\);

Kết quả: Ghi trên \(M\) dòng, dòng thứ \(i\) là tổng giá trị các phần quà mà A nhận được ở ngày thứ \(i\).

Ví dụ:

Giải thích

• Ngày thứ nhất, các phần quà có giá trị là \(1,\ 5,\ 4,\ 1,\ 2\). \(A\) có thể lấy được các phần quà có tổng giá trị là \(1 + 5 + 2 = 8\).

• Ngày thứ hai, các phần quà có giá trị là \(7,\ 5,\ 4,\ 1,\ 2\). \(A\ \)có thể lấy được các phần quà có tổng giá trị là \(7 + 4 + 1 = 12\).

• Ngày thứ ba, các phần quà có giá trị là \(7,\ 3,\ 4,\ 1,\ 2.\) \(A\) có thể lấy được các phần quà có tổng giá trị là \(7 + 3 + 1 = 11\).

Chú ý:

Bạn cần Đăng nhập để nộp bài

Đếm đảo (demdao01.*)

Cho bản đồ kích thước \(m \times \ n\ (1 < m,n \leq 100)\) biểu diễn một vùng biển đảo. Các ô có giá trị 1 là phần đất thuộc một đảo nào đó, một đảo có thể gồm một hoặc nhiều ô kề cạnh với nhau, các ô có giá trị 0 là những ô biểu diễn mặt nước biển.

Yêu cầu: Hãy đếm số lượng đảo của bản đồ đã cho.

Dữ liệu vào:

- Dòng đầu là 2 số \(m,\ n\);

- \(m\) dòng tiếp theo là các giá trị biểu diễn bản đồ.

Kết quả:

- Ghi ra số lượng đảo đã đếm được.

Bạn cần Đăng nhập để nộp bài

Number of steps (numofstep.*)

Bạn được cho 2 số nguyên \(a,b\).

Hãy làm việc này sau đây cho đến khi một trong hai số \(a,b\) là số 0 :

• Nếu \(b \leq a\) thì lấy a trừ đi b \((a = a - b)\).

• ngươc lại lấy b trừ a\((b = b - a)\).

Nhập vào 2 số \(a,b\). Hãy đếm số lần bạn làm công việc trên

Dữ liệu vào:

• \(t(t \leq 1000)\) - số test

• \(t\) dòng, mỗi dòng gồm 2 số nguyên dương \(a,b(a,b \leq 1000000000)\)

Kết quả:

• \(t\) dòng, số lần thực hiện để một trong 2 số \(a,b\) có 1 số là số 0

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Số tình nghĩa (sotinhnghia.*)

Số "tình nghĩa" là số thoả mãn các điều kiện sau:

• các chữ số của nó chỉ bao gồm 4 hoặc 7

• Số lượng chữ số \(4\) bằng số lượng chữ số \(7\).

Ví dụ: \(4774,477744\) là các ví dụ về số "tình nghĩa"

Yêu cầu: Cho trước số nguyên dương \(n\). Hãy in ra số "tình nghĩa" nhỏ nhất mà không nhỏ hơn \(n\)

Dữ liệu vào:

• Dòng thứ nhất chứa số \(t(1 \leq t \leq 100)\)- Thể hiện số lượng testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n(1 \leq n \leq 10^{9})\)

Kết quả:

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Ví dụ:

Bạn cần Đăng nhập để nộp bài