PRE THI HUYỆN #06

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Số đẹp 100 (p) 1.0s 1G
2 Mua nhà 100 (p) 1.0s 1G
3 Tam giác đều 100 (p) 1.0s 1G
4 Giải cứu gấp 100 (p) 2.0s 1G

1. Số đẹp

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: SODEP.INP Output: SODEP.OUT

Cho một số nguyên dương \(N\), một số nguyên dương \(N\) được gọi là số đẹp nếu nó có thể phân tích thành tổng các số nguyên dương chẵn. Nhiệm vụ của bạn là kiểm tra xem số đó có phải là số đẹp không.

Dữ liệu vào

Dữ liệu nhập vào từ tệp văn bản SODEP.INP

  • Dòng đầu tiên chứa duy nhất một số nguyên \(T\) - là số lượng bộ test. \((1 \leq T \leq 100)\)
  • \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\), là số cần kiểm tra \((1 \leq N \leq 10^{18})\)

Dữ liệu ra

Dữ liệu in ra tệp văn bản SODEP.OUT

  • Gồm \(T\) dòng, mỗi dòng chứa đáp án của mỗi truy vấn. YES nếu là số đẹp và NO nếu ngược lại.

Ràng buộc

  • \(30\%\) số test có \(T=1, N \leq 40\)
  • \(70\%\) số test còn lại không có ràng buộc gì thêm
Sample
Input 
5
10000000000
19122007
24102007
20222025
12
Output 
YES
NO
NO
NO
YES

2. Mua nhà

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: MUANHA.INP Output: MUANHA.OUT

Ngành IT Việt Nam hiện nay ở đầu của sự phát triển. Có thể nói IT là vua của các nghề. Vừa có tiền, có quyền. Vừa kiếm được nhiều $ lại được xã hội trọng vọng.
Thằng em mình học bách khoa cơ khí, sinh năm \(96\). Tự mày mò học code rồi đi làm remote cho công ty Mỹ \(2\) năm nay. Mỗi tối online \(3-4\) giờ là xong việc. Lương tháng \(3k6\). Nhưng thu nhập chính vẫn là từ nhận các project bên ngoài làm thêm. Tuần làm \(2,3\) cái nhẹ nhàng \(9,10k\) tiền tươi thóc thật không phải đóng thuế. Làm gần được \(3\) năm mà nhà xe nó đã mua đủ cả. Nghĩ mà thèm.
Gái gú thì cứ nghe nó bảo làm CNTT thì chảy nước. Có bé kia dân du học sinh Úc, về được cô chị giới thiệu làm ngân hàng VCB. Thế nào thằng ấy đi mở thẻ tín dụng gặp phải thế là hốt được cả chị lẫn em. 3 đứa nó sống chung một căn hộ cao cấp. Nhà con bé kia biết chuyện ban đầu phản đối sau biết thằng đấy học IT thì đổi thái độ, cách ba bữa hỏi thăm, năm bữa tặng quà lấy long, luôn giục cưới kẻo lỡ kèo ngon.

Bây giờ, anh ấy đang đi mua nhà cho bố mẹ của \(2\) cô gái ấy, khu đất ấy có \(NxM\) ngôi nhà và được bao quanh bởi biển, ngôi nhà hàng \(i\) cột \(j\) có độ cao là \(h_{i,j}\). Vì là một anh chàng giàu có, anh ấy muốn tìm một ngôi nhà có ít nhất một hướng có thể nhìn ra biển - tương đương với việc từ ngôi nhà, có một đường thẳng nhìn đến biển, không có ngôi nhà nào có cùng độ cao hoặc cao hơn ngôi nhà đó. Hãy đếm số ngôi nhà thỏa mãn điều kiện của anh ấy để anh ấy mua nhé.

Dữ liệu vào

Dữ liệu nhập vào từ tệp văn bản MUANHA.INP

  • Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) - Là số hàng và số cột của khu đất. \((1 \leq N,M \leq 100)\)
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên dương. - Là độ cao của các ngôi nhà thuộc hàng. \((h_{i,j} \leq 10^9)\)

Dữ liệu ra

Dữ liệu in ra tệp văn bản MUANHA.OUT
- Một dòng duy nhất là số lượng nhà mà anh chàng ấy có thể mua.

Sample
Input 
3 5 
9 4 6 5 2
4 3 7 6 3
6 7 2 9 10
Output 
14

3. Tam giác đều

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: TAMGIACDEU.INP Output: TAMGIACDEU.OUT

Cho dãy số nguyên dương \(N\) phần tử, hãy đếm cách chọn \(3\) phần tử từ \(N\) phần tử sao cho độ dài của \(3\) phần tử đó là tam giác đều.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản TAMGIACDEU.INP

  • Dòng đầu tiên gồm một số nguyên dương \(N\) - là số lượng phần tử \((3 \leq N \leq 10^5)\)
  • Dòng thứ hai chứa \(N\) số nguyên dương - lần lượt là các phần tử của dãy số. \((a_i \leq 10^6)\)

Dữ liệu ra

Dữ liệu in ra tệp văn bản TAMGIACDEU.OUT
- Một dòng duy nhất là số cách chọn \(i,j,k\) sao cho \(a_i,a_j,a_k\) là \(3\) cạnh của tam giác đều. In ra kết quả chia dư cho \(19122007\).

Lưu ý

Các cách chọn mà \(i,j,k\) là hoán vị của nhau thì đều tính là một cách.

Chấm điểm

Số điểm Ràng buộc
\(70\) \(1 \leq N \leq 100\)
\(30\) \(100 \leq N \leq 10^5\)
Sample
Input 
4
1 1 1 2
Output 
1
Giải thích

Có \(1\) bộ \((1,2,3)\)

4. Giải cứu gấp

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: TRUYVANX.INP Output: TRUYVANX.OUT


Kỳ thi HSG Huyện Lệ Thủy đã đến gần, chỉ còn vài ngày nữa thôi! Nhưng trong những ngày tháng vừa qua, Nobita đã phải chép code của Dekisugi nhiều lần. Do đã bị bắt chép code \(3\) lần, tài khoản của Nobita và Dekisugi đã bị ban vĩnh viễn nên bây giờ không thể ôn tập trên LTOJ được nữa. Và giờ chỉ còn một cách duy nhất để được mở lại tài khoản đó chính là giải bài toán dưới đây.
Cho dãy số nguyên dương \(N\) phần tử \(a_1,a_2,...,a_n\) và \(Q\) truy vấn. Với mỗi truy vấn có dạng \(l\) \(r\) \(x\), hãy đếm số phần tử \(x\) trong đoạn \(l\) \(r\)

Tuy nhiên, Nobita không biết nên giải quyết bài toán thế nào để có thể \(AC\) nên Nobita đã cầu xin bạn giúp đỡ, hãy giúp Nobita nhé.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản TRUYVANX.INP

  • Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\).\(( 1 \leq N,Q \leq 5.10^6)\)
  • Dòng thứ hai chứa \(N\) số nguyên dương.\((a_i \leq 10^9)\)
  • \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn cần xử lý.

Dữ liệu ra

Dữ liệu in ra tệp văn bản TRUYVANX.OUT
- \(Q\) dòng,mỗi dòng là đáp án của mỗi truy vấn

Subtasks

Số điểm Ràng buộc
\(42\) \(N.Q \leq 10^8\)
\(12\) Tất cả truy vấn có \(x\) giống nhau
\(19\) Tất cả \(a_i \leq 10^3\)
\(27\) Ràng buộc gốc
Sample
Input 
5 3
1 2 3 1 3 
1 3 2 
1 5 3
2 3 1
Output 
1
2
0