FUHO - Đi học nghề phụ hồ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Là một người mới vào nghề phụ hồ, thầy Lộc fuho cho bạn một bài tập:
Khách hàng muốn đưa nhiều nhất các ô của sổ hình vuông có độ dài ~K~ vào bức tường hình vuông dài ~N~.
Hãy vẽ một bản thiết kế và đếm số lượng cửa sổ có thể đặt vào (các cửa sổ có thể đặt sát nhau).
Input
Dòng đầu gồm một số ~T~ - số bộ test (~1 \le T \le 100~)
~T~ dòng tiếp theo gồm hai số cách nhau bằng một dấu cách lần lượt là:
- ~N~ - độ dài của bước tường hình vuông (~1 \le N \le 10^5~)
- ~K~ - độ dài của ô cửa sổ hình vuông (~1 \le K \le 100~)
Output
Gồm ~T~ dòng, mỗi dòng gồm một số là kết quả của mỗi test
Sample
Input #1
4
5 1
3 3
4 3
9 10
Output #1
25
1
1
0
Hint
Test 1: Vì ô cửa số có độ dài là 1 nên có thể lấp kín tường
Test 4: Độ dài của sổ lớn hơn cả bức tường nên không thể thêm và được
Bình luận
Ý tưởng: Các bạn đọc để và test chắc hẳn sẽ nghĩ đến việc tính diện tích bước tường, sau đó chia ra cho diện tích của cửa sổ để ra được số lượng cửa sổ có thể lắp.
Ok! tư duy không sai, xong nếu bạn vẫn chưa AC được bài thì vấn đề nằm cách tính. Nếu cách tính của bạn là N^2 // K^2 thì bản chất là đúng, nhưng không thể AC. Bạn cần biến biểu thức kia trở lên tối ưu hơn đó là (N // K) * (N // K). khi đó số N (có thể bộ test của N rất lớn) sẽ được giảm bớt K lần, sau đó mới được nhân lại với nhau. Nếu bạn làm thế này N^2 // K^2, khi gặp test lớn sẽ tràn số mất.
Có rất nhiều bài các bạn không thể AC, không phải vì cách tư duy sai, mà vấn để nằm ở cách xử lý số. Tin học khác toán học ở chỗ đó, 2 biểu thức cùng 1 ý nghĩa, xong có cái cách tính tối ưu hơn hẳn cái còn lại.
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG