Hướng dẫn NTUCoder Round #17

middlest - 28/05/2016

ALARM - Đồng hồ báo thức

Rất đơn giản, duyệt số giờ và số phút, sau đó kiểm tra tổng số vạch hiển thị có bằng n hay không.

CIRCLENUM - Số vòng

Gọi F(x) là số số vòng trong đoạn [1; x], khi đó kết quả bài toán là F(R) - F(L - 1)

Cách tính F(x):

- Nếu x < 10 thì F(x) = x

- Ngược lại, gọi len là độ dài của x, x' là x bỏ đi chữ số đầu tiên và cuối cùng, x[i] là số thứ i của x tính từ trái sang phải bắt đầu từ 1, ban đầu kết quả bằng 9, duyệt biến i từ 2 đến len - 1 rồi cộng thêm 9 * 10i - 2 vào kết quả. Sau đó cộng thêm (x[1] - 1) * 10len - 2 nếu x[1] - 1 > 0 và cộng thêm x' + 1 vào kết quả. Lưu ý nếu x[1] > x[len] thì kết quả phải trừ đi 1.

LCSUB - Dãy con có giá trị liên tiếp dài nhất

Sắp xếp lại dãy tăng dần

Quy hoạch động f(i, 0) là độ dài dãy con lớn nhất có các phần tử có giá trị liên tiếp kết thúc tại i, f(i, 1) là độ dài dãy con lớn nhất có các phần tử có giá trị liên tiếp bắt đầu tại i

Nếu trong dãy không có phần tử giá trị 0 thì kết quả là max(f(i, 0)). Ngược lại, ta có thể tăng độ dài dãy con lớn nhất có các phần tử có giá trị liên tiếp bằng cách nối phần tử có giá trị 0 với đầu, cuối của 1 dãy con có các phần tử có giá trị liên tiếp hoặc nối 2 dãy con con có các phần tử có giá trị liên tiếp. Để dễ hiểu, gọi res là kết quả bài toán, ta có:

res = max(res, f(i, 0) + 1) với 1 <= i <= n và a[i] khác n (tức là gán phần tử có giá trị 0 bằng a[i] + 1 và a[i] + 1 chưa xuất hiện trong dãy)

res = max(res, f(i, 1) + 1) với 1 <= i <= n và a[i] khác 1 (tức là gán phần tử có giá trị 0 bằng a[i] - 1 và a[i] - 1 chưa xuất hiện trong dãy)

res = max(res, f(i, 0) + 1 + f(j, 1)) với 1 <= i < j <= n và a[j] - a[i] = 2 (tức là gán phần tử có giá trị 0 bằng a[i] + 1 và a[i] + 1 chưa xuất hiện trong dãy)

ROBOT5 - Robot đi tuần

Dễ thấy robot có di chuyển đến tọa độ nào thì tích của tung độ và hoành độ là không đổi

Nếu robot nằm trong vòng tròn mà rada quét thì khoảng cách từ tâm tới tọa độ robot phải <= bán kính, nghĩa là nếu robot đang ở vị trí (x, y) thì x2 + y2 <= c2

Mà x >= 0, y >= 0 nên theo bất đẳng thức AM-GM ta có x2 + y2 >= 2xy

Vì vậy chỉ cần kiểm tra nếu c2 > 2xy thì robot nằm trong vùng nguy hiểm.

AGEGAME - Trò chơi đoán tuổi

Dễ thấy chỉ cần đoán các số nguyên tố trong đoạn [2; n] thì sẽ loại được những số chia hết cho số nguyên tố đó. Tuy nhiên đây chưa phải cách tối ưu nhất, ví dụ với n = 6, thay vì đoán 2, 3, 5 ta có thể đoán 6 ( = 2 x 3) rồi đoán 5, vì vậy ta chia các số nguyên tố trong đoạn [2; n] thành các nhóm sao cho tích của mỗi nhóm <= n và số nhóm là ít nhất, lúc này kết quả là số nhóm chia được.

CÁC PHẢN HỒI

  • trevorjoker - 28/05/16 23:00
    mình thấy bài ROBOT5 có vấn đề rồi, bạn phải chứng minh dãy x và dãy y là 2 dãy hội tụ và cả 2 dãy đều hội tụ về giá trị căn xy. Vì vậy trong trường hợp c * c > 2 * x * y thì luôn có 1 lúc nào đó máy ra đa quét qua điểm (x, y) nhưng nếu c * c = 2 * x * y và x y khác nhau thì sẽ không thể có lúc nào ra đa quét qua điểm (x, y) được vì y > x
  • middlest - 28/05/16 23:06
    @trevorjoker: em quên mất lúc đó x phải bằng y rồi, cảm ơn anh
  • hoangvuduyanh - 29/05/16 00:11
    bài LCSUB duyệt two pointer cũng đc mak
  • vdn1999bxvp - 29/05/16 06:37
    @hoangvuduyanh: bài LCSUB chặt nhị phân cũng đc mak =]]
  • nhokphuthuy - 29/05/16 16:10
    huhu mất điểm bài A chỉ vì hình vẽ sai
  • phuleethanh - 30/05/16 18:44
    Bai LCSUB: minh sort, roi chia ra nhung doan phan tu lien tiep, tu cac doan nay minh chen them so 0 vao xem the nao. Cach nay kha don gian
  • phuleethanh - 30/05/16 18:46
    Bai ROBOT5 minh dong y voi y kien cua trevorjorker: hai day nay hoi tu, den mot luc nao do x va y se hoi tu, dan den kc tu (x,y) den goc toa do gan nhu ko thay doi --> ta co the ket luan la SAFE hoac DANGER. Bai nay cai bang dequy cung kha la dep
  • cong8a3tdn2017 - 07/10/17 16:30
    bai nam nay kho vai cut ********
  • hieu8a3tdn2017 - 07/10/17 16:31
    dung roi kho vcl ******************** bo may so may qua co
  • minhhien - 07/05/21 21:13
    Bài ROBOT5 có phải nhảy vào ô có tọa độ không nguyên không?
    vì xy không đổi, nên cần tìm x*x+y*y min.
    nếu chỉ nhảy vào điểm nguyên nó là 1 bài toán khác.
    Vì ta cần tìm x.y = a và |x-y| nhỏ nhất, khi đó chưa chắc điều kiện c*c > 2*x*y đã là SAFE.
  • tiendat0604 - 14/10/21 08:04
    yuffu
Back to Top