C, 109 97 바이트 및 정확성 증명

나는 내 솔루션을 작성하고 있었지만 @steveverrill이 나를 이겼다. 나는 사용 된 전략에 대한 정확성 증명을 포함했기 때문에 모두 동일하게 공유 할 것이라고 생각했습니다.

축소 된 코드 :

m,n,x;main(){for(scanf("%i%i",&m,&n); n;)putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));}

축소하기 전에 :

m,n,x;

main(){
    for(scanf("%i%i",&m,&n); n;)

        /* If x == m, prints out a newline, and iterates outer
         * loop (x=0,n--) using comma operator.
         * Otherwise, paints a '#' on :
         *     Every even column (when x%2 is 0)
         *     On odd columns of the last row (++x^m||~n&1 is 0)
         *     On the first row (when n^1 is 0)
         * And a ' ' on anything else (when predicate is 1) */
        putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));
}

전략과 증거 :

최대 주변기 방정식 (M + 1) (N + 1)-((M + 1) (N + 1)) mod 2 의 정확성을 가정하면, 다음은 사용 된 최적 전략을 설명하고 유도에 의한 정확성을 증명합니다.

홀수 M의 경우 M / 2 + 1 손가락으로 손 모양을 그립니다.

3x2
# #
###

5x3
# # #
# # #
#####

우리는 이제이 전략이 유도에 의해 모든 홀수 M에 최적임을 증명합니다

기본 사례 : M = N = 1
단일 셀이 채워집니다. (1 + 1) * (1 + 1) = 2 * 2 = 4이므로 해가 정확하고 정사각형에는 4 변이 있습니다.

너비에 대한 유도 : M이 홀수 인 (N, M-2)에
대해 핸드 셰이프 전략이 작동한다고 가정합니다. 즉 , 그 주변이 최적이고 (N + 1) (M-2 + 1) + ((M -1) (N + 1)) mod 2 . 이제 (N, M) 작동한다는 것을 보여줍니다 .

손가락을 추가하는 과정은 다각형에서 하나의 가장자리를 제거하고 3 + 2N을 추가합니다 . 예를 들면 다음과 같습니다.

 5x3 -> 7x3
 # # # $
 # # # $
 #####$$

이를 이전 경계가 최적이라는 가설과 결합하면 새로운 경계는 다음과 같습니다.

(N + 1)*(M - 2 + 1) - ((M+1)*(N+1)) mod 2 - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2 - 2(N + 1) - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2

모듈로 2 산술을 다루고 있기 때문에

((M-1)*(N+1)) mod 2 = ((M+1)*(N+1)) mod 2

따라서 손가락을 추가하여 너비를 늘리면 최적의 경계선이됩니다.

높이에 대한 유도 :
손 모양 전략이 (N-1, M)에 대해 작동한다고 가정합니다 . 여기서 M 은 홀수입니다. 즉 둘레가 최적이며 N (M + 1) + ((M + 1) N) mod 2 . 이제 (N, M) 작동한다는 것을 보여줍니다 .

손의 높이를 늘리면 손가락이 길어지고 첫 번째 및 다른 모든 x- 색인에 위치합니다. 각 높이가 증가 할 때마다 각 손가락이 둘레에 2를 더하고 (M + 1) / 2 개의 손가락이 있으므로 N 이 증가하면 2 (M + 1) / 2 = M + 1 이 증가합니다. 둘레.

이것을 가설과 결합하면 새로운 경계는 다음과 같습니다.

N*(M + 1) + ((M+1)*N) mod 2 + M + 1
(N + 1)*(M + 1) + ((M+1)*N) mod 2

모듈 식 산술을 사용하면 마지막 항을 단순화하여 다음을 얻을 수 있습니다.

(N + 1)*(M + 1) + ((M+1)*(N+1)) mod 2

솔루션이 모든 N> 0 및 홀수 M> 0에 대해 최적임을 증명합니다.

M조차도 홀수 M과 같은 방식으로 보드를 채우지 만 마지막 세그먼트에는 예를 들어 크레 넬을 추가합니다.

4x3
# ##
# #
####

6x4
# # #
# # ##
# # #
######

이제이 전략이 최적임을 증명합니다.

짝수 M에 대한 유도 :
솔루션이 (N, M-1)에 대해 올바른 것으로 가정합니다. (N + 1) M을 – ( M (N + 1)) mod 2 . 이제 (N, M)에서 작동한다는 것을 보여줍니다.

손가락을 늘리는 것처럼 각 crenelation은 다각형 둘레에 2를 더합니다. 총 생성 횟수는 (N + N mod 2) / 2 이며 총 N + N mod 2입니다. 둘레가 더해집니다.

이것을 가설과 결합하면 새로운 경계는 다음과 같습니다.

(N + 1)*M - (M*(N+1)) mod 2 + N + N mod 2
(N + 1)*(M + 1) - (M*(N+1)) mod 2 + N mod 2 - 1
(N + 1)*(M + 1) - (M*(N+1)) mod 2 - (N + 1) mod 2

우리는 그것을 가지고

(M*(N+1)) mod 2 - (N + 1) mod 2 = ((M+1)*(N+1)) mod 2

N이 홀수이면 0으로 감소하고 N이 짝수이면

- A mod 2 - 1 = -(A + 1) mod 2

따라서 전략은 모든 M, N> 0에 대해 최적입니다 .

---

답변