HSG THPT Vòng 1 Hà Nội 2015
Bộ số tam giác
Nộp bàiNguồn: Học sinh Giỏi THPT Hà Nội năm 2014 - 2015
Cho số nguyên dương \(n\), \(3 \le n \le 100000\).
Yêu cầu: Hãy đếm số lượng các bộ số \(i\), \(j\), \(k\) (\(0 < i < j < k \le n\)) tạo thành độ dài ba cạnh của một tam giác.
Input
Dữ liệu vào từ tệp văn bản BAI1.INP:
- Chứa duy nhất số \(n\).
Output
Kết quả ra tệp văn bản BAI1.OUT:
- Số dư của số lượng bộ số tạo thành tam giác chia cho \(10^9\).
Examples
Test 1
Input
5Output
3Note
- Các bộ số tạo thành ba cạnh của một tam giác là: \((2,3,4), (2,4,5), (3,4,5)\) và \(3\) mod \(10^9 = 3\)
Tích lớn nhất
Nộp bàiNguồn: Học sinh Giỏi THPT Hà Nội năm 2014 - 2015
Cho một dãy số nguyên \(a_1, a_2 , a_3, ..., a_n\) (\(3 \le n \le 10^6\) , \(|a_i| \le 1000\), với mọi \(i = 1, 2, ...,n\)). Xét các tích \(S = a_i . a_j . a_k\) (\(i < j < k\)).
Yêu cầu: Hãy tìm \(i, j, k\) để tích \(S\) đạt giá trị lớn nhất.
Input
Dữ liệu vào từ tệp văn bản BAI2.INP:
- Dòng đầu ghi số \(n\);
- Dòng tiếp theo ghi các số nguyên \(a_i\) (các số cách nhau ít nhất một dấu cách).
Output
Kết quả ra tệp văn bản BAI2.OUT:
- Số nguyên là tích lớn nhất tìm được.
Examples
Test 1
Input
5
3 5 7 10 4Output
350Note
- Tích \(3\) số: \(5, 7, 10\)
Chia hết
Nộp bàiNguồn: Học sinh Giỏi THPT Hà Nội năm 2014 - 2015
Bình là một học sinh yêu môn toán học và cũng rất hứng thú với môn tin học. Bình rất thích thú với chương trình của một cậu bạn học bên lớp chuyên tin khi chỉ cần bấm tổ hợp phím CTRL + F9 đã có ngay hàng ngàn số nguyên tố. Bình nghĩ ra bài toán sau : Cho một dãy \(n\) số nguyên dương \(a_1, a_2, ..., a_n\). Đếm số lượng các số ai mà \(a_i!\) (\(a_i! = 1.2.3...a_i\) ) chia hết cho \(a_i^2\). Bình loay hoay mãi mà vẫn chưa lập trình xong.
Yêu cầu: Bạn hãy giúp Bình lập chương trình giải bài toán trên.
Input
Dữ liệu vào từ tệp văn bản BAI3.INP:
- Dòng đầu chứa số \(n\) (\(1 \le n \le 100\));
- Dòng tiếp theo ghi \(n\) số nguyên dương \(a_1, a_2,..., a_n\) (\(1 \le a_i \le 10^9\))
Output
Kết quả ra tệp văn bản BAI3.OUT:
- Số nguyên duy nhất là số lượng các số trong dãy có tính chất đã nêu.
Examples
Test 1
Input
5
10 2 4 7 6Output
2Note
- Chỉ có \(2\) số \(10\) và \(6\) có thỏa mãn:
- \(10!\) Chia hết cho \(100\) và \(6!\) Chia hết cho \(36\)
Tìm đường
Nộp bàiNguồn: Học sinh Giỏi THPT Hà Nội năm 2014 - 2015
Một bản đồ mô tả vùng biển đảo được cho bởi một lưới các ô vuông đơn vị gồm \(m\) dòng, \(n\) cột (\(2 < m,n ≤ 200\), chỉ số dòng được đánh số từ trên xuống dưới, chỉ số cột được đánh số từ trái sang phải), trong đó vùng nước được đánh số \(0\) và các vùng khác thuộc đảo được đánh số \(1\). Giả sử rằng bên ngoài biên của bản đồ là đại dương mênh mông. Một hòn đảo là một tập các ô vuông có giá trị \(1\) và có chung cạnh với nhau, số các ô vuông này chính là diện tích của hòn đảo. Một tàu đánh cá đang đánh bắt cá ở vị trí \((x, y)\) trên vùng biển đảo này thì nghe tin có cơn bão lớn sắp tràn tới, các ngư dân trên tàu muốn đến một hòn đảo có diện tích lớn nhất trong các hòn đảo để tránh bão cho an toàn. Khi di chuyển trên biển tàu có thể đi theo các ô số \(0\) kề cạnh và chỉ đi trong vùng thuộc bản đồ.
Yêu cầu: Cho trước bản đồ của vùng biển chứa quần đảo và vị trí \((x,y)\) của tàu đánh cá. Hãy tìm một đường đi ngắn nhất trên biển từ vị trí \((x, y)\) đến một vị trí bất kỳ trên đảo có diện tích lớn nhất (đường đi ngắn nhất là đường đi qua ít ô chứa số \(0\) nhất).
Input
Dữ liệu vào từ tệp văn bản BAI4.INP:
- Dòng đầu ghi hai số nguyên dương \(m, n\) cho biết kích thước bản đồ, hai số \(x, y\) là vị trí tàu đánh cá;
- \(m\) dòng tiếp theo, mỗi dòng ghi \(n\) số \(0\) hoặc \(1\) cho biết nội dung bản đồ. Các số trên cùng một dòng cách nhau ít nhất một dấu cách. (Dữ liệu đảm bảo luôn có đường đi đến đảo lớn nhất)
Output
Kết quả ra tệp văn bản BAI4.OUT:
- Số lượng ô số \(0\) nằm trên đường đi ngắn nhất (không kể ô xuất phát) để đến một đảo có diện tích lớn nhất nào đó.
Examples
Test 1
Input
6 7 2 3
0 0 0 0 0 0 0
0 0 0 0 0 1 0
0 1 0 0 1 1 0
0 1 0 0 1 1 0
0 1 1 0 0 1 0
0 0 0 0 0 0 0Output
2Note
- Từ ô \((2,3)\) đi qua các ô \((2,4)\), \((2,5)\) thì đến được ô \((2,6)\) hoặc ô \((3,5)\) là các ô thuộc đảo lớn nhất.