Hướng dẫn giải Contest chuyentin.pro vòng 9

 Số đối xứng dạng nón

Nhận xét: một số nguyên x có k chữ số sẽ tạo được 2 số đối xứng, số thứ nhất có 2*k chữ số, số thứ hai có 2*k – 1 chữ số.

Ví dụ:  x = 1258 sẽ tạo được 2 số 12588521 và 1258521.

Thuật toán

Lặp số i từ 1 và tăng dần

          Kiểm tra nếu i có các chữ số tăng dần

                     Từ i tạo ra 2 số đối xứng

                     Số nào < N thì lấy, nếu > N thì ngừng lặp.

Chữ số 0 tận cùng

Tính xem trong A có bao nhiều thừa số 2, bao nhiêu thừa số 5

Tính xem trong B có bao nhiều thừa số 2, bao nhiêu thừa số 5

Từ đó suy ra A * B đã có bao nhiêu thừa số 2, bao nhiêu thừa số 5

Để A * B * C có k chữ số 0 ở cuối, thì trong tích này phải có ít nhất k thửa số 2, k thừa số 5

Nếu trong tích A * B chưa đủ, thiếu bao nhiều thừa số ta sẽ lấy vào C. Từ đó suy ra cách tính C.

Ví dụ: A = 15, B = 12, k = 3

A = (3 * 5)

B = (2 * 2 * 3)

k = 3 nên cần A * B * C phải có ít nhất 3 thừa số 2, 3 thừa số 5

A * B hiện tại có 2 thừa số 2, 1 thừa số 5, còn thiếu 1 thừa số 2, 2 thừa số 5 nên C = 2 * 5 * 5 = 50

Chia kẹo

tư tưởng tham lam

          Thay vì cố gắng tìm cách chia túi kẹo lớn thành các túi nhỏ hơn, ta sẽ  ghép các túi nhỏ hơn ấy thành 1 túi lớn ban đầu sao cho tổng chi phí là nhỏ nhất.

Chi phí khi ghép 2 túi lại với nhau chính là tổng số kẹo của 2 túi, vì vậy, để giảm chi phí đến mức tối thiểu, chúng ta sẽ tìm 2 túi kẹo sao cho tổng số kẹo của 2 túi ấy là nhỏ nhất ó chọn 2 túi kẹo ít nhất.

          Cấu trúc heap sẽ giải quyết công việc này một cách dễ dàng với độ phức tạp O(NlogN). Với mỗi bước, chúng ta chỉ việc lấy ra 2 túi có số kẹo nhỏ nhất, ghép chúng lại sau đó cho túi mới vào heap, lặp đến khi nào chỉ còn 1 túi duy nhất.

Chú ý cách cài đặt heap min trong c++

Dãy con không giảm dài nhất

Dãy u[] : 1 ; 3 ; 6 ; 10 ; 15 ; 21 ; 28; 36; 45; 55; 67; 79;          … .

Nhận xét u[k] = 1 + 2 + … + k = k(k+1)/2;

Nếu x = k(k + 1)/2

2x = k(k+1) Û nếu 2x là tích 2 số tự nhiên liên tiếp thì x thuộc u[]

* Cách kiểm tra 2x là tích 2 số tự nhiên liên tiếp

k*k ≤ 2x = k*(k+1) ≤ (k+1)*(k+1).

k ≤ sqrt(2x) ≤ (k+1)

k = int(sqrt(2x))

if(k*(k+1)==2x) return true ;

else return false ;

Duyệt qua dãy để tìm đoạn con các phần tử thỏa đề.