Đề bài

Viết chương trình tính tổng của các số nguyên tố nằm trong đoạn [L, R] cho trước.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương T, là số bộ dữ liệu thử nghiệm. (1 ≤ T ≤ 106)
• T dòng tiếp theo, mỗi dòng gồm hai số nguyên dương L và R, giới hạn của đoạn. (1 ≤ L ≤ R ≤ 106)

Kết quả

Ghi kết quả ra gồm T dòng, mỗi dòng ghi kết quả tổng của các số nguyên tố nằm trong đoạn [L, R] tương ứng.

Ví dụ

Input

2
1 10
10 20

Output

17
60

Ràng buộc

• Subtask 1: 60% số bộ test có 1 ≤ T ≤ 100 và 1 ≤ L, R ≤ 106.
• Subtask 2: 40% số bộ test có 1 ≤ T ≤ 106 và 1 ≤ L, R ≤ 106.

Tên bài: Số Lượng Bộ Tộc

Có một hòn đảo rất xinh đẹp, thu hút nhiều khách du lịch đến tham quan. Trên đảo có ~ N ~ người thuộc nhiều bộ tộc sinh sống ở đó, dân cư trên đảo rất thân thiện và mến khách. Mỗi người sẽ thuộc một bộ tộc nào đó. Trong đoàn du lịch có một nhà nhân chủng học. Trong quá trình khảo sát, ông đã hỏi từng người mà ông gặp trên đảo câu hỏi duy nhất: Trên đảo, bộ tộc của bạn có bao nhiêu người?.

Từ kết quả khảo sát đó, ông đã xác định được số bộ tộc khác nhau tồn tại trên đảo.

Yêu cầu

Cho số ~ N ~ và các câu trả lời. Hãy xác định số bộ tộc có trên đảo. (Dữ liệu vào của bài toán đảm bảo luôn đúng).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~ N ~ ( ~ 1 \leq N \leq 1,000,000 ~ ).
• Mỗi dòng trong ~ N ~ dòng sau, chứa một số nguyên (~< 20~) chính là câu trả lời nhận được.

Dữ liệu ra

• Một số nguyên duy nhất là số bộ tộc có trên đảo.

Ví dụ

Dữ liệu vào (BOTOC.INP):

3
1
1
1

Dữ liệu ra (BOTOC.OUT):

3

Dữ liệu vào (BOTOC.INP):

7
3
1
2
1
3
2
3

Dữ liệu ra (BOTOC.OUT):

4

Đề bài

Cho số nguyên dương ~ n ~ và dãy ~ n ~ số nguyên dương ~ a_1, a_2, \ldots, a_n ~. Ta gọi một số ~ a_i ~ là độc thân nếu ~ a_i \neq a_j, \forall j \neq i ~. Hãy đếm số lượng số độc thân trong dãy số trên.

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 dương ~ a_1, a_2, \ldots, a_n ~ (~ 1 \leq a_i \leq 10^6 ~).

Dữ liệu ra

• Một dòng duy nhất ghi số nguyên là số lượng số độc thân tìm được.

Ví dụ

Input:

5
1 2 2 3 1

Output:

1

Giải thích:

• Chỉ có duy nhất một số độc thân là ~ 3 ~.

Giới hạn

• Subtask #1: 80% số điểm với ~ n \leq 10^3 ~ và ~ 1 \leq a_i \leq 10^6 ~;
• Subtask #2: 20% số điểm với ~ 10^3 < n \leq 10^6 ~ và ~ 1 \leq a_i \leq 10^6 ~.

Mô tả bài toán:

Công ty IBM yêu cầu mỗi nhân viên phải có một số ID là một số nguyên dương duy nhất. Để đảm bảo tính khoa học, khi có nhân viên mới, số ID được cấp phải là số nguyên dương nhỏ nhất chưa được sử dụng trong danh sách các số IP hiện có.

Đầu vào:

• Dòng đầu tiên chứa số nguyên ~ N ~ (~ 1 \leq N \leq 10^5 ~) — số lượng nhân viên hiện tại.
• ~ N ~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~ a_i ~ (~ 1 \leq a_i \leq 10^9 ~) — số ID của từng nhân viên hiện tại.

Đầu ra:

• Một dòng duy nhất chứa số nguyên dương nhỏ nhất chưa được sử dụng.

Ví dụ:

Input:

3
1
2
3

Output:

4

Giải thích:

Các số ID hiện tại là ~[1, 2, 3]~. Số nguyên dương nhỏ nhất chưa được sử dụng là ~4~.

