| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P192PROH - Problem H - Ghép hình chữ nhật |
Cho N hình chữ nhật với kích thước cho trước. Cần ghép cả N hình chữ nhật này thỏa mãn điều kiện sau:
- N hình chữ nhật nhỏ ghép được thành một hình chữ nhật lớn.
- Được phép xoay hình tùy ý.
- Không có 2 hình chữ nhật nhỏ nào chồng lên nhau, hay nói cách khác, tổng diện tích các hình chữ nhật nhỏ sẽ đúng bằng diện tích hình chữ nhật lớn.
Có bao nhiêu hình chữ nhật khác nhau có thể ghép được? Hai hình chữ nhật được coi là khác nhau nếu không thể có cách xoay nào để biến 1 hình thành hình còn lại.
Input
Dòng đầu tiên chứa 1 số nguyên T duy nhất là số bộ test (1 ≤ T ≤ 1000).
Mỗi bộ test có dạng như sau:
- Dòng thứ nhất chứa 1 số nguyên N là số hình chữ nhật con (2 ≤ N ≤ 4).
- N dòng tiếp theo, dòng thứ i chứa 2 số nguyên ai, bi; lần lượt là chiều dài và chiều rộng của hình chữ nhật con thứ i (1 ≤ ai, bi ≤ 15).
Output
- Với mỗi bộ test, in ra trên 1 dòng duy nhất 1 số nguyên là số hình chữ nhật lớn khác nhau ghép được.
Example
Input 1 3 1 2 1 1 3 1 Output 2
Giải thích
Chỉ có 2 hình chữ nhật thỏa mãn, đó là hình chữ nhật kích thước 1x6 và 2x3.
| Được gửi lên bởi: | adm |
| Ngày: | 2019-02-23 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
