Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.
Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.
Write a function:
def solution(A, X)
that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.
For example, given X = 5 and the following array A:
A[0] = 1 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 1 A[5] = 2 A[6] = 3 A[7] = 5 A[8] = 1the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- X is an integer within the range [1..1,000,000,000];
- each element of array A is an integer within the range [1..1,000,000,000].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 91:Tasks from Indeed Prime 2016 challenge
# P 91.1 RectangleBuilderGreaterArea
def solution(A, X):
"""
利用数组A中的元素,构建面积不小于X的不同矩形的个数
:param A: 数组
:param X: 面积阈值
:return: 满足条件的矩形的个数
"""
count_item = {}
for i in A:
if i in count_item:
count_item[i] += 1
else:
count_item[i] = 1
no_less_than_2 = [j for j in count_item if count_item[j] >= 2] # 出现次数大于等于2的存储下来
ordered_list = sorted(no_less_than_2) # 按照栅栏的长度升序排序
length = len(ordered_list) # 可用栅栏的个数
if not length: # 没有可用的栅栏
return 0
else:
if length == 1: # 只有一种长度的栅栏,只有栅栏数不小于4时,才可以建立围栏
if count_item[ordered_list[0]] >= 4:
return 1
else:
return 0
else:
sum_count = 0 # 记录总的个数
for index, value in enumerate(ordered_list):
if count_item[value] >= 4:
start = index # 如果用一种长度的栅栏,其数量需要不小于4
else:
start = index + 1
end = length - 1
# 开始二分查找算法
while start <= end:
middle = int((start + end) / 2)
if ordered_list[middle] * value >= X:
end = middle - 1
else:
start = middle + 1
sum_count += length - end - 1
if sum_count > 1e9:
return -1
return sum_count
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 91:Tasks from Indeed Prime 2016 challenge
# P 91.1 RectangleBuilderGreaterArea
def solution(A, X):
"""
利用数组A中的元素,构建面积不小于X的不同矩形的个数
:param A: 数组
:param X: 面积阈值
:return: 满足条件的矩形的个数
"""
count_item = {}
for i in A:
if i in count_item:
count_item[i] += 1
else:
count_item[i] = 1
no_less_than_2 = [j for j in count_item if count_item[j] >= 2] # 出现次数大于等于2的存储下来
ordered_list = sorted(no_less_than_2) # 按照栅栏的长度升序排序
length = len(ordered_list) # 可用栅栏的个数
if not length: # 没有可用的栅栏
return 0
else:
if length == 1: # 只有一种长度的栅栏,只有栅栏数不小于4时,才可以建立围栏
if count_item[ordered_list[0]] >= 4:
return 1
else:
return 0
else:
sum_count = 0 # 记录总的个数
for index, value in enumerate(ordered_list):
if count_item[value] >= 4:
start = index # 如果用一种长度的栅栏,其数量需要不小于4
else:
start = index + 1
end = length - 1
# 开始二分查找算法
while start <= end:
middle = int((start + end) / 2)
if ordered_list[middle] * value >= X:
end = middle - 1
else:
start = middle + 1
sum_count += length - end - 1
if sum_count > 1e9:
return -1
return sum_count
The solution obtained perfect score.