Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2019 - Tin học - Khối 11

Long và Vân cùng nhau chơi trò chơi trên dãy số như sau: Long sẽ chọn một dãy gồm \(n\) số \(a_1, a_2,\dots , a_n\). Sau đó, Vân sẽ tìm cách biến đổi dãy số nguyên \(a_1, a_2,\dots , a_n\) về dãy đẹp bậc \(d\) bằng dãy các bước biến đổi như sau: Mỗi bước, chọn một số trong dãy, tăng hoặc giảm số đó đi một đơn vị. Một dãy \(b_1, b_2,\dots , b_n\) được gọi là dãy đẹp bậc \(d\) nếu \(b_i = b_{i−1} + d\) với \(i = 2, 3,\dots , n\). Cụ thể, dãy \(b_1, b_2 = b_1 + d, … , b_n = b_{n−1} + d\) là dãy đẹp bậc \(d\).

Ví dụ, dãy (\(3, 2, 2\)) với \(d = 1\) mất ít nhất \(3\) phép biến đổi để đưa về dãy (\(1, 2, 3\)) là một dãy đẹp bậc \(1\).

Yêu cầu: Cho dãy số nguyên \(a_1, a_2,\dots , a_n\) và số nguyên dương \(d\), hãy tính số bước ít nhất cần dùng để biến đổi dãy \(a_1, a_2,\dots , a_n\) thành một dãy đẹp bậc \(d\).

Input

• Dòng đầu chứa số nguyên \(n\) (\(n \leq 1000\)) và \(d\);
• Dòng thứ hai chứa \(n\) số nguyên mô tả dãy \(a_1, a_2,\dots , a_𝑛\).

Output

• Một dòng, chứa một số nguyên là số bước ít nhất cần dùng để biến đổi dãy \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) thành một dãy đẹp bậc \(𝑑\).

Scoring

• Subtask #1 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^3\)
• Subtask #2 (\(25\%\) số điểm): \(d = 0\) và \(|a_i| \leq 10^9\)
• Subtask #3 (\(25\%\) số điểm): \(d = 1\) và \(|a_i| \leq 10^3\)
• Subtask #4 (\(25\%\) số điểm): \(d \leq 10^9\) và \(|a_i| \leq 10^9\)

Example

3 1 
3 2 2

3

Nguồn: 2019 chính thức

Một lớp học có \(𝑛\) học sinh, các học sinh được đánh số hiệu từ 1 đến \(𝑛\). Thầy chủ nhiệm muốn tổ chức một trò chơi, trò chơi đòi hỏi các thành viên tham gia phải rất hiểu nhau. Là một giáo viên có nhiều năm kinh nghiệm và rất sâu sắc với học sinh, nên thầy biết hai học sinh \(𝑖\) và \(𝑗\) bất kỳ có hiểu nhau hay không (học sinh \(𝑖\) hiểu học sinh \(𝑗\) thì học sinh \(𝑗\) cũng hiểu học sinh \(𝑖\)). Với ba số nguyên \(𝑎, 𝑏, 𝑘,\) nhóm học sinh mà thầy giáo muốn chọn để tham gia trò chơi sẽ thỏa mãn các yêu cầu sau:

• Các học sinh có thể được chọn là học sinh có số hiệu từ \(𝑎\) đến \(𝑏\);
• Mỗi học sinh trong nhóm sẽ có ít nhất \(𝑘\) học sinh trong nhóm hiểu mình;
• Số lượng học sinh trong nhóm được chọn là nhiều nhất.

Yêu cầu: Cho mối quan hệ hiểu nhau của tất cả các học sinh trong lớp và \(𝑇\) bộ ba số nguyên \(𝑎_𝑠, 𝑏_𝑠, 𝑘_𝑠\ (𝑠 = 1,2, … , 𝑇)\), với mỗi bộ ba hãy giúp thầy giáo chọn nhóm thỏa mãn yêu cầu.

Input

• Dòng đầu chứa hai số nguyên \(𝑛, 𝑚\);
• \(𝑚\) dòng sau, mỗi dòng chứa 2 số nguyên \(𝑖,𝑗\ (𝑖 ≠ 𝑗)\) cho biết học sinh \(𝑖\) và \(𝑗\) hiểu nhau;
• Dòng tiếp theo chứa số nguyên \(𝑇\) là số bộ ba;
• Dòng thứ \(𝑠\) trong \(𝑇\) dòng tiếp theo chứa ba số \(𝑎_𝑠, 𝑏_𝑠, 𝑘_𝑠\ (1 \le 𝑎_𝑠 \le 𝑏_𝑠 \le 𝑛; 𝑠 = 1,2, … , 𝑇)\).

Output

