แนวคิด
สำหรับถ้วยที่แตกต่างกัน 3 ประเภท (p[]) และจานรอง (q[]) และจำนวนชั้นวาง m ให้พิจารณาว่าสามารถจัดถ้วยและชั้นวางได้อย่างเหมาะสมหรือไม่
ตอนนี้การจัดถ้วยและจานรองจะเรียบร้อยหากเป็นไปตามกฎต่อไปนี้ −
- ตามกฎข้อแรก ไม่มีชั้นวางใดที่สามารถมีทั้งถ้วยและจานรองได้
- ตามกฎข้อที่สอง ชั้นวางใดก็ได้ในชั้นวางไม่เกิน 5 ถ้วย
- ตามกฎข้อที่สาม มีจานรองได้ไม่เกิน 10 ใบในชั้นใดก็ได้
อินพุต
p[] = {4, 3, 7}
q[] = {5, 9, 10}
m = 11 ผลลัพธ์
Yes
คำอธิบาย
ถ้วยทั้งหมด =14 ชั้นวางที่ต้องการ =3
จำนวนจานรอง =24 ชั้นวางที่ต้องการ =3
ดังนั้น ชั้นวางที่ต้องการทั้งหมด =3 + 3 =6,
ซึ่งน้อยกว่าจำนวนชั้นวางที่กำหนด m. ผลลัพธ์คือใช่
อินพุต
p[] = {5, 8, 5}
q[] = {4, 10, 11}
m = 3 ผลลัพธ์
No
ถ้วยทั้งหมด =18 ชั้นวางที่ต้องการ =4
จำนวนจานรอง =25 ชั้นวางที่ต้องการ =3
จำนวนชั้นวางที่ต้องการทั้งหมด =4 + 3 =7
ซึ่งมากกว่าจำนวนชั้นวางที่กำหนด m. ผลลัพธ์คือ No.
วิธีการ
สำหรับการจัดเรียงถ้วยและจานรอง ให้กำหนดจำนวนถ้วยทั้งหมด p และจำนวนจานรอง q เนื่องจากไม่สามารถใส่ถ้วยได้มากกว่า 5 ถ้วยในชั้นวางเดียวกัน ดังนั้นให้กำหนดจำนวนชั้นวางสูงสุดที่ต้องการสำหรับถ้วยตามสูตร (p+5-1)/5 และจำนวนชั้นวางสูงสุดที่จำเป็นสำหรับจานรองโดยใช้สูตร ( ค+10-1)/10. จะเห็นได้ว่าหากผลรวมของสองค่านี้เท่ากับหรือน้อยกว่า m การจัดเรียงก็เป็นไปได้อย่างอื่นไม่
ตัวอย่าง
// 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;
} ผลลัพธ์
Yes
