주어진 작은 숫자와 큰 숫자, 원하는 번호 - 루프없이

Question

파이썬에서 codingbat의 코딩 문제를 해결하고 있습니다. 우리는 목표 인치가 긴 벽돌의 행을 만들고 싶어

: 같이 make_bricks 문제는 정의된다. 우리는 작은 벽돌 (각 1 인치)과 큰 벽돌 개 (각각 5 인치)의 숫자 을 가지고 있습니다. 의 경우 True를 반환합니다. 주어진 벽돌에서부터 까지 골을 넣을 수 있습니다. 이 은 외모보다 약간 더 밝고 어떤 루프도없이 할 수 있습니다.

make_bricks(3, 1, 8) → True 
make_bricks(3, 1, 9) → False 
make_bricks(3, 2, 10) → True 

내가 생각 해낸 첫 번째 솔루션

했다 : 올바르지 만 수입이 허용되지 않기 때문에 판단 소프트웨어에 의해 거부되었다

from itertools import permutations 

def make_bricks(small, big, goal): 
    l = small*[1]+big*[5] 
    return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \ 
    for i in range(2,len(l)+1)])]) 

. 그래서 나의 다음 솔루션이었다

또한 정확하지만 make_bricks(1000000, 1000, 1000100) 같은 입력에 타임 아웃으로 숨 막혀

def make_bricks(small, big, goal): 
    bricks = small*[1]+big*[5] 
    for step in range(len(bricks)+1,1,-1): 
     for start in range(len(bricks)): 
      if len(bricks[start:start+step])==step: 
       if sum(bricks[start:start+step])==goal: 
        return True 
    return False 

.

그래서 파이썬에서 루프를 사용하지 않고 가져 오기를 사용하지 않고 시간 제한에이 문제를 어떻게 해결할 수 있습니까?

Answer 1

이것은 수학 문제입니다. S 작은 벽돌이 있고 B 큰 벽돌이 있고 길이가 L 인 블록이라고 가정 해보십시오.

큰 벽돌은 K = min(B, L div 5), 작은 벽돌은 L - 5K이므로 작은 벽돌이 충분한 지 확인해야합니다.

div은 정수 나누기 (층)입니다.

편집이 L-K에서 L-5K으로 변경되었습니다. 오식.

Answer 2

최종 크기에 도달하면됩니다. 그러므로 벽돌을 어느 순서로 배치하든 전혀 문제가되지 않습니다.

다음 중요한 아이디어는 가능할 때마다 5 인치 벽돌을 사용하는 것입니다. 그 중 하나를 사용하는 경우 5 인치를 커버하고, 1 인치 벽돌 중 5 개를 사용하는 경우에도 커버합니다. 따라서 하나의 벽돌을 사용하는 것이 바람직합니다.

이제 5 인치 벽돌이 떨어지거나 타겟 길이가 5 인치 미만이 될 때까지 주어진 5 인치 벽돌로 만들 수있는 최대 길이를 확인하십시오. . 어느 쪽이든, 거리가 누락되어 남아있는 1 인치 벽돌로 채워야합니다.

여기서는 코드를 제공하지 않습니다. 왜냐하면 실제로는 매우 간단한 문제이고, 위에서 설명한 내용을 통해 어떻게 해결했는지 쉽게 이해할 수 있기 때문입니다.

Answer 3

단일 단위 항목과 하나의 큰 크기 항목 만 있으면 큰 항목으로 항상 채울 수 있으므로 그리 어렵지 않습니다.

하드너 (Harder) 쿼터 및 십진수가 있고 정확하게 금액을 만들려고합니다. 예를 들어 55c를 만들어야하는 경우 대상보다 작더라도 2 쿼터에서 시작하면 실패합니다.

물론 당신이 가질 수있는 다른 조합은 "양보다 더 가까이 가지 마라 - 당신이 가진 가장 작은 단위"라는 문제를 훨씬 더 복잡하게 만들 것입니다.

일치하는 방정식 (Ax + By) % AB = C를 풀면 C와 같은 A (x + B) + B (yA)를 사용하여 더 많은 방정식을 얻을 수 있습니다. 벽돌/동전 등의 제한된 수량.

일치하는 방정식의 예는 (7x + 9y) % 63 = 47과 같으며이를 해결하는 함수를 작성할 수 있습니다. 우리는 가장 낮은 항으로 분해하여 A와 B가 HCF에 의해 공동 소수 (co-prime) 또는 감소한다고 가정합니다.

x = 0 인 유일한 해결책이 있습니다.이 경우 x = 8, y = 6으로 끝나고 각각 최대 값 56 + 54 = 110이됩니다. 이는 47 mod 63과 같습니다. 실제로 표적이 47 일 경우 7과 9의 어떤 숫자로도 풀 수 없습니다.

대상이 110이면 8 개의 벽돌이 7 개, 6 개가 9 개이면 해결할 수 있습니다. 그렇지 않으면 해결 방법이 없습니다.

목표가 높으면 무제한의 벽돌이있는 여러 솔루션이 있지만 우리가 필요로하는 9 개의 벽돌 수는 항상 8 mod 9이므로 8, 17, 26 등이됩니다. 우리는 가장 높은 숫자를 취합니다. 이 범주에 해당하며 7 개의 벽돌로 나머지를 채우십시오. 우리가 그들을 가지고 있다면 우리는 목표를 세울 수 있습니다. 우리가 9 개의 벽돌을 가지고 있다면, 26 개를 사용해야합니다.

일치가 해결되면 그것은 알고리즘입니다.

Answer 4

크기 5 홀은 1s 또는 5s로 채울 수 있지만 5s 미만은 1s로 채울 수 있습니다. 예를 들면 : 19 개를 만들려면 적어도 4 1 개가 있어야합니다. 운 좋게도 3 개 밖에 없으면 100 개 5 개가 있더라도 상관 없습니다.

그래서 나머지는 5에서 나머지를 채우려면 1을, 나머지는 5에서 1로 남겨 둡니다.

def make_bricks(small, big, goal): 
    # minimum number of 1s needed 
    rem = goal % 5 # ex: 19 % 5 == 4 

    if rem > small: 
    # too few 1s 
    return false 
    else: 
    # we have enough 1s; deduct what we just used 
    small -= rem 
    goal -= rem 

    # now see if what's left will fill the rest of the hole 
    return small + 5*big >= goal 

희망은 당신에게 의미가 있습니다!

Answer 5

def make_bricks(small, big, goal): 
    if goal > small + big * 5: 
    return False 
    else: 
    return goal % 5 <= small 

Answer 6

def make_bricks(s,b,g): 
    return not(g>b*5+s or g%5>s) 

의 = 작은 | b = 큰 | g = 목표

Answer 7

N = INT (목표/5)

작은 + 큰 목표> 5 * 경우 : 리턴 거짓 ELIF (목표 < = 작은 + 큰 * 5) 경우 목표> N * 5 + 작은 :
반환 거짓 다른
: 참 반환

Answer 8

여기에 내가 생각 해낸 해결책이다 - 아니이 얻을 수있는 응축,하지만 충분히 쉽게 통해 logic'd 같이

def make_bricks(small, big, goal): 
    if int(goal/5) < big: 
    big -= big - int(goal/5) 
    return big*5 + small >= goal