link chấm bài:

https://chuyentinpbc.ucode.vn/contests/bai-tap-ngay-37-69019

Bài 1. Âm tiết

Các học viên nhí của Trung tâm Anh ngữ ABC Smart bị nghỉ dài vì dịch bệnh viêm phổi cấp nCoV-19, vì vậy Anh ngữ ABC Smart đã giao bài tập về nhà cho các học viên nhí. Đầu tháng tới, nếu không có gì thay đổi, các học viên nhí sẽ quay trở lại trung tâm để học. Trung tâm yêu cầu các học viên nhí sẽ trình bày bài viết đã được chuẩn bị của kỳ nghỉ vừa rồi trước cả lớp. Các giảng viên muốn tính trước thời gian đọc thành tiếng của từng bài viết để tìm cách phân lịch trình bày của các học viên sao cho hợp lý về mặt thời gian. Thời gian để phát âm một từ được tính bằng số âm tiết của từ đó. Mỗi âm tiết là một cụm liên tiếp các nguyên âm mà không chứa phụ âm nào. Nguyên âm bao gồm a, i, u, e, o, y, còn lại là phụ âm. Hãy lập trình giúp các giảng viên tính thời gian đọc của một bài viết.

Dữ liệu: Vào từ file văn bản BAI1.INP gồm:

+ Dòng đầu tiên số nguyên dương N là số từ trong bài viết (N <= 105)

+ N dòng tiếp theo mỗi dòng chứa một từ. Các từ chỉ bao gồm chữ cái tiếng Anh in thường và luôn chứa ít nhất một nguyên âm. Không có từ nào dài hơn 31 kí tự. 

Kết quả: Ghi ra file văn bản BAI1.OUT là kết quả của đề bài

BAI1.INPBAI1.OUT
4
aid
astra
per
aspera
7

Giải thích: Có 4 từ:  “aid” có một âm tiết thời gian phát âm của từ là 1 đơn vị thời gian; “astra” có 2 âm tiết nên thời gian phát âm của từ là 2 đơn vị thời gian; Tương tự  “per” thời gian phát âm là 1; “aspera” thời gian phát âm là 3 => tổng thời gian phát âm của bài viết là: 1+2+1+3 = 7;

Ràng buộc:

+ Có 50% số điểm ứng với tất cả các từ: không có 2 nguyên âm nào ở vị trí cạnh nhau.

+ Có 50% số điểm tương ứng với các trường hợp còn lại.

Bài 2. Biểu thức

Hôm nay, các bạn nhỏ ABC Smart lại được Thầy giáo đố một bài toán sau: Một dãy gồm n số nguyên a1, a2,..., an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n­-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n­-1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ: với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên a1, a2,..., anvà số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n­-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Dữ liệu: Vào từ file văn bản BAI2.INP: 

 + Dòng đầu chứa hai số nguyên dương n, k (k < n);

 + Dòng thứ hai chứa n số nguyên a1, a2,..., an (|an| ≤ 106)

Kết quả: Đưa ra file văn bản BAI2.OUT một số nguyên là giá trị của biểu thức đặt được.

BAI2.INPBAI2.OUT
5 2
28 9 5 1 69
100

Ví dụ:

Ràng buộc:

+ Có 50% số điểm có n ≤ 105 và k = 1;

+ Có 50% số điểm có n ≤ 105;

Bài 3. Bộ 3 số đẹp

Các học viên nhí của Anh ngữ ABC Smart lại tìm được một bài toán liên quan đến dãy số như sau: Một bộ 3 số được xem là đẹp nếu như tổng của chúng bằng hai lần một trong 3 số. Cho một dãy số a1, a2, …an; đếm số lượng bộ 3 số (ai, aj, ak) là bộ 3 số đẹp trong dãy (1 <= i < j < k <= n). 

Dữ liệu: Vào từ file văn bản BAI3.INP

+ Dòng đầu tiên là số nguyên dương N(N< 5*103) 

+ Dòng thứ 2 chứa N số nguyên dương a1, a2, … aN (ai <= 106) 

Kết quả: Ghi ra file văn bản BAI3.OUT: là kết quả của bài toán

Ví dụ:

BAI3.INPBAI3.OUT
10
1 9 10 3 9 2 30 1 1 8
19

Ràng buộc:

+ Có 50% số điểm tưng ứng với n <= 102

+ Có 50% số điểm còn lại không có ràng buộc gì thêm.

Bài 4. 

 Trên mặt phẳng tọa độ có n+1 điểm: điểm tọa độ nguyên A(x,y) và n điểm tọa độ nguyên B1(x1,0), B2(x2,0),……., Bn(xn,0).

Yêu cầu: Với số nguyên không âm S, hãy đếm số lượng tam giác có diện tích lớn hơn S mà ba đỉnh của tam giác là ba điểm trong N+1 điểm đã cho. 

Dữ liệu: Vào từ file BAI4.INP gồm

+ Dòng đầu tiên chứa hai số nguyên n và S (2< n, 0< S < 109 )  .

 + Dòng thứ hai chứa hai số nguyên x, y (|x|, |y| < 109 ).

 + Dòng thứ ba chứa n số nguyên x1, x2,….,xn (|xi| < 109 )

Kết quả: Ghi ra file BAI4.OUT là số lượng tam giác đếm được.

Ví dụ

BAI4.INPBAI4.OUTGiải thích
5 3
3 5
1 2 5 7 8
8 

Ràng buộc:

  1. + Có 25% số điểm có n=2  
  2. + Có 25% số điểm có n< 2000
  3. + Có 25% số điểm có n< 200000 và S=0   
  4. + Có 25% số điểm có n< 200000