BÀI 1: THUÊ XE (5.0 điểm)

Tên file chương trình: THUEXE.CPP

Trong một hội thao, có m nhóm vận động viên, mỗi nhóm có một số lượng vận động viên nhất định. Ban tổ chức cần thuê các xe ô tô 7 chỗ (bao gồm cả tài xế, tức là mỗi xe chở được tối đa 6 hành khách) để đưa đón các vận động viên.

Để thuận tiện cho việc quản lý, Ban tổ chức yêu cầu: các vận động viên thuộc cùng một nhóm phải ngồi chung trên cùng một xe (không được tách nhóm ra các xe khác nhau). Một xe có thể chở một hoặc nhiều nhóm nếu tổng số người không vượt quá 6.

Yêu cầu: Hãy tính số lượng xe ít nhất mà Ban tổ chức cần thuê.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương m (1 <= m <= 10^5) là số lượng nhóm

Dòng thứ hai chứa m số nguyên dương a1, a2, ..., am (1 <= ai <= 6) là số lượng vận động viên của từng nhóm.

Dữ liệu ra:

Một số nguyên duy nhất là số lượng xe ít nhất cần thuê.

Input:

3
6 1 3

Output:

2

BÀI 2: XÂU ĐỐI XỨNG (5.0 điểm)

Tên file chương trình: PALINDROME.CPP

Một xâu đối xứng là xâu khi đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ: ABA, ACCA, RACECAR.

Yêu cầu: Cho một xâu ký tự s chỉ gồm các chữ cái in hoa. Hãy tìm độ dài của xâu con liên tiếp đối xứng dài nhất trong xâu s.

Dữ liệu vào: Một dòng duy nhất chứa xâu ký tự s (độ dài xâu không quá 2000 ký tự).

Dữ liệu ra: Một số nguyên duy nhất là độ dài của xâu con đối xứng dài nhất tìm được

Input:

ACBCA

Output:

5

BÀI 3: SỐ ĐẸP (4.0 điểm)Tên file chương trình: SOBEAUTY.CPP

Định nghĩa một số nguyên được gọi là số đẹp nếu số lượng các ước nguyên tố phân biệt của nó là một số nguyên tố.

Ví dụ: Số 12 có các ước là 1, 2, 3, 4, 6, 12. Các ước nguyên tố phân biệt là {2, 3}.

Số lượng ước nguyên tố là 2. Vì 2 là số nguyên tố nên 2 là số đẹp.

Yêu cầu: Cho dãy số A gồm n phần tử và q câu hỏi. Mỗi câu hỏi gồm hai số l và r, hãy đếm xem trong đoạn từ vị trí l đến vị trí r của dãy A có bao nhiêu số đẹp

Dữ liệu vào:

Dòng 1: Gồm số nguyên dương n và q (1 <= n, q <= 10^5).

Dòng 2: Gồm n số nguyên của dãy A (1 <= Ai <= 10^6).

q dòng tiếp theo: Mỗi dòng chứa hai số nguyên l, r (1 <= l <= r <= n)

Dữ liệu ra:

Với mỗi câu hỏi, in ra số lượng số đẹp trên một dòng tương ứng

Input:

5 3
1 10 2 30 14
1 5
1 2
4 5

Output:

3
1
2