O (n ^ 2) недостаточно быстро решает это. любые более быстрые подходы?

Ответ 1

При малом n алгоритм грубой силы O(n²), проверяющий каждую пару, быстрее, конечно, поэтому хотелось бы найти хорошую точку отсечки для алгоритмов переключения. Без измерения я ожидал бы значение от 200 до 3000 из-за соображений, не связанных с обратным конвертом.

Преобразуйте идентификатор пирата в int, проанализировав его как шестнадцатеричное число. Сохраните идентификаторы в

int[] pirates = new int[n];

Сначала подсчитайте количество пар пиратов с идентичными идентификаторами (этот шаг здесь можно опустить, так как в заявлении проблемы нет).

int[] allFour = new int[65536];
for(int i = 0; i < n; ++i) {
    allFour[pirate[i]] += 1;
}
int fourIdentical = 0;
for(int i = 0; i < 65536; ++i) {
    fourIdentical += allFour[i]*(allFour[i] - 1) / 2;
}

Затем подсчитайте пары пиратов с тремя одинаковыми кусками в их ID,

int oneTwoThree(int p) {
    return p >> 4;
}
int oneTwoFour(int p) {
    return (p & 0x000F) | ((p & 0xFF00) >> 4);
}
int oneThreeFour(int p) {
    return (p & 0x00FF) | ((p & 0xF000) >> 4);
}
int twoThreeFour(int p) {
    return p & 0x0FFF;
}

int[] noFour  = new int[4096];
int[] noThree = new int[4096];
int[] noTwo   = new int[4096];
int[] noOne   = new int[4096];

for(int i = 0; i < n; ++i) {
    noFour[oneTwoThree(pirate[i])] += 1;
    noThree[oneTwoFour(pirate[i])] += 1;
    noTwo[oneThreeFour(pirate[i])] += 1;
    noOne[twoThreeFour(pirate[i])] += 1;
}

