Duyên hải Bắc Bộ 2020 CT

Minh nhận được một chiếc máy tính bấm tay màn hình LCD. Màn hình được chia thành các ô biểu diễn chữ số, mỗi ô gồm \(7\) vạch LED và mỗi chữ số sẽ tương ứng với một số vạch LED được kích hoạt nổi màu đen trên ô đó. Cách hiển thị các số như sau:

Minh bấm số nguyên dương \(N\) hiển thị trên màn hình và thắc mắc 2 câu hỏi:

1. Có bao nhiêu vạch LED được kích hoạt để hiển thị số \(N\).
2. Tính số lượng các số lớn hơn \(N\), có thể được hiển thị bởi kích hoạt thêm ít nhất một vạch LED ngoài các vạch đang được kích hoạt để hiển thị số \(N\) (không tắt bất kỳ vạch LED nào đang hiển thị và không kích hoạt vạch LED trên ô chưa có vạch kích hoạt).

Yêu cầu: Hãy lập trình giúp Minh trả lời \(2\) câu hỏi trên.

Input

• Dòng đầu tiên ghi mã câu hỏi \(V\) là \(1\) hoặc \(2\).
• Dòng thứ 2 ghi số nguyên dương \(N\) (không bắt đầu bởi chữ số \(0\)).

Output

• Nếu \(V=1\) thì in ra số vạch LED được kích hoạt để hiển thị số \(N\).
• Nếu \(V=2\) thì in ra số lượng số lớn hơn \(N\), có thể được hình thành bằng cách kích hoạt thêm ít nhất một vạch LED, bên cạnh các vạch đã kích hoạt được sử dụng để hiển thị số \(N\).

Constraints

• \(N \leq 10 ^ {18}\)

Scoring

