Свершилось! Аркадий Дьяконов darkaha@mail.ru победил задачи, поставленные перед нашими читателями экспертами компании ABBYY, за что и был награжден сертификатом на FineReader. Слава ему!

 

Правильные ответы

 

Задача 1

Дан массив из целых чисел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.

 

Решение

Идея алгоритма: ищем первый положительный элемент в последовательности. Если такого не окажется, то решением будет максимальный элемент. Если такой элемент нашелся, то считаем, что текущая сумма и максимальная равны этому элементу. Проходим по массиву. На каждом шаге увеличиваем текущую сумму на текущий элемент. Если текущая сумма оказалась отрицательной — обнуляем ее. Проверяем, если значение текущей суммы оказывается больше максимальной, то максимальной сумме присваиваем текущую.

Одно из решений задачи:

// Далее считаем, что массив, в котором ищем подмассив, именуется как array.
// Его размер же именуется как arraySize
int maxSum = array[0];
int maxStartIdx = 0;
int maxEndIdx = 0;
int currentSum = 0;
int currentStartIdx = 0;
for( int i = 0; i < arraySize; i++ ) {
    currentSum += array[i];
    if( currentSum > maxSum ) {
        maxSum = currentSum;
        maxStartIdx = currentStartIdx;
        maxEndIdx = i;
    } else if( currentSum < 0 ) {
        currentSum = 0;
        currentStart = i + 1;
    }
}
 

Задача 2

Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичное время, объясните их преимущества и недостатки.

 

Решение

  1. Префиксное дерево (оно же бор). Строится за O(length(Text)k), где k — размер алфавита. Можно сделать log(k), если при построении в узлах дерева хранить какое-то сбалансированное дерево, чтобы искать символ за логарифм. Для решения задачи нужно при построении в листьях хранить счетчик. Когда при построении дерева прошли слово и добавили новый лист, нужно поставить 1 или сделать +1 (если лист уже существовал). Построение бора есть тут.
  2. Нам понадобится хеш-функция для строки и какая-нибудь хеш-таблица для этих же строк. Каждый раз через хеш добавляем строку в таблицу. Если строка была, то делаем +1 к счетчику, иначе заводим новый, равный 1 (используем готовый контейнер CHashTable<CString, int>). Проходим по таблице и проверяем счетчики для вывода статистики.
 

Задача 3

Даны числительные языка хауса:

đari bakwai da hamsin da shidda — 756
sitta da đari bakwai da biyar — 6705
saba’a da đari biyar da sittin — 7560

Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda.
Запишите на хауса: 67 и 5605.

 

Решение

saba’in da biyar — 75
đari shidda da sittin da shidda — 666
67 — sittin da biyar
5605 — hama’a da dari shidda da biyar
 

Задача 4

Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

 

Решение

Сгенерируем пять чисел x1, x2, x3, x4, х5.
Их сумма Х = x1 + x2 + x3 + x4 + х5, принимает значение 5 <= X <= 25, то есть ровно 21 значение.

Далее Х % 7 + 1 и будет равновероятно выдавать нам числа от 1 до 7. Может потребоваться несколько выполнений цикла.

Check Also

DDoS на Bluetooth. Разбираем трюк, который поможет отключить чужую колонку

На свете существует не так много вещей, которые бесят практически всех без исключения. Это…

6 комментариев

  1. Аватар

    bestdark

    26.06.2016 at 18:45

    Решение 4й задачи неверное
    Генерироваться числа будут и правда в диапазоне от 1 до 7
    Но вот не с равной вероятностью
    Дело в том что сумма этих чисел не равномерно распределена
    сумма будет равняться 5 только в том случае если все числа будут равны 1 (единственный вариант 1 1 1 1 1)
    А вот например сумма 6 может быть в 5 разных вариантах (1 1 1 1 2\1 1 1 2 1\1 1 2 1 1\1 2 1 1 1\2 1 1 1 1)
    Таким образом взятые по модулю 7 числа также не будут иметь равномерное распределение
    Вот такой код на visual c++ это доказывает
    #include «stdafx.h»
    #include
    int main()
    {
    int counter[7];
    memset(counter, 0, sizeof(int) * 7);
    for (int x1 = 1; x1 <= 5; x1++)
    for (int x2 = 1; x2 <= 5; x2++)
    for (int x3 = 1; x3 <= 5; x3++)
    for (int x4 = 1; x4 <= 5; x4++)
    for (int x5 = 1; x5 <= 5; x5++)
    counter[(x1 + x2 + x3 + x4 + x5)%7]++;
    for (int i = 0; i < 7; i++)
    std::cout << i + 1 << " — " << counter[i] << "\n";
    return 0;
    }
    Результат работы программы:
    1 — 450
    2 — 451
    3 — 450
    4 — 446
    5 — 441
    6 — 441
    7 — 446

    • Аватар

      bestdark

      26.06.2016 at 18:47

      вот второй строке кода подключаеться iostream
      при отправке коментария код испортился

    • Аватар

      mrPrizrak

      28.06.2016 at 15:40

      Согласен, решение 4-ой задачи неверное.
      Чтобы распределение исходов было равновероятным нужно:

      1. Делаем 7 вызовов функции [ rnd(5) — 1 ]
      2. Склеиваем результаты и получаем семизначное число
      3. Предполагаем, что полученное число записано в системе счисления с основанием 5, и переводим в десятичную
      4. Вычисляем остаток от деления на 7
      5. Прибавляем единицу. Полученное значение — и есть ответ

      Пояснение — в результате работы шагов 1-2 мы получаем случайное число в диапазоне от 0000000 до 4444444. Распределение результатов при этом равномерное. Количество возможных вариантов без остатка делится на 7. Таким образом, деление полученного числа на 7 равновероятно дает остаток от деления в диапазоне [0..6]

      • Аватар

        bestdark

        30.06.2016 at 16:31

        Это тоже неверный ответ
        7 вызовов функции дают нам 5^7 различных вариантов набора чисел
        Каждому такому набору вы ставите в соответствие 7 различных значений
        Но так как 5^7 не кратно 7 то распределение не может быть равномерным

        Такое контр-доказательство применимо практически ко всем подобным методам

        Проблема в том что количество вариантов которые мы получаем генерируя рандомные числа в пределах 1..5 никогда не будет кратно 7
        Тогда мы не можем равномерно распределить ответы

        Единственный правильный подход это ставить в соответствие число лишь некоторым наборам сгенерированых чисел, а именно чтобы количество наборов которым будут отвечать числа было кратно 7
        А в случаях когда сгенерированому набору чисел не ставиться в соответствие число генерировать новый набор и начинать алгоритм заново

        Например генерируем 2 числа r1 r2
        берем сумму r1+5*(r2-1)
        Если сумма будет меньше либо равно 21 то берем ёё по модулю 7 и прибавляем 1
        В противном случае генерируем другие числа и начинаем заново

        P.S. ваш метод можно упростить не используя системы исчисления в явном виде
        просто берем сумму случайных чисел с коефициентами 5^0,5^1,5^2 и т.д.

  2. Аватар

    stacco

    28.06.2016 at 22:40

    В ответе на третью задачу, кажется, есть ошибка: исходя из предоставленных данных можно предположить, что 67 наиболее вероятно переводится sittin da bakwai или, менее вероятно sittin da saba. В то время как sittin da biyar скорее всего — 65.

Оставить мнение