有n个木棒,需要用上所有木棒,围成一个正方形,如果可以围成正方形,则输出"yes", 否则输出"no"。
时间: 2023-04-21 18:01:55 浏览: 77
可以使用以下方法判断是否能围成正方形:
1. 计算所有木棒的长度总和sum,如果sum不能被4整除,则无法围成正方形,输出"no"。
2. 将所有木棒按长度从大到小排序。
3. 创建一个长度为4的数组side,表示正方形的4条边,初始值都为。
4. 从最长的木棒开始,依次尝试将其放入4条边中的一条,如果能放入,则更新该边的长度,并继续尝试下一根木棒。如果无法放入任何一条边,则无法围成正方形,输出"no"。
5. 当所有木棒都被尝试过后,如果4条边的长度都相等,则可以围成正方形,输出"yes",否则输出"no"。
以下是Python代码实现:
n = int(input())
sticks = []
for i in range(n):
sticks.append(int(input()))
sum = sum(sticks)
if sum % 4 != :
print("no")
else:
side = [] * 4
sticks.sort(reverse=True)
def dfs(index):
if index == n:
return side[] == side[1] == side[2] == side[3]
for i in range(4):
if side[i] + sticks[index] <= sum // 4:
side[i] += sticks[index]
if dfs(index + 1):
return True
side[i] -= sticks[index]
return False
if dfs():
print("yes")
else:
print("no")