Максимальное количество символов с использованием нажатий клавиш A, Ctrl + A, Ctrl + C и Ctrl + V

Question

Это вопрос интервью от Google.Я не могу решить это самостоятельно.Может кто-нибудь пролить свет?

Напишите программу для печати последовательности нажатий клавиш таким образом, чтобы она генерировала максимальное количество символов «А».Вам разрешено использовать только 4 клавиши: A , Ctrl + A , Ctrl + C и Ctrl + V * * 1016.Допускается только N нажатий клавиш.Все символы Ctrl + считаются одним нажатием клавиши, поэтому Ctrl + A - это одно нажатие клавиши.

Например, последовательность A , Ctrl + A , Ctrl + C , Ctrl + V генерирует два А за 4 нажатия клавиш.

• Ctrl + A - Выбрать все
• Ctrl + C - Копировать
• Ctrl + V - Вставить

Я занимался математикой.Для любого N, используя x чисел A, один Ctrl + A , один Ctrl + C и y Ctrl + V , мы можем сгенерировать максимальное ((N-1) / 2) ² количество A.Для некоторого N> M лучше использовать столько Ctrl + A , Ctrl + C и Ctrl + V последовательности, так как это удваивает число A.

Последовательность Ctrl + A , Ctrl + V , Ctrl + C не будет перезаписывать существующий выбор.Это добавит скопированный выбор к выбранному.

Answer 1

Есть решение для динамического программирования.Мы начинаем, зная, что 0 ключей могут сделать нас 0 A.Затем мы выполняем итерацию от i до n, выполняя две вещи: нажимая A один раз и нажимая select all + copy, затем вставляем j раз (на самом деле j-i-1 ниже; обратите внимание на хитрость здесь: содержимое по-прежнемув буфер обмена, поэтому мы можем вставить его несколько раз, не копируя каждый раз).Нам нужно учесть только до 4 последовательных вставок, поскольку выбор, копирование, вставка x 5 эквивалентны выбору, копированию, вставке, выделению, копированию, вставке, и последнее лучше, поскольку оставляет больше в буфере обмена.Как только мы достигли n, мы получили желаемый результат.

Может показаться, что сложность равна O (N), но, поскольку числа растут с экспоненциальной скоростью, на самом деле это O (N ^).2 ) из-за сложности умножения больших чисел.Ниже приведена реализация Python.Для N = 50000 требуется около 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 нажатий клавиш, и 2 новых нажатия идут для выбора всех и копирования.Поэтому мы наносим пасту j-i-2 раз.Так как вставка добавляет к существующей последовательности dp[i] A, нам нужно добавить 1, делая ее j-i-1.Это объясняет j-i-1 во 2-ой последней строке.

Вот некоторые результаты (n => количество символов A):

• 7 => 9
• 9 => 16
• 10 => 20 * +1033 *
• 100 => 1391569403904 * тысяча тридцать-пять *
• 1 000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50 000 => очень большое число!

Я согласен с @SB, что вы всегда должны высказывать свои предположения: мое состоит в том, что вам не нужно вставлятьдважды, чтобы удвоить количество символов.Это дает ответ на 7, поэтому, если мое решение неверно, предположение должно быть правильным.

В случае, если кто-то задается вопросом, почему я не проверяю последовательности вида Ctrl + A , Ctrl + C , A , Ctrl + V : конечный результат всегда будетбыть таким же, как A , Ctrl + A , Ctrl + C , Ctrl + V , которые я делаю считаю.

Answer 2

Используя решение 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 идеальным шаблоном является выбор, копирование, вставка, вставка, вставка и повторение.Это умножит количество As на 4 каждые 5 нажатий клавиш.Если этот шаблон 5 нажатий клавиш не может использовать оставшиеся нажатия клавиш сам по себе, некоторое количество из 4 шаблонов нажатий клавиш (SCPP) использует последние нажатия клавиш, заменяя SCPPP (или удаляя одну из вставок) по мере необходимости.4 шаблона нажатия клавиш умножают общее количество на 3 каждые 4 нажатия клавиш.

