2020 아리필기시험 3월 25일 파이톤3

첫 번째 문제 최소 인접차 절대치 구화

제목설명:

입력 설명:

출력 설명:

해석:

샘플 입력:

샘플 출력:

사고방식:

코드:

두 번째 문제 복원 디지털 매트릭스

제목설명:

입력 설명:

출력 설명:

샘플 입력:

샘플 출력:

사고방식:

코드:

첫 번째 문제 최소 인접차 절대치 구화

1번 AC, 흐뭇.

제목 설명:

2차원 그룹, 3줄 n열을 정하고, 각 열에서 하나의 수를 선택하여 1차원 그룹 (1*N) 을 구성하고, 이 그룹의 인접차 절대값을 합쳐서, 이것과 최소를 확보하고, 이 최소의 인접차 절대값의 합을 출력합니다.

설명 입력:

첫 번째 줄의 정수는 n을 대표하고 다음 세 줄을 대표하며 2차원 그룹 행렬 5, 5, 9, 5, 4, 4, 7, 4, 10, 3, 2, 10, 9, 2, 3.

출력 설명:

5

설명:

1차원수 그룹은 [5, 7, 5, 4, 4]로 선택되고 인접차 절대값은 2, 2, 1, 0, 0과 5이기 때문에 5를 출력합니다.

예 입력:

#     
5
5 9 5 4 4
4 7 4 10 3
2 10 9 2 3

샘플 출력:

5

아이디어:

동적 기획 dp[i][j]는arr[i][j]를 끝으로 하는 최소 인접차 절대값의 구화 결과를 나타낸다

코드:

n = int(input().strip())
arr = [[0]*n for _ in range(3)]
for i in range(3):
    arr[i] = list(map(int, input().split()))
dp = [[0]*n for _ in range(3)]
dp[:][0] = 0                        # dp       
for lie in range(1,n):
    for hang in range(3):
        res1 = dp[0][lie - 1] + abs(arr[hang][lie] - arr[0][lie - 1])
        res2 = dp[1][lie - 1] + abs(arr[hang][lie] - arr[1][lie - 1])
        res3 = dp[2][lie - 1] + abs(arr[hang][lie] - arr[2][lie - 1])
        dp[hang][lie] = min(res1, res2, res3)
print(min(dp[0][-1], dp[1][-1], dp[2][-1]))

두 번째 문제 복원 디지털 매트릭스

두 번째 문제는 시간이 충분하지 않아서, 시험이 끝난 후 10분이 지나서야 비로소 계산해 냈다.

제목 설명:

행렬 n*m을 지정합니다. 줄마다 등차수열입니다. 그러나 일부 값은 숨겨져 있습니다. 수치가 0이면 숨겨집니다.입력한 값 i, j에 따라 이 위치의 값이 유도될 수 있는지 판단하고 출력할 수 있다. 그렇지 않으면 Unknown을 출력할 수 있다.

설명 입력:

첫 번째 줄은 세 개의 정수로 n, m, q의 다음 n줄을 대표하고 2차원 그룹 매트릭스 A[n*m]의 다음 q줄을 대표하며 줄마다 두 개의 정수 i, j, 접근 매트릭스의 가능한 값 A[i][j]

출력 설명:

출력 q행에서 대응하는 위치의 행렬 요소 값을 유도할 수 있다면, 이 값을 유도할 수 없으면 Unknown으로 되돌려줍니다

예 입력:

#    
2 3 6
1 0 3
0 0 0
1 1
1 2
1 3
2 1
2 2
2 3

샘플 출력:

1
2
3
Unkown
Unkown
Unkown

아이디어:

복원 매트릭스 단계: 1. 줄별 복원 매트릭스 2, 열별 복원 매트릭스 3, 줄별 복원 매트릭스 4, 열별 복원 매트릭스

코드:

def recover_hang():
    for hang in range(n):
        flag = 0
        i, i_val, j, j_val = -1, 0, -1, 0
        for lie in range(m):
            if A[hang][lie]:
                flag += 1
                if i == -1:
                    i, i_val = lie, A[hang][lie]
                elif j == -1:
                    j, j_val = lie, A[hang][lie]
        if flag >= 2:
            for lie in range(m):
                A[hang][lie] = A[hang][i] + int((j_val - i_val) / (j - i) * (lie - i))