int threeIdentical = 0;
for(int i = 0; i < 4096; ++i) {
    threeIdentical += noFour[i]*(noFour[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
    threeIdentical += noThree[i]*(noThree[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
    threeIdentical += noTwo[i]*(noTwo[i]-1) / 2;
}
for(int i = 0; i < 4096; ++i) {
    threeIdentical += noOne[i]*(noOne[i]-1) / 2;
}

Но каждая пара пиратов с четырьмя одинаковыми кусками была подсчитана 4 choose 3 = 4 раз здесь, для каждого из возможных выборов из трех кусков, поэтому нам нужно вычесть это (ну, а не для проблемы, но в принципе)

threeIdentical -= 4*fourIdentical;

Затем подсчитайте пары пиратов с двумя одинаковыми кусками в их ID:

int oneTwo(int p) {
    return p >> 8;
}
int oneThree(int p) {
    return ((p & 0x00F0) >> 4) | ((p & 0xF000) >> 8);
}
int oneFour(int p) {
    return (p & 0x000F) | ((p & 0xF000) >> 8);
}
int twoThree(int p) {
    return (p & 0x0FF0) >> 4;
}
int twoFour(int p) {
    return (p & 0x000F) | ((p & 0x0F00) >> 4);
}
int threeFour(int p) {
    return p & 0x00FF;
}

выделите шесть массивов 256 int и подсчитайте количество пиратов с соответствующими кусками в местах a и b, например

int twoIdentical = 0;
int[] firstTwo = new int[256];
for(int i = 0; i < n; ++i) {
    firstTwo[oneTwo(pirate[i])] += 1;
}
for(int i = 0; i < 256; ++i) {
    twoIdentical += firstTwo[i]*(firstTwo[i] - 1) / 2;
}
// analogous for the other five possible choices of two nibbles

Но пары с четырьмя одинаковыми кусками были подсчитаны здесь 4 choose 2 = 6 раз, а пары с тремя одинаковыми кусками были подсчитаны 3 choose 2 = 3 раз, поэтому нам нужно вычесть

twoIdentical -= 6*fourIdentical + 3*threeIdentical;

Затем число пар с одним одинаковым куском. Надеюсь, вы можете догадаться, какие четыре функции и массивы необходимы. Затем мы будем считать пары с четырьмя одинаковыми кусками 4 choose 1 = 4 раз, те, у которых три одинаковых nibbles 3 choose 1 = 3 times, и пары с двумя одинаковыми nibbles 2 choose 1 = 2 times, поэтому

oneIdentical -= 4*fourIdentical + 3*threeIdentical + 2*twoIdentical;

Наконец, число пар без одинаковых кусков:

int noneIdentical = (int)((long)n*(n-1) / 2) - oneIdentical - twoIdentical - threeIdentical - fourIdentical;

(приведение к long во избежание переполнения n*(n-1)).

Ответ 2

Это может быть быстрый способ сравнить пары идентификаторов. Предполагается, что оба идентификатора были прочитаны как шестнадцатеричные числа, а не строки.

int bits = p[i] ^ p[j];
int ans = ((bits | bits >> 1 | bits >> 2 | bits >> 3) & 0x1111) % 15;
diff[ans - 1]++;

Ответ 3

Как насчет этого:

Создайте 4-мерный массив целых чисел с каждым размером, составляющим 16, с элементами, инициализированными до 0. Таким образом, это будет 16*16*16*16*4 = 262144 байты, что около 262KB. Теперь проиндексируйте (вставляйте) каждый из идентификаторов в эту структуру по мере их чтения. Когда вы индексируете, увеличивайте counter на каждом измерении...

По мере того, как вы индексируете эту структуру, вы можете постепенно вычислить требуемый ответ.

В качестве примера предположим, что я индексирую идентификатор мертвый. В первом измерении выберите позицию, соответствующую d, скажем, счетчик в этой позиции n1, это означает, что до сих пор были n1 идентификаторы с d в позиции 1. Теперь возьмите e и вставьте его в правильное положение во втором измерении... и скажем, что счетчик в этом положении n2, тогда я точно знаю, что есть n1 - n2, которые отличаются в 3 положениях по сравнению с текущим идентификатором, который вставлен...

EDIT: Я начинаю сомневаться в себе. Что делать, если два идентификатора отличаются от первого символа, но равны во втором? Этот подход не сможет понять, что я думаю. Нужно больше думать...

РЕДАКТИРОВАТЬ: После паузы в "интеллектуальном решении" я попытался улучшить базовый алгоритм O(n^2), как показано ниже.

Каждый идентификатор имеет 4 шестнадцатеричных десятичных разряда и поэтому может быть упакован в одно целое число (достаточно двух байтового слова). Итак, такое целое число будет выглядеть так:

[ ][ ][ ][ ] * [ ][ ][ ][ ] * [ ][ ][ ][ ] * [ ][ ][ ][ ]

Где каждый [ ] представляет бит, и каждая группа [ ][ ][ ][ ] (полубайт) соответствует шестнадцатеричной цифре в идентификаторе. Теперь нам нужен способ быстро сравнить два из этих идентификаторов. Учитывая два идентификатора a и b, сначала вычисляем c = a ^ b, что даст нам XOR двух бит-паттеров (разница, вид). Теперь мы сравниваем этот бит-шаблон c со следующими постоянными шаблонами:

u = [1][1][1][1] * [0][0][0][0] * [0][0][0][0] * [0][0][0][0]

v = [0][0][0][0] * [1][1][1][1] * [0][0][0][0] * [0][0][0][0]

w = [0][0][0][0] * [0][0][0][0] * [1][1][1][1] * [0][0][0][0]

x = [0][0][0][0] * [0][0][0][0] * [0][0][0][0] * [1][1][1][1]

Сравнение выглядит следующим образом:

diffs = 0

if (c & u)
  diffs++
if (c & v)
  diffs++
if (c & w)
  diffs++
if (c & x)
  diffs++

В конце этой операции diffs будет содержать количество символов, из которых a и b отличается. Обратите внимание, что один и тот же подход может быть реализован без упаковки идентификаторов в целые числа (т.е. Хранить каждую шестнадцатеричную цифру на собственном цельном /char типе), но я думал, что память, сохраненная этой упаковкой, может означать что-то.

IMHO, это лишь незначительное улучшение по сравнению с основным алгоритмом O(n^2). Я был бы очень разочарован, если принятый ответ - это трюк, а не ответ на основе лучшего алгоритма/структуры данных. С нетерпением жду, когда кто-нибудь предложит какой-то совет по такому ответу...: -)

Ответ 4

Это можно решить с помощью одного прохода через список идентификаторов, так что время O (n), но вы все равно должны быть осторожны, чтобы реализация выполнялась вовремя.

Рассмотрим проблему нахождения пар равных строк. Это можно сделать, отслеживая количество каждой строки, ранее найденной на карте:

long pairs = 0;
Set<String, Long> map = new HashMap<String, Long>();
for(String id:ids) {
    if(map.containsKey(id)) {
        pairs += map.get(id);
        map.put(id, map.get(id) + 1);
    } else {
        map.put(id, 1);
    }
}

Теперь найдите пары, которые отличаются одним символом. Вы можете хранить строки, исключая каждый символ. Итак, для "abcd" храните ".bcd", "a.cd", "ab.d" и "abc". на карте. Для каждого идентификатора вы можете добавить количество строк каждой строки для каждой отсутствующей позиции символа. Это также будет считать равные строки, поэтому вычитайте количество равных строк.

Обобщите более отсутствующие символы, используя Принцип включения/исключения. Например, количество строк с двумя разными символами из s:

sum of all character positions `x` and `y`:
    the number of strings equal to `s` excluding characters `x` and `y`
    - the number of strings equal to `s` excluding character `x`
    - the number of strings equal to `s` excluding character `y`
    + the number of strings equal to `s`

По соображениям эффективности вы не хотите выполнять строковые манипуляции, поэтому фактическая реализация должна преобразовывать String в целые числа. Кроме того, вместо Map вы можете использовать длинный массив (где индекс представляет String, а значение - количество совпадающих строк).

Ответ 5

Вместо подсчета пар вы могли бы просто подсчитать совпадения, а затем вычислить пары? IE 5 коды, которые начинаются с d, на самом деле будут 5!= 10 пар.

Это позволит вам использовать структуру, которая могла бы рассчитывать совпадения позиций во время вставки, а не итеративно.

EDIT:

В то время я думал о том, что возможно иметь древовидную структуру с корнем node и 4 вложенными уровнями. Каждый уровень представляет собой одну позицию в коде. IE root → d → e → a → f. Когда вы вставляете каждый код, если этот char не существует на этом уровне, вставьте его, если он его подсчитает. В конце каждой вставки кода вы узнаете, сколько совпадений имеет код, который затем добавляется в соответствующее ведро в diff. Затем конвертируйте в пары, а не только в совпадения, взяв n! каждого ведра.

Ответ 6

У вас есть пары n!/(n-2)!2! = O (n ²) (n - количество входов), и независимо от того, что вы делаете, вам нужно будет проверить их все, поскольку это требование.

Вы можете оптимизировать время, вставив весь ввод в DAWG и пройдя его позже. Для любых 2 путей в DAWG подобие определяется как набор, состоящий из ребер, присутствующих в обоих путях. Постройте этот набор и вычтите его размер от длины пути, чтобы найти расстояние разности.

Ответ 7

Можно ли сопоставить рядовое число с одной трехмерной матрицей P [x] [y] [z]?

• x - число рядовых (2 ≤ n ≤ 65536).
• y - идентификатор, который находится между 0 и 15 (0 - 9, a - f).
• z будет 1, содержащим опцию идентификатора (0 - f).

например:

мертвые
говядина
f00d

Соответствующий p [x] [y] будет

0 1 2 3 4 5 6 7 8 9 a b c d e f

0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

z demension будет

0 0 0 0 0 0 0 0 0 2 0 0 9 4 0 (2 → 0010, 9 → 1001, 4 → 0100)
0 0 0 0 0 0 0 0 0 0 8 0 0 6 1 (6 → 0110, 8 → 1000, 1 → 0001)
6 0 0 0 0 0 0 0 0 0 0 0 1 0 8

Мы проверяем столбец p [x] [y] по столбцу, если два пирата имеют одинаковый идентификатор, тогда мы делаем один "&" разрядную операцию между их позициями и сохранение результата (может понадобиться еще одна матрица, чтобы решить, сколько раз эти два пирата соответствовали этому новому совпадению в текущем столбце, O (1)).

Пройдите эту матрицу один раз, возможно, будет достаточно O (n).

Не доказано кодом, такого рода идея. Надеюсь, поможет.

Спасибо за эту головоломку.

Ответ 8

Этот ответ представляет собой разработку ответов, предоставленных @fgb/@Daniel.

Представьте каждый идентификатор, например H1H2H3H4 (четыре шестнадцатеричных числа)

• У нас есть четыре массива, каждая из которых имеет длину 16*16*16 (4096). Эти четыре массива будут использоваться для отслеживания идентификаторов, которые равны в 3-х позициях.

• Для каждого прочитанного идентификатора вычислите значения (целые числа) H2H3H4, H1H3H4, H1H2H4, H1H2H3 (обратите внимание, что эти значения варьируются от 0 до 4095, поэтому мы выбрали массив размер 4096). Теперь используйте каждое из этих значений для индексации в четыре массива, упомянутых в шаге (1), и увеличивайте соответствующую позицию на единицу.

• У нас есть еще один массив шесть, каждый из которых имеет длину 16*16 (256). Эти пять массивов будут использоваться для отслеживания идентификаторов, которые равны в двух позициях.

• Для каждого прочитанного идентификатора вычислите значения (целые числа) H3H4, H2H4, H1H4, H1H3, H1H2, H2H3. Теперь используйте каждое из этих значений для индексации в шесть массивов, упомянутых на шаге (3), и увеличивайте соответствующую позицию на единицу. Каждая позиция массива эффективно подсчитывает количество идентификаторов, которые равны в двух положениях (обратите внимание, однако, что этот счет будет включать в себя количество идентификаторов, равное в 3-х позициях).

• У нас есть еще один массив четыре, каждый из которых имеет ширину 16. Эти четыре массива будут использоваться для отслеживания идентификаторов, которые равны в 1 позиции.

• Для каждого прочитанного идентификатора вычислите значения (целые числа) H4, H3, H2, H1. Теперь используйте каждое из этих значений для индексации в четыре массива, упомянутых на шаге (5), и увеличивайте соответствующую позицию на единицу. Каждая позиция массива эффективно подсчитывает количество идентификаторов, которые равны в 1 позиции (опять же, этот счет будет включать в себя количество идентификаторов, которые равны и в 3, 2 позиции).

Обратите внимание, что все это может быть выполнено за один проход через вход. Однако этого недостаточно для вычисления окончательного ответа, мы должны постепенно вычислять окончательный ответ вместе с шагами 1 - 6. Вот как мы можем это сделать:

diff1 = 0
diff2 = 0
diff3 = 0
diff4 = 0

• На шаге (2), когда мы увеличиваем некоторую позицию массива, если результирующее значение u (u > 1), тогда diff1 = diff1 + (u - 1). Это означает, что с уже найденными идентификаторами (u - 1) мы можем сделать (u - 1) новые пары (путем объединения каждого из них с текущим идентификатором).

• На шаге (4), когда мы увеличиваем некоторую позицию массива, если результирующее значение v (v - u >= 1), тогда diff2 = diff2 + (v - u). Это означает, что мы знаем, что число идентификаторов u уже было рассмотрено на предыдущем шаге, их не следует пересчитывать. Таким образом, (v - u) дает те другие идентификаторы, которые равны/отличаются от этого идентификатора на только 2 позициях. С помощью этих идентификаторов мы можем сделать (v - u) новые пары (путем объединения каждого из них с текущим идентификатором).

• На шаге (6), когда мы увеличиваем некоторую позицию массива, если результирующее значение w (w - u >= 1), тогда diff3 = diff3 + (w - u). Объяснение очень похоже на приведенное выше.

Запомните еще раз, что все эти шаги можно выполнить за один проход по всему вводу.

Теперь, следующее, как вычислить diff4. Это можно сделать на шаге (2), когда мы увеличиваем некоторую позицию в массиве, если новое значение равно 1, а затем diff4 = diff4 + 1 и, если новое значение равно 2, а затем diff4 = diff4 - 1. Это отслеживает свежие идентификаторы, для которых до сих пор не найдены совпадающие идентификаторы.

ОБНОВЛЕНИЕ:. Этот подход работает хорошо, но метод, который я предложил для вычисления diff4, не будет работать. В принципе, diff4 - это не об уникальных идентификаторах, а о том, сколько пар мы можем сформировать, объединив идентификаторы, которые отличаются от друг друга на всех 4 позициях.

Другой подход (для diff4) использовался в следующей реализации в C:

#include <stdio.h>
#include <stdlib.h>

// forward declarations
__inline int update_same3 (int x1, int x2, int x3, int* map, int* diff1, int* overlaps);
__inline int update_same2 (int x1, int x2, int u, int* map, int* diff2, int* overlaps);
__inline void update_same1 (int x1, int v, int* map, int* diff3, int* overlaps);

int main () {
  // number of input identifiers
  int n = 0;

  // each identifier represented as four hexa-decimal digits
  int h1, h2, h3, h4; 

  // final answer
  int diff1 = 0;
  int diff2 = 0;
  int diff3 = 0;
  int diff4 = 0;

  int i, u1, u2, u3, u4, v1, v2, v3, v4, v5, v6, overlaps;

  // maps for keeping track of the identifiers
  int* maps [14];
  maps[0] = (int*) calloc (4096, sizeof(int)),  // h1h2h3
  maps[1] = (int*) calloc (4096, sizeof(int)),  // h2h2h4
  maps[2] = (int*) calloc (4096, sizeof(int)),  // h1h3h4
  maps[3] = (int*) calloc (4096, sizeof(int)),  // h2h3h4
  maps[4] = (int*) calloc (256, sizeof(int)),  // h1h2
  maps[5] = (int*) calloc (256, sizeof(int)),  // h1h3
  maps[6] = (int*) calloc (256, sizeof(int)),  // h1h4
  maps[7] = (int*) calloc (256, sizeof(int)),  // h2h3
  maps[8] = (int*) calloc (256, sizeof(int)),  // h2h4
  maps[9] = (int*) calloc (256, sizeof(int)),  // h3h4
  maps[10] = (int*) calloc (16, sizeof(int)),  // h1
  maps[11] = (int*) calloc (16, sizeof(int)),  // h2
  maps[12] = (int*) calloc (16, sizeof(int)),  // h3
  maps[13] = (int*) calloc (16, sizeof(int)),  // h4

  // main loop
  fscanf (stdin, "%d\n", &n);
  for (i = 0; i < n; i++) {
    // scan identifier 
    fscanf (stdin, "%1x%1x%1x%1x", &h1, &h2, &h3, &h4);

    // keeps track of the number of identifiers that the current
    // identifier overlaps with, required for calculating diff4
    overlaps = 0;

    u1 = update_same3 (h1, h2, h3, maps[0], &diff1, &overlaps); //h1h2h3
    u2 = update_same3 (h1, h2, h4, maps[1], &diff1, &overlaps); //h1h2h4
    u3 = update_same3 (h1, h3, h4, maps[2], &diff1, &overlaps); //h1h3h4
    u4 = update_same3 (h2, h3, h4, maps[3], &diff1, &overlaps); //h2h3h4

    v1 = update_same2 (h1, h2, u1 + u2, maps[4], &diff2, &overlaps); //h1h2
    v2 = update_same2 (h1, h3, u1 + u3, maps[5], &diff2, &overlaps); //h1h3
    v3 = update_same2 (h1, h4, u2 + u3, maps[6], &diff2, &overlaps); //h1h4
    v4 = update_same2 (h2, h3, u1 + u4, maps[7], &diff2, &overlaps); //h2h3
    v5 = update_same2 (h2, h4, u2 + u4, maps[8], &diff2, &overlaps); //h2h4
    v6 = update_same2 (h3, h4, u3 + u4, maps[9], &diff2, &overlaps); //h3h4

    update_same1 (h1, (v1 + v2 + v3) - (u1 + u2 + u3), maps[10], &diff3, &overlaps); //h1
    update_same1 (h2, (v1 + v4 + v5) - (u1 + u2 + u4), maps[11], &diff3, &overlaps); //h2
    update_same1 (h3, (v2 + v4 + v6) - (u1 + u3 + u4), maps[12], &diff3, &overlaps); //h3
    update_same1 (h4, (v3 + v5 + v6) - (u2 + u3 + u4), maps[13], &diff3, &overlaps); //h4

    // if the current identifier overlapped with n existing identifiers
    // then it did not overlap with (i - n) identifiers
    if (i - overlaps > 0)
      diff4 += (i - overlaps); 
  }

  // print results
  printf ("%d %d %d %d\n", diff1, diff2, diff3, diff4);
}

// identify overlaps at 3 positions
__inline int update_same3 (int x1, int x2, int x3, int* map, int* diff1, int* overlaps) {
  int idx = (x1 << 8 | x2 << 4 | x3);
  int u = (map[idx])++;
  if (u > 0) {
    (*diff1) += u;
    (*overlaps) += u;
  }
  return u;
}

// identify overlaps at 2 positions
__inline int update_same2 (int x1, int x2, int u, int* map, int* diff2, int* overlaps) {
  int idx = (x1 << 4 | x2);
  int v = (map[idx])++;
  if (v - u > 0) {
    (*diff2) += (v - u);
    (*overlaps) += (v - u);
  }
  return v;
}

// identify overlaps at 1 position
__inline void update_same1 (int x1, int v, int* map, int* diff3, int* overlaps) {
  int w = (map[x1])++;
  if (w - v > 0) {
    (*diff3) += (w - v);
    (*overlaps) += (w - v);
  }
}

Я тестировал это с некоторыми примерами ввода, и, похоже, он работает. Было бы здорово, если OP сможет проверить это и посмотреть, работает ли он. Это может потребовать еще немного работы.

UPDATE: ОК, он работает! пришлось переформатировать код немного, чтобы получить его через компилятор там. Я также обновил код, указанный здесь, чтобы отразить изменения.

Ответ 9

Вы могли бы попробовать что-то в этом направлении:

когда вы обрабатываете каждую запись, добавьте ее в список имен, которые имеют конкретную букву в позиции 1. Любые записи в списке уже попадают в список "4 матча кандидатов".

Затем добавьте его в список имен, имеющих вторую букву. Любые записи, находящиеся в этом списке, которые находятся в "4 матчах кандидатов", остаются в "4 матчах кандидатов", все остальные записи в "кандидате на 4 кандидата" переносятся в список "3 матча кандидатов" вместе со всеми записями в этом списке,

Затем добавьте его в список имен, имеющих третью букву. Любые записи, уже находящиеся в этом списке, которые находятся в "3 матчах кандидатов", остаются в "3 матчах кандидатов", все остальные записи в "кандидате на 3 кандидата" переносятся в список "2 совпадающих кандидатов" вместе со всеми записями, уже указанными в этом список. Любые записи в этом списке, которые находятся в "4 матчах кандидатов", остаются в "4 матчах кандидатов", все остальные записи в "4 кандидатах на матч" переносятся в список "3 матча кандидатов".

Затем добавьте его в список имен, имеющих определенную четвертую букву. Любые записи, уже внесенные в этот список, добавляются к счету из 1 совпадающего кандидата, любые записи в списке кандидатов на 2 кандидата добавляются к счету из 2 совпадающих кандидатов, любые записи в списке кандидатов 3 матча добавляются в кол-во 3 кандидатов в матче, и любые записи в списке кандидатов на 4 матча добавляются к счету из 4 совпадающих кандидатов.

Это означает, что вы только обрабатываете список один раз и вместо того, чтобы проверять каждую другую запись, вам нужно только проверить подмножество, которое имеет одинаковые буквы в тех же позициях.

Или, может быть, мне нужно лечь спать...

EDIT:

Итак, я неправильно понял цель вчера вечером. Вышеупомянутый процесс подсчитывает сходство, а не различия, но мы можем использовать аналогичный подход для подсчета различий. В основном сохраняйте 4 списка для 1 разностных слов, 2 разностных слов, 3 разностных слова и 4 разностных слова. Добавьте все слова, которые мы видели до сих пор, в список из 4 разностных слов. Затем начните с списка, содержащего все существующие имена, затем найдите список слов, на которых в первую очередь будут указаны первые слова первого слова. Переместите все слова в этом списке, которые находятся в 2-х разностном списке, в один список различий, 3-х разностный список для 2-х разностных списков и 4-х разностных списков в 3-х разном списке.

После того, как вы обработали весь список, вы можете добавить счет в каждом списке к глобальным подсчетам.

Я думаю, это должно сработать, но я расскажу об этом позже...