• Subtask \(1\) (\(45\%\) số điểm): \(V = 1, N \leq 10 ^ {18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(V = 2, N < 20\)
• Subtask \(3\) (\(35\%\) số điểm): \(V = 2, 20 \leq N \leq 10 ^ {18}\)

Example

1 
823 

17

2 
823 

5

Bình là một cậu bé rất đam mê toán học, đặt biệt là phần số học. Giải các bài toán về số nguyên tố, số chính phương, chia hết, \(\ldots\) là sở trường của Bình. Nhân dịp Kỳ thi Duyên hải năm nay được tổ chức lần dầu tiên theo hình thức thi online, Bình gửi đến các bạn một bài toán liên quan đến số chính phương.

Với số tự nhiên \(n\) cho trước, Bình yêu cầu bạn đếm số bộ ba số nguyên \((a,b,c)\) với \((1 \leq a<b<c \leq n)\) sao cho tất cả các tích \(a×b,a×c\) và \(b×c\) đều là các số chính phương.

Input

• Duy nhất số nguyên dương n \((n \leq 5 * 10 ^ 6)\)

Output

• Ghi ra số lượng bộ 3 số \(a,b,c\) tìm được.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(1 \leq n \leq 100\)
• Subtask \(2\) (\(20\%\) số điểm): \(100 < n \leq 5000\)
• Subtask \(3\) (\(28\%\) số điểm): \(5000 < n \leq 10 ^ 5\)
• Subtask \(4\) (\(28\%\) số điểm): \(10 ^ 5 < n \leq 5 * 10 ^ 6\)

Example

20 

5

Một công ty cung cấp dịch vụ cho các đối tác của mình đặt tại n vùng khác nhau được đánh số \(1, 2, 3, …, n\). Công ty có \(3\) nhân viên phục vụ lưu động. Nếu xuất hiện một yêu cầu tại một địa điểm mà hiện đang không có nhân viên đang ở đó, một trong ba nhân viên di chuyển từ vị trí hiện tại của anh ta đến trực tiếp địa điểm xuất hiện yêu cầu mà không qua bất kỳ một địa điểm trung gian nào khác. Tại mọi thời điểm, chỉ có một nhân viên di chuyển. Các nhân viên chỉ di chuyển khi có yêu cầu phục vụ và không có hai nhân viên nào ở cùng một vị trí tại bất kỳ thời điểm. Chi phí để di chuyển từ vị trí \(i\) đến vị trí \(j\) là \(C_{ij}\). Chú ý rằng hàm chi phí không nhất thiết phải là đối xứng, tuy nhiên chi phí khi không di chuyển luôn bằng \(0(Cii=0)\). Các yêu cầu phải được thực hiện theo thứ tự xuất hiện (yêu cầu xuất hiện trước phải được phục vụ trước, phục vụ xong một yêu cầu mới phục vụ yêu cầu tiếp theo).

Yêu cầu: Hãy tìm lịch di chuyển các nhân viên phục vụ yêu cầu sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,m,\) lần lượt là số vùng khác nhau và số yêu cầu cần phục vụ \((3 \leq n \leq 200,1 \leq m \leq 1000)\).
• n dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên không âm có giá trị không vượt quá \(2000\). Số thứ \(j\) của dòng thứ \(i\) là giá trị của \(C_{ij}\) - chi phí để đi từ \(i\) đến \(j\).
• Dòng cuối cùng chứa \(m\) số nguyên là danh sách các yêu cầu phục vụ theo thứ tự đăng ký. Mỗi yêu cầu được mô tả bằng một số nguyên - số hiệu địa điểm, nơi yêu cầu xảy ra. Ban đầu ba nhân viên phục vụ đang ở các địa điểm \(1, 2\) và \(3\).

Output

• Ghi ra một số nguyên \(S\) là tổng chi phí nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(3 \leq n , m \leq 8\)
• Subtask \(2\) (\(20\%\) số điểm): \(8 < n , m \leq 50\)
• Subtask \(3\) (\(28\%\) số điểm): \(50 < n \leq 200, 50 < m \leq 1000\)

Example

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1 

5

Sau khi khống chế thành công COVID 19, các đường bay đã được mở lại, nhu cầu đi lại tăng cao sau kì nghỉ Tết dài nhất trong lịch sử. Hiện tại là thời điểm 0, có N máy bay đang tiếp cận để hạ cánh tại sân bay Cát Bi. Máy bay thứ \(i\) \((1 \leq i \leq N)\) có thể điều chỉnh tốc độ để hạ cánh ở một mốc thời điểm nguyên trong khoảng thời gian \([L_i,R_i]\). Trong đó \(L_i\) là thời điểm sớm nhất máy bay có thể hạ cánh, \(R_i\) là thời điểm muộn nhất máy bay phải hạ cánh, quá thời gian \(R_i\), máy bay sẽ chuyển hướng hạ cánh tại sân bay khác. Khoảng thời gian \(R_i−L_i\) được gọi là giới hạn chờ của máy bay thứ \(i\) và giới hạn này tất cả N máy bay là giống nhau.

Sân bay có \(K\) đường băng, có thể hoạt động độc lập và tiếp nhận các máy bay hạ cánh. Các máy bay phải thực hiện lệnh giãn cách \(X\) giây. Hay 2 máy bay liên tiếp hạ cánh trên một đường băng phải cách nhau ít nhất \(X\) giây.

Yêu cầu: Hãy lên phương án sắp xếp các máy bay, sao cho số lượng máy bay hạ cánh là nhiều nhất có thể. Nếu có cùng phương án đảm bảo số lượng máy bay hạ cánh nhiều nhất, tìm phương án tối ưu sao cho thời gian chênh lệch nhỏ nhất giữa 2 máy bay cùng hạ cánh trên một đường băng là lớn nhất.

Input

• Dòng đầu tiên ghi \(3\) số nguyên dương \(N,K,X\) \((N \leq 10 ^ 5,K \leq 4,X \leq 10^9)\)
• Tiếp theo là \(N\) dòng, mỗi dòng ghi \(2\) số \(L_i,R_i\) \((0 \leq L_i \leq R_i \leq 10^9)\) Dữ liệu đảm bảo giá trị \(R_i−L_i\) của tất cả các máy bay là giống nhau.

Output

• Ghi ra 2 số nguyên \(T\) và \(P\) được ghi trên một dòng, phân tách bởi dấu cách. Số thứ nhất \(P-\) là số máy bay lớn nhất có thể hạ cánh được. Số thứ hai \(T-\) là giá trị của chênh lệch nhỏ nhất giữa 2 máy bay bất kỳ trên cùng một đường băng trong phương án tối ưu tìm được. Nếu mỗi đường băng chỉ tiếp nhận không quá 1 máy bay thì ghi ra \(-1\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(N \leq 8,K=1\)
• Subtask \(2\) (\(12\%\) số điểm): \(N \leq 8,K=2\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 16,K=1,0 \leq L_i \leq R_i \leq 100\)
• Subtask \(4\) (\(16\%\) số điểm): \(N \leq 16,K=2,0 \leq L_i \leq R_i \leq 100\)
• Subtask \(5\) (\(20\%\) số điểm): \(N \leq 10^5,K=1\)
• Subtask \(6\) (\(16\%\) số điểm): \(N \leq 10^5,2 \leq K \leq 4\)

Example

5 1 60
0 20
0 20
100 120
60 80
110 130 

3 65

5 2 60
0 20
0 20
100 120
60 80
110 130 

5 65

5 3 60
0 20
0 20
100 120
60 80
110 130 

5 120

Do dịch Covid-19, hai bạn Hồng và Chi không được đi học và gặp nhau nhưng hai bạn vẫn thường xuyên nhắn tin cho nhau. Một lần, Hồng muốn gửi mật khẩu tham gia lớp học online cho Chi nhưng không muốn em Phúc tò mò và biết được. Theo ý tưởng giấu tin trong ảnh, Hồng quyết định sẽ giấu mật khẩu vào trong đoạn văn bản gửi cho Chi. Cụ thể, với một văn bản mà Hồng gửi cho Chi được biểu diễn bằng xâu ký tự \(T=t_1t_2 \cdots t_n\) (gồm \(n\) ký tự, mỗi ký tự thuộc \(′a′\) đến \(′z′\)) và dãy số nguyên \(a_1,a_2,…,a_m\) \((1 \leq a_1<a_2< \cdots <a_m \leq n)\) là dãy số mà hai bạn đã thống nhất thì mật khẩu là một xâu \(P=t_{a_1}t_{a_2} \cdots t_{a_m}\), là xâu độ dài \(m\) nhận được bằng cách ghép lần lượt các ký tự ở các vị trí \(a_1,a_2,\cdots,a_m\). Ví dụ, \(T= ′missyouuu′\) và dãy số \(a_1=2,a_2=3,a_3=5,a_4=6,a_5=8\) thì mật khẩu là \(P= “isyou”\).

Hồng nhanh chóng nhận ra rằng, với một xâu \(T\) và mật khẩu \(P\) sẽ tồn tại nhiều dãy số để xác định mật khẩu. Ví dụ, một dãy số khác \(a_1=2,a_2=4,a_3=5,a_4=6,a_5=7\) cũng xác định được mật khẩu \(P= “isyou”\) trong xâu \(T= ′missyouuu′\).

Trong quá trình gửi, xâu \(T\) sẽ được mã hóa theo phương thức RLE (Run Length Encoding). Nghĩa là, một xâu \(T\) chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) được mã hóa thành xâu \(TE\) (chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) và ký tự \(‘0’\) đến \(‘9’\)) bằng cách đi từ trái sang phải, mã hoá dãy các ký tự liên tiếp giống nhau trong \(T\) thành ký tự đại diện và số lượng.