Используя этот шаблон, приведем некоторый код Python, который получает те же результаты, что и решение marcog, но имеет значение 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 == 1 есть 3, n % 5 == 2 есть 2, n % 5 == 3 есть 1 и n % 5 == 4 есть 0. Это можно упростить до (4 - n) % 5.

Расчет e4: Общее количество шаблонов увеличивается на 1 всякий раз, когда n % 5 == 0, поскольку оказывается, что это число увеличивается точно до n / 5.Используя деление по полу, мы можем получить общее количество шаблонов, общее число для e4 - это общее количество шаблонов минус e3.Для тех, кто не знаком с Python, // - это ориентированная на будущее запись для разделения пола.

Answer 3

Вот как бы я подошел к этому:

• предположим Ctrl A = выбрать все
• предположим, Ctrl C = выбор копии
• предположим, Ctrl V = вставить скопированное выделение

учитывая некоторый текст, для его дублирования требуется 4 нажатия клавиш:

• Ctrl A , чтобы выделить все
• Ctrl C , чтобы скопировать его
• Ctrl V для вставки (это вставит поверх выделенного элемента - Укажите ваши предположения)
• Ctrl V , чтобы вставить снова, что удваивает его.

Оттуда вы можете рассмотреть вопрос о том, чтобы сделать 4 или 5 A, а затем повторить все вышеперечисленное. Обратите внимание, что выполнение ctrl + a, c, v, v будет увеличивать ваш текст в геометрической прогрессии при прохождении цикла. Если оставшиеся штрихи <4, просто продолжайте делать <kbd>Ctrl V

Ключ к интервью в таких местах, как Google, заключается в том, чтобы высказать свои предположения и поделиться своим мнением. они хотят знать, как вы решаете проблемы.

Answer 4

Это решаемо в O (1): Как и с числами Фибоначчи, есть формула для вычисления количества напечатанных As (и последовательности нажатий клавиш):

---

1) Мы можем упростить описание проблемы:

• Имеет только [A], [C-a] + [C-c], [C-v] и пустой буфер копирования-вставки

равно

• имеет только [C-a] + [C-c], [C-v] и «A» в буфере копирования-вставки.

---

2) Мы можем описать последовательность нажатий клавиш как строку из N символов из {'*', 'V', 'v'}, где 'v' означает [Cv], а '*' означает [Ca] и «V» означает [Cc]. Пример: "vvvv * Vvvvv * Vvvv"

Длина этой строки по-прежнему равна N.

Произведение длин Vv-слов в этой строке равно количеству произведенных As.

---

3) Учитывая фиксированную длину N для этой строки и фиксированное число слов K, результат будет максимальным, если все слова будут иметь примерно одинаковую длину. Их попарная разница не более ± 1.

Теперь, каково оптимальное число K, если дано N?

---

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) Предположим, у нас достаточно большое N, чтобы сгенерировать строку со многими словами длиной 4, но осталось несколько нажатий клавиш; как мы должны их использовать?

• Если осталось 5 или более: добавьте другое слово длиной 4.

• Если осталось 0: Готово.

• Если осталось 4: мы могли бы либо

  а) добавить одно слово длиной 3: 4 * 4 * 4 * 4 * 3 = 768.

  b) или увеличьте 4 слова до 5: 5 * 5 * 5 * 5 = 625. => Лучше добавить одно слово.

• Если осталось 3: мы можем либо

  a) или добавьте одно слово длиной 3, изменив предваряющее слово от длины 4 до 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144. </p>

  б) увеличить 3 слова до 5: 5 * 5 * 5 = 125. => Лучше добавить одно слово.

• Если осталось 2: мы могли бы либо

  а) или добавьте одно слово длиной 3, изменив два предыдущих слова на длину от 4 до 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27. </p>

  б) увеличить 2 слова до 5: 5 * 5 = 25. => Лучше добавить одно слово.

• Если осталось 1: мы могли бы либо

  а) или добавьте одно слово длиной 3, изменив предыдущие три слова длиной от 4 до 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81. </p>

  б) увеличить слово на длину 5: 4 * 4 * 5 = 80. => Лучше добавить одно слово.

---

