日期：2026年3月8日
ZeroJudge 題目連結：c110. 00311 - Packets
解題想法
如果面積 $6 \times 6$ 的商品數量為 $n_6$，需要的箱子數量就是 $n_6$，而且沒有剩下的空間。 如果面積 $5 \times 5$ 的商品數量為 $n_5$，需要的箱子數量為 $n_5$，每一個箱子會剩下面積為 $11$ 的空間，總空間為 $11 n_5$，可以放入面積 $1 \times 1$ 的商品。 如果面積 $4 \times 4$ 的商品數量為 $n_4$，需要的箱子數量為 $n_4$，每一個箱子會剩下面積為 $20$ 的空間，總空間為 $20 n_4$，可以放入面積 $2 \times 2$ 的商品最多 $5$ 個，如果還有剩下的空間，可以再放入面積 $1 \times 1$ 的商品。下圖的 O 代表可用空間，X 代表已被面積 $4 \times 4$ 商品佔用的空間。
OOOOOO
OOOOOO
XXXXOO
XXXXOO
XXXXOO
XXXXOO
OOOOOO OOOOOO XXXOOO
OOOOOO OOOOOO XXXOOO
OOOOOO OOOOOO XXXOOO
XXXOOO XXXXXX XXXXXX
XXXOOO XXXXXX XXXXXX
XXXOOO XXXXXX XXXXXX
Python 程式碼
使用時間約為 10 ms，記憶體約為 3.2 MB，通過測試。
import sys
for line in sys.stdin:
if not line.strip(): continue
n1, n2, n3, n4, n5, n6 = map(int, line.split())
if n1 == 0 and n2 == 0 and n3 == 0 and n4 == 0 and n5 == 0 and n6 == 0: break
""" 放入 5*5 的商品 """
s5 = 11*n5 # 放 5*5 商品箱子剩下的空間
if s5 >= n1: # 可以放入所有 1*1 商品
s5 -= n1; n1 = 0
else: # 無法放入所有 1*1 商品
n1 -= s5; s5 = 0
""" 放入 4*4 的商品 """
s4 = 20*n4 # 放 4*4 商品箱子剩下的空間
if s4 >= n2*4: # 可以放入所有 2*2 商品
s4 -= n2*4; n2 = 0
else: # 無法放入所有 2*2 商品
n2 -= s4//4; s4 = 0
if s4 > 0 and n1 > 0: # s4 還有空間而且還有 1*1 商品要放
if s4 >= n1: # 可以放入所有 1*1 商品
s4 -= n1; n1 = 0
else: # 無法放入所有 1*1 商品
n1 -= s4; s4 = 0
""" 放入 3*3 的商品 """
r3 = n3%4 # 沒放滿的箱子中 3*3 商品數量
p3 = n3//4 + (r3 > 0) # 3*3 商品使用的箱子數量
s3 = 0 # 沒放滿的箱子剩下的面積
if r3 == 1: # 放 1 個 3*3 商品
s3 = 27 # 面積剩下 27
if n2 <= 5: # 可以放入所有 2*2 商品
s3 -= n2*4; n2 = 0
else: # 無法放入所有 2*2 商品
s3 -= 20; n2 -= 5
elif r3 == 2: # 放 2 個 3*3 商品
s3 = 18 # 面積剩下 18
if n2 <= 3: # 可以放入所有 2*2 商品
s3 -= n2*4; n2 = 0
else: # 無法放入所有 2*2 商品
s3 -= 12; n2 -= 3
elif r3 == 3: # 放 3 個 3*3 商品
s3 = 9 # 面積剩下 9
if n2 == 1: # 可以放入所有 2*2 商品
s3 -= 4; n2 = 0
elif n2 > 1: # 無法放入所有 2*2 商品
s3 -= 4; n2 -= 1
if s3 > 0 and n1 > 0: # s3 還有空間而且還有 1*1 商品要放
if s3 >= n1: # 可以放入所有 1*1 商品
s3 -= n1; n1 = 0
else: # 無法放入所有 1*1 商品
n1 -= s3; s3 = 0
""" 放入 2*2 的商品 """
r2 = n2%9 # 沒放滿的箱子中 3*3 商品數量
p2 = n2//9 + (r2 > 0) # 2*2 商品使用的箱子數量
s2 = 0 if r2 == 0 else 36 - r2*4 # 沒放滿的箱子剩下的面積
if s2 > 0 and n1 > 0: # s2 還有空間而且還有 1*1 商品要放
if s2 >= n1: # 可以放入所有 1*1 商品
s2 -= n1; n1 = 0
else: # 無法放入所有 1*1 商品
n1 -= s2; s2 = 0
""" 放入 1*1 的商品 """
p1 = n1//36 + (n1%36 > 0)
""" 印出答案 """
print(p1 + p2 + p3 + n4 + n5 + n6)
C++ 程式碼
使用時間約為 1 ms，記憶體約為 52 kB，通過測試。
#include <cstdio>
int main() {
int n1, n2, n3, n4, n5, n6;
while(scanf("%d %d %d %d %d %d", &n1, &n2, &n3, &n4, &n5, &n6) != EOF) {
if (n1 == 0 && n2 == 0 && n3 == 0 && n4 == 0 && n5 == 0 && n6 == 0) break;
/* 放入 5*5 的商品 */
int s5 = 11*n5; // 放 5*5 商品箱子剩下的空間
if (s5 >= n1) { // 可以放入所有 1*1 商品
s5 -= n1; n1 = 0;
} else { // 無法放入所有 1*1 商品
n1 -= s5; s5 = 0;
}
/* 放入 4*4 的商品 */
int s4 = 20*n4; // 放 4*4 商品箱子剩下的空間
if (s4 >= n2*4) { // 可以放入所有 2*2 商品
s4 -= n2*4; n2 = 0;
} else { // 無法放入所有 2*2 商品
n2 -= s4/4; s4 = 0;
}
if (s4 > 0 && n1 > 0) { // s4 還有空間而且還有 1*1 商品要放
if (s4 >= n1) { // 可以放入所有 1*1 商品
s4 -= n1; n1 = 0;
} else { // 無法放入所有 1*1 商品
n1 -= s4; s4 = 0;
}
}
/* 放入 3*3 的商品 */
int r3 = n3%4; // 沒放滿的箱子中 3*3 商品數量
int p3 = n3/4 + (r3 > 0); // 3*3 商品使用的箱子數量
int s3 = 0; // 沒放滿的箱子剩下的面積
if (r3 == 1) { // 放 1 個 3*3 商品
s3 = 27; // 面積剩下 27
if (n2 <= 5) { // 可以放入所有 2*2 商品
s3 -= n2*4; n2 = 0;
} else { // 無法放入所有 2*2 商品
s3 -= 20; n2 -= 5;
}
} else if (r3 == 2) { // 放 2 個 3*3 商品
s3 = 18; // 面積剩下 18
if (n2 <= 3) { // 可以放入所有 2*2 商品
s3 -= n2*4; n2 = 0;
} else { // 無法放入所有 2*2 商品
s3 -= 12; n2 -= 3;
}
} else if (r3 == 3) { // 放 3 個 3*3 商品
s3 = 9; // 面積剩下 9
if (n2 == 1) { // 可以放入所有 2*2 商品
s3 -= 4; n2 = 0;
} else if (n2 > 1) { // 無法放入所有 2*2 商品
s3 -= 4; n2--;
}
}
if (s3 > 0 && n1 > 0) { // s3 還有空間而且還有 1*1 商品要放
if (s3 >= n1) { // 可以放入所有 1*1 商品
s3 -= n1; n1 = 0;
} else { // 無法放入所有 1*1 商品
n1 -= s3; s3 = 0;
}
}
/* 放入 2*2 的商品 */
int r2 = n2%9; // 沒放滿的箱子中 3*3 商品數量
int p2 = n2/9 + (r2 > 0); // 2*2 商品使用的箱子數量
int s2 = (r2 == 0 ? 0 : 36 - r2*4); // 沒放滿的箱子剩下的面積
if (s2 > 0 && n1 > 0) { // s2 還有空間而且還有 1*1 商品要放
if (s2 >= n1) { // 可以放入所有 1*1 商品
s2 -= n1; n1 = 0;
} else { // 無法放入所有 1*1 商品
n1 -= s2; s2 = 0;
}
}
/* 放入 1*1 的商品 */
int p1 = n1/36 + (n1%36 > 0);
/* 印出答案 */
printf("%d\n", p1 + p2 + p3 + n4 + n5 + n6);
}
return 0;
}
沒有留言:
張貼留言