Input:

5
2
5
1
6
8

Output:

3

Giải thích:

Các số ID hiện tại là ~[2, 5, 1, 6, 8]~. Số nguyên dương nhỏ nhất chưa được sử dụng là ~3~.

Bài 4. Dãy con có tổng lớn nhất

Cho dãy số nguyên ~a_1, a_2, \dots, a_N~. Một dãy con liên tiếp có dạng ~a_i, a_{i+1}, \dots, a_j~ với ~1 \leq i \leq j \leq N~, tổng của dãy con liên tiếp ~a_i, a_{i+1}, \dots, a_j~ là ~a_i + a_{i+1} + \dots + a_j~.

Yêu cầu: Cho dãy số nguyên ~a_1, a_2, \dots, a_N~, tìm dãy con liên tiếp có tổng lớn nhất.

Dữ liệu:

Vào từ tệp văn bản TONGMAX.INP gồm:

• Dòng 1: ghi số nguyên dương ~N~.
• Dòng 2: ghi lần lượt các số nguyên ~a_1, a_2, \dots, a_N~ (~|a_i| \leq 10^6~, với ~i = 1 \dots N~).

Kết quả: ghi ra tệp văn bản TONGMAX.OUT gồm một số duy nhất là tổng của dãy con tìm được.

Ví dụ:

Dữ liệu đầu vào (TONGMAX.INP):

6
3 8 -2 4 5 -1

Dữ liệu đầu ra (TONGMAX.OUT):

18

Giới hạn:

• Subtask 1: Có 40% số điểm với ~N \leq 100~
• Subtask 2: Có 40% số điểm với ~N \leq 1000~
• Subtask 3: Có 20% số điểm với ~N \leq 10^6~

Nội dung bài toán

Ký hiệu ~ \sigma(n) ~ là tổng các ước của số nguyên ~ n ~.

Ví dụ, ~ \sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 ~.

Nhiệm vụ của bạn là tính tổng: ~ \sum_{i=1}^n \sigma(i) \mod (10^9 + 7) ~

Dữ liệu vào

• Dòng duy nhất chứa một số nguyên ~ n ~.

Dữ liệu ra

• In ra tổng ~ \sum_{i=1}^n \sigma(i) \mod (10^9 + 7) ~.

Ràng buộc

• ~ 1 \leq n \leq 10^{12} ~

Ví dụ

Dữ liệu vào

5

Dữ liệu ra

21

Tên bài: Đọc sách cùng nhau

Mô tả bài toán

Có ~ n ~ cuốn sách, và cả hai người bạn Tý và Tèo muốn đọc hết tất cả. Mỗi cuốn sách ~ i ~ mất ~ t_i ~ phút để đọc. Cả hai người có thể đọc đồng thời nhưng không thể đọc cùng một cuốn sách tại cùng một thời điểm.

Hai người đều đọc từ đầu đến cuối cuốn sách mà họ chọn. Nhiệm vụ của bạn là tìm tổng thời gian tối thiểu để cả hai đều đọc hết tất cả sách.

Input Format:

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ t_1, t_2, \dots, t_n ~: thời gian cần thiết để đọc mỗi cuốn sách.

Output Format:

• In ra một số nguyên: tổng thời gian tối thiểu.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq t_i \leq 10^9 ~

Ví dụ

Input:

3
2 8 3

Output:

16

Giải thích:

• Phân chia công việc tối ưu:
  • Tý đọc quyển 1 và 3 hết: ~ [2] và [3] ~, tổng thời gian = ~ 2 + 3 = 5 ~.
  • Tèo đọc quyển 2: ~ [8] ~, tổng thời gian = ~ 8 ~.
  • Vì yêu cầu cả 2 phải đọc hết các sách nên tổng thời gian tối thiểu để hoàn thành là ~ 16 ~.

Đề bài

Cho mảng ~ A ~ gồm ~ n ~ số nguyên không âm: ~ a_1, a_2, \ldots, a_n ~, hãy đếm số lần xuất hiện của các phần tử khác nhau trong mảng.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~ n ~ là số phần tử của mảng (~ 1 \leq n \leq 10^6 ~);
• Dòng thứ hai ghi ~ n ~ số ~ a_1, a_2, \ldots, a_n ~ (~ |a_i| \leq 10^9 ~).

Dữ liệu ra

