Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

Hải dùng ổ khóa số (Hình ảnh) để khóa tủ cá nhân tại đội tuyển.

Khóa gồm có bốn vòng số, mỗi vòng gồm ~10~ chữ số từ ~0~ đến ~9~. Các vòng số của khóa này có thể xoay tròn theo chiều kim đồng hồ hoặc ngược lại.

Hải đặt mật khẩu khóa của mình theo thứ tự từ trên xuống dưới của vị trí chốt là ~\{2,0,2,5\}~. Mỗi lần khóa, Hải xoay các số đi, khi nào muốn mở thì lại đưa các số về đúng dãy ~\{2,0,2,5\}~. Mỗi lần xoay thì một chữ số sẽ chuyển thành số kề bên trái hoặc kề bên phải của nó.

Chú ý: kề bên trái của ~0~ là ~9~, kề bên phải của ~9~ là ~0~.

Yêu cầu: Cho biết ~4~ chữ số ~A, B, C, D~ lần lượt là các chữ số đang xuất hiện từ trên xuống dưới của vị trí chốt. Em hãy lập trình tính giúp Hải xem phải xoay ít nhất bao nhiêu lần để có thể mở khóa.

Dữ liệu vào (KHOASO.INP)

Gồm bốn chữ số ~A, B, C, D~ trên cùng một dòng, cách nhau bởi một dấu cách ~(0 \le A, B, C, D \le 9)~.

Kết quả (KHOASO.OUT)

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Input

2 3 8 1

Output

11

Giải thích: Cách xoay ít lần nhất để mở khóa là:

• Chữ số thứ nhất giữ nguyên;
• Chữ số thứ hai xoay từ ~3~ thành ~0~ mất ~3~ lần xoay;
• Chữ số thứ ba xoay từ ~8~ thành ~2~ mất ~4~ lần xoay như sau: ~8 \to 9 \to 0 \to 1 \to 2~;
• Chữ số thứ tư xoay từ ~1~ thành ~5~ mất ~4~ lần xoay;

Tổng số lần xoay là: ~0 + 3 + 4 + 4 = 11~.

Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

Một cửa hàng trên sàn thương mại điện tử có ~N~ sản phẩm khác nhau được niêm yết với giá tiền lần lượt là ~A_1, A_2, \ldots, A_N~. Việt muốn mua hai sản phẩm, mỗi sản phẩm mua tối đa một lần, sao cho tổng số tiền phải trả nằm trong khoảng từ ~L~ đến ~R~.

Yêu cầu: Em hãy lập trình đưa ra số tiền nhỏ nhất mà Việt phải trả khi mua hai sản phẩm khác nhau mà tổng số tiền phải trả nằm trong đoạn ~[L, R]~.

Dữ liệu vào (MUASAM.INP)

• Dòng đầu tiên gồm ba số nguyên dương ~N, L, R~ ~(N \le 10^6;\ 1 \le L \le R \le 10^9)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(A_i \le 10^9;\ 1 \le i \le N)~.

Kết quả (MUASAM.OUT)

Một số nguyên duy nhất là kết quả của bài toán.

Dữ liệu đảm bảo luôn tồn tại ít nhất một cách mua thỏa mãn.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm có ~N \le 10^3~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

5 5 9
8 1 2 2 5

Output

6

Giải thích: Mua hai sản phẩm ~2~ và ~5~ với tổng số tiền phải trả là ~6~.

Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

Khu phố Nam ở đã treo ~N~ chiếc đèn lồng, được đánh số từ ~1~ đến ~N~, từ trái sang phải. Ban đầu, chiếc đèn lồng thứ ~i~ có màu kí hiệu ~A_i~ ~(1 \le A_i \le 9)~. Một dãy đèn lồng liên tiếp được gọi là "cát tường" nếu có không quá ~K~ màu khác nhau, độ dài của dãy đèn được tính là số lượng đèn trong dãy đó.

Để chào mừng năm mới sắp đến, khu phố của Nam quyết định thay một số đèn sao cho xuất hiện dãy đèn "cát tường" là dài nhất có thể. Do ngân sách có hạn, khu phố chỉ thay thế được tối đa ~X~ chiếc đèn lồng.

