Trám Đen
Đề bài
Hiên, một huyện miền núi phía tây Quảng Nam có rất nhiều quả trám. Các bạn Sinh viên Tình nguyện Mùa hè xanh thấy hột trám vương vãi quanh trường khá nhiều, đã nảy ra sáng kiến "trám hóa" sân trường. Có $k$ hạt trám được thu thập về.
Sân trường có hình chữ nhật. Bằng $m$ đường cách đều nhau song song với một cạnh của sân trường và $n$ đường cách đều nhau song song với cạnh kia của sân trường, toàn bộ sân được chia thành các hình chữ nhật con giống nhau $(1 \le m \le n)$.
Các hột trám sẽ được chặt đôi. Sau khi ăn nhân bên trong, học sinh sẽ đóng nửa hạt này xuống sân tại các điểm giao nhau giữa các đường kẻ và ở tâm các hình chữ nhật con. Tại mỗi điểm chỉ đóng nửa hạt trám.
Để không lãng phí số hạt trám đã thu nhặt và hạt trám được đóng phân bố đều trên sân, các bạn sinh viên quyết định chọn $m$ và $n$ sao cho số hạt trám sẽ được dùng hết và hiệu $n - m$ là nhỏ nhất.
Với $k$ cho trước hãy xác định $m$ và $n$. Nếu không tồn tại $m$ và $n$ thỏa mãn thì đưa ra số $-1$.
Dữ liệu vào: là một số nguyên dương $k$ $(1 \le k \le 10^{12})$.
Dữ liệu ra: gồm 2 số nguyên $m$ và $n$ cách nhau một khoảng trắng. Nếu không có kết quả in ra $-1$. Lưu ý là phải dùng hết số trám, không được dư dù chỉ $\frac{1}{2}$ quả.
Subtask:
- 20% số test đầu tiên có $k \le 10^2$.
- 30% số test tiếp theo có $k \le 10^6$.
- 30% số test tiếp theo có $k \le 10^9$.
- 20% số test còn lại có $k \le 10^{12}$.
92 36-1Giải thích ví dụ 1: với $m = 2$ đường ngang và $n = 3$ đường dọc, sân chia thành $3 \times 4 = 12$ hình chữ nhật con (12 tâm) và có $2 \times 3 = 6$ giao điểm. Tổng cộng $18$ điểm, mỗi điểm nửa hạt, đúng $9$ hạt trám. Ví dụ 2: không có cách chọn nào dùng hết đúng 6 hạt.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm thêm đó là toàn bộ tin nhắn của mình với em ấy, để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bước 1Đếm số điểm đóng trám
Trước khi đọc tin nhắn, mình cùng đếm lại cho chắc nha. $m$ đường song song chia sân thành $m + 1$ dải, $n$ đường song song cạnh kia chia thành $n + 1$ dải, nên:
- Số hình chữ nhật con (số tâm) là $(m + 1)(n + 1)$.
- Số giao điểm giữa các đường kẻ là $m \cdot n$ (mỗi đường này cắt mỗi đường kia đúng 1 lần, không tính đường biên sân).
Mỗi điểm đóng nửa hạt, $k$ hạt là $2k$ nửa hạt, và phải dùng hết nên:
Em thử đổi $m$, $n$ rồi bấm chạy để thấy từng loại điểm hiện ra:
Gợi ý cho em: hãy đưa bài toán về dạng $A \times B = C$. Có được $C$ rồi thì tìm $A$, $B$ thì $A$, $B$ sẽ là cặp ước của $C$. Từ đó rất đơn giản để xét hết tất cả các cặp $A$, $B$ thoả mãn.
Bước 2Biến đổi về dạng A × B = C
Có phải em đã tìm ra công thức là $(m + 1)(n + 1) + m \cdot n = 2k$ đúng không? $k$ thì đề đã cho, giờ cần tìm $m$, $n$. Hãy cố gắng biến đổi phương trình về dạng $A \times B = C$, với $C$ là số có sẵn, $A$, $B$ là số cần tìm (trong trường hợp này là $m$, $n$). Giả sử tìm được $A$ và giả sử trước đó em đã đặt $A = m + 1$ chẳng hạn thì nghĩa là $m = A - 1$.
Ở mức độ gợi ý thì anh chỉ nói đến đây thôi chứ nói thêm sâu nữa thì ra hết luôn rồi.
Vậy anh cho em thấy hen:
Đến đây chắc em đã nhận ra rồi :))
- $C = 4k - 1$ luôn là số lẻ, nên mọi ước của nó đều lẻ và $A - 1$, $B - 1$ luôn chia hết cho 2. Code bên dưới vẫn kiểm tra điều kiện chẵn cho chắc ăn.
- $m \ge 1$ nên $A \ge 3$: phải bỏ cặp $A = 1$ (ứng với $m = 0$, không có đường kẻ nào).
- Ví dụ $k = 9$: $C = 35 = 5 \times 7$, nên $m = 2$, $n = 3$ ✓. Ví dụ $k = 6$: $C = 23$ là số nguyên tố, chỉ có cặp $1 \times 23$ bị loại, nên in $-1$ ✓.
Bước 3Duyệt ước trong O(√C)
Không cần duyệt $i$ từ 1 đến $C$ đâu em. Ước số luôn đi theo cặp: nếu $i$ chia hết $C$ thì $\frac{C}{i}$ cũng là ước, và trong mỗi cặp luôn có một thằng $\le \sqrt{C}$. Vậy chỉ cần cho $i$ chạy từ 1 tới khi $i \cdot i \le C$, mỗi lần $C$ chia hết cho $i$ thì ta có luôn cặp $(i, \frac{C}{i})$. Với $k \le 10^{12}$ thì $C < 4 \cdot 10^{12}$, $\sqrt{C} < 2 \cdot 10^6$, chạy vèo vèo. Ở trong bài anh viết trước đây thì anh chỉ tạo biến đếm, nhưng em vẫn có thể lấy ra được 2 ước số của mỗi lần là gì.
Em nhập $k$ rồi bấm Tiếp để xem từng cặp ước được xét (mình chỉ dừng lại ở các $i$ là ước của $C$):
CodeKhông cần mảng
Em ấy làm ra và gửi code nhờ anh tối ưu giúp:
Code của em học viên (dùng mảng)
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long long k;
cin >> k;
k = 4 * k - 1;
long long a[100000], index = 0, b[100000];
long long temp, vitri = -1, mdiff = 1000000000, diff, length = sqrt(k);
for (long long i = 1; i <= length; i++)
{
if (k % i == 0)
{
temp = k / i;
a[index] = (i - 1) / 2;
b[index] = (temp - 1) / 2;
if (a[index] > b[index])
{
break;
}
diff = b[index] - a[index];
if (diff <= mdiff)
{
mdiff = diff;
vitri = index;
}
index = index + 1;
}
}
if (vitri == -1 || a[vitri] == 0 || b[vitri] == 0)
{
cout << -1;
}
else
{
cout << a[vitri] << " " << b[vitri];
}
}Ủa phải dùng mảng sao? 🤪 Làm gì phức tạp đến mức phải dùng mảng ta? Anh không cần dùng mảng gì cả.
Chỉ cần 2 biến m, n lưu cặp tốt nhất hiện tại. Mỗi cặp ước mới tìm được thì so độ chênh b - a của nó với n - m của cặp đang lưu, nhỏ hơn thì thay. Biến m = -1 nghĩa là chưa có cặp nào.
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ với em chứ chưa có clean đâu nha. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long k, m, n;
cin >> k;
k = 4 * k - 1;
m = n = -1;
for(long long i = 1; i * i <= k; ++i){
if(k % i == 0){
long long a = i;
long long b = k / a;
if((a - 1) % 2 == 0 && (b - 1) % 2 == 0){
a = (a - 1) / 2;
b = (b - 1) / 2;
if(a != 0 && b != 0 && (m == -1 || b - a < n - m)){
m = a;
n = b;
}
}
}
}
if(m != -1){
cout << m << " " << n;
}
else{
cout << -1;
}
return 0;
}k = int(input())
k = 4 * k - 1
m = n = -1
i = 1
while i * i <= k:
if k % i == 0:
a = i
b = k // a
if (a - 1) % 2 == 0 and (b - 1) % 2 == 0:
a2 = (a - 1) // 2
b2 = (b - 1) // 2
if a2 != 0 and b2 != 0 and (m == -1 or b2 - a2 < n - m):
m = a2
n = b2
i += 1
if m != -1:
print(m, n)
else:
print(-1)Có một nhận xét giúp code gọn và nhanh hơn: khi $A$ tăng (vẫn $\le \sqrt{C}$) thì $B = \frac{C}{A}$ giảm, nên độ chênh $B - A$ giảm dần. Vậy cặp tốt nhất chính là ước lớn nhất $\le \sqrt{C}$. Ta có thể duyệt ngược $A$ từ $\lfloor\sqrt{C}\rfloor$ xuống 3, gặp ước đầu tiên là dừng luôn:
from math import isqrt
k = int(input())
C = 4 * k - 1 # (2m+1)(2n+1) = 4k-1, luôn là số lẻ
# A = 2m+1 <= B = 2n+1 nên A <= căn(C); A càng lớn thì n-m càng nhỏ
# => duyệt A từ căn(C) giảm dần, gặp ước đầu tiên (A >= 3) là dừng
ans = None
for A in range(isqrt(C), 2, -1):
if C % A == 0:
ans = ((A - 1) // 2, (C // A - 1) // 2)
break
print(*ans) if ans else print(-1)Đọc chắc cũng mỏi mắt luôn chứ, vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 😅. Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này 🤪.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét