Hướng dẫn giải của [Beginner Free Contest 02] SQUARE
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Với mỗi trường hợp, tìm ~T~ lớn nhất sao cho tồn tại ~H \in [H_{min}, H_{max}]~ và ~W \in [W_{min}, W_{max}]~ cùng chia hết cho ~T~. Tức là ~T~ có một bội trong khoảng chiều cao và một bội trong khoảng chiều rộng; điều kiện đó viết được là ~\lfloor H_{max}/T \rfloor > \lfloor (H_{min}-1)/T \rfloor~ và tương tự cho ~W~.
Sub 1: Thử ~T~ từ lớn xuống nhỏ — dùng khi ~H_{max}, W_{max} \le 10^6~
Bắt đầu từ ~T = \min(H_{max}, W_{max})~ giảm dần cho đến khi điều kiện trên thỏa (~T=1~ luôn thỏa). Mỗi trường hợp ~O(\min(H_{max}, W_{max}))~ bước. Nếu chỉ nộp sub này: đúng 20/100 test.
Sub 2: Duyệt theo khối thương — ~O(\sqrt{H_{max}})~ mỗi trường hợp
Bốn thương ~\lfloor x/T \rfloor~ (với ~x = H_{max}, H_{min}-1, W_{max}, W_{min}-1~) chỉ đổi giá trị ~O(\sqrt{x})~ lần khi ~T~ chạy. Trong một khối ~T~ mà cả bốn thương không đổi thì điều kiện thỏa/không thỏa là như nhau, nên đi từ ~T~ lớn xuống theo từng khối (đầu mút trái khối là lớn nhất trong các ~x/(x/T+1)+1~) và chỉ kiểm tra đầu mút phải; khối thỏa đầu tiên cho đáp án. Dùng số nguyên 32 bit không dấu cho phép chia để chạy nhanh. Nếu chỉ nộp sub này: đúng 100/100 test.
Chương trình hoàn chỉnh
Main đọc ~N~ trường hợp (máy chấm dùng đọc/ghi chuẩn), dữ liệu nhỏ gọi sub1, lớn gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int N;
long long hmin[1005], hmax[1005], wmin[1005], wmax[1005];
// T tốt nếu tồn tại bội của T trong [hmin, hmax] và trong [wmin, wmax]
inline bool good(long long T, long long h1, long long h2, long long w1, long long w2) {
return h2 / T > (h1 - 1) / T && w2 / T > (w1 - 1) / T;
}
// Sub 1: thử T từ lớn xuống nhỏ — O(min(Hmax,Wmax)) mỗi trường hợp, dùng khi Hmax, Wmax <= 10^6
void sub1() {
for (int i = 0; i < N; i++) {
long long T = min(hmax[i], wmax[i]);
while (!good(T, hmin[i], hmax[i], wmin[i], wmax[i])) T--;
printf("%lld\n", T);
}
}
// Sub 2: các giá trị floor(x/T) của 4 số hmax, hmin-1, wmax, wmin-1 chỉ đổi O(sqrt) lần theo T.
// Đi T từ lớn xuống nhỏ theo từng khối mà cả 4 thương đều không đổi: điều kiện "good" không đổi
// trong khối, nên chỉ cần kiểm tra T = đầu mút phải của khối; gặp khối thỏa đầu tiên thì dừng.
void sub2() {
for (int i = 0; i < N; i++) {
unsigned x[4] = {(unsigned)hmax[i], (unsigned)(hmin[i] - 1), (unsigned)wmax[i], (unsigned)(wmin[i] - 1)};
unsigned T = min(x[0], x[2]);
while (true) {
if (x[0] / T > x[1] / T && x[2] / T > x[3] / T) break;
unsigned l = 1;
for (int t = 0; t < 4; t++) l = max(l, x[t] / (x[t] / T + 1) + 1); // đầu mút trái khối
T = l - 1; // T >= 1 vì T=1 luôn thỏa
}
printf("%u\n", T);
}
}
int main() {
scanf("%d", &N);
long long mx = 0;
for (int i = 0; i < N; i++) {
scanf("%lld %lld %lld %lld", &hmin[i], &hmax[i], &wmin[i], &wmax[i]);
mx = max(mx, max(hmax[i], wmax[i]));
}
if (mx <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận