Bạn cần Đăng nhập để nộp bài

Cho dãy \(n\) số nguyên, các phần tử trong dãy được đánh số thứ tự từ 1 đến \(n\). Dãy số được chia thành \(\frac{n}{k}\) đoạn, \(k\) là ước của \(n\), mỗi đoạn có \(k\) số theo quy luật:

- Đoạn thứ nhất có giá trị tăng dần từ 1 đến \(k\);

- Đoạn thứ hai có giá trị giảm dần từ \(2 \times k\) về \(k + 1\);

- Đoạn thứ ba có giá trị tăng dần từ \(2 \times k + 1\) đến \(3 \times k\);

- Đoạn thứ tư có giá trị giảm dần từ \(4 \times k\) về \(3 \times k + 1\);

…

- Đoạn thứ \(i\ (i \leq \frac{n}{k})\):

Nếu \(i\) lẻ: có giá trị tăng dần từ \((i - 1) \times k + 1\) đến \(i \times k\);

Nếu \(i\) chẵn: có giá trị giảm dần từ \(i \times k\) về \((i - 1) \times k + 1\);

Ví dụ với \(n = 24,\ k = 4\), dãy số nguyên có giá trị như sau:

1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13 17 18 19 20 24 23 22 21

Yêu cầu: Hãy tính tổng các số ở các vị trí từ \(l\) đến \(r\) trong dãy số đã cho.

Dữ liệu vào: Ghi 4 số nguyên \(n,\ k,\ l,\ r\) trên một dòng, trong đó \(k\) là ước của \(n\) \(\left( 1 \leq l \leq r \leq n \leq 10^{9} \right)\);

Kết quả: Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 50% số test tương ứng 50% số điểm có \(k = 1\ \)hoặc \(k = n\);

- Có \(30\%\ \)số test khác tương ứng \(30\%\) số điểm có \(n \leq 10^{6}\);

- Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Tại xứ sở thần tiên Alpha có \(n\) chú thỏ đang thu hoạch cà rốt. Chú thỏ thứ \(i\ (1 \leq i \leq n)\) bắt đầu thu hoạch ở vị trí \(x_{i}\) và thực hiện \(m_{i}\) bước nhảy, mỗi bước nhảy được đúng \(k_{i}\) đơn vị độ dài; chú thỏ thứ \(i\) có cách thu hoạch cà rốt như sau:

- Ở vị trí bắt đầu \(x_{i}\) thỏ thu hoạch được \(x_{i}\) củ cà rốt;

- Ở lần nhảy thứ nhất, thỏ thu hoạch được \(x_{i} + k_{i}\) củ cà rốt;

- Ở lần nhảy thứ \(t\ (2 \leq t \leq m_{i})\) số cà rốt thỏ thu hoạch được nhiều hơn \(k_{i}\) củ cà rốt so với lần nhảy thứ \(t - 1\).

Yêu cầu: Tính tổng số cà rốt sau khi \(n\) chú thỏ thu hoạch xong. Số lượng cà rốt thu hoạch có thể rất lớn nên chỉ cần đưa ra kết quả sau khi đã chia lấy phần dư cho \((10^{9} + 7)\).

Dữ liệu vào:

- Dòng đầu tiên chứa số nguyên dương \(n\ (1 \leq n \leq 10^{6})\);

- Trong \(n\) dòng tiếp theo, dòng thứ \(i\ (1 \leq i \leq n)\) chứa 3 số nguyên dương \(x_{i},m_{i},k_{i}\ (1 \leq x_{i},m_{i},k_{i} \leq 10^{9})\).

Kết quả:

- Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 60% test tương ứng 60% số điểm có \(n,x_{i},m_{i},k_{i} \leq 10^{3};1 \leq i \leq n\);

- Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Cho dãy \(A\) gồm \(n\) số nguyên dương \(a_{1},a_{2},\ldots,\ a_{n}\).

Yêu cầu: Hãy cho biết trong dãy \(A\) có bao nhiêu phần tử có số lượng ước nguyên dương là số lẻ?

Dữ liệu vào:

- Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^{6})\);

- Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ ({1 \leq a}_{i} \leq 10^{18};1 \leq i \leq n)\).

Kết quả:

- Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 50% test tương ứng với 50% số điểm có \(n \leq 10^{3},a_{i} \leq 10^{3}\);

- Có 30% test khác tương ứng với 30% số điểm có\(\ n \leq 10^{4},\ {\ a}_{i} \leq 10^{6}\);

- Có 20% test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Có \(n\) thẻ bài trên bàn, trên tấm thẻ thứ \(i\ (1 \leq i \leq n)\) ghi số \(a_{i}\). Mặt có ghi số của tấm thẻ được đặt úp xuống mặt bàn.

Có \(m\) học sinh lần lượt tham gia lật thẻ, mỗi học sinh được chọn hai tấm thẻ bất kỳ, sau đó để tấm thẻ có số nhỏ hơn lại trên bàn và mang tấm thẻ có số lớn hơn về, nếu hai tấm thẻ có số bằng nhau thì học sinh có thể chọn mang về một tấm thẻ bất kì trong hai tấm thẻ đó.

Yêu cầu: Gọi \(s\) là tổng các số trên thẻ mà các học sinh mang về. Hãy cho biết giá trị lớn nhất của \(s\) có thể là bao nhiêu?

Dữ liệu vào:

- Dòng đầu tiên chứa lần lượt hai số nguyên dương \(n,\ m\ (1 \leq m \leq n \leq 10^{5})\);

- Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{9};1 \leq i \leq n)\).

Kết quả:

Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Có 50% số test tương ứng 50% số điểm có \(m = 1\);

- Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Trên một con đường thẳng các vị trí được đánh số từ \(1\) tới \(n\), khoảng cách giữa hai vị trí liên tiếp là một đơn vị độ dài, có một con thỏ đang ở vị trí \(x_{1}\) và một củ cà rốt đang ở vị trí \(x_{2}\). Cà rốt luôn là món ăn yêu thích của thỏ nên nó muốn nhảy thật nhanh đến đó để lấp đầy chiếc bụng đói của mình. Tuy vậy, mỗi bước nhảy thỏ chỉ nhảy được tối đa \(a\) đơn vị độ dài.

Yêu cầu: Thỏ cần nhảy ít nhất bao nhiêu bước để tới vị trí của cà rốt?

Dữ liệu vào:

Chứa 3 số nguyên \(x_{1},\ x_{2}\) và \(a\) \((1 \leq x_{1} \leq x_{2} \leq 10^{12},\ 1 \leq a \leq 10^{3})\) trên một dòng.

Kết quả:

Ghi ra một số nguyên duy nhất cho biết kết quả bài toán.

Ràng buộc:

- Có 80% số test tương ứng 80% số điểm có \(x_{2} \leq 10^{6}\);

- Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

An được một người bạn tặng cho một xâu ký tự \(s\). Cậu muốn tìm một xâu con liên tiếp không rỗng của xâu \(s\) sao cho chênh lệnh giữa số lần ký tự xuất hiện nhiều nhất và số lần ký tự xuất hiện ít nhất ở trong xâu con là lớn nhất. Lưu ý rằng, ký tự xuất hiện ít nhất phải xuất hiện ít nhất một lần trong xâu con. Cụ thể, nếu xâu con chỉ có duy nhất một loại ký tự, thì ký tự xuất hiện nhiều nhất và ký tự xuất hiện ít nhất là một.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^{6}\)).

+ Dòng thứ hai chứa xâu ký tự \(s\) chỉ gồm các chữ cái Latin thường.

Kết quả:

+ Một số nguyên duy nhất là chênh lệch lớn nhất đạt được.

Ràng buộc:

+ Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thoả mãn: \(n \leq 10^{2}\);

+ \(40\%\) số test khác ứng với 4\(0\%\) số điểm của bài thoả mãn: \(n \leq 10^{5}\);

+ \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Một công ty gồm \(N\) nhân viên được đánh số từ \(1\) tới \(N\). Người thứ \(i\) có lương là \(a_{i}\). Tổng giám đốc của công ty được đánh số là \(1\), mỗi người từ \(2\) tới \(N\) có đúng một cấp trên trực tiếp của mình.

Nếu người \(i\) là cấp trên trực tiếp của người \(j\), ta nói người \(i\) là quản lý của người \(j\). Nếu người \(i\) quản lý người \(j\) và người \(j\) quản lý người \(k\), ta cũng có thể nói người \(i\) là quản lý của người \(k\). Không có trường hợp người \(A\) là quản lý người \(B\) và người \(B\) là quản lý người \(A\).

Công ty có chế độ lương thưởng rất đặc biệt, vậy nên chưa chắc người có cấp bậc quản lý cao đã có lương cao hơn những người cấp dưới.

Nói cách khác, công ty này có mô hình dưới dạng một đồ thị cây gồm \(N\) đỉnh với gốc là đỉnh \(1\).

Công ty muốn tổ chức team building, tuy nhiên, nếu hai người \(u\) và \(v\) tham gia mà \(u\) là quản lý của \(v\) và \(a_{u} \leq a_{v}\) thì sẽ gây ra bất hòa (lương quản lý không cao hơn lương cấp dưới). Công ty muốn chọn ra được nhiều người tham gia team building nhất mà không có sự bất hòa nào.

8

4

2

1

7

3

Phòng tổ chức sự kiện đã lên \(Q\) giả định có dạng như sau:

• Xét người \(u\ (1\ \leq \ u\ \leq \ N)\), sẽ cần chọn ra các nhân viên thuộc quyền quản lý của \(u\) (tính cả \(u\)) để tham gia team building.

• Tìm cách chọn ra nhiều nhân viên nhất (có thể không chọn \(u\)) sao cho không gây ra sự bất hòa nào.

Yêu cầu: Với mỗi giả định, in ra số nhân viên nhiều nhất có thể chọn để tham gia team building.

Dữ liệu vào: từ tệp văn bản CONGTY.INP

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\ \left( 1\ \leq \ n,q\ \leq \ 2\ \times 10^{5} \right)\).

• Dòng thứ hai gồm \(N\) số nguyên dương, số thứ \(i\) là \(a_{i}\) miêu tả mức lương của người thứ \(i\) \(\left( 1\ \leq a_{i} \leq 10^{9} \right)\).

• Dòng thứ ba gồm \(N - 1\) số nguyên dương, số thứ \(i\) là \(p_{i}\), tức là người thứ \(i + 1\) sẽ có cấp trên trực tiếp là \(p_{i}\left( 1\ \leq \ p_{i} \leq \ N \right)\).

• \(Q\) dòng tiếp theo, dòng thứ \(i\) gồm một số nguyên dương \(u_{i}\) \(\left( 1\ \leq \ u_{i} \leq \ N \right)\), miêu tả giả định thứ \(i\).

Kết quả: ghi ra tệp văn bản CONGTY.OUT:

+ Với mỗi giả định, in ra kết quả tương ứng.

Ràng buộc:

• Có 15% số test thỏa mãn: \(n\ \leq \ 15,\ q\ = \ 1\).

• Có 20% số test thỏa mãn: Nếu \(u\) là cấp trên của \(v\) thì \(a_{u} > \ a_{v}.\)

• Có 15% số test thỏa mãn: Nhân viên thứ \(i\) là cấp trên của nhân viên thứ \(i + 1\), \(\forall i \in \lbrack 1,n - 1\rbrack\).

• Có 15% số test thỏa mãn: \(N\ \leq \ 1000,\ a_{i} \leq \ 100\).

• Có 20% số test thỏa mãn: \(N\ \leq \ 10^{5},\ a_{i} \leq \ 100\).

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

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Cho một dãy số gồm \(n\) số nguyên dương. Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Dữ liệu vào:

Dòng đầu tiên gồm một số nguyên dương \(n\) (n\(\leq 10^{6}\)) là số lượng phần tử của dãy số;

Dòng thứ hai gồm \(n\) số nguyên dương \(a_{i}\) (\(a_{i} \leq 10^{7}\)) mô tả các phần tử của dãy số theo thứ tự.

Kết quả:

Một số nguyên duy nhất là độ dài dãy con thỏa mãn đề bài. Trường hợp không tồn tại dãy con thỏa mãn, in ra \(- 1\).

Ràng buộc:

+ Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(n \leq 10^{3}\), \(a_{i} \leq 10^{3}\) \((1 \leq i \leq n)\);

+ \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(n \leq 10^{3}\)

+ \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là \(5\ ml\), \(3\ ml\) và \(2\ ml\). Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng \(n(ml)\).

Dữ liệu vào:

+ Một số nguyên dương duy nhất \(n\ (2 \leq n \leq 10^{18})\) là số nước cần đong.

Kết quả:

+ Một số nguyên dương duy nhất là số lượng lần đong ít nhất

Ví dụ:

Bạn cần Đăng nhập để nộp bài