Khái niệm
Cho ba loại cốc (p[]) và ba loại bát (q[]), cùng m kệ. Xác định xem có thể sắp xếp cốc và bát gọn gàng không.
Sắp xếp gọn gàng nếu tuân theo:
- Quy tắc 1: Không kệ nào chứa cả cốc và bát.
- Quy tắc 2: Mỗi kệ chứa tối đa 5 cốc.
- Quy tắc 3: Mỗi kệ chứa tối đa 10 bát.
Đầu vào
p[] = {4, 3, 7} q[] = {5, 9, 10} m = 11
Đầu ra
Yes
Giải thích
Tổng cốc = 14, kệ cần = 3
Tổng bát = 24, kệ cần = 3
Tổng kệ cần = 6, nhỏ hơn m = 11. Kết quả Yes.
Đầu vào
p[] = {5, 8, 5} q[] = {4, 10, 11} m = 3
Đầu ra
No
Tổng cốc = 18, kệ cần = 4
Tổng bát = 25, kệ cần = 3
Tổng kệ cần = 7, lớn hơn m = 3. Kết quả No.
Phương pháp
Tính tổng cốc p và tổng bát q. Vì mỗi kệ tối đa 5 cốc, số kệ cho cốc = (p+5-1)/5. Tương tự cho bát: (q+10-1)/10. Nếu tổng hai giá trị này <= m thì sắp xếp được, ngược lại không.
Ví dụ
// C++ kiểm tra sắp xếp cốc và kệ gọn gàng
#include<bits/stdc++.h>
using namespace std;
void canArrange1(int p[], int q[], int m){
int sump = 0, sumq = 0;
for(int i = 0; i < 3; i++) sump += p[i];
for(int i = 0; i < 3; i++) sumq += q[i];
int mp = (sump + 5 - 1) / 5;
int mq = (sumq + 10 - 1) / 10;
if(mp + mq <= m)
cout << "Yes";
else
cout << "No";
}
int main(){
int p[] = {4, 3, 7};
int q[] = {5, 9, 10};
int m = 10;
canArrange1(p, q, m);
return 0;
}
Đầu ra
Yes