Ví dụ: Với ~K = 2~, xét dãy ~6~ đèn lồng liên tiếp có kí hiệu màu của từng chiếc là ~\{4,1,5,3,3,1\}~. Dãy này đang xuất hiện dãy "cát tường" dài nhất có độ dài ~3~ là ~\{5,3,3\}~ hoặc ~\{3,3,1\}~. Khi ~X = 1~, ta có thể thay đèn thứ ~3~ thành màu ~1~ hoặc màu ~3~, được dãy đèn có kí hiệu màu là ~\{4,1,1,3,3,1\}~ hoặc ~\{4,1,3,3,3,1\}~ thì sẽ xuất hiện dãy "cát tường" dài nhất có độ dài ~5~.

Yêu cầu: Em hãy lập trình xác định độ dài lớn nhất của dãy đèn "cát tường" sau khi thay thế tối đa ~X~ chiếc đèn lồng.

Dữ liệu vào (DENLONG.INP)

• Dòng đầu tiên gồm ba số nguyên dương lần lượt là ~N, K, X~ ~(1 \le K \le 9;\ 1 \le X \le N \le 10^5)~ với ~N~ là số đèn lồng đã treo, ~K~ là giá trị lớn nhất về số màu trong dãy đèn "cát tường", ~X~ là số lượng đèn nhiều nhất có thể thay thế;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_i~ mô tả màu của chiếc đèn thứ ~i~ ~(1 \le A_i \le 9)~.

Kết quả (DENLONG.OUT)

Một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~N \le 10^2;\ 1 \le A_i \le 2~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 10^3;\ K = X = 1~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~N \le 10^5;\ K = 1~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

6 2 2
1 9 3 2 3 5

Output

5

Giải thích: Một trong những cách thay thế ~2~ chiếc đèn để khu phố xuất hiện dãy ~5~ đèn liên tiếp "cát tường" là:

• Thay thế đèn thứ ~2~ thành màu ~3~, thay thế đèn thứ ~4~ thành màu ~3~;
• Dãy đèn sau khi thay thế sẽ có màu: ~\{1, 3, 3, 3, 3, 5\}~.

Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

Công ty của Chiến tổ chức trò chơi chọn số trong buổi tiệc cuối năm. Ban tổ chức chuẩn bị sẵn một bộ số gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ và ~N~ tấm thẻ. Trên mỗi tấm thẻ ghi một số tự nhiên có giá trị từ ~1~ đến ~N~, các giá trị trên thẻ đôi một khác nhau. Ban tổ chức sẽ phát cho mỗi người chơi một tấm thẻ bất kỳ trong ~N~ tấm thẻ trên. Luật chơi đưa ra như sau:

• Giả sử người chơi nhận được tấm thẻ ghi số nguyên ~K~;
• Sau đó, người chơi chọn ra tối đa ~K~ đoạn con trên bộ số ban đầu mà Ban tổ chức đã chuẩn bị, mỗi đoạn gồm một hoặc nhiều phần tử liên tiếp, các đoạn con không có phần tử chung. Người chơi có quyền không chọn đoạn con nào;
• Điểm của người chơi là tổng các số trong các đoạn đã chọn. Ban tổ chức sẽ trao phần thưởng tương ứng với số điểm mà người chơi đạt được.

Yêu cầu: Có ~Q~ người chơi khác nhau. Em hãy lập trình đưa ra số điểm lớn nhất mà mỗi người chơi có thể nhận được.

Dữ liệu vào (TROCHOI.INP)

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le Q \le N \le 10^5)~ tương ứng số lượng phần tử trong bộ số và số lượng người tham gia trò chơi;
• Dòng thứ hai chứa ~N~ số nguyên, số nguyên thứ ~i~ biểu diễn giá trị của ~A_i~ ~(-10^4 \le A_i \le 10^4)~;
• Dòng thứ ba chứa ~Q~ số nguyên, số nguyên thứ ~i~ là ~K_i~ ~(1 \le K_i \le N)~ mô tả số ghi trên tấm thẻ của người chơi thứ ~i~. Các ~K_i~ đảm bảo phân biệt và được sắp xếp theo thứ tự tăng dần.

Kết quả (TROCHOI.OUT)

Gồm ~Q~ dòng, dòng thứ ~i~ tương ứng là kết quả của người chơi thứ ~i~ khi được phát tấm thẻ ghi số ~K_i~.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm có ~N \le 10^5;\ Q = 1;\ K = 1~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 10^5;\ Q = 1;\ K \le 2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 10^5;\ Q = 1;\ K \le 50~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 10^5;\ Q = 1;\ K \le N~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

5 3
1 -1 2 -2 3
1 2 5

Output

3
5
6

Giải thích:

