HSG THCS Hà Nội 2024

Cho phương trình hóa học sau:

Trong phương trình hóa học trên, cứ \(3\) mol \(Fe\) phản ứng với \(2\) mol \(O_2\) tạo ra \(1\) mol \(Fe_3O_4\).

Yêu cầu: Cho \(a\) mol \(Fe\) và \(b\) mol \(O_2\), tính số mol \(Fe_3O_4\) được tạo ra.

Input

• Dữ liệu nhập vào từ file văn bản HOAHOC.INP:
  • Dòng đầu tiên chứa một số nguyên dương \(a\) là số mol \(Fe\)
  • Dòng thứ hai chứa một số nguyên dương \(b\) là số mol \(O_2\)
• Giới hạn: \(a, b \leq 1000\)

Output

• Ghi ra file văn bản HOAHOC.OUT một số nguyên là phần nguyên của số mol \(Fe_3O_4\) được tạo ra.

Example

10
10

3

Cho hai số nguyên dương \(a\) và \(b\).

Trong các ước số chung nguyên dương của \(a\) và \(b\), hãy đưa ra số lớn thứ hai. Nếu không tồn tại số cần tìm, in ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(a\)
• Dòng thứ hai chứa một số nguyên dương \(b\) \((a, b \leq 10^{12})\)

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

30
40

5

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(a, b \leq 1000\)
• Subtask \(2\) (\(20\%\) số điểm): Không có ràng buộc gì thêm

Trong một trò chơi huấn luyện thú, mỗi người chơi sẽ sở hữu một con thú và sẽ huấn luyện để con thú của mình có điểm sức mạnh lớn nhất. Người chơi có \(M\) phút huấn luyện con thú của mình:

• Có \(N\) kĩ năng người chơi có thể lựa chọn để huấn luyện cho con thú;
• Mỗi phút huấn luyện kĩ năng thứ \(i\), con thú sẽ được tăng thêm \(e_i\) điểm sức mạnh (có thể lựa chọn huấn luyện một kĩ năng nhiều lần);
• Với kĩ năng thứ \(i\) mà con thú được huấn luyện lần đầu, con thú sẽ được tăng thêm \(s_i\) điểm sức mạnh.

Yêu cầu: Hãy lên phương án huấn luyện trong \(M\) phút để điểm sức mạnh của con thú là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) \((1 \leq N \leq 10^5; 1 \leq M \leq 10^9)\) là số lượng kĩ năng và thời gian huấn luyện cho thú.
• \(N\) dòng sau, dòng thứ \(i\) chứa hai số nguyên dương \(s_i, e_i\) \((s_i, e_i \leq 10^6; 1 \leq i \leq N)\) là điểm sức mạnh được tăng khi huấn luyện kĩ năng lần đầu và điểm sức mạnh của kĩ năng.

Output

• In ra màn hình một số duy nhất là số điểm sức mạnh tối đa có thể đạt được.

Example

3 4
2 2
2 5
5 1

23

Scoring

• \(40\%\) số test ứng với \(40\%\) số điểm thoả mãn: \(M = 2\)
• \(40\%\) số test khác ứng với \(40\%\) số điểm thoả mãn: \(M \leq 100\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm

Có một bản đồ dạng lưới ô vuông gồm \(N\) dòng và \(M\) cột, các dòng đánh số từ trên xuống dưới, từ \(1\) đến \(N\); các cột đánh số từ trái sang phải, từ \(1\) đến \(M\); ô ở dòng thứ \(i\) và cột thứ \(j\) được gọi là ô \((i,j)\) và có giá trị là \(A(i,j)\).

Robot đang ở ô \((1,1)\), cần di chuyển đến ô \((N,M)\). Tuy nhiên, trong mỗi lượt di chuyển, nếu robot ở ô \((i,j)\), chỉ được phép di chuyển sang ô \((i,j+1)\) hoặc ô \((i+1,j)\) hoặc ô \((i+1,j+1)\).

Cho một số nguyên dương \(K\). Robot có \(Q\) thử thách, trong thử thách thứ \(i\), cho một số nguyên \(x\) và robot cần di chuyển từ ô \((1,1)\) tới ô \((N,M)\) sao cho đi qua nhiều nhất các ô có giá trị chia \(K\) dư \(x\).

Input

• Dòng đầu chứa bốn số nguyên dương \(N, M, Q, K\) \((N,M \leq 1000; Q \leq 10^5; K \leq 10^6)\) tương ứng là kích thước của lưới ô vuông, số lượng thử thách và số \(K\) cho trước
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên dương mô tả các giá trị của bản đồ lưới ô vuông. Các số có giá trị không quá \(10^9\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\) \((0 \leq x < K)\) của mỗi thử thách

Output

• Gồm \(Q\) dòng, mỗi dòng gồm một số nguyên là số lượng ô nhiều nhất thỏa mãn yêu cầu đề bài

Example

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

5
3

Scoring

• \(20\%\) số test ứng với \(20\%\) số điểm có \(N = 1\)
• \(20\%\) số test ứng với \(20\%\) số điểm có \(N = 2; Q \leq 10^3\)
• \(30\%\) số test ứng với \(30\%\) số điểm có \(N, M, K \leq 300\)
• \(30\%\) số test còn lại với \(30\%\) số điểm không có ràng buộc gì thêm

Một đoạn thẳng được mô tả bằng một cặp số nguyên \([L, R]\). Hai đoạn thẳng được gọi là giao nhau nếu chúng có ít nhất một điểm chung.

Một tập đoạn tốt là tập các đoạn thẳng sao cho với mỗi một đoạn thẳng trong tập, đều giao nhau với ít nhất một đoạn thẳng khác trong tập đó (coi tập đoạn thẳng chỉ có một đoạn thẳng duy nhất là tập đoạn tốt). Ví dụ, tập \(\{[1, 3], [4, 5], [5, 7], [3, 4]\}\) hay \(\{[1, 4], [2, 3]\}\) là một tập đoạn tốt, còn \(\{[1, 4], [3, 5], [6, 7]\}\) thì không phải là tập đoạn tốt. Độ tốt của một tập đoạn tốt là số lượng các đoạn thẳng trong tập đó.

Lưu ý: Hai tập đoạn tốt có ít nhất một điểm chung sẽ được gộp thành một tập đoạn tốt.

Yêu cầu: Ban đầu tập đoạn thẳng không có đoạn thẳng nào. Cho \(N\) đoạn thẳng, mỗi lần lấy một đoạn thẳng theo thứ tự thêm vào tập đoạn thẳng, yêu cầu tính tích độ tốt của các tập đoạn tốt được sinh ra từ tập đoạn thẳng hiện tại. Do kết quả rất lớn, in ra phần dư của đáp án sau khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \le 10^5\)) là số đoạn thẳng lần lượt được thêm vào.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) (\(L \le R \le 10^9\)) mô tả một đoạn thẳng.

Output

• Gồm \(N\) dòng, dòng thứ \(i\) (\(1 \le i \le N\)) chứa một số nguyên là kết quả theo yêu cầu đề bài khi thêm đoạn thẳng thứ \(i\).

Example

6
1 3
4 5
5 7
3 4
8 10
9 11

1
1
2
4
4
8

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(L = R; N \le 30\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(R \le 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \le 2000\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm không có ràng buộc gì thêm.