GIAO LƯU LẦN 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Thương của phép chia 3 (p) 1.0s 100M
2 Từ chỉ chứa một loại kí tự 3 (p) 1.0s 1G
3 Đoạn con M phần tử có tổng lớn nhất 4 (p) 1.0s 100M
4 Dãy con dài nhất có tổng không lớn hơn S 5 (p) 1.0s 1G

1. Thương của phép chia

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 100M Input: bàn phím Output: màn hình

Cho một số nguyên dương n và 4 số nguyên a, b, c, d.

Yêu cầu:

Viết chương trình đưa ra thương lớn nhất của n chia cho một trong 4 số a, b, c, d với điều kiện là n phải chia hết cho số được xét.

Dữ liệu vào:

Cho trong tệp văn bản CHIAHET.INP gồm

  • Dòng 1: Ghi số nguyên dương n (1 < n \(\leq\) \(10^{18}\))
  • Dòng 2: Ghi 4 số nguyên a, b, c, d lần lượt, giá trị tuyệt đối mỗi số không vượt quá n.

Dữ liệu ra:

  • Dòng 1: Ghi vào tệp văn bản CHIAHET.OUT ghi ‘YES’ nếu n thỏa mãn, ngược lại ghi ‘NO’.
  • Dòng 2: Ghi giá trị thương tìm được, nếu không có thì để trống dòng 2.
Ví dụ
Input 
10
2 3 5 9
Output 
YES
5
Giải thích 
Trong 4 số 2, 3, 5, 9 thì N chia hết cho số 2 (a) và số 5 (c) nên sẽ lấy thương của N/a so sánh với thương của N/c, lấy thương của N/a.

2. Từ chỉ chứa một loại kí tự

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một xâu S kí tự gồm nhiều từ, mỗi từ có thể bao gồm các kí tự chữ cái viết hoa, viết thường, chữ số và dấu cách. Độ dài của xâu S không quá \(10^5\) kí tự.

Yêu cầu:

Đưa ra các từ chỉ chứa duy nhất một loại kí tự trong từ đó

Dữ liệu vào:

  • Dòng 1: Ghi xâu S

Dữ liệu ra

  • Dòng 1: Ghi ra các từ theo thứ tự tìm được, mỗi từ cách nhau đúng 1 dấu cách
  • Dòng 2: Ghi số lượng từ tìm được
Ví dụ
input 
Chao cac ban hsg Tin hoc a aa aaa b c
Output 
a aa aaa b c
5
Lưu ý 
Dữ liệu vào luôn đảm bảo có ít nhất 1 từ theo yêu cầu

3. Đoạn con M phần tử có tổng lớn nhất

Điểm: 4 (p) Thời gian: 1.0s Bộ nhớ: 100M Input: bàn phím Output: màn hình

Một dãy số B được gọi là dãy con của A nếu các phần tử của B được lấy từ một hoặc một số phần tử liên tiếp nhau trong A.
Cho một dãy số A gồm N phần tử là các số nguyên.

Yêu cầu:

Tìm một dãy con của A gồm M phần tử (M ≤ N) sao cho dãy con này có tổng lớn nhất.

Dữ liệu vào:

Cho trong file văn bản DCMAX.INP có cấu trúc như sau:

  • Dòng 1: Ghi 2 số nguyên N, M (0 < M ≤ N ≤ \(10^6\) ). Hai số ghi cách nhau ít nhất một dấu cách.
  • Dòng 2: Chứa N số nguyên \(A_i\) ( -\(10^6\) ≤ \(A_i\) ≤ \(10^6\), i = 1, 2, ..., N). Mỗi số ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

Ghi ra file văn bản DCMAX.OUT có cấu trúc như sau:

  • Dòng 1: Ghi ra tổng lớn nhất của dãy con tìm được.
  • Dòng 2: Ghi ra các phần tử của dãy con tìm được. Nếu có nhiều dãy con thỏa mãn thì in ra dãy con xuất hiện đầu tiên trong dãy.
Ví dụ
Input 
8 3
4 3 5 2 8 7 9 6
Output 
24
8 7 9

4. Dãy con dài nhất có tổng không lớn hơn S

Điểm: 5 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy số a có N phần từ nguyên \(a_1\), \(a_2\), .., \(a_n\) và một số nguyên S bất kì. Một dãy con liên tiếp của dãy số a có dạng \(a_i\), \(a_{i+1}\), .., \(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}\), .., \(a_j\) độ dài của dãy con liên tiếp \(a_i\), \(a_{i+1}\), .., \(a_j\) bằng \(j - i + 1\) .

Yêu cầu:

Tìm dãy con liên tiếp của dãy số a có độ dài lớn nhất và có tổng không lớn hơn S?

Dữ liệu:

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

  • Dòng 1: ghi 2 số nguyên N và S (N \(\leq\) \(10^6\), S \(\leq\) \(10^9\))
  • Dòng 2: ghi lần lượt các số nguyên không âm \(a_1\), \(a_2\), .., \(a_n\) ( \(a_i\) \(\leq\) \(10^6\) , i = 1..N)

Kết quả:

ghi ra tệp văn bản LONGEST.OUT gồm một số duy nhất là độ dài của dãy con liên tiếp dài nhất thoả mãn.

Ví dụ:
LONGEST.INP 
8 7
6 8 2 4 5 1 9 3
LONGEST.OUT 
2

Giới hạn:

  • Có 10/25 test có n \(\leq\) 100 tương ứng 2 điểm;
  • Có 10/25 test có 100 < n \(\leq\) 1000 tương ứng 2 điểm;
  • Có 5/25 test có 1000 < N \(\leq\) \(10^6\), \(a_i\) > 0, i = 1..N tương ứng 1 điểm.