def recover_lie():
    for lie in range(m):
        flag = 0
        i, i_val, j, j_val = -1, 0, -1, 0
        for hang in range(n):
            if A[hang][lie]:
                flag += 1
                if i == -1:
                    i, i_val = lie, A[hang][lie]
                elif j == -1:
                    j, j_val = lie, A[hang][lie]
        if flag >= 2:
            for hang in range(n):
                A[hang][lie] = A[hang][i] + int((j_val - i_val) / (j - i) * (lie - i))

n,m,q = list(map(int,input().split()))
A = [[0]*m for _ in range(n)]
Q = [[0]*2 for _ in range(q)]
for i in range(n):
    A[i] = list(map(int, input().split()))
for i in range(q):
    Q[i] = list(map(int, input().split()))

recover_hang()
#print(A)
recover_lie()
#print(A)
recover_hang()
#print(A)
recover_lie()
#print(A)
for i in range(q):
    if A[Q[i][0]-1][Q[i][1]-1] == 0:
        print('Unkown')
    else:
        print(A[Q[i][0]-1][Q[i][1]-1])

구분선
두 번째 문제는 행렬을 복원하고 나서야 내가 생각하는 것이 너무 간단하다는 것을 발견했다.아니면 한 가지 상황을 빠뜨린 거야?만약 네 개의 점이 모두 같은 줄이나 같은 열에 없다면 전체 행렬을 복원하기에 충분하다.예컨대
[0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]\begin {gathered}\begin {bmatrix} 0 & 1 & 0 &\0 &1 &0\0 &0\0\\0&0 &0\end {bmatrix}\end {gathered}\0010 100001\001\end {end {gathered}\end {gathered}\91210 1000001\1000010\1} 은 전체 행렬을 복원할 수 있음을 증명할 수 있는 유일한 행렬입니다.가운데 네 개의 원소를 미지의 변수로 설정하면 네 개의 선형 방정식, 네 개의 미지수를 열거할 수 있다.[ 0 1 0 0 0 x 1 x 2 1 1 x 3 x 4 0 0 0 1 0 ]\begin{gathered}\begin{bmatrix}0& 1& 0& 0\\0 &x_1 &x_2 &1\\1& x_3& x_4&0\0&0&1&0\end {bmatrix}\end {gathered}\0010 1x1 x3 0 x2 x4 1 0100\방정식이 선형과 무관하다는 것을 증명할 수 있으므로 풀 수 있습니다.그리고 다시 행렬 행이나 행렬을 사용하면 전체 행렬을 복원할 수 있다.4원 일차 선형 방정식 그룹의 코드를 풀기는 매우 번거롭고 시험 시간이 이렇게 짧아도 두드리기 힘들죠.비고: 4 단계 단위 행렬이면
[10 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]\begin {gathered}\begin {bmatrix} 1&0 & 0 &0 &\0 &1 &0 &1\0&0 &1\end {bmatrix}\end {gathered}\10000100 0001\end {end {gathered}\end {gathered}\1000100001 0001\9101\복원은 불가능할 것 같습니다.[1 + a 1 + a 1 + 2 a 1 + 1 + 3 a 1 + 1 1 1 + a 1 + a 1 + 1 + a 1 + a 1 + a 1 + 1 1 + 2 a 1 + 3 a 1 + 1 1 1 1 + a 1 + 1 1 + a 1 = 1]\begin {gathered}\begin {bmatrix} 1 & 1 + a 1 & 1 + a 1 + 1 + 1 + 2 a 1 + 2 a 1 & 1 & 1 & 1 + 2 a\1 & 1 & 1 + 2 a\1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 + a\1 & 1 & 1 & 1 + 1 + a\1 & 1 & 1 + 1 + 1 + a\1 + 1 & 1 + 1 + 1 + a\1 + 1 + 11:a1:a1:2a1:1+a11:a1:1+2a1+a11:a1+2a1+a1:a1+3a1+2a1+a1
이 문제는 정말 변태적이다.
다음 학우들이 제공한 사고방식, 시정 및 교류 경험에 감사 드립니다. (블로그 닉네임)
1、weixin_383906632 한가하지 못한 왕소 C 3, August-us