Olympic Truyền thống 30/4 2019 - Tin học - Khối 10

Một nhà Toán học đang làm việc với các số nguyên tố cần sự giúp đỡ của bạn. Cụ thể, nhà
Toán học có \(T\) câu hỏi, mỗi câu hỏi là một cặp số \(L\) và \(R\), bạn cần trả lời số lượng số nguyên tố nằm
trong đoạn \([L, R]\), tính cả hai đầu. Nhận thấy các thí sinh tham gia Kỳ thi Olympic Truyền thống
30-4 có khả năng trả lời được câu hỏi này, nhà Toán học nhờ các bạn trợ giúp. Các bạn hãy giúp nhà
Toán học nhé.

Yêu cầu: Hãy viết chương trình trả lời các truy vấn của nhà Toán học.

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(1 \le T \le 1000\)) là số truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương, dòng thứ \(i+1\) ghi cặp số \(L_i, R_i\),
  (\(1 \le L_i \le R_i \le 10^9\)) là các tham số của truy vấn thứ \(i\).
• Tổng độ dài của các đoạn truy vấn không vượt quá \(10^6\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) chứa một số nguyên là
  câu trả lời của truy vấn thứ \(i\).

Scoring

• 50% số điểm của bài tương ứng với các test có \(L_i, R_i \le 10^5\) và tổng độ dài các đoạn truy
  vấn không vượt quá \(10^5\)

Example

2
1 50
10000000 10000050

15
1

Hành tinh Marvelous Land gồm \(N\) thành phố, được kết nối với nhau bởi \(M\) tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới \(N\). Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố \(N\). Tuyến đường thứ \(i\) cho phép đi lại giữa hai thành phố \(u_i\) và \(v_i\) với \(t_i\) đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố \(N\) với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5, 1 \le M \le 2 × 10^5\)), số thành phố và số
  tuyến đường.
• \(M\) dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ \(i+1\) ghi số \(u_i, v_i, t_i\) (\(1 \le u_i, v_i \le N, 1 \le t_i \le 10^6\)) là các thông tin của tuyến đường thứ \(i\).

Output

• Ghi ra duy nhất một số nguyên là số tuyến đường trọng
  yếu.

Scoring

• 50% số điểm của bài tương ứng với các test có \(N \le 1000\) và \(M \le 1000\)

Example

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

3

Hai anh em An và Bình tham gia một trò chơi thám hiểm trên bảng số \(xTremeMaze\).
Bảng có kích thước \(N\)x\(M\) (\(N\) dòng và \(M\) cột). Các ô trong bảng được đánh số từ trái sang phải và từ
trên xuống dưới.

Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi
đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người
chơi sẽ bị giảm nếu đi vào ô này.

An và Bình bắt đầu tại ô trái trên, đánh số là (\(1, 1\)). Mỗi lượt, một người chỉ có thể di chuyển tới ô
kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi
qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết
thúc tại ô (\(N, M\)).

Mục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô
mà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí (\(1, 1\)) và ô kết thúc
tại vị trí (\(N, M\)). Quy ước: giá trị điểm kinh nghiệm tại ô (\(1, 1\)) và ô (\(N, M\)) đều bằng 0.

Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt
được.

Input

• Dòng đầu chứa hai số nguyên \(N\) và M (\(2 \le N, M \le 200\)), số dòng và số cột của bảng.
• \(N\) dòng tiếp theo, mỗi dòng ghi M số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng.
  Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.

Output

• Ghi ra duy nhất một số nguyên là tổng điểm lớn nhất mà
  An cùng với Bình đạt được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 3\) và \(M \le 200\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 50\) và \(M \le 50\).
• Subtask \(3\) (\(30\%\) số điểm): Không có điều kiện gì thêm.

Example

3 3
0 2 3
4 5 6
7 8 0

32