Hải dùng ổ khóa số để 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 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 bốn 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 số lần xoay ít nhất để mở khóa.

Đầu vào

• Dữ liệu từ file văn bản \(KHOASO.INP\).
• Gồm một dòng duy nhất chứa bốn chữ số \(A\ B\ C\ D\), cách nhau bởi một dấu cách \((0 \le A, B, C, D \le 9)\).

Đầu ra

• Ghi ra file văn bản \(KHOASO.OUT\).
• Một số nguyên duy nhất là số lần xoay tối thiểu.

Ví dụ

2 3 8 1

11

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, \dots, 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 sao cho tổng tiền nằm trong đoạn \([L, R]\).

Đầu vào

• Dữ liệu từ file văn bản \(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, \dots, A_N\) \((A_i \le 10^9; 1 \le i \le N)\)

Đầu ra

• Ghi ra file văn bản \(MUASAM.OUT\)
• Một số nguyên duy nhất là số tiền nhỏ nhất có thể trả.
• 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

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

Ví dụ

5 5 9
8 1 2 2 5

6

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.

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.

Đầu vào

• Dữ liệu từ file văn bản \(DENLONG.INP\):
• Dòng đầu tiên gồm ba số nguyên dương \(N, K, X\) \((1 \le K \le 9; 1 \le X \le N \le 10^5)\)
  • \(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\) \((1 \le A_i \le 9)\) mô tả màu của từng đèn lồng

Đầu ra

• Ghi ra file văn bản \(DENLONG.OUT\)
• Một số nguyên duy nhất là độ dài lớn nhất của dãy đèn “cát tường” sau khi thay thế tối đa \(X\) đèn lồng

Ràng buộc

• 40% số test ứng với 40% số điểm: \(N \le 10^2\), \(1 \le A_i \le 2\)
• 30% số test khác ứng với 30% số điểm: \(N \le 10^3\), \(K = X = 1\)
• 20% số test khác ứng với 20% số điểm: \(N \le 10^5\), \(K = 1\)
• 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ụ

6 2 2
1 9 3 2 3 5

5

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, \dots, 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 như sau:

• Giả sử người chơi nhận được tấm thẻ ghi số nguyên \(K\)
• Người chơi chọn ra tối đa \(K\) đoạn con trên bộ số ban đầu, 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 trao phần thưởng tương ứng với số điểm mà người chơi đạt được

Yêu cầu:
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

Đầu vào

• Dữ liệu từ file văn bản \(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

Đầu ra

• Ghi ra file văn bản \(TROCHOI.OUT\)
• Gồm \(Q\) dòng, dòng thứ \(i\) tương ứng là số điểm lớn nhất mà người chơi thứ \(i\) đạt được khi nhận tấm thẻ ghi số \(K_i\)

Ràng buộc

• 20% số test ứng với 20% số điểm: \(N \le 10^5\), \(Q=1\), \(K=1\)
• 20% số test khác ứng với 20% số điểm: \(N \le 10^5\), \(Q=1\), \(K \le 2\)
• 20% số test khác ứng với 20% số điểm: \(N \le 10^5\), \(Q=1\), \(K \le 50\)
• 20% số test khác ứng với 20% số điểm: \(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ụ

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

3
5
6

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 \(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ã khóa 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, \dots, S_K\) là điểm “check-in” để hoàn thành thử thách.

Ở mỗi lượt chơi:

• Ban đầu tất cả các cửa chắn đều khóa
• Người chơi nhận được hai số \((X, D)\):
  • \(X\) là điểm bán hàng xuất phát
  • Chìa khóa số \(D\) mở được những cửa có mã khóa là bội của \(D\)
    • Ví dụ: chìa số 2 mở các cửa 2,4,6,8,…; chìa số 7 mở các cửa 7,14,21,…

Yêu cầu đường đi:

• Xuất phát từ điểm \(X\)
• Điểm đến là một trong các điểm đặc biệt \(S_1,\dots,S_K\)
• Số lượng con đường đi qua là nhỏ nhất

Em hãy lập trình đưa ra số lượng con đường nhỏ nhất Thắng cần đi qua cho mỗi lượt chơi.

Đầu vào

• Dữ liệu từ file văn bản HOICHO.INP:
  • Dòng đầu tiên: \(N, M, K, Q\) \((N, M, Q \le 3 \cdot 10^5; 1 \le K \le N)\)
  • Dòng thứ hai: \(K\) số nguyên dương \(S_1, \dots, S_K\) \((1 \le S_i \le N)\), các điểm bán hàng đặc biệt
  • \(M\) dòng tiếp theo, mỗi dòng ba số \(u, v, c\) \((1 \le u,v \le N; 1 \le c \le 10^6)\), biểu diễn đường hai chiều nối \(u\) và \(v\) với cửa có mã khóa \(c\)
  • \(Q\) dòng sau, mỗi dòng hai số \(X, D\) thông tin lượt chơi

Đầu ra

• Ghi ra file HOICHO.OUT
• Gồm \(Q\) dòng, dòng thứ \(i\):
  • Số con đường nhỏ nhất Thắng cần đi qua để đến một điểm check-in
  • Nếu không có cách đi, ghi -1

Ràng buộc

• 30% số test: \(Q=1\), \(D=1\)
• 15% số test khác: \(K=1\), \(D \le 10\)
• 25% số test khác: \(D \le 10\)
• 20% số test khác: \(D \le 10^4\)
• 10% số test còn lại: không có ràng buộc gì thêm

Ví dụ

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

2
-1
1
3