이것은 코드 골프입니다. 승자는 바이트 수가 가장 적은 유효한 코드입니다.
도전
사각형 사각형 격자의 너비와 높이가 M 과 N 인 입력 은 다음을 만족하는 다각형을 출력합니다.
- 다각형 가장자리는 정사각형 가장자리로만 구성됩니다. 대각선 가장자리는 없습니다. 모두 세로 또는 가로입니다.
- 다각형에는 구멍이 없습니다. 다각형 바깥 쪽의 모든 사각형은 사각형 바깥 쪽의 다각형 바깥 쪽 사각형에서 시작하여 다각형 바깥 쪽 사각형의 직교 단계를 통해 도달 할 수 있습니다.
- 다각형에는 자체 교점이 없습니다 . 정점에서 만나는 정사각형 모서리 중 다각형 경계의 일부는 2를 초과 할 수 없습니다.
- 다각형이 연결됩니다. 다각형 내에있는 직교 단계를 통해 다각형의 다른 사각형에서 다각형의 모든 사각형에 도달 할 수 있어야합니다.
- 다각형은 아래에 표시된 공식에 따라 가능한 최대 둘레를 갖습니다 .
코드는 M 과 N에 대해 1에서 255까지 작동해야합니다 .
최대 둘레에 대한 공식
여기서 가장 어려운 점은 최대 둘레를 가진 다각형 중 가장 골프 가능한 것을 찾는 것입니다. 최대 둘레 자체는 항상 다음 공식으로 정의됩니다.
모든 정사각형 정점이 주변에 있어야하기 때문에 이는 사실입니다. 홀수의 꼭짓점에 대해서는 이것이 불가능하며 얻을 수있는 최선은 한 쪽 꼭짓점이 적습니다 (주변이 항상 고르기 때문에).
산출
모양을 개행 문자로 구분 된 문자열 ( 정확히 M 문자 의 N 행) 로 출력하십시오 . 여기서는 다각형 외부의 사각형에 공간을 사용하고 다각형 내부의 사각형에 ‘#’을 사용하지만 그 의미가 모든 입력에 일관성이 있다면 시각적으로 다른 두 문자를 사용할 수 있습니다.
최대 하나의 선행 개행 문자와 최대 하나의 후행 개행 문자를 포함 할 수 있습니다.
원하는 경우 대신 정확히 N 문자 의 M 행을 출력하고 일부 입력의 경우 M by N 출력을 선택 하고 다른 입력의 경우 N by M 출력을 선택할 수 있습니다 .
예
구멍 때문에 유효 하지 않습니다 :
###
# #
###
교차점 (대각선 터치-주변에 4 개의 정사각형 모서리가있는 정점) 및 실수로 구멍으로 인해 유효 하지 않습니다.
##
# #
###
연결이 끊어져서 유효 하지 않습니다 :
#
# #
#
최대 둘레의 유효한 다각형 :
# #
# #
###
크레딧
처음에는 최대 둘레의 값을 얼마나 빨리 계산할 수 있는지 과소 평가했으며 그 값을 출력으로 요구하려고했습니다. 채팅에 도움이 된 사람들 덕분에 임의의 N과 M의 최대 경계를 해결하는 방법을 설명하고 하나 이상의 대답을 마지막됩니다 도전에이 차례 돕는 …
특히 감사합니다 :
Sparr , Zgarb , feersum , jimmy23013 .
답변
CJam, 47 바이트
l~_2%{\}|_'#:H*@({N+1$(2md\HS+*H+\SH+R=*++}fR\;
설명:
l~ Get and convert input.
_2% Calculate second value modulo 2.
{\}| If value is even, swap the two inputs. This puts odd on top if one is odd.
_'#:H* Create top row of all # signs. Also save away # character as shortcut for later.
@( Pull number of rows to top, and decrement because first is done.
{ Start loop over rows.
N+ Add newline.
1$ Copy row length to top of stack.
(2md Decrement, and calculate mod/div with 2.
\ Swap mod and div, will use div first.
HS+ "# "
* Repeat it based on div 2 of row length.
H+ Add one more #.
\ Swap mod of earlier division to top.
SH+ " #"
R= Pick space or # depending on even/odd row number.
* Repeat 0 or 1 times depending on mod 2 of row length.
+ Add the possible extra character to line.
+ Add line to result.
}fR End of for loop over lines.
\; Remove row length from stack, leaving only result string.
결과에는 두 가지 주요 사례가 있습니다. 크기 중 하나 이상이 홀수 인 경우 패턴은 일반 “레이크”입니다. 예를 들어, 입력의 경우 7 6
:
#######
# # # #
# # # #
# # # #
# # # #
# # # #
두 크기가 모두 짝수이면 두 번째 사각형이 모두 “켜짐”인 추가 열이 있습니다. 예를 들어, 입력의 경우 8 6
:
########
# # # #
# # # ##
# # # #
# # # ##
# # # #
이제이 패턴들이 문제 설명에 주어진 이론상의 최대 경계선에 도달한다는 것을 보여주기 위해 첫 번째 패턴의 경계선이 (M + 1) * (N + 1)
가 있고 두 마이너스 1인지 확인해야합니다.
첫 번째 패턴의 경우 둘레의 M
치수가 홀수입니다.
M
상단 가장자리.2
맨 윗줄의 측면에.(M - 1) / 2
치아 사이의 간격을 위해.(M + 1) / 2
둘레가2 * (N - 1) + 1
각각있는 치아 .
이것은 다음에 추가됩니다.
M + 2 + (M - 1) / 2 + (M + 1) / 2 * (2 * (N - 1) + 1) =
M + 2 + (M - 1) / 2 + (M + 1) * (N - 1) + (M + 1) / 2 =
2 * M + 2 + (M + 1) * (N - 1) =
(M + 1) * 2 + (M + 1) * (N - 1) =
(M + 1) * (N + 1)
두 번째 경우의 경우 M
와 N
도 있으며, 주변은 합계 :
M
상단 가장자리.2
맨 윗줄의 측면에.M / 2
맨 윗줄의 열린 #.M / 2
2 * (N - 1) + 1
일반 치아의 둘레가 각각있는 치아.- 가장 오른쪽 치아에는 재 기둥을위한 여분의
2 * (N / 2 - 1)
둘레 조각이 있습니다.
이 모든 것을 함께 추가 :
M + 2 + M / 2 + (M / 2) * (2 * (N - 1) + 1) + 2 * (N / 2 - 1) =
M + 2 + (M / 2) * (2 * (N - 1) + 2) + N - 2 =
M + M * N + N =
(M + 1) * (N + 1) - 1
답변
루비, 개정 1, 66
->(m,n){n.times{|i|puts ("#"*m**(1-i%2)).rjust(m,i>n-2?"# ":" ")}}
m
0을 1로 올리는 데 사용 하여 1을 m
#
인쇄 할지 여부를 결정합니다 .
>
대신 마지막 행을 테스트하는 데 사용 됩니다 ==
.
풋이나 괄호 후에 공간을 제거 할 수 없습니다!
루비, 레브 0, 69
->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}
이것은 익명의 람다 함수입니다. 다음과 같이 사용하십시오.
f=->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}
M=gets.to_i
N=gets.to_i
f.call(M,N)
결국, M과 N을 교환 할 수 있는지 묻고 나서 필요하지 않았습니다.
N 홀수에 대한 일반적인 출력. 삭제하면#
오른쪽에서 직접 (N + 1) (M + 1)이됩니다. 셰이프를 결합하도록 포함하면 가로 둘레 2 제곱이 제거되고 세로 둘레 2 제곱이 추가되므로 아무런 변화가 없습니다.
여기서 우리는 표현 "#"*(i%2==0?m:1)
에 의존하여 M #
개의 행 과 한 개의 행을 번갈아 가며 #
M 문자에 맞 춥니 다.
5 6
5 5
##### ######
# #
##### ######
# #
##### ######
N 짝수에 대한 일반적인 출력. 맨 아래 줄의 주름으로 인해 세로 둘레를 추가 한 것과 비교하여와 5 6
동일한 둘레 6 5
또는 M + 1 = 6 씩 증가 5 5
합니다. 세로 둘레의 (M + 1) -1 = 6 증가와 6 6
동일 6 5
합니다. 따라서 그들은 공식에 따릅니다.
5 6
6 6
##### ######
# #
##### ######
# #
##### ######
# # # # # ##
Ruby의 rjust
빈 셀에 사용할 패딩을 지정할 수있어 매우 편리합니다 . 일반적으로 패딩은로 설정 " "
되지만 마지막 행에 대해 전환합니다 "# "
. N이 짝수이면 패딩은 마지막 행에만 필요합니다. N이 홀수 인 경우 마지막 행이 완료되고 정당화되지 않습니다. 화장을 볼 수 없습니다.)
답변
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에 대해 최적입니다 .