n개의 학생 그룹이 대학 버스를 타고 대학에서 집으로 돌아오기를 기다리고 있다고 가정합니다. 각 학생 그룹에는 m명의 학생이 있습니다. 학생 단체는 흩어지지 않고 버스로 여행하기를 원합니다. 그들은 그룹의 모든 구성원이 버스에 탈 수 있는 경우에만 버스에 탑승합니다. 또한 이전 그룹이 버스에 탑승하지 않았거나 이미 목적지에 도착한 경우 해당 그룹은 버스에 탑승하지 않습니다. 그룹의 수와 각 그룹의 학생 수가 주어지면 버스가 모든 그룹을 수송할 수 있도록 버스의 크기를 알아야 하고 버스가 대학에서 출발할 때마다 빈 공간이 없습니다 버스에서.
따라서 입력이 그룹 또는 gr_no =[3, 4, 2, 2, 1, 4, 3, 5]와 같으면 출력은 [12, 24]가 됩니다.
버스 크기가 12인 경우 첫 번째 여행에서는 그룹 1~5를 포함하고 두 번째 여행에서는 나머지 그룹을 포함할 수 있습니다.
버스 크기가 24인 경우 모든 그룹을 포함할 수 있으며 한 번만 이동할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- factor_ret() 함수를 정의합니다. n
- 이 걸립니다.
- i 범위(0 ~ n ^ 0.5)에 대해
- n mod i가 0과 같으면
- 튜플(i, (n/i)의 하한값)을 output_list에 추가
- n mod i가 0과 같으면
- 출력 목록 정렬
- output_list를 집합으로 반환
- i 범위(0 ~ n ^ 0.5)에 대해
- 이제 다음 단계를 수행하십시오 -
- total :=항목 gr_no[0]를 포함하는 새 목록
- 범위 1에서 gr_no 크기의 i에 대해 다음을 수행합니다.
- 총계 끝에 합계[i - 1] + gr_no[i] 삽입
- b_sizes :=새 목록
- factor_ret(목록의 합계(gr_no))의 각 크기에 대해 수행
- temp_list :=total에서 0이 아닌 모든 요소의 새 목록
- 색인:=1
- 지시자 :=참
- temp_list의 각 지점에 대해 다음을 수행합니다.
- 포인트가 크기 * 인덱스와 같지 않으면
- 지시자 :=거짓
- 루프에서 나오다
- 인덱스 :=인덱스 + 1
- 포인트가 크기 * 인덱스와 같지 않으면
- 지표가 True이면
- b_sizes 끝에 크기 삽입
- b_size 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from functools import reduce def solve(gr_no): total = [gr_no[0]] for i in range(1, len(gr_no)): total.append(total[i - 1] + gr_no[i]) b_sizes = [] for size in factor_ret(sum(gr_no)): temp_list = list(filter(lambda x : x % size == 0, total)) index = 1 indicator = True for point in temp_list: if point != size * index: indicator = False break index += 1 if indicator: b_sizes.append(size) return b_sizes def factor_ret(n): return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))) print(solve([3, 4, 2, 2, 1, 4, 3, 5]))
입력
[3, 4, 2, 2, 1, 4, 3, 5]
출력
[12, 24]