6) А что, если у нас нет «достаточно большого N», чтобы использовать правила из 5)? Мы должны придерживаться плана б), если это возможно! Струны для маленьких 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) Каково оптимальное количество слов K в строке длины N?

Если N <7, то K = 1, иначе, если 6 <N <11, то K = 2; в противном случае: <strong>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, число of Как будет: 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}

Answer 5

Использование Ctrl A + Ctrl C + Ctrl V являетсяПреимущество только после 4 'А.* Редактировать

1. Вернуться к использованию одного Ctrl V в основном цикле.
2. Добавлены некоторые комментарии, чтобы объяснитьЯ пытаюсь сделать здесь.
3. Исправлена ​​проблема с блоком «первые четыре А».

Answer 6

Для удвоения числа As требуется 3 нажатия клавиш.Имеет смысл начать удваивать, когда у вас есть 3 или более, как уже напечатано.Вы хотите, чтобы последним разрешенным нажатием клавиши было Ctrl V , чтобы удостовериться, что вы удваиваете наибольшее возможное число, поэтому для его выравнивания мы заполним любые дополнительные нажатия клавиш послеПервые три Как в начале с более как.

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. Это лучше, чем умножение на 3 с использованием 4 нажатий клавиш, и лучше, чем умножение на 5 с использованием 6 нажатий клавиш.Я сравнил это, дав каждому методу одинаковое количество нажатий клавиш, достаточное для того, чтобы каждый из них завершал цикл в одно и то же время (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-х множитель.

Answer 7

В последующем используется второе редактирование OP, при котором вставка не заменяет существующий текст.

Обратите внимание на несколько вещей:

• ^ A и ^ C можно рассматривать как одно действие, которое требует двух нажатий клавиш, поскольку никогда не имеет смысла выполнять их по отдельности. Фактически, мы можем заменить все экземпляры ^ A ^ C на ^ K ^ V, где ^ K является одноклавишной операцией «вырезать» (давайте сократим ее X). Мы увидим, что иметь дело с ^ K гораздо приятнее, чем с двумя издержками ^ A ^ C.
• Предположим, что в буфере обмена начинается буква «А». Тогда ^ V (сокращенно Y) строго превосходит A, и мы можем отбросить последнее из всех соображений. (В реальной задаче, если буфер обмена начинается пустым, в дальнейшем мы просто заменим Y на A вместо ^ V вплоть до первого X.)

Таким образом, любая разумная последовательность нажатий клавиш может быть интерпретирована как группа Y, разделенных X, например, YYYXYXYYXY. Обозначим через V (s) число 'A, произведенных последовательностью s. Тогда V (nXm) = V (n) * V (m), потому что X по существу заменяет каждый Y в m на V (n) 'A's.

Проблема копирования-вставки, таким образом, изоморфна следующей проблеме: «используя числа m + 1, которые суммируют с N-m, максимизируйте их произведение». Например, когда N = 6, ответом является m = 1 и числа (2,3). 6 = 2 * 3 = V (ГГГГГГ) = V (AA ^ A ^ C ^ V ^ V) (или V (ГГГГГГ) = V (AAA ^ A ^ C ^ V).)

Мы можем сделать несколько замечаний:

Для фиксированного значения 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 и найдя ее корень. Аналитического решения не существует, но корень можно найти, например, с помощью Метод Ньютона. Затем используйте пол и потолок этого корня для значения m и выберите тот, который лучше.

Answer 8

Предположим, у вас есть x символов в буфере обмена и x символов в текстовой области; давайте назовем это «состояние х».

Давайте несколько раз нажмем «Вставить» (для удобства я обозначу его m-1), затем «Выбрать все» и «Копировать»; после этой последовательности мы получаем «состояние 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

(не уверен, что это оптимальный вариант).

Количество нажатий А в начале равно 3: если вы нажмете его 4 раза, вы упустите возможность удвоить число А еще 3 нажатиями клавиш.

Количество нажатий кнопки «Вставить» в конце составляет не более 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, ...

Answer 9

Если разрешены 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.

Answer 10

Вот мое решение с динамическим программированием, без вложенного цикла, которое также печатает фактические символы, которые вам нужно набрать:

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]))

Это вывод («означает»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