• Gồm \(𝑇\) dòng, dòng thứ \(𝑠\) ghi một số nguyên là số lượng học sinh trong nhóm chọn được tương ứng với bộ ba thứ \(𝑠\).

Scoring

• Subtask #1 (\(30\%\) số điểm): \(𝑛 \leq 20; 𝑚 \leq 100; 𝑇 = 1\)
• Subtask #2 (\(30\%\) số điểm): \(𝑛 \leq 10^4; 𝑚 \leq 10^5; 𝑘 = 1; 𝑇 \leq 3\)
• Subtask #3 (\(30\%\) số điểm): \(𝑛 \leq 10^4; 𝑚 \leq 10^5; 𝑇 = 1;\)
• Subtask #4 (\(10\%\) số điểm): \(𝑛 \leq 10^5; 𝑚 \leq 10^5; 𝑇 \leq 300.\)

Example

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

3
0

Nguồn: 2019 chính thức

Công ty Long Vân giới thiệu siêu máy tính có khả năng thực hiện được tỉ tỉ phép toán trong vòng một giây. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện một số lượng rất lớn các thao tác như sau:

• Ban đầu, dãy \(𝑆\) không có phần tử nào;
• Có \(𝑡\) thao tác, thao tác thứ \(𝑖\ (𝑖 = 1,2, … ,𝑡)\) thuộc một trong các loại:
  • 1- Thêm vào dãy \(𝑆\) một phần tử mới \(𝑥_𝑖\);
  • 2- Tính tổng các phần tử của dãy \(𝑆\) hiện tại có giá trị nằm trong đoạn \([𝑎_𝑖, 𝑏_𝑖]\);
  • 3- Sắp xếp dãy 𝑆 hiện tại theo thứ tự không giảm rồi tính tổng tất cả các phần tử có thứ tự từ \(𝑝_𝑖\) đến \(𝑞_𝑖\) (\(1 ≤ 𝑝_𝑖 ≤ 𝑞_𝑖 ≤ |𝑆|\), trong đó \(|𝑆|\) là số lượng phần tử của dãy \(𝑆\) hiện tại). Sau đó, chèn vào dãy \(𝑆\) hai phần tử, một phần tử có giá trị bằng phần tử có thứ tự \(𝑝_𝑖\) cộng với \(1\) và phần tử có giá trị bằng phần tử có thứ tự \(𝑞_𝑖\) trừ đi \(1\).

Công ty sẽ trao thưởng cho người nào kiểm chứng được kết quả mà siêu máy tính đưa ra. Bạn được cho dãy gồm \(𝑡\) thao tác, với mỗi thao tác loại \(2\) và \(3\) hãy đưa câu trả lời tương ứng.

Input

• Dòng đầu chứa số nguyên dương \(𝑡\);
• Dòng thứ \(𝑖\) trong \(𝑡\) dòng tiếp theo mô tả thao tác thứ \(𝑖\) là một trong ba loại thao tác theo khuôn dạng: Bắt đầu số \(𝑘_𝑖\) (\(𝑘_i\) bằng \(1\) hoặc \(2\) hoặc \(3\)).
  • Nếu là thao tác loại \(1\) thì tiếp theo là một số nguyên \(𝑥_𝑖\) (\(−10^9 ≤ 𝑥_𝑖 ≤ 10^9\)),
  • Nếu là thao tác loại \(2\) thì tiếp theo là hai số nguyên \(𝑎_𝑖, 𝑏_𝑖\) (\(−10^9 ≤ 𝑎_𝑖 ≤ 𝑏_𝑖 ≤ 10^9\)),
  • Nếu là thao tác loại \(3\) thì tiếp theo là hai số nguyên dương \(𝑝_𝑖, 𝑞_𝑖\) (\(1 ≤ 𝑝_𝑖 ≤ 𝑞_𝑖 ≤ |𝑆|\)).

Output

• Gồm một số dòng, mỗi dòng chứa một số lần lượt là các câu trả lời cho các thao tác loại \(2, 3\) theo thứ tự xuất hiện ở dữ liệu vào.

Scoring

• Subtask #1 (\(40\%\) số điểm): \(𝑡\leq 10^3\)
• Subtask #2 (\(40\%\) số điểm): \(𝑡\leq 10^5\) và không có thao tác loại 3
• Subtask #3 (\(20\%\) số điểm): \(𝑡\le 10^5\).

Example

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

3
5
10

S = ()
S = (5)
S = (5,3)
S = (5,3,1)
Đưa ra 3
S = (5,3,1,2)
S = (1,2,3,5), đưa ra 5, S = (1,2,3,5,3,2)
Đưa ra 10

Nguồn: 2019 chính thức