• Dòng đầu ghi số nguyên ~ m ~ là số phần tử khác nhau trong mảng ~ A ~;
• ~ m ~ dòng tiếp theo, mỗi dòng ghi 2 số ~ u_i ~, ~ f_i ~, trong đó:
  • ~ u_i ~ là giá trị có trong mảng ~ A ~,
  • ~ f_i ~ là số lần xuất hiện của ~ u_i ~.
    (Các số ~ u_i ~ được sắp xếp theo thứ tự xuất hiện lần đầu trong mảng ~ A ~).

Ví dụ

Input:

6
5 3 2 3 2 2

Output:

3
5 1
3 2
2 3

Giải thích:

• Có 3 giá trị khác nhau là ~ 5, 3, 2 ~ (theo đúng thứ tự xuất hiện).
• Số ~ 5 ~ xuất hiện 1 lần, số ~ 3 ~ xuất hiện 2 lần và số ~ 2 ~ xuất hiện 3 lần.

Giới hạn

• ~ 1 \leq n \leq 10^6 ~
• ~ |a_i| \leq 10^9 ~

Đếm số đôi tất

Mô tả bài toán

Bé Hải Dương có ~n~ chiếc tất, chiếc tất thứ ~i~ có màu là ~c_i~. Bé Hải Dương muốn biết bé có thể ghép được bao nhiêu đôi tất để cho các bạn cùng lớp mỗi người một đôi, biết rằng hai chiếc tất có thể ghép thành một đôi nếu chúng có cùng màu.

Input

Dữ liệu đầu vào được cung cấp như sau:

• Dòng đầu tiên chứa số nguyên ~n~: số tất mà bé Hải Dương có (~1 \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~c_i~ (~1 \leq c_i \leq 10^6~): màu của từng chiếc tất.

Output

Dữ liệu đầu ra là một số nguyên duy nhất: số lượng đôi tất mà bé Hải Dương có thể ghép được.

Ví dụ

Input:

9
10 20 20 10 10 30 50 10 20

Output:

3

Bài toán: Cặp số

Đề bài:

Cho dãy số nguyên ~a_1, a_2, \dots, a_n~ và một số nguyên ~S~. Hãy đếm xem có bao nhiêu cặp chỉ số ~(i, j)~ với ~i \neq j~ mà tổng của ~a_i + a_j = S~.

Input:

• Dòng thứ nhất chứa hai số nguyên ~n~ ~(n \leq 10^5)~ và ~S~ ~(|S| \leq 10^9)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \leq 10^9)~.

Output:

• Một số nguyên duy nhất là số lượng cặp chỉ số ~(i, j)~ thỏa mãn yêu cầu.

Sample Input:

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

Sample Output:

7

Diễn giải:

• Các cặp ~(i, j)~ thỏa mãn ~a[i] + a[j] = 7~ là:
  • ~(1, 7): 5 + 2 = 7~,
  • ~(3, 7): 5 + 2 = 7~,
  • ~(4, 6): 3 + 4 = 7~,
  • ~(5, 6): 4 + 3 = 7~,
  • ~(8, 9): 6 + 1 = 7~.
• Tổng số cặp: ~7~.

Bài toán Josephus

Có ~n~ người đứng thành một vòng tròn và bắt đầu từ người đầu tiên, đếm theo thứ tự, cứ đến người thứ ~k~ thì người đó sẽ bị loại khỏi vòng tròn. Quá trình này tiếp tục cho đến khi chỉ còn lại một người duy nhất. Nhiệm vụ của bạn là xác định vị trí (index từ 1) của người sống sót cuối cùng.

Ví dụ minh họa:

Giả sử ~n = 5~ và ~k = 3~:

• Bắt đầu: [1, 2, 3, 4, 5], người thứ 3 bị loại (3).
• Còn lại: [1, 2, 4, 5], người thứ 6 (vòng lại là người thứ 1) bị loại (1).
• Còn lại: [2, 4, 5], người thứ 3 bị loại (5).
• Còn lại: [2, 4], người thứ 3 (vòng lại là người thứ 2) bị loại (2).
• Người cuối cùng còn lại là 4.

Vậy vị trí người sống sót cuối cùng là 4 (nếu đánh số từ 1).

Input

5 3
1 2 3 4 5

Output

4

Ràng buộc:

• 30% số test ứng với 30% số điểm có ~N \leq 1000~ và ~k \leq 1000~.
• 30% số điểm còn lại có ~N \leq 100,000~ và ~k \leq 1000~.
• 40% số test ứng với 40% số điểm có ~N \leq 10^{18}~ và ~k=2~.