• Với ~K_1 = 1~, chọn đoạn ~[5,5]~;
• Với ~K_2 = 2~, chọn đoạn ~[3,3]~ và đoạn ~[5,5]~;
• Với ~K_3 = 5~, chọn đoạn ~[1,1]~, ~[3,3]~ và ~[5,5]~.

Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

Thắng tham gia thử thách "check-in" trong hội chợ tết của thành phố. Hội chợ gồm có ~N~ điểm bán hàng được đánh số từ ~1~ đến ~N~. Các điểm bán hàng được nối với nhau bởi ~M~ đường hai chiều, mỗi đường có một cửa chắn với mã khóa là một số nguyên dương. Các mã khoá trên cửa chắn là đôi một khác nhau. Có ~K~ điểm bán hàng đặc biệt ~S_1, S_2, \ldots, S_K~ là điểm "check-in" để hoàn thành thử thách.

Ở mỗi lượt, ban đầu cửa chắn tại tất cả các con đường đều khóa. Người chơi sẽ nhận được thông tin gồm hai số tự nhiên ~X~ và ~D~ tương ứng là số hiệu của điểm bán hàng xuất phát và chìa khóa có số ~D~. Chìa khóa có số ~D~ sẽ mở được những cánh cửa có mã khóa là bội của ~D~. Ví dụ: chìa khoá có số ~2~ sẽ mở được các cánh cửa bị khóa bởi mã khoá là ~2, 4, 6, 8, \ldots~; chìa có số ~7~ sẽ mở được các cửa bị khóa bởi mã khoá là ~7, 14, 21, 28, \ldots~ Người chơi cần tìm đường đi như sau:

• Xuất phát từ điểm bán hàng ~X~;
• Đích đến là một trong các điểm bán hàng đặc biệt ~S_1, S_2, \ldots, S_K~;
• Số lượng con đường đi qua là nhỏ nhất.

Yêu cầu: Thắng tham gia ~Q~ lượt chơi, với mỗi lượt Thắng nhận được một cặp số ~(X, D)~. Em hãy lập trình đưa ra số lượng con đường nhỏ nhất Thắng cần đi qua để đến đích tại mỗi lượt chơi.

Dữ liệu vào (HOICHO.INP)

• Dòng đầu tiên gồm bốn số nguyên dương ~N, M, K, Q~ ~(N, M, Q \le 3 \times 10^5;\ 1 \le K \le N)~ tương ứng lần lượt là số lượng điểm bán hàng, số lượng con đường nối giữa ~N~ điểm bán, số lượng điểm bán đặc biệt và số lượt chơi;
• Dòng thứ hai gồm ~K~ số nguyên dương ~S_1, S_2, \ldots, S_K~ ~(1 \le S_i \le N;\ 1 \le i \le K)~ mô tả các điểm bán hàng đặc biệt;
• ~M~ dòng sau, mỗi dòng gồm ba số nguyên ~u, v, c~ ~(1 \le u, v \le N;\ 1 \le c \le 10^6)~ mô tả có một đường hai chiều nối giữa điểm bán ~u~ và điểm bán ~v~ mà trên đường đó có một cánh cửa chắn với mã khóa là ~c~;
• ~Q~ dòng sau, mỗi dòng gồm hai số nguyên ~X~ và ~D~ là thông tin của mỗi lượt chơi.

Kết quả (HOICHO.OUT)

Gồm ~Q~ dòng, tương ứng với ~Q~ lượt chơi, nếu có đường đi thoả mãn yêu cầu đề bài thì in ra số con đường nhỏ nhất Thắng cần đi qua để đến đích, ngược lại, nếu không có cách nào để đi đến đích thì in ra ~-1~.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~Q = 1;\ D = 1~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm có ~K = 1;\ D \le 10~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~D \le 10~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~D \le 10^4~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

5 7 2 4
4 5
3 4 14
1 2 16
2 4 5
1 4 7
4 5 9
1 3 8
3 5 4
1 2
1 5
1 1
2 4

Output

2
-1
1
3

Giải thích:

• Ở lượt chơi ~1~, có thể chọn đường đi: ~1 \to 3 \to 5~ hoặc ~1 \to 3 \to 4~ đều có số lượng con đường đi qua nhỏ nhất là ~2~;
• Ở lượt chơi ~2~, không có đường đi thoả mãn;
• Ở lượt chơi ~3~, có thể chọn đường đi: ~1 \to 4~;
• Ở lượt chơi ~4~, có thể chọn đường đi: ~2 \to 1 \to 3 \to 5~.