Phần 1. Đề cơ bản

Link chấm bài

https://chuyentinpbc.ucode.vn/contests/de-co-ban-so-6-52350

Bài 1. Chó và thỏ

Trong giờ toán, Long lại được các bạn trong lớp đố bài toán sau: Một con chó đuổi một con thỏ cách nó D mét. Một bước nhảy của chó dài X mét, một bước nhảy của thỏ dài Y mét và khi chó nhảy một bước thì thỏ củng nhảy một bước. Hỏi chó phải nhảy ít nhất bao nhiêu bước mới đuổi kịp hoặc vượt qua được thỏ (số bước nhảy phải là số nguyên và hai con chạy cùng chiều). 

Dữ liệu: Vào từ file BAI1.INP gồm 1 dòng là 3 số nguyên dương D, X, Y (Y < X < D ≤ 10⁹); 

Kết quả: Ghi ra file BAI1.OUT một số nguyên là kết quả của bài toán.

Bài 2. Dãy số

Hôm nay, các bạn nhỏ ABC Smart lại được Thầy giáo đố một bài toán sau: Cho một dãy số nguyên a₁, a₂,..., a_n. Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là a_i ≤ a_i+1 với mọi 1 ≤ i < n. Ta định nghĩa độ đẹp của dãy a là khoảng cách lớn nhất giữa hai phần tử liên tiếp bất kì trong dãy. Nói cách khác, độ đẹp của dãy a là giá trị a_i – a_i-1 lớn nhất với mọi 2 ≤ i ≤ n. 

Yêu cầu: Hãy xoá một phần tử bất kì trong dãy a sao cho độ đẹp của dãy nhận được là lớn nhất có thể.

Dữ liệu: Vào từ file BAI2.INP gồm: 

+ Dòng đầu tiên là số nguyên dương n (3 ≤ n ≤ 10⁶);

+ Dòng thứ hai chứa n số nguyên a₁, a₂,..., a_n (|a_i| ≤ 2.10⁹).

Kết quả: Ghi ra file BAI2.OUT một số nguyên là độ đẹp của dãy sau khi đã xoá 1 phần tử.

Ràng buộc:

+ Có 50% số điểm có n ≤ 10⁴ và a_i ≤ 10⁹;

+ Có 50% số điểm là các trường hợp còn lại.

Bài 3. Phép chia

Long là một học sinh chuyên Toán nhưng lại rất đam mê lập trình. Trong một lần Long được học về phép chia có dư đối với các số tự nhiên như sau: Nếu số tự nhiên N chia X dư R thì số N sẽ được biểu diễn thành dạng sau: N = K*X + R. Tình cờ được biết sắp tới ở trường chuyên PBC có tổ chức thi khảo sát chất lượng học sinh giỏi cấp 2, nên Long có bài toán đố các bạn như sau: Cho một số tự nhiên N. Tìm số tự nhiên X < N sao cho kết quả của phép chia lấy dư N cho X là lớn nhất. Vì các bạn lập trình nên sẽ trả lời rất nhanh nên Long sẽ đưa ra T câu hỏi liên tục để các bạn trả lời.

Dữ liệu: Vào từ file BAI3.INP gồm

1. + Dòng đầu tiên chứa số nguyên dương T là số lượng câu hỏi mà Long đưa ra ( T ≤ 10⁵);
2. + T dòng tiếp theo, mỗi dòng chứa một số nguyên N là một câu hỏi của Long (5 ≤ N ≤ 10¹⁸).

Kết quả: Ghi ra file BAI3.OUT gồm T dòng là các đáp án tương ứng.

Ràng buộc:

1. + Có 20% số điểm tương ứng với T ≤ 10³ và N ≤ 10⁴;
2. + Có 80% số điểm còn lại không có ràng buộc gì thêm.

Bài 4. Xâu con

Hôm nay Long lại được học về xâu. Người ta định nghĩa một xâu đẹp là xâu chỉ chứa các ký tự là chữ cái nguyên âm. Theo quy ước thì các chữ cái là nguyên âm: ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ . Long liền nghĩ ra một bài toán để đố các bạn như sau: Cho xâu ST chỉ gồm các chữ cái in thường từ ‘a’ đến ‘z’. Tìm độ dài lớn nhất xâu con của xâu ST trên là xâu đẹp. Ta định nghĩa xâu con của xâu ST là xâu có các ký tự ở vị trí liên tiếp trong xâu ST và độ dài của một xâu là số ký tự của xâu đó.

Dữ liệu: Vào từ file BAI4.INP gồm:

+ Dòng đầu tiên là số nguyên dương n, n là độ dài xâu ST (1 <= n <= 10⁵);

+ Dòng thứ hai là xâu ST.

Kết quả: Ghi ra file BAI4.OUT một số nguyên là kết quả của bài toán. Nếu không có xâu con nào thoả mãn thì ghi ra số -1.

Ràng buộc:

1. + Có 20% số điểm tương ứng với  n <= 100;

+ Có 80% số điểm còn lại không có ràng buộc gì thêm.

Phần 2. Đề nâng cao

link chấm bài

https://chuyentinpbc.ucode.vn/contests/de-nang-cao-so-6-52357

1. ĐẾM ĐOẠN

