키 입력 A, Ctrl + A, Ctrl + C 및 Ctrl + V를 사용하는 최대 문자 수
이것은 Google의 인터뷰 질문입니다. 혼자서는 해결할 수 없습니다. 누군가 빛을 비출 수 있습니까?
최대 문자 'A'를 생성하도록 키 입력 순서를 인쇄하는 프로그램을 작성하십시오. A, Ctrl+ A, Ctrl+ C및 Ctrl+의 4 개 키만 사용할 수 있습니다 V. N 개의 키 입력 만 허용됩니다. 모든 Ctrl+ 문자는 한 번의 키 입력으로 간주되므로 Ctrl+ A는 한 번의 키 입력입니다.
예를 들어, 시퀀스는 A, Ctrl+ A, Ctrl+ C, Ctrl+ V두 A의 키 입력에 4를 생성한다.
- Ctrl + A는 모두 선택입니다.
- Ctrl + C는 복사입니다.
- Ctrl + V는 붙여 넣기입니다.
나는 수학을했다. 모든 N에 대해 A의 x 수, 하나의 Ctrl+ A, 하나의 Ctrl+ C및 y Ctrl+ V를 사용하여 최대 ((N-1) / 2) 2 개의 A를 생성 할 수 있습니다 . 일부 N> M의 경우, 많은으로 사용하는 것이 좋습니다 Ctrl+ AS ', Ctrl+ C와 Ctrl+ V시퀀스는 A의 수를 두 배로한다.
시퀀스 Ctrl+ A, Ctrl+ V, Ctrl+ C는 기존 선택을 덮어 쓰지 않습니다. 복사 된 선택 항목을 선택한 항목에 추가합니다.
동적 프로그래밍 솔루션이 있습니다. 우리는 0 개의 키가 우리를 0A로 만들 수 있다는 것을 알기 시작합니다. 그런 다음 i최대를 반복하여 n두 가지 작업을 수행합니다. A를 한 번 누르고 모두 선택 + 복사를 누른 다음 붙여 넣기 j시간을 누릅니다 (실제로 j-i-1아래에있는 트릭에 유의하십시오. 내용이 여전히 클립 보드에 있으므로 여러 번 붙여 넣을 수 있습니다. 매번 복사). 선택, 복사, 붙여 넣기 x 5는 선택, 복사, 붙여 넣기, 선택, 복사, 붙여 넣기와 동일하고 후자는 클립 보드에 더 많은 것을 남겨두기 때문에 최대 4 개의 연속 붙여 넣기 만 고려하면됩니다. 에 도달 n하면 원하는 결과를 얻을 수 있습니다.
복잡성은 O (N)으로 보일 수 있지만 숫자가 기하 급수적으로 증가하기 때문에 실제로 는 큰 숫자를 곱하는 복잡성으로 인해 O (N 2 )입니다. 아래는 Python 구현입니다. N = 50,000을 계산하는 데 약 0.5 초가 걸립니다.
def max_chars(n):
dp = [0] * (n+1)
for i in xrange(n):
dp[i+1] = max(dp[i+1], dp[i]+1) # press a
for j in xrange(i+3, min(i+7, n+1)):
dp[j] = max(dp[j], dp[i]*(j-i-1)) # press select all, copy, paste x (j-i-1)
return dp[n]
코드에서 j새 키를 누른 후 누른 총 키 수를 나타냅니다. i이 단계에서 이미 키 누르기가 있으며 두 번의 새 키 누르기가 모두 선택 및 복사로 이동합니다. 따라서 우리는 붙여 넣기 j-i-2시간을 맞이하고 있습니다. 붙여 넣기는의 기존 시퀀스에 dp[i] A추가 1되므로 만들기 를 추가해야 합니다 j-i-1. 이것은 j-i-1마지막 두 번째 줄에서 설명합니다 .
다음은 몇 가지 결과입니다 ( n=> A의 수) :
- 7 => 9
- 8 => 12
- 9 => 16
- 10 => 20
- 100 => 1391569403904
- 1,000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
- 50,000 => 매우 많은 수!
나는 당신이 항상 당신의 가정을 진술해야한다는 @SB에 동의한다 : 내 것은 문자 수를 두 배로 늘리기 위해 두 번 붙여 넣을 필요가 없다는 것입니다. 이것은 7에 대한 답을 얻으므로 내 솔루션이 틀리지 않는 한 가정이 옳 아야합니다.
나는 형태의 시퀀스를 확인 아니에요 이유 경우 누군가 불가사의에서 Ctrl+ A, Ctrl+ C, A, Ctrl+ V: 최종 결과는 항상 동일합니다 A, Ctrl+ A, Ctrl+ C, Ctrl+ V내가하는 않는 것이 좋습니다.
marcog의 솔루션을 사용하여 n=16. 이를 설명하기 위해 n=24최대에 대한 키 입력은 n=29^ A를 S (선택)로, ^ C를 C (복사)로, ^ V를 P (붙여 넣기)로 대체하여 가독성을 높였습니다.
24: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
4 * 4 * 4 * 4 * 4 = 1024
25: A,A,A,A,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P,S,C,P,P
4 * 4 * 3 * 3 * 3 * 3 = 1296
26: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P
4 * 4 * 4 * 3 * 3 * 3 = 1728
27: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P
4 * 4 * 4 * 4 * 3 * 3 = 2304
28: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P
4 * 4 * 4 * 4 * 4 * 3 = 3072
29: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
4 * 4 * 4 * 4 * 4 * 4 = 4096
초기 4 As 이후에 이상적인 패턴은 선택, 복사, 붙여 넣기, 붙여 넣기, 붙여 넣기 및 반복하는 것입니다. 이렇게하면 키를 5 번 누를 때마다 As에 4가 곱해집니다. 이 5 개의 키 입력 패턴이 나머지 키 입력을 자체적으로 사용할 수없는 경우 일부 4 개의 키 입력 패턴 (SCPP)이 최종 키 입력을 사용하여 필요에 따라 SCPPP를 교체 (또는 붙여 넣기 중 하나를 제거)합니다. 4 개의 키 스트로크 패턴은 총 4 개의 키 스트로크마다 3을 곱합니다.
이 패턴을 사용하면 marcog의 솔루션과 동일한 결과를 얻는 Python 코드가 있지만 O (1) edit : 이것은 지수화로 인해 실제로 O (log n)입니다.이를 지적한 IVlad 덕분입니다.
def max_chars(n):
if n <= 15:
return (0, 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81)[n]
e3 = (4 - n) % 5
e4 = n // 5 - e3
return 4 * (4 ** e4) * (3 ** e3)
e3 계산 : 키 입력 목록 끝에는 항상 0 ~ 4 개의 SCPP 패턴 n % 5 == 4이 있습니다. 왜냐하면 4 개, n % 5 == 13 개, n % 5 == 22 개, n % 5 == 31 개, n % 5 == 40 개가 있기 때문 (4 - n) % 5입니다. 이것은로 단순화 할 수 있습니다 .
E4 계산 : 패턴 증가의 총 수를 1로 할 때마다 n % 5 == 0, 정확히이 번호가 증가 밝혀 n / 5. 바닥 분할을 사용하여 총 패턴 수를 얻을 수 있습니다. 총 패턴 수 e4는 총 패턴 수에서 e3. 파이썬에 익숙하지 않은 사람들을 //위해 바닥 분할에 대한 미래 보장형 표기법입니다.
내가 접근하는 방법은 다음과 같습니다.
- 가정 CtrlA= 모두 선택
- 가정 CtrlC= 선택 복사
- 가정 CtrlV= 복사 된 선택 붙여 넣기
일부 텍스트가 주어지면 복제하는 데 4 번의 키 입력이 필요합니다.
- CtrlA 모두 선택하려면
- CtrlC 복사하려면
- CtrlV 붙여 넣으려면 (선택 항목 위에 붙여 넣을 것입니다. 가정을 진술하십시오)
- CtrlV 다시 붙여 넣으면 두 배가됩니다.
거기에서 4 개 또는 5 개의 A를 수행 한 다음 위의 내용을 반복하는 것을 고려할 수 있습니다. 일을하는 것을 참고 ctrl + a, c, v, v통해 루프 기하 급수적으로 텍스트를 성장할 것입니다. 남은 스트로크가 4 미만이면 계속CtrlV
Google과 같은 장소에서 인터뷰하는 열쇠는 가정을 진술하고 생각을 전달하는 것입니다. 그들은 당신이 문제를 어떻게 해결하는지 알고 싶어합니다.
O (1)에서 풀 수 있습니다. 피보나치 수와 마찬가지로 인쇄 된 As의 수 (및 키 입력 순서)를 계산하는 공식이 있습니다.
1) 문제 설명을 단순화 할 수 있습니다.
- [A], [Ca] + [Cc], [Cv] 및 빈 복사-붙여 넣기 버퍼 만 있음
같음
- 복사-붙여 넣기-버퍼에 [Ca] + [Cc], [Cv] 및 "A"만 있습니다.
2) 키 입력 순서를 { '*', 'V', 'v'} 중 N 개의 문자열로 설명 할 수 있습니다. 여기서 'v'는 [Cv]를 의미하고 '*'는 [Ca] 및 'V를 의미합니다. '는 [Cc]를 의미합니다. 예 : "vvvv * Vvvvv * Vvvv"
해당 문자열의 길이는 여전히 N입니다.
해당 문자열에있는 Vv 단어 길이의 곱은 생성 된 As의 수와 같습니다.
3) 해당 문자열에 대해 고정 된 길이 N과 고정 된 수의 단어 K가 주어지면 모든 단어의 길이가 거의 같으면 결과가 최대가됩니다. 쌍별 차이는 ± 1 이하입니다.
이제 N이 주어지면 최적의 수 K는 얼마입니까?
4) 길이가 L 인 단일 단어 하나를 추가하여 단어 수를 늘리고 싶다면 이전 단어의 L + 1 배를 하나의 'v'만큼 줄여야합니다. 예 : "… * Vvvv * Vvvv * Vvvv * Vvvv"-> "… * Vvv * Vvv * Vvv * Vvv * Vvv"
이제 최적의 단어 길이 L은 얼마입니까?
(5 * 5 * 5 * 5 * 5) <(4 * 4 * 4 * 4 * 4) * 4, (4 * 4 * 4 * 4)> (3 * 3 * 3 * 3) * 3
=> 최적은 L = 4입니다.
5) 길이가 4 인 많은 단어가 포함 된 문자열을 생성하기에 충분한 큰 N이 있지만 몇 번의 키 입력이 남아 있다고 가정합니다. 어떻게 사용해야합니까?
5 개 이상 남은 경우 : 길이가 4 인 다른 단어를 추가합니다.
0이 남아있는 경우 : 완료.
4 개가 남아있는 경우 :
a) 길이 3으로 한 단어 추가 : 4 * 4 * 4 * 4 * 3 = 768.
b) 또는 길이 5로 4 단어를 늘립니다 : 5 * 5 * 5 * 5 = 625. => 한 단어를 추가하는 것이 좋습니다.
3 개가 남아있는 경우 :
a) 또는 길이 4에서 3으로 이전 단어를 조정하여 길이가 3 인 한 단어를 추가합니다. 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.
b) 길이 5로 3 단어 증가 : 5 * 5 * 5 = 125. => 한 단어를 추가하는 것이 좋습니다.
2 개가 남아있는 경우 :
a) 또는 길이 4에서 3으로 이전 두 단어를 조정하여 길이가 3 인 한 단어를 추가합니다. 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.
b) 2 단어를 길이 5로 늘립니다. 5 * 5 = 25. => 한 단어를 추가하는 것이 좋습니다.
1 개가 남아있는 경우 :
a) 또는 길이 4에서 3으로 이전의 3 개 단어를 조정하여 길이가 3 인 한 단어를 추가합니다. 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.
b) 길이 5로 한 단어 증가 : 4 * 4 * 5 = 80. => 한 단어를 추가하는 것이 좋습니다.
6) 이제 5)의 규칙을 사용하기에 "충분한 큰 N"이 없다면 어떨까요? 가능하다면 계획 b)를 고수해야합니다! 작은 N의 문자열은 다음과 같습니다.
1 : "v", 2 : "vv", 3 : "vvv", 4 : "vvvv"
5 : "vvvvv"→ 5 (플랜 b)
6 : "vvvvvv"→ 6 (계획 b)
7 : "vvv * Vvv"→ 9 (계획 A)
8 : "vvvv * Vvv"→ 12 (계획 A)
9 : "vvvv * Vvvv"→ 16
10 : "vvvv * Vvvvv"→ 20 (플랜 B)
11 : "vvv * Vvv * Vvv"→ 29 (계획 A)
12 : "vvvv * Vvv * Vvv"→ 36 (계획 A)
13 : "vvvv * Vvvv * Vvv"→ 48 (플랜 A)
14 : "vvvv * Vvvv * Vvvv"→ 64
15 : "vvv * Vvv * Vvv * Vvv"→ 81 (플랜 A)
…
7) 자, 길이 N의 문자열에서 최적의 단어 수 K는 얼마입니까?
N <7이면 K = 1 그렇지 않으면 6 <N <11이면 K = 2; 그렇지 않으면 : K = ceil ((N + 1) / 5)
C / C ++ / Java로 작성 : int K = (N<7)?(1) : (N<11)?(2) : ((N+5)/5);
N> 10이면 길이가 3 인 단어의 수는 K * 5-1-N입니다. 이를 통해 다음과 같이 인쇄 된 수를 계산할 수 있습니다.
N> 10이면 As의 수는 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}입니다.
CtrlA+ CtrlC+를 사용 CtrlV하는 것은 4 개의 'A'이후에만 장점입니다.
그래서 나는 다음과 같이 할 것입니다 (적절한 언어를 지정하지 않았기 때문에 의사 기본 코드에서).
// We should not use the clipboard for the first four A's:
FOR I IN 1 TO MIN(N, 4)
PRINT 'CLICK A'
NEXT
LET N1 = N - 4
// Generates the maximum number of pastes allowed:
FOR I IN 1 TO (N1 DIV 3) DO
PRINT 'CTRL-A'
PRINT 'CTRL-C'
PRINT 'CTRL-V'
LET N1 = N1 - 3
NEXT
// If we still have same keystrokes left, let's use them with simple CTRL-Vs
FOR I IN N1 TO N
PRINT 'CTRL-V'
NEXT
편집하다
- 다시 CtrlV메인 루프에서 단일을 사용합니다 .
- 내가 여기서 무엇을하려고하는지 설명하기 위해 몇 가지 주석을 추가했습니다.
- "처음 4 개의 A"블록 문제를 수정했습니다.
As의 수를 두 배로 늘리려면 3 번의 키 입력이 필요합니다. 이미 인쇄 된대로 3 개 이상이있는 경우에만 두 배로 시작하는 것이 좋습니다. 마지막으로 허용 된 키 입력을 a CtrlV로 설정하여 가능한 가장 큰 숫자를 두 배로 늘리기를 원하므로 정렬하기 위해 처음 세 개의 As 이후에 추가 키 입력을 더 많은 As로 채 웁니다.
for (i = 3 + n%3; i>0 && n>0; n--, i--) {
print("a");
}
for (; n>0; n = n-3) {
print("ctrl-a");
print("ctrl-c");
print("ctrl-v");
}
편집하다:
이것은 끔찍합니다. 나는 완전히 앞서 가고 각 사본에 대해 여러 개의 붙여 넣기를 고려하지 않았습니다.
편집 2 :
나는 당신이 그것을 할 수있는 충분한 키 입력이있을 때 3 번 붙여 넣는 것이 가장 좋습니다. 5 번의 키 스트로크에서는 As에 4를 곱합니다. 이것은 4 개의 키 스트로크를 사용하여 3을 곱하는 것보다 낫고 6 개의 키 스트로크를 사용하여 5를 곱하는 것보다 낫습니다. 저는 각 방법에 동일한 수의 키 입력을 제공하여이를 비교하여 각 방법이 동시에 사이클을 완료 할 수 있도록 (60), 3 승수는 15 사이클, 4 승수는 12 사이클, 5 승수는 10주기를 수행합니다. 3 ^ 15 = 14,348,907, 4 ^ 12 = 16,777,216 및 5 ^ 10 = 9,765,625입니다. 키 입력이 4 개만 남아있는 경우 3 배를 수행하는 것이 4 번 더 붙여 넣는 것보다 낫습니다. 기본적으로 이전 4 배를 8 배가되도록 만듭니다. 키 입력이 3 개만 남아있는 경우 2 승수가 가장 좋습니다.
클립 보드에 x 개의 문자가 있고 텍스트 영역에 x 개의 문자가 있다고 가정합니다. 이것을 "상태 x"라고합시다.
"붙여 넣기"를 몇 번 m-1누른 다음 (편의를 위해로 표시) "모두 선택"및 "복사"; 이 시퀀스 후에 우리는 "state m * x"에 도달합니다. 여기서 우리는 총 m + 1 키 입력을 낭비했습니다. 따라서 점근 적 성장은 (적어도) f^n, 여기서 f = m^(1/(m+1)). 나는 그것이 (아직) 증명할 수는 없지만 가능한 최대 점근 성장이라고 믿습니다.
m의 다양한 값을 시도하면 f에 대한 최대 값이 m=4.
다음 알고리즘을 사용해 보겠습니다.
Press A a few times
Press Select-all
Press Copy
Repeat a few times:
Press Paste
Press Paste
Press Paste
Press Select-all
Press Copy
While any keystrokes left:
Press Paste
(최적의 것인지 확실하지 않습니다).
처음에 A를 누르는 횟수는 3입니다. 4 번 누르면 3 번 더 키를 눌러 A를 두 배로 늘릴 수있는 기회를 놓치게됩니다.
마지막에 붙여 넣기를 누르는 횟수는 5 개 이하입니다. 키 입력이 6 개 이상 남아 있으면 붙여 넣기, 붙여 넣기, 붙여 넣기, 모두 선택, 복사, 붙여 넣기를 대신 사용할 수 있습니다.
따라서 다음 알고리즘을 얻습니다.
If (less than 6 keystrokes - special case)
While (any keystrokes left)
A
Else
First 5 keystrokes: A, A, A, Select-all, Copy
While (more than 5 keystrokes left)
Paste, Paste, Paste, Select-all, Copy
While (any keystrokes left)
Paste
(최적의 것인지 확실하지 않습니다). 이것을 실행 한 후의 문자 수는 다음과 같습니다.
3 * pow(4, floor((n - 6) / 5)) * (2 + (n - 1) % 5).
샘플 값 : 1,2,3,4,5,6,9,12,15,18,24,36,48,60,72,96,144,192,240,288, ...
다음은 붙여 넣기로 기존 텍스트를 대체 하지 않는 OP의 두 번째 편집을 사용합니다 .
몇 가지 사항에 유의하십시오.
- ^ A 및 ^ C는 두 번의 키 입력을 수행하는 단일 작업으로 간주 될 수 있습니다. 개별적으로 수행하는 것은 의미가 없기 때문입니다. 사실, 우리는 ^ A ^ C의 모든 인스턴스를 ^ K ^ V로 바꿀 수 있습니다. 여기서 ^ K는 하나의 키 "잘라 내기"연산입니다 (X로 축약합시다). ^ K를 다루는 것이 두 비용의 ^ A ^ C보다 훨씬 더 좋다는 것을 알게 될 것입니다.
- 'A'가 클립 보드에서 시작한다고 가정 해 보겠습니다. 그러면 ^ V (Y로 축약하자)는 A보다 엄격하게 우월하며 모든 고려에서 후자를 제거 할 수 있습니다. (실제 문제에서 클립 보드가 비어있는 상태로 시작하면 다음에서는 첫 X까지 ^ V 대신 Y를 A로 대체합니다.)
따라서 모든 합리적인 키 입력 시퀀스는 YYYXYXYYXY와 같이 X로 구분 된 Y 그룹으로 해석 될 수 있습니다. 시퀀스 s에 의해 생성 된 'A'의 수를 V (s)로 표시합니다. 그러면 V (nXm) = V (n) * V (m). X는 본질적으로 m의 모든 Y를 V (n) 'A'로 대체하기 때문입니다.
따라서 복사-붙여 넣기 문제는 "Nm에 합이되는 m + 1 수를 사용하여 제품을 최대화합니다."라는 문제와 동형이됩니다. 예를 들어 N = 6이면 답은 m = 1이고 숫자 (2,3)입니다. 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (또는 V (YYYXYY) = V (AAA ^ A ^ C ^ V).)
몇 가지 관찰을 할 수 있습니다.
A에 대한 고정 값 m을 선택하려면 숫자 ceil( (N-m)/(m+1) )와 floor( (N-m)/(m+1) )(무엇이든에 조합 합 작업 아웃하게, 더 구체적으로 당신이 필요합니다 (N-m) % (m+1) ceils나머지 floor들). 이는 a < b, (a+1)*(b-1) >= a*b.
불행히도 나는의 가치를 찾는 쉬운 방법을 보지 못합니다 m. 이것이 내 인터뷰라면이 시점에서 두 가지 해결책을 제안 할 것입니다.
옵션 1. 가능한 모든 루프 m. O ( n log n) 솔루션.
C ++ 코드 :
long long ipow(int a, int b)
{
long long val=1;
long long mul=a;
while(b>0)
{
if(b%2)
val *= mul;
mul *= mul;
b/=2;
}
return val;
}
long long trym(int N, int m)
{
int floor = (N-m)/(m+1);
int ceil = 1+floor;
int numceils = (N-m)%(m+1);
return ipow(floor, m+1-numceils) * ipow(ceil, numceils);
}
long long maxAs(int N)
{
long long maxval=0;
for(int m=0; m<N; m++)
{
maxval = std::max(maxval, trym(N,m));
}
return maxval;
}
옵션 2. m정수가 아닌 값을 얻고 근에 [(N-m)/(m+1)]^m대한 도함수를 취하고 m그 근을 구하여 최적의 값을 찾을 수 있습니다. 분석적인 해결책은 없지만, 근본은 예를 들어 Newton의 방법을 사용하여 찾을 수 있습니다. 그런 다음 해당 루트의 바닥과 천장을의 값으로 사용 m하고 가장 좋은 것을 선택합니다.
public int dp(int n)
{
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = i + 1;
for (int i = 2; i < n - 3; i++)
{
int numchars = arr[i] * 2;
int j = i + 3;
arr[j] = Math.max(arr[j], numchars);
while (j < n - 1)
{
numchars = numchars + arr[i];
arr[++j] = Math.max(arr[j], numchars);
}
}
return arr[n - 1];
}
다음은 아래 코드를 사용한 접근 방식과 솔루션입니다.
접근하다:
수행 할 수있는 세 가지 고유 한 작업이 있습니다.
- 키 입력 A- 한 문자 'A'를 출력합니다.
- 키 입력 (Ctrl-A) + (Ctrl-C) -기본적으로 아무것도 출력하지 않습니다. 이 두 키 입력은 각각의 키 입력이 개별적으로 의미가 없기 때문에 하나의 작업으로 결합 될 수 있습니다. 또한이 키 입력은 다음 붙여 넣기 작업에 대한 출력을 설정합니다.
- 키 입력 (Ctrl-V) -이 키 입력에 대한 출력은 실제로 이전 (두 번째) 작업에 따라 달라 지므로 코드에서이를 고려해야합니다.
이제 세 가지 별개의 작업과 각각의 출력이 주어지면 이러한 작업의 모든 순열을 실행해야합니다.
인수:
이제이 문제의 일부 버전에서는 키 입력 시퀀스 (Ctrl + A-> Ctrl + C-> Ctrl + V)가 강조 표시된 선택 항목을 덮어 씁니다. 이 가정을 고려하려면 케이스 2에서 인쇄 된 변수가 0으로 설정된 아래 솔루션에 코드 한 줄만 추가하면됩니다.
case 2:
//Ctrl-A and then Ctrl-C
if((count+2) < maxKeys)
{
pOutput = printed;
//comment the below statement to NOT factor
//in the assumption described above
printed = 0;
}
이 솔루션의 경우
아래 코드는 몇 개의 시퀀스를 인쇄하고 마지막 시퀀스는 주어진 N에 대한 정답입니다. 예를 들어 N = 11의 경우 올바른 시퀀스가됩니다.
가정하에
A, A, A, A, A, C, S, V, V, V, V, : 20 :
가정없이
A, A, A, C, S, V, V, C, S, V, V, : 27 :
이 솔루션에 대한 가정을 유지하기로 결정했습니다.
키 입력 범례 :
'A'-A
'C'-Ctrl + A
'S'-Ctrl + C
'V'-Ctrl + V
암호:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void maxAprinted(int count, int maxKeys, int op, int printed, int pOutput, int *maxPrinted, char *seqArray)
{
if(count > maxKeys)
return;
if(count == maxKeys)
{
if((*maxPrinted) < printed)
{
//new sequence found which is an improvement over last sequence
(*maxPrinted) = printed;
printf("\n");
int i;
for(i=0; i<maxKeys; i++)
printf(" %c,",seqArray[i]);
}
return;
}
switch(op)
{
case 1:
//A keystroke
printed++;
seqArray[count] = 'A';
count++;
break;
case 2:
//Ctrl-A and then Ctrl-C
if((count+2) < maxKeys)
{
pOutput = printed;
//comment the below statement to NOT factor
//in the assumption described above
printed = 0;
}
seqArray[count] = 'C';
count++;
seqArray[count] = 'S';
count++;
break;
case 3:
//Ctrl-V
printed = printed + pOutput;
seqArray[count] = 'V';
count++;
break;
}
maxAprinted(count, maxKeys, 1, printed, pOutput, maxPrinted, seqArray);
maxAprinted(count, maxKeys, 2, printed, pOutput, maxPrinted, seqArray);
maxAprinted(count, maxKeys, 3, printed, pOutput, maxPrinted, seqArray);
}
int main()
{
const int keyStrokes = 11;
//this array stores the sequence of keystrokes
char *sequence;
sequence = (char*)malloc(sizeof(char)*(keyStrokes + 1));
//stores the max count for As printed for a sqeuence
//updated in the recursive call.
int printedAs = 0;
maxAprinted(0, keyStrokes, 1, 0, 0, &printedAs, sequence);
printf(" :%d:", printedAs);
return 0;
}
위의 답변에서 언급 한 트릭을 사용하여 수학적으로 솔루션은 다음과 같이 하나의 방정식으로 설명 할 수 있습니다.
4 + 4 ^ [(N-4) / 5] + ((N-4) % 5) * 4 ^ [(N-4) / 5]. 여기서 []는 최대 정수 인자입니다.
mA를 수동으로 인쇄 한 다음 Ctrl+ A, Ctrl+ C및 Nm-2 Ctrl+ 를 사용하는 것 사이에는 절충안이 있습니다 V. 가장 좋은 해결책은 중간에 있습니다. 최대 키 스트로크 = 10 인 경우 가장 좋은 해결책은 5A 또는 4A를 입력하는 것입니다.
이것을 사용해보십시오 http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ 그리고 중간 정도의 결과를 찾기 위해 약간 최적화 하십시오. 포인트.
다음은 중첩 루프없이 동적 프로그래밍을 사용하는 내 솔루션이며 입력해야하는 실제 문자도 인쇄합니다.
N = 52
count = [0] * N
res = [[]] * N
clipboard = [0] * N
def maybe_update(i, new_count, new_res, new_clipboard):
if new_count > count[i] or (
new_count == count[i] and new_clipboard > clipboard[i]):
count[i] = new_count
res[i] = new_res
clipboard[i] = new_clipboard
for i in range(1, N):
# First option: type 'A'.
# Using list concatenation for 'res' to avoid O(n^2) string concatenation.
maybe_update(i, count[i - 1] + 1, res[i - 1] + ['A'], clipboard[i - 1])
# Second option: type 'CTRL+V'.
maybe_update(i, count[i - 1] + clipboard[i - 1], res[i - 1] + ['v'],
clipboard[i - 1])
# Third option: type 'CTRL+A, CTRL+C, CTRL+V'.
# Assumption: CTRL+V always appends.
if i >= 3:
maybe_update(i, 2 * count[i - 3], res[i - 3] + ['acv'], count[i - 3])
for i in range(N):
print '%2d %7d %6d %-52s' % (i, count[i], clipboard[i], ''.join(res[i]))
이것이 출력입니다 ( 'a'는 'CTRL + A'등을 의미합니다.)
0 0 0
1 1 0 A
2 2 0 AA
3 3 0 AAA
4 4 0 AAAA
5 5 0 AAAAA
6 6 3 AAAacv
7 9 3 AAAacvv
8 12 3 AAAacvvv
9 15 3 AAAacvvvv
10 18 9 AAAacvvacv
11 27 9 AAAacvvacvv
12 36 9 AAAacvvacvvv
13 45 9 AAAacvvacvvvv
14 54 27 AAAacvvacvvacv
15 81 27 AAAacvvacvvacvv
16 108 27 AAAacvvacvvacvvv
17 135 27 AAAacvvacvvacvvvv
18 162 81 AAAacvvacvvacvvacv
19 243 81 AAAacvvacvvacvvacvv
20 324 81 AAAacvvacvvacvvacvvv
21 405 81 AAAacvvacvvacvvacvvvv
22 486 243 AAAacvvacvvacvvacvvacv
23 729 243 AAAacvvacvvacvvacvvacvv
24 972 243 AAAacvvacvvacvvacvvacvvv
25 1215 243 AAAacvvacvvacvvacvvacvvvv
26 1458 729 AAAacvvacvvacvvacvvacvvacv
27 2187 729 AAAacvvacvvacvvacvvacvvacvv
28 2916 729 AAAacvvacvvacvvacvvacvvacvvv
29 3645 729 AAAacvvacvvacvvacvvacvvacvvvv
30 4374 2187 AAAacvvacvvacvvacvvacvvacvvacv
31 6561 2187 AAAacvvacvvacvvacvvacvvacvvacvv
32 8748 2187 AAAacvvacvvacvvacvvacvvacvvacvvv
33 10935 2187 AAAacvvacvvacvvacvvacvvacvvacvvvv
34 13122 6561 AAAacvvacvvacvvacvvacvvacvvacvvacv
35 19683 6561 AAAacvvacvvacvvacvvacvvacvvacvvacvv
36 26244 6561 AAAacvvacvvacvvacvvacvvacvvacvvacvvv
37 32805 6561 AAAacvvacvvacvvacvvacvvacvvacvvacvvvv
38 39366 19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacv
39 59049 19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvv
40 78732 19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvv
41 98415 19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvvv
42 118098 59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacv
43 177147 59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv
44 236196 59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvv
45 295245 59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvvv
46 354294 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacv
47 531441 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv
48 708588 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvv
49 885735 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvvv
50 1062882 531441 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacv
51 1594323 531441 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv
N 개의 키 스트로크가 허용되면 결과는 N-3입니다.
A의-> N-3
CTRL+ A-> N 개의 문자 선택 : +1
CTRL+ C-> N 개의 문자 복사 : +1
Ctrl+ V-> N 문자 붙여 넣기. : +1 즉, ( CTRL+를 사용하여 전체 문자를 선택 했으므로 A) 기존 N-3 문자를 복사 된 N-3 문자 (동일한 문자를 재정의)로 대체하면 결과는 N-3입니다.
'program tip' 카테고리의 다른 글
| Python 프로그램에서 EXE 파일을 어떻게 만들 수 있습니까? (0) | 2020.08.10 |
|---|---|
| 실제 데이터로 테스트하기 위해 공개적으로 액세스 할 수있는 JSON 데이터 소스가 있습니까? (0) | 2020.08.10 |
| 파이썬에서 언제 메서드 대신 함수를 사용해야합니까? (0) | 2020.08.10 |
| Python subprocess.Popen“OSError : [Errno 12] 메모리를 할당 할 수 없습니다.” (0) | 2020.08.10 |
| 대화 형 Matplotlib 그림 저장 (0) | 2020.08.10 |