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.
