Chọn ĐTQG Đà Nẵng 2023

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Chiến đấu

Cuội là một dũng sĩ lành nghề. Trong thế giới mà Cuội sinh sống, có tồn tại $k$ kĩ năng chiến đấu khác nhau được đánh số từ 1 đến $k$ . Ban đầu, Cuội đã thành thạo 4 kĩ năng khác nhau, đó là $s 1,s 2,s 3$ và $s 4$ .

Cuội lên kế hoạch tấn công một lâu đài chứa chấp các tên tội phạm. May mắn thay, Cuội đã có được thông tin về kiến trúc của lâu đài. Lâu đài bao gồm $n$ phòng được đánh số từ 1 đến $n$ . Nếu Cuội hiện đang ở phòng thứ $x$ , thì Cuội chỉ có thể ghé thăm phòng $x+1$ , nhưng không thể quay lại phòng $x-1$ .

Có 2 loại phòng là phòng chiến đấu và phòng thư viện. Phòng $x$ có một trong các thông tin sau:

$1 a$ : phòng $x$ là phòng chiến đấu. Trong căn phòng này có một tên tội phạm mà Cuội có thể chiến đấu. Tên này làm chủ kĩ năng $a$ . Cuội cũng có thể chọn không chiến đấu với tên tội phạm này và ngay lập tức chuyển sang căn phòng tiếp theo.

$2$ : phòng $x$ là một thư viện. Trong căn phòng này, Cuội có thể học cách sử dụng một trong những kĩ năng chiến đấu mới, nhưng anh phải quên một kĩ năng mà hiện anh đang làm chủ. Cuội cũng có thể chọn không học gì cả và ngay lập tức chuyển sang phòng tiếp theo.

Khả năng đánh bại tội phạm của Cuội được thể hiện bằng ma trận $M$ . Ma trận $M$ có kích thước là $ktimesk$ , trong đó mỗi phần tử có thể là $0$ hoặc $1$ . Các hàng và cột của $M$ được đánh số từ $1$ đến $k$ . Nếu Cuội thành thạo kĩ năng chiến đấu $i$ , thì Cuội có thể đánh bại những tên tội phạm làm chủ kĩ năng chiến đấu $j$ nếu và chỉ nếu khi hàng $i$ và cột $j$ của ma trận $M$ là $1$ .

Trước khi tấn công lâu đài, Cuội xin lời khuyên của bạn để có thể đánh bại càng nhiều tên tội phạm càng tốt. Hãy giúp Cuội đếm số lượng tội phạm tối đa mà anh ta có thể đánh bại!

Input

Dòng đầu tiên chứa hai số nguyên $n,k$ $(1len \leq 2 \cdot 105, 4 \leq k \leq 20)$

Dòng hai chứa bốn số $s 1,s 2,s 3,s 4$ ( $1les 1,s 2,s 3,s 4 lek$ )

$k$ dòng tiếp theo, mỗi dòng chứa xâu $k$ kí tự $0$ hoặc $1$ mô tả ma trận $M$

Tiếp theo là $n$ dòng mô tả các phòng trong lâu đài, mỗi dòng theo một trong hai loại sau: $1 a$ : nếu là phòng chiến đấu ( $1 \leq a \leq k$ ) $2$ : nếu là phòng thư viện. Có tối đa 100 phòng là thư viện.

Output

Đưa ra số tên tội phạm tối đa bị đánh bại.

Subtasks

$15%$ số test không có phòng nào là thư viện

$15%$ số test có số lượng phòng là thư viện $\leq 3$

$15%$ số test có $k=5$

$15%$ số test có $n \leq 1000,k \leq 10$

$15%$ số test có $n \leq 1000$

$15%$ số test có $k \leq 10$

$10%$ số test còn lại không có ràng buộc gì thêm.

Sample Input

Sample Output

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Tổ kiến

Các nhà khoa học đang nghiên cứu về tổ kiển, họ mô phỏng tổ kiến trên một lưới ô vuông n $\times$ m bao gồm $k$ ô $(x i,y i)$ . Các ô này có cấu trúc theo dạng cây, hai ô kề cạnh có thể di chuyển qua nhau, hai ô bất kì có thể di chuyển qua lại lẫn nhau thông qua một đường đi duy nhất không lặp lại các ô. Bây giờ các nhà khoa học quan tâm đến việc nếu xét một hình chữ nhật $(x 1,y 1,x 2,y 2)$ và xem xét các ô thuộc tổ kiến nằm trong hình chữ nhật này thì sẽ có bao nhiêu thành phần liên thông. Các nhà khoa học sẽ xem xét nhiều kịch bản là các hình chữ nhật khác nhau.

Yêu cầu : cho dữ liệu về tổ kiến và $q$ truy vấn, mỗi truy vấn là một hình chữ nhật, hãy đếm số thành phần liên thông trong hình chữ nhật đó.

Input

Dòng đầu chứa hai số nguyên $n,m$ ( $1len,m \leq 2 \cdot 105$ )

Dòng thứ hai chứa số nguyên $k,q$ ( $2lek \leq 2 \cdot 105,1 \leq \leq 2 \cdot 105$ ).

$k-1$ dòng tiếp theo, mỗi dòng chứa $f i,x i,y i$ mô tả ô ( $x i,y i$ ) thuộc tổ kiến kết nối với ô ( $x i +1,y i$ ) nếu $f i = h$ , hoặc kết nối với ô $(x i,y i +1)$ nếu $f i =v$ ( $1lex i len,1ley i lem$ ). Dữ liệu đảm bảo các ô này tạo thành một cây.

$q$ dòng tiếp theo mỗi dòng chứa bốn số $x 1,y 1,x 2,y 2$ ( $1lex 1 lex 2 len,1ley 1 ley 2 lem$ ). Các ô ( $x,y$ ) được coi là nằm trong hình chữ nhật thỏa mãn $x 1 lexlex 2,y 1 leyley 2$ .

Output

Ghi ra $q$ dòng là kết quả của mỗi truy vấn.

Subtask

$20 %$ số test có $n,m,k,q \leq 100$

$20 %$ số test có $n,m,k,q \leq 3000$

$30 %$ số test có $n,m \leq 3000,k,q \leq 105$

$30 %$ số test còn lại không có ràng buộc gì thêm.

Sample Input

Sample Output

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Đường đi ngắn nhất

Cảnh sát đang cần sự giúp đỡ của bạn trong việc tìm kiếm nơi trú ở của một tên tội phạm, kẻ đang ẩn náu ở đâu đó trong thành phố gồm n địa điểm khác nhau, được đánh số từ 1 đến $n$ , và có $m$ đường hai chiều kết nối hai địa điểm khác nhau.

Thông tin từ các người dân trong thành phố, cảnh sát biết được tên tội phạm đã di chuyển từ một địa điểm $x$ nào đó để đến nơi trú ẩn $y$ nào đó. Và các nhân chứng có trông thấy hắn xuất hiện ở $k$ địa điểm $u 1,u 2, \dots,u k$ trên đường đi từ $x$ đến $y$ theo thứ tự nào đó mà cảnh sát chưa xác định. Lưu ý rằng tên tội phạm có thể di chuyển từ $x$ đến $y$ thông qua các địa điểm khác không có trong $k$ địa điểm mà các nhân chứng trông thấy. Tuy nhiên, cảnh sát đã phân tích đặc điểm của tên tội phạm này và biết rằng hắn sẽ luôn di chuyển theo đường đi ngắn nhất giữa hai địa điểm $x$ và $y$ .

Nhiệm vụ của bạn là tìm các địa điểm có thể là $y$ để giúp cảnh sát có thể nhanh chóng tìm được hắn. Tất nhiên, có thể lời khai của các nhân chứng không đồng nhất dẫn đến không tìm thấy một địa điểm $y$ nào thỏa mãn.

Input

Dòng đầu chứa số nguyên $n,m,k$ ( $1leklen \leq 2 \cdot 105,1lem \leq 2 \cdot 105$ )

Dòng thứ hai chứa $k$ số nguyên $u i$ mô tả những địa điểm tên tội phạm đi qua $(1leu i len)$

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a,b,c$ mô tả có đường nối trực tiếp giữa hai địa điểm $a$ và $b$ có độ dài là $c$ $(1leaneblen,1lec \leq 109)$

Output

Dòng đầu ghi ra số $p$ là số địa điểm có thể là $y$

Dòng thứ hai ghi ra $p$ số nguyên là những địa điểm có thể là $y$ theo thứ tự tăng dần.

Subtasks

$15 %$ số test có $m=n-1$ , và mỗi địa điểm được kết nối trực tiếp với tối đa 2 địa điểm khác.

$15 %$ số test có $m=n-1$

$15 %$ số test có $n,m \leq 100$

$15 %$ số test có $n,m \leq 1000$

$20 %$ số test có $k \leq 5$

$20 %$ số test còn lại không có ràng buộc gì thêm

Sample Input

Sample Output

4
1 2 4 5

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. NUM19

Cho hai số nguyên dương $L,R$ . Hãy đếm xem có bao nhiêu số nguyên dương $x$ thuộc đoạn [ $L,R$ ] chia hết cho $19$ ; sao cho ở dạng biểu diễn thập phân, $x$ không chứa hai chữ số nào có tổng chia hết cho $3$ .

Input

Dòng đầu chứa số nguyên dương $T$ là số lượng testcase ( $1 \leq T \leq 105$ );

Mỗi test được mô tả trên hai dòng là $L$ và $R$ ( $1 \leq L \leq R \leq 1010000$ ).

Output

Với mỗi testcase, ghi trên một dòng số lượng số nguyên dương $x$ tìm được, sau khi chia lấy dư cho $1000000007$

Subtasks

Có $50 %$ số test với $R \leq 106$ ;

Có $30%$ số test với tổng độ dài của tất cả các số $R$ trong $T$ testcase không vượt quá $103$ ;

Có $20 %$ số test với ràng buộc gốc.

Sample Input

2
1 100
101 200

Sample Output

4
2

Giải thích

Các số thỏa mãn testcase 1 là: $19, 38, 76, 95$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Xếp hình

Xếp hình là một trong những trò kinh điển thời tuổi thơ dữ dội của chúng ta. Trò chơi gồm một bảng $3 \times 3$ chứa 8 miếng ghép và một ô trống. Người chơi cố gắng sắp xếp lại các miếng ghép thành một thứ tự định sẵn, bằng cách lặp lại việc di chuyển một trong các miếng ghép kề cạnh với ô trống vào ô trống (và dĩ nhiên ô trống sẽ chuyển sang vị trí của miếng ghép). Để đơn giản, các miếng ghép được đánh số từ 1 đến 8 và thứ tự định sẵn được cho trong hình sau:

Ở phiên bản khó của trò chơi, bạn cần tìm số bước di chuyển ít nhất để đưa trạng thái đã cho về trạng thái định sẵn. Hùng đã chơi trò này nhiều lần nhưng vẫn gặp vấn đề với phiên bản khó, và có vẻ bài tập này được thiết kế để dành riêng cho cậu.

Input

Dòng đầu chứa số nguyên dương $T$ là số lượng testcase;

$T$ dòng tiếp theo mỗi dòng chứa 9 số nguyên là một hoán vị của $0, 1, 2, . . . , 8$ mô tả một trạng thái bắt đầu. Các số trong hoán vị lần lượt là các số ghi trên các ô của bảng, theo thứ tự từ trái sang phải, từ trên xuống dưới. Số 0 đại diện cho ô trống.

Output;

Gồm $T$ dòng, mỗi dòng ghi một số nguyên là số bước di chuyển ít nhất, hoặc -1 nếu không thể đưa trạng thái này về trạng thái định sẵn.

Subtasks

Trong tất cả các test: $T \leq 106$ ;

$30 %$ test với $T = 5$ và kết quả không vượt quá 10;

$30 %$ test tiếp theo có kết quả không vượt quá 10;

$40 %$ test tiếp theo với ràng buộc gốc.

Sample Input

4 
0 1 2 3 4 5 6 7 8 
3 1 2 0 4 5 6 7 8 
1 2 3 4 5 6 7 8 0 
2 3 0 4 1 5 8 6 7

Sample Output

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. CAPITAL

Vương quốc có $n$ thành phố và $n-1$ con đường hai chiều, đảm bảo đi lại giữa mọi cặp thành phố. Thành phố x được gọi là quản lý $y$ nếu $x$ nằm trên đường đi đơn từ $y$ đến 1. Sản lượng lương thực tại thành phố $x$ là $w x$ . Quốc vương muốn chọn ra một đỉnh để xây dựng kho dự trữ, chi phí vận chuyển lương thực nếu xây dựng kho dự trữ tại $u$ là $\sum v=1 n {w v timesd(v,u)}$ với $d(v,u)$ là số cạnh trên đường đi đơn từ $v$ đến $u$ .

Có $Q$ thay đổi cho sản lượng được báo cáo, mỗi thay đổi có dạng $1 u c$ hoặc $2 u c$ tương ứng là tăng $w u$ lên $c$ đơn vị hoặc tăng $w v$ lên $c$ đơn vị với mọi $v$ quản lý bởi $u$ . Sau mỗi thay đổi, cần tìm đỉnh $u$ để xây dựng kho dữ trữ sao cho tổng chi phí vận chuyển lương thực là nhỏ nhất, nếu có nhiều $u$ như vậy thì chọn $u$ nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên dương $n$ và $Q$ ;

Dòng thứ hai chứa $n$ số $w 1,w 2,...,w n$ ;

Mỗi dòng trong số $n - 1$ dòng tiếp theo chứa hai số $u v$ mô tả một cạnh của cây;

Mỗi dòng trong số $Q$ dòng tiếp theo chứa ba số $t u c$ mô tả một thay đổi

Output

Ghi $Q$ dòng là chỉ số của đỉnh được chọn sau thay đổi thứ $Q$ .

Subtasks

Trong tất cả các test: $n,Q \leq 105; 1 \leq w i \leq 106; |c| \leq 106 .$

Có $12 %$ số test với $n,Q \leq 5000$ ;

Có $16 %$ số test có cạnh nối từ $x$ đến $x - 1$ với mọi $2 \leq x \leq n;$

Có $16 %$ số test có cạnh nối từ $x$ đến $[x/2]$ với mọi $2 \leq x \leq n;$

Có $20 %$ số test không có thay đổi loại 2;

Có $36 %$ số test với ràng buộc gốc.

\Needspace{20\baselineskip}

Sample Input

Sample Output

2 
2 
1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: Lời giải phụ thuộc cách hiểu đề; cần đối chiếu nguồn.

Cấu trúc đề và tiến độ