Ví dụ, xâu \(T= ′missyouuuuuuuuuu′\) thì \(TE= ′m1i1s2y1o1u10′\).

Yêu cầu: Cho xâu \(TE\) (là mã hóa của xâu \(T\)) và xâu mật khẩu \(P\), gọi \(R\) là số lượng dãy số khác nhau có thể xác định được mật khẩu \(P\) trong xâu \(T\). Hãy tính \(R\) chia dư cho \(10^9+7\).

Input

• Dòng đầu chứa hai số nguyên dương \(n,m\);
• Dòng thứ hai chứa một xâu là mã hóa của xâu \(T\)
• Dòng thứ ba chứa một xâu là xâu \(P\).

Output

• Ghi ra một số nguyên duy nhất là số \(R\) chia dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20,m=1\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 20,m<n\);
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^5,m=3\);
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^5,m \leq 30\);
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 10^9,m \leq 30\) và xâu mã hóa của xâu \(T\) có độ dài không vượt quá \(10^5\)

Example

9 5
m1i1s2y1o1u3
isyou 

6

11 3
m1i1s2i1s2i1p2i1
isi 

14

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt nam không có ca nhiễm mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau: Xét lưới ô vuông thước \(m \times n\), các dòng được đánh số từ \(1\) đến \(m\) từ trên xuống, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm trên giao của dòng \(i\), cột \(j\) được gọi là ô \((i,j)\) và ô này chứa một số nguyên dương \(a(i,j)\). Nếu một virus đang ở ô \((x,y)\), virus có thể thực hiện bước di chuyển sau:

• Virus di chuyển sang ô kề cạnh với ô \((x,y)\) nằm trong lưới, việc di chuyển này mất 1 đơn vị thời gian;
• Virus di chuyển sang ô \((u,v)\) nằm trong lưới nếu \(u \times v=a(x,y)\), việc di chuyển này mất 3 đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô \((p,q)\) đến ô \((r,s)\).

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm 2020 giải giúp.

Yêu cầu: Cho lưới kích thước \(m \times n\) và các số trên lưới. Có \(h\) câu hỏi, với câu hỏi thứ \(k\) (\(k=1,2, \cdots ,h\)) cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô \((p_k,q_k)\) đến ô \((r_k,s_k)\) là bao nhiêu?

Input

• Dòng đầu chứa ba số nguyên dương \(m,n,h\) \((h \leq 5)\);
• Dòng thứ \(i\) \((i=1,2,\cdots,m)\) trong \(m\) dòng tiếp theo chứa \(n\) số nguyên dương \(a(i,1)\),\(a(i,2)\),\(\cdots\),\(a(i,n)\). Các số có giá trị không vượt quá \(10^6\).
• Dòng thứ \(k\) \((k=1,2,\cdots,h)\) trong \(h\) dòng tiếp theo chứa bốn số nguyên \(p_k,q_k,r_k,s_k\).

Output

• Ghi ra \(h\) dòng, dòng thứ \(k\) \((k=1,2,\cdots,h)\) ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô \((pk,qk)\) đến ô \((rk,sk)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \times n \leq 10^2\);
• Subtask \(2\) (\(20\%\) số điểm): \(m \times n \leq 10^3\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \times n \leq 10^4\);
• Subtask \(4\) (\(20\%\) số điểm): \(m \times n \leq 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(m \times n \leq 10^6\)

Example

2 5 2
8 6 4 1 1
1 1 1 1 1
1 1 2 5
2 5 1 1 

4
3

Vào ngày 19 tháng 5, là ngày sinh nhật Bác, thầy Phương sẽ tổ chức một buổi liên hoan và tặng thưởng cho các bạn có nhiều tiến bộ khi tham HCC. Có \(n\) bạn được mọi người đánh giá cao, các bạn này sẽ được nhận quà của thầy Phương. Thầy Phương đã chuẩn bị \(m\) món quà, đồng thời thu thập thông tin mong muốn nhận quà của từng bạn. Các bạn được đánh số từ 1 đến \(n\), các món quà được đánh số từ 1 đến \(m\), với bạn thứ \(i(i=1,2,\cdots,n)\) và món quà \(j (j=1,2,\cdots,m)\) thầy Phương có thông tin \(s_{i_j}\) là một số nguyên dương đánh giá nguyện vọng của bạn \(i\) muốn nhận món quà \(j\).

Mỗi một món quà sẽ được tặng cho đúng một bạn, mỗi bạn sẽ được nhận ít nhất một món quà. Gọi \(r_i\) \((i=1,2,\cdots,n)\) là tổng đánh giá nguyện vọng của các món quà mà người \(i\) nhận được và \(w=min\){\(r_1,r_2,\cdots,r_n\)}. Thầy Phương muốn tìm cách tặng quà để giá trị \(w\) đạt giá trị càng lớn càng tốt.

Yêu cầu: Cho \(n,m\) và các giá trị \(s_{i_j}\), em hãy giúp thầy Phương tìm phương án tặng quà để giá trị \(w\) đạt giá trị càng lớn càng tốt.

Input

• Dòng đầu chứa hai số nguyên dương \(n,m\) \((n \leq m)\);
• Dòng thứ \(i (i=1,2,\cdots,n)\) trong \(n\) dòng tiếp theo chứa \(m\) số nguyên dương \(s_{i1},s_{i2},\cdots,s_{im}\). Các số có giá trị không vượt quá 1000.

Output

• Ghi ra \(n\) dòng, dòng thứ \(i (i=1,2,\cdots,n)\) có dạng:
  • Số đầu tiên ghi số \(p_i\) là số món quà mà bạn \(i\) nhận được;
  • Tiếp theo là \(p_i\) số là chỉ số những món quà mà bạn \(i\) được nhận. Các chỉ số được liệt kê theo thứ tự tăng dần.
    Tính điểm:
    Với mỗi test, gọi \(w_p\) là giá trị theo phương án mà thầy Phương tìm được (giá trị này em không được biết, chỉ dùng khi chấm), \(w\) giá trị theo phương án của em, khi đó em sẽ nhận được \(\frac{1000 \times w − 999\times w_p}{w_p}\) trên tổng số 1 điểm của test đó, nếu \(1000 \times w < 999 \times w_p\) em sẽ nhận 0 điểm. Khác với kỳ thi chính thức, các bạn sẽ được bonus nếu đáp án lớn hơn đáp án của thầy.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m,n \leq 12\);
• Subtask \(2\) (\(40\%\) số điểm): \(m \leq 1200,n=2\);
• Subtask \(3\) (\(30\%\) số điểm): \(m=n \leq 1200\)

Example

2 5
1 2 3 4 5
3 3 4 2 1 

2 4 5
3 1 2 3