Khái niệm
Đối với ba loại cốc khác nhau (p []) và đĩa (q []), và m số kệ, hãy xác định xem có thể sắp xếp ngăn nắp các cốc và kệ hay không.
Giờ đây, việc sắp xếp cốc và đĩa sẽ gọn gàng nếu tuân theo các quy tắc sau -
- Theo quy tắc đầu tiên, không có kệ nào có thể chứa cả cốc và đĩa.
- Theo quy tắc thứ hai, không được có quá 5 cốc trong bất kỳ kệ nào.
- Theo quy tắc thứ ba, không được có nhiều hơn 10 đĩa trong bất kỳ kệ nào.
Đầu vào
p[] = {4, 3, 7}
q[] = {5, 9, 10}
m = 11 Đầu ra
Yes
Giải thích
Tổng số cốc =14, số kệ cần thiết =3
Tổng số đĩa =24, giá bắt buộc =3
Vì vậy, tổng số kệ cần thiết =3 + 3 =6,
nhỏ hơn số kệ đã cho m. Vì vậy, đầu ra là Có.
Đầu vào
p[] = {5, 8, 5}
q[] = {4, 10, 11}
m = 3 Đầu ra
No
Tổng số cốc =18, số kệ cần thiết =4
Tổng số đĩa =25, giá bắt buộc =3
Vì vậy, tổng số kệ cần thiết =4 + 3 =7,
lớn hơn số kệ cho trước m. Vì vậy, đầu ra là Không.
Phương pháp
Để sắp xếp các cốc và đĩa, hãy xác định tổng số cốc p và tổng số đĩa q. Bởi vì, không thể có nhiều hơn 5 cốc trong kệ sames, do đó hãy xác định số giá tối đa cần thiết cho cốc theo công thức (p + 5-1) / 5 và số giá tối đa cần cho đĩa bằng cách thực hiện công thức ( q + 10-1) / 10. Có thể thấy rằng nếu tổng của hai giá trị này bằng hoặc nhỏ hơn m thì có thể sắp xếp được nếu không.
Ví dụ
// C++ code to find if neat
// arrangement of cups and
// shelves can be made
#include<bits/stdc++.h>
using namespace std;
// Shows function to check arrangement
void canArrange1(int p[], int q[], int m){
int sump = 0, sumq = 0;
// Used to calculate total number
// of cups
for(int i = 0; i < 3; i++)
sump += p[i];
// Used to calculate total number
// of saucers
for(int i = 0; i < 3; i++)
sumq += q[i];
// Now adding 5 and 10 so that if the
// total sum is smaller than 5 and
// 10 then we can get 1 as the
// answer and not 0
int mp = (sump + 5 - 1) / 5;
int mq = (sumq + 10 - 1) / 10;
if(mp + mq <= m)
cout << "Yes";
else
cout << "No";
}
// Driver code
int main(){
// Shows number of cups of each type
int p[] = {4, 3, 7};
// Shows number of saucers of each type
int q[] = {5, 9, 10};
// Shows number of shelves
int m = 10;
// ndicates calling function
canArrange1(p, q, m);
return 0;
} Đầu ra
Yes