Đề thi chọn ĐT HSG QG Đà Nẵng 2022 - Ngày 2

Hệ thống mạng trên hành tinh XYZ gồm \(n\) nút mạng và \(m\) dây cáp, mỗi dây cáp nối hai nút mạng và cho phép truyền tin theo cả hai chiều. Không có hai dây cáp nào nối cùng một cặp nút, và không có dây cáp nào nối một nút với chính nó. Hệ thống đảm bảo việc truyền tin giữa hai nút bất kỳ (trực tiếp hoặc qua một số nút trung gian), đây gọi là tính liên thông của mạng. Tuy nhiên nếu một dây cáp bị hỏng, mạng có thể không còn tính liên thông nữa. Để khắc phục điều này, ban quản lý sẽ thêm vào một số dây cáp, sao cho sau khi thêm thì việc một dây cáp bất kỳ bị hỏng cũng không làm mất tính liên thông của mạng, đồng thời số dây cáp cần thêm vào là nhỏ nhất có thể. Hãy giúp ban quản lý tính số dây cáp ít nhất cần thêm để mạng đảm bảo được tính liên thông ngay cả khi có một dây cáp bất kỳ bị hỏng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_i, v_i\) cho biết có một dây cáp nối giữa \(u_i\) và \(v_i\).

Output

• Ghi một số nguyên duy nhất là số dây cáp cần thêm.

Example

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

1

3 3
1 2
2 3
3 1

0

Scoring

• Có \(32\%\) số test với \(m = n-1\).
• Có \(32\%\) số test với \(n, m \le 1000\).
• Có \(36\%\) số test với \(n, m \le 10^5\).

Nguồn: Bài 1 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Trọng số của một số tự nhiên \(x\) được tính bằng cách biểu diễn \(x\) dưới dạng hệ cơ số 10 và tính tổng tất cả các số sinh ra từ các đoạn con của \(x\). Ví dụ trọng số của \(10034\) là \(1+10+100+1003+10034+0+00+003+0034+0+03+034+3+34+4=11263\). Hoài đang nghiên cứu các tính chất đặc biệt của số. Cô liệt kê tất cả các số nguyên dương có \(n\) chữ số, các chữ số đều bé hơn hoặc bằng 7 và không có số 0 đứng đầu. Cô muốn biết trong các số vừa liệt kê, có bao nhiêu bộ ba số (\(x,y,z\)) thoả mãn \(x<y<z\) và tổng trọng số của \(x,y,z\) chia hết cho \(k\).

Input

• Gồm hai số nguyên dương \(n, k\).

Output

• Ghi một số nguyên duy nhất là số bộ ba tìm được, chỉ cần in ra kết quả sau khi chia lấy dư cho \(10^9+7\).

Example

1 10

4

2 100

273

Scoring

• Có \(8\%\) test với \(n\le 6; k\le 10\).
• Có \(20\%\) test với \(n\le 9; k\le 100\).
• Có \(28\%\) test với \(n\le 100; k\le 100\).
• Có \(44\%\) test với \(n\le 1000; k\le 1000\).

Cho một tập các hình chữ nhật và một điểm \(A\). Cần kẻ một số đường thẳng qua \(A\) sao cho mỗi hình chữ nhật đều có điểm chung với ít nhất một đường thẳng đã kẻ, và số đường thẳng cần kẻ là ít nhất có thể. Lưu ý là đường thẳng được phép kéo dài tới vô tận theo cả hai hướng.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, x, y\) với \(n\) là số lượng hình chữ nhật và \((x, y)\) là toạ độ điểm \(A\).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa \(l_i, d_i, r_i, u_i\) mô tả hình chữ nhật thứ \(i\), với toạ độ của góc trái dưới là \((l_i, d_i)\) và góc phải trên là \((r_i, u_i)\) (\(l_i < r_i; d_i < u_i\)).

Output

• Ghi số đường thẳng cần kẻ.

Scoring

• Trong tất cả các test: \(n \le 10^5; 0 \le x, y, l_i, d_i, r_i, u_i \le 10^9\).
• Có \(16\%\) số test với \(n \le 20\).
• Có \(20\%\) số test với \(n \le 1000\) và \(y = 10^9; d_i = 0, u_i = 1\) với mọi \(i\).
• Có \(28\%\) số test với \(y = 10^9; d_i = 0, u_i = 1\) với mọi \(i\).
• Có \(36\%\) số test với ràng buộc gốc.

Example

3 4 4
2 1 5 2
5 3 8 4
1 6 3 9

2

(Nguồn: Bài 3 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023)