Cho một xâu kí tự S  chỉ gồm số 0 và 1. 

Các kí tự được đánh số thứ tự từ 1 đến n (với n là độ dài xâu). 

Ta có một số khái niệm sau:

• Xâu X được gọi là một đoạn con của S nếu X là một dãy các kí tự liên tiếp thuộc S. 
• Hai đoạn con X và Y của S được gọi là khác nhau nếu có ít nhất một kí tự thuộc X mà không thuộc Y hoặc ngược lại.

Yêu cầu: Hãy chỉ ra 2 đoạn con khác nhau của S sao cho: 

• Chúng có độ dài bằng nhau.
• Độ dài của mỗi đoạn là dài nhất có thể
• Số lượng số 1 của hai đoạn con là bằng nhau.

Dữ liệu: Vào từ file văn bản SSTRING.INP 

gồm một dòng duy nhất chứa xâu S có độ dài n(3<n<10^6).

Kết quả: Ghi ra file văn bản SSTRING.OUT gồm 4 số nguyên l1, h1, l2, h2 tương ứng là chỉ số bắt đầu và kết thúc của hai đoạn con cần tìm thỏa mãn các điều kiện của đề bài.

Nếu tồn tại nhiều hơn 1 đáp án hãy in ra một cặp bất kì. Dữ liệu đảm bảo bài toán luôn có đáp số.

Ví dụ:

Bộ test chia làm 2 subtasks

Subtask 1 (50% số điểm):n<1000

Subtask 2 (50% số điểm): Không có ràng buộc bổ sung

2.Chia đội

Kì thi Hackathon CSP sắp tới, Ban tổ chức muốn chia các thí sinh thành các đội chơi theo nguyện vọng của chính các thí sinh. Biết rằng, có n thí sinh tham gia cuộc thi. Thí sinh thứ i mong muốn đội của mình không ít hơn ai người.

Để cuộc thi thêm nhiều gay cấn, Ban tổ chức mong muốn chia n thí sinh thành các đội sao cho:

• Mỗi thí sinh chỉ thuộc một đội.
• Số lượng thí sinh thuộc mỗi đội không nhỏ hơn nguyện vọng của từng thí sinh thuộc đội đó
• Số lượng đội là nhiều nhất có thể. Nếu có nhiều phương án chia thành nhiều đội nhất, hãy chọn cách chia để số thí sinh thuộc đội nhiều nhất là ít nhất có thể.

Yêu cầu: Biết nguyện vọng của từng thí sinh, hãy cho biết Ban tổ chức có thể chia các bạn thí sinh thành tối đa bao nhiêu đội. 

Dữ liệu: Vào từ file văn bản TEAMS.INP gồm:

• Dòng đầu ghi số nguyên dương n (1<n<10^6).
• Dòng tiếp theo ghi n số nguyên dương a1, a2,…,an (1<ai<n)  là nguyện vọng của từng thí sinh

Kết quả: Ghi ra file văn bản TEAMS.OUT gồm:

• Dòng đầu tiên ghi số nguyên dương k– số đội lớn nhất có thể chia được thỏa mãn nguyện vọng của tất cả các thí sinh
• k dòng tiếp theo, mỗi dòng gồm cấu trúc ti i1, i2, ….iti: trong đó ti là số lượng thí sinh thuộc đội thứ i, ti số sau là chỉ số của các thí sinh thuộc đội thứ i

Ví dụ:

Bộ test chia làm 2 subtasks

Subtask 1 (50% số điểm):n<5000

Subtask 2 (50% số điểm): Không có ràng buộc bổ sung

Bài 3. Miền lớn nhất

Cho đồ thị vô hướng G gồm n đỉnh đánh số từ 1 tới n và m cạnh đánh số từ 1 tới m. 

Cạnh thứ i nối giữa hai đỉnh ui, vi. Mỗi đỉnh được tô một trong n màu đánh số từ 1 tới n

Ta gọi tập đỉnh S là một miền nếu nó thỏa mãn hai điều kiện:

• Các đỉnh thuộc S phải cùng màu
• Giữa hai đỉnh bất kỳ thuộc S có đường đi chỉ qua các đỉnh thuộc S

Bạn được phép đổi màu một đỉnh nếu muốn. Hãy tìm cách để thu được đồ thị có miền lớn nhất

 (tính theo số đỉnh), cho biết số đỉnh của miền lớn nhất đó.

Dữ liệu: Vào từ file văn bản RECOLOR.INP

• Dòng đầu tiên chứa số nguyên dương T<10 là số test
• T nhóm dòng tiếp theo mỗi nhóm dòng chứa dữ liệu một test theo khuôn dạng
  • Dòng 1 chứa hai số nguyên dương n<10^5; m<2.10^5
  • Dòng 2 chứa n số nguyên, số thứ i là màu của đỉnh i.
  • m dòng tiếp theo, dòng thứ j chứa hai số nguyên uj, vj ứng với một cạnh của đồ thị

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Kết quả: Ghi ra file văn bản RECOLOR.OUT một số nguyên duy nhất là số đỉnh của miền lớn nhất thu được.

Ví dụ

Bộ test chia làm 2 subtasks

Subtask 1 (50% số điểm): n<1000

Subtask 2 (50% số điểm): Không có ràng buộc bổ sung