ĐỀ THI MỚI

 1. Đề thi HSG Chọn Đội tuyển tỉnh Yên Bái năm học 2022-2023 _day2  - Người góp admin   88 lượt xem

 2. Đề thi HSG THPT tỉnh Khánh Hòa năm học 2025-2026  - Người góp admin   567 lượt xem

 3. Đề thi HSG THCS TP Hà Nội năm học 2021-2022  - Người góp admin   985 lượt xem

 4. Đề thi Tuyển sinh 10 tỉnh Khánh Hòa năm học 2025-2026  - Người góp admin   2100 lượt xem

 5. Đề thi HSG THPT TP Hà Nội năm học 2023-2024  - Người góp admin   733 lượt xem

BÀI TẬP MỚI

Điện toán đám mây (aws.*)

Hiện nay, điện toán đám mây đang trở nên phổ biến và phát triển vượt bậc, trở thành xu thế công nghệ hàng đầu mà các tổ chức, doanh nghiệp hướng tới. Một trong những nhà cung cấp tiên phong trong dịch vụ điện toán đám mây là Amazon Web Service (AWS). AWS đang dẫn đầu về doanh thu và sự phổ biến với hơn 50% doanh thu về dịch vụ này trên.

Để có thể tạo ra những service phục vụ hàng triệu người dùng trên toàn cầu, AWS xây dựng được một hạ tầng trên toàn thế giới. Theo thống kê, hầu hết các nước phát triển trên toàn cầu đều có trung tâm dữ liệu do AWS xây dựng, giúp cho người sử dụng có thể truy cập dễ dàng hơn. Hơn nữa, trên mỗi quốc gia không chỉ có một mà còn có nhiều trung tâm dữ liệu khác để phòng trường hợp một trung tâm dữ liệu bị hỏng không thể sử dụng được.

Hiện tại, AWS có \(N\) trung tâm dữ liệu, mỗi trung tâm đặt ở một địa điểm khác nhau. Đặc biệt, có một vài trung tâm dữ liệu được đặt rất gần nhau tạo thành một cụm máy. Cụ thể, trong N trung tâm dữ liệu này có G cụm máy, mỗi cụm gồm một số trung tâm dữ liệu, các trung tâm dữ liệu trong cùng một cụm kết nối trực tiếp với nhau và có cùng độ trễ là \(cost\). Hơn nữa, một trung tâm dữ liệu có thể thuộc nhiều cụm máy.

Để các trung tâm dữ liệu có thể kết nối đến nhau, AWS thêm \(M\) đường truyền, mỗi đường nối trực tiếp 2 trung tâm dữ liệu \(u\) \(v\) có độ trễ là \(w\).

Trong \(N\) trung tâm dữ liệu, có đúng \(S\) trung tâm được gọi là server chứa các dịch vụ cho người dùng. Các trung tâm còn lại muốn được cung cấp các dịch vụ đó phải kết nối với một trong số S server trên. Trung tâm \(a\) có thể kết nối với trung tâm \(b\) nếu tồn tại đường đi từ \(a\) đến \(b\) trên mạng lưới đó, với độ trễ là tổng độ trễ các đường truyền phải đi qua.

AWS cần trả lời \(Q\) câu hỏi có dạng sau: trung tâm dữ liệu \(X\) muốn được cung cấp các dịch vụ thì độ trễ nhỏ nhất khi kết nối vào một trong các server là bao nhiêu?

Yêu cầu: Em hãy viết chương trình trả lời \(Q\) câu hỏi trên.

Dữ liệu vào:

- Dòng đầu tiên gồm 4 số nguyên \(N,\ S,\ G,\ M\ (1\ \leq \ N,\ M\ \leq \ 10^{5};\ S,\ G\ \leq \ N)\) lần lượt là số trung tâm dữ liệu, số server, số cụm máy và số đường dây mạng trên mạng lưới đó.

- Dòng thứ hai gồm \(S\) số là các trung tâm máy tính server trong số \(N\) trung tâm.

- G dòng tiếp theo, mỗi dòng có cấu trúc như sau:

+ Số đầu tiên là \(num\ (1\ \leq \ num\ \leq \ N)\), biểu thị cho số lượng các trung tâm máy tính trong cụm máy đó.

+ \(num\) số tiếp theo là chỉ số của các trung tâm dữ liệu trong cụm đó. Không có 2 trung tâm dữ liệu nào trùng nhau.

+ Cuối cùng là \(cost\ (1\ \leq \ cost\ \leq \ 10^{9})\), độ trễ để kết nối giữa 2 trung tâm bất kỳ trong cụm máy đó.

Tổng số trung tâm dữ liệu trong G cụm không quá 105.

- \(M\) dòng tiếp theo, mỗi dòng gồm 3 số u, v, w là một đường dây mạng 2 chiều nối giữa trung tâm \(u\) \(v\), với độ trễ \(w\ (1\ \leq \ w\ \leq \ 10^{9})\).

- Dòng tiếp theo chứa 1 số nguyên \(Q\ (1\ \leq \ Q\ \leq \ 10^{5})\), số lượng truy vấn.

- Q dòng cuối, mỗi dòng gồm 1 số là trung tâm dữ liệu \(X\ (1\ \leq \ X\ \leq \ 10^{5})\)

Kết quả: Ghi \(Q\) dòng, mỗi dòng một số nguyên là độ trễ nhỏ nhất cho \(Q\) câu hỏi tương ứng trong tệp dữ liệu vào.

Ví dụ:

Input Output Giải thích ví dụ
7 1 2 2
1
3 1 2 3 2
4 4 5 6 7 3
3 4 4
1 5 10
1
5
9
- Tổng độ trễ nhỏ nhất từ 5 đến 1 là 9

Ràng buộc:

+ Có 10% số test ứng với 10% số điểm có \(S = 1,\ G = 0\).

+ 20% số test ứng với 20% số điểm có \(S\ = \ 1\), tổng số máy trong \(G\) cụm không quá 105.

+ 10% số test ứng với 10% số điểm có \(G = 0\).

+ 20% số test ứng với 20% số điểm có tổng số máy trong G cụm không quá 103.

+ 40% số test ứng với 40% số điểm không có ràng buộc gì thêm.

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

Du lịch (tourist.*)

Tại thành phố Alpha có N điểm du lịch hấp dẫn được đánh số từ 1 đến \(n\). Thành phố có \(n - 1\) con đường 2 chiều để nối các điểm du lịch. Thị trưởng thành phố phát hiện ra việc tổ chức các tour đi từ địa điểm \(u\) đến các địa điểm được đánh số là bội của \(u\) sẽ rất thú vị, các tour như vậy thì du khách sẽ được thăm tất cả các địa điểm trên đường đi đơn giữa 2 địa điểm này.

Yêu cầu: Cho biết tổng số địa điểm được thăm với tất cả cách tổ chức tour được xây dựng như trên.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên \(n\ (1\ \leq n \leq \ 10^{5})\) là số địa điểm du lịch của thành phố.

  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u,\ v\) thể hiện đường nối giữa hai thành phố \(u\ \)và \(v\).

Kết quả: Ghi tổng số địa điểm du lịch được thăm với tất cả các tour được xây dựng như trên.

Ví dụ:

Input Output Giải thích
10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9
55
Có tất cả các con đường và số địa điểm có thể thăm được như sau: 1→2=4; 1→3=3; 1→4=2; 1→5=2; 1→6=3; 1→7=4; 1→8=3; 1→9=3; 1→10=2; 2→4=5; 2→6=6; 2→8=2; 2→10=3; 3→6=3; 3→9=3; 4→8=4; 5→10=3
Do đó, tổng số địa điểm du lịch được thăm sẽ là 55.

Ràng buộc:

  • 40% số test với \(1\ \leq \ n\ \leq \ 10^{3}\)

  • 60% số test với \(1\ \leq \ n \leq \ 10^{5}\)

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

Cờ nhảy (jumpf.*)

Cờ nhảy là trò chơi một người có quy tắc như sau:

  • Trò chơi diễn ra trên một dãy n ô vuông xếp thành một hàng, các ô được đánh số \(1,\ 2,\ \ldots,\ n\) từ trái sang phải.

  • Ban đầu quân cờ ở ô 1, nhiệm vụ của người chơi là đưa quân cờ đến ô \(n\).

  • Trong lượt đi đầu tiên, người chơi phải đưa quân cờ đến ô 2 (thực hiện bước nhảy độ dài 1).

  • Trong các lượt đi sau đó, nếu đưa quân cờ tiến lên thì độ dài bước nhảy phải tăng lên 1, còn nếu đưa quân cờ lùi lại thì độ dài bước nhảy phải giữ nguyên.

  • Phí phải trả khi đưa quân cờ nhảy vào ô \(i\)\(a_{i}\). Chú ý rằng việc quân cờ ở ô 1 lúc xuất phát là không phải trả phí.

Yêu cầu: Hãy xác định tổng phí phải trả nhỏ nhất để đưa được quân cờ đến ô \(n\).

Dữ liệu vào:

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

  • Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1\ \leq \ a_{i}\ \leq \ 500,\ 1\ \leq \ i\ \leq \ n)\).

Kết quả: Ghi một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Input Output
6
1 2 3 4 5 6
12
8
2 3 4 3 1 6 1 4
14

Ràng buộc:

  • 40% số test với \(2\ \leq \ n\ \leq \ 20\)

  • 60% số test với \(2\ \leq \ n\ \leq \ 1000\)

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

Từ điển (dict.*)

Cho từ điển gồm \(n\) từ, mỗi từ tối đa 10 chữ cái thường và T truy vấn.

Yêu cầu: Mỗi truy vấn cho một dãy các chữ cái. Hãy cho biết với dãy chữ cái này thì có thể tạo ra từ nào trong từ điển.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương \(n\ (1\ \leq \ n\ \leq \ 10^{5})\).

  • n dòng tiếp theo chứa các từ trong từ điển.

  • Dòng tiếp theo chứa số nguyên dương \(T\ (1\ \leq \ T\ \leq \ {3.10}^{4})\).

  • T dòng tiếp theo, mỗi dòng chứa một dãy các chữ cái (không quá 10).

Kết quả: Ghi \(T\) dòng tương ứng là kết quả của \(T\) truy vấn. Mỗi dòng in ra từ trong từ điển có thể tạo ra. Nếu có nhiều kết quả thì in ra từ dài nhất. Nếu nhiều từ cùng độ dài nhất thì đưa ra từ có thứ tự từ điển nhỏ nhất. Nếu không tạo ra được từ nào thì in ra “IMPOSSIBLE”.

Ràng buộc:

  • 30% số test với \(1\ \leq \ n\ \leq \ 10^{5},\ 1\ \leq \ T\ \leq \ 4\)

  • 40% số test với \(5\ \leq \ n\ \leq \ 10^{5},\ 1\ \leq \ T\ \leq \ 1000\)

  • 30% số test với \(1\ \leq \ n\ \leq \ 10^{5},\ \ 1\ \leq \ T\ \leq \ {3.10}^{4}\)

Ví dụ:

Input Otput
6
hanoi
haiduong
hungyen
haiphong
danang
yenbai
5
howareyou
hfyuennug
xinchaovn
dhhpongaiu
ybaiengh
IMPOSSIBLE
hungyen
hanoi
haiduong
yenbai

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

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ụ:

Input Output Giải thích
3
2 3 9
214
  • \(f(1,1) = 2 \times 2 \times 1 = 4,f(2,2) = 9,f(3,3) = 81\);
  • \(f(1,2) = 2 \times 3 \times 2 = 12,f(2,3) = 54\);
  • \(f(1,3) = 54\).
Tổng thu được \(= 4 + 9 + 81 + 12 + 54 + 54 = 214\)

Chú ý:

Subtasks % điểm Giới hạn
1 40% \(n \leq 5000\);
2 30% \(n \leq 3 \times 10^{5},\ a_{1} \leq a_{2} \leq \ldots \leq a_{n}\);
3 30% \(n \leq 10^{5},a_{i} \leq 500,\ \forall\ i \in \lbrack 1,\ n\rbrack\).

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\).

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\)

Input Output
5 6 1
1 2 10
1 3 30
2 3 5
2 4 20
3 5 15
4 5 10
1: 0
2: 10
3: 15
4: 30
5: 30

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\).

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\).

Input Output
6 8 1 4 6
1 2 5
1 3 10
2 4 8
3 4 2
4 5 3
4 6 7
5 6 4
2 3 1
15

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)\)\(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}\)\(y_{i}\ (1 \leq x_{i},y_{i} \leq n)\).

\(q\) truy vấn, truy vấn thứ \(i\ (1 \leq i \leq q)\) cho hai số \(l\)\(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}\)\(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\)\(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ụ:

Input Output Giải thích
4 6
1 2
2 3
3 4
4 1
1 3
2 3
2
1 3
3 5
Yes
No
- Ở truy vấn đầu tiên, các con đường có thể sử dụng là (1, 2), (2, 3), (3, 4). Tất cả 4 địa điểm chiến lược đều có thể đến được với nhau;
- Ở truy vấn thứ hai, các con đường có thể sử dụng là (3, 4), (4, 1), (1, 3). Các địa điểm 1, 3, 4 có thể đến được với nhau, tuy nhiên địa điểm 2 lại bị cô lập.

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\).

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

Input Output
6 8 1 6
1 2 5
1 3 10
2 4 10
3 4 5
3 5 15
4 5 5
4 6 10
5 6 5
25
4

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_{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\)\(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ố st. 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ụ:

Input

Output

hình minh họa

4 5
1 3 8
1 2 1 1
1 3 1 4
1 4 2 3
3 4 5 2
3 2 1 2
9.00

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

Thông báo cập nhật Website

  1. 05/02/2025: Cộng điểm và thời gian sử dụng Với mỗi lượt nộp bài đúng (đạt 100% số test) được cộng điểm và thời gian sử dụng:

    • Cộng round(12/x,2) điểm
    • Cộng round(5/x,2) ngày sử dụng

    Trong đó x là số lần nộp đúng của bài tập (không tính của admin)

  2. 05/02/2025: Với các tài khoản đăng kỳ từ 05/02/2025 sẽ có 30 ngày sử dụng. Tất cả các tài khoản có ít nhất 05 lượt nộp/bài tập

  3. 03/02/2025: Contest luyện tập cho kỳ thi Olympic 30/4 Để chuẩn bị cho kỳ thi truyền thống Olympic 30/4 tại Thành phố Hồ Chí Minh, admin tạo hai Contest dành cho hai khối 10 và 11. Các bài tập trong hai Contest này được lấy từ đề thi Olympic các năm trước. Tham gia Contest:

  4. 01/01/2025: Có thể xem được đề bài của tất cả các bài tập không thuộc Contest chưa diễn ra mà không cần đăng nhập, tuy nhiên để được nộp bài bạn cần phải đăng nhập.

  5. 14/11/2024: Cộng điểm và thời hạn sử dụng tài khoản khi nộp bài bằng Ngôn ngữ Scracth

    • Người đầu tiên sử dụng Scratch để nộp đúng 100% số test của 1 bài tập bạn sẽ nhận 80 điểm (không tính các ngôn ngữ lập trình khác)
    • Mỗi lượt nộp bài đúng 100% số test bạn sẽ nhận được 20 điểm5 ngày sử dụng
    • Lưu ý: Mỗi bài tập bạn nhận được tối đa 100 điểm5 ngày sử dụng
  6. 09/11/2024: Trình chấm bài bằng ngôn ngữ lập trình Scratch đã được thêm vào hpcode. Các bạn xem hướng dẫn nộp bài tại đây

  7. 30/10/2024: Chức năng Shortlink dùng để rút gọn link được thêm vào hpcode không chỉ dùng để rút gọn từ một đường link dài, xấu thành đường link ngắn gọn, dễ nhớ mà còn là nơi chia sẽ tài liệu, chuyên đề,bộ test.
  8. Ngừng cộng điểm cho các bài nộp: Từ ngày 27/9/2024 Website ngừng cộng điểm
  9. Các chuyên đề bồi dưỡng HSG: Các chuyên đề này được tìm thấy trên Internet nên admin chia sẻ với mọi người, tiếc là phần lớn không có Testcase kèm theo
  10. Quảng cáo: admin đang tiến hành thử nghiệm 1 loại quảng cáo trên web. Quảng cáo xuất hiện ở mọi trang trên Website ngoại trừ phần nộp và chấm bài.
  11. Không chia sẻ đề thi: admin có khá nhiều đề thi của các tỉnh, tuy nhiên vì một số lý do nên các bạn không xem được các đề thi thuộc mục Đề thi HSG. Tuy vậy trong thời gian tới admin vẫn chia sẻ một số đề thi do admin tự soạn lại (gõ lại đề, sinh test,...) dựa trên các đề thi có sẵn trên Internet.
hpcode.edu.vn
Code tích cực
Trong 24h
  1. cosu (13/16)
  2. ducbac (11/19)
  3. nhakyyy (6/7)
Trong 7 ngày
  1. cosu (46/65)
  2. trungdimid (42/57)
  3. ducbac (23/35)
Trong 30 ngày
  1. ndhdang091011 (211/265)
  2. cosu (86/162)
  3. trungdimid (82/150)
Thống kê
AC/Sub: 120817/226949
Pascal: 18142
C++: 157988
Python: 50747
Lượt xem/tải tests: 42675

Lưu Hải Phong - 2020
[email protected]