[algorithm] 키 입력 A, Ctrl + A, Ctrl + C 및 Ctrl + V를 사용하는 최대 문자 수

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) 3 단어를 길이 5로 늘립니다. 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 인 한 단어를 추가합니다. 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}입니다.

답변

// 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

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");
}

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

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