RTF - Cân thăng bằng
Giới hạn- Thời gian: 0.173s
- Bộ nhớ: 1536MB
- Mã nguồn: 5000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Có 1 bộ N loại quả cân , loại quả i nặng A[i] kg . Một bộ con của bộ N quả cân gồm k loại quả cân là A[i1] , A[i2] , … A[ik] gọi là thay thế được bộ N loại quả cân trên nếu như tồn tại hệ đẳng thức sau :
- A[1] = A[i1] * H[1][1] + … + A[ik] * H[1][k]
- A[2] = A[i1] * H[2][1] + … + A[ik] * H[2][k]
- …
- A[N] = A[i1] * H[N][1] + … + A[ik]* H[N][k]
Trong đó H[i][j] là các số nguyên .
Hãy tìm bộ quả cân thay thế được cho bộ N quả cân với số phần tử là nhỏ nhất .
Input
Dòng 1 là số nguyên T là số bộ test ( 1 ≤ T ≤ 100 ) . Các dòng tiếp theo mô tả T bộ test , mỗi bộ test gồm 2 dòng :
Dòng 1 : Số nguyên dương N ( N ≤ 100 ) .
Dòng 2 : N số nguyên dương A[1] , … , A[N] ( A[i] ≤ 60000 )
Output
Với mỗi bộ test ghi ra 1 số nguyên dương là số lượng quả cân của nhóm tìm được .
Example
Input: 1 3 2 3 4 Output: 2
- Người up: hard7771988