51 Ответ от aza_inf

(3 ответов, оставленных в Algo)

не, я это знаю, но кто может придумать решение с использованием дерева отрезков?
и еще, кто может дать ссылки на задачи на дерево отрезков?

Перейти к разделу: Algo

52 Тема от aza_inf

(3 ответов, оставленных в Algo)

Закраска прямой
(Время: 1 сек. Память: 16 Мб)
На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.

Входные данные

Входной файл INPUT.TXT в первой строке содержит число N, в следующих N строках - пары Li и Ri. Ограничения: все числа целые, не превышающие 109 по абсолютной величине, 1 <= N <= 15 000.

Выходные данные

В выходной файл OUTPUT.TXT выведите длину окрашенной части прямой.

Пример
input.txt
2
1 3
2 4
output.txt
3

кто может решить эту задачу разными способами? у кого есть идеи?

Перейти к разделу: Algo

53 Тема от aza_inf

(2 ответов, оставленных в Problems)

(1 задача)
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N. ограничения M и N могут достигать до 5*10^18

(2 задача)
Какое наименьшее число N можно представить в виде произведения N = A?B ровно K способами? Произведения A?B и B?А считаются одним

способом, все числа натуральные (1?K?50).

Перейти к разделу: Problems

54 Ответ от aza_inf

(9 ответов, оставленных в Problems)

длина подпоследовательности всегда нечетная

Перейти к разделу: Problems

55 Ответ от aza_inf

(3 ответов, оставленных в Algo)

Brainail, а ты можешь дать реализацию декартового дерева на PASCAL?!

Перейти к разделу: Algo

56 Тема от aza_inf

(3 ответов, оставленных в Algo)

Кто знает какая самая легкая структура данных, которая выполняет процедуры sum(left..right), min(left..right), max(left..right), add(x), delete(x), ... Пожалуйста, дайте реализацию, но без использования STL, желательно на PASCAL!!!

А можно делать add(x), delete(x) с помощью дерева отрезков за O(logn)?

Перейти к разделу: Algo

57 Тема от aza_inf

(9 ответов, оставленных в Problems)

дана последовательность из N чисел a1,a2, ..., an  и число M
Надо найти количество подпоследовательностей в которых медиана равна числу M

Пояснения:
Подпоследовательность - это a(i),a(i+1), ... a(i+k) (непрерывно идущие подряд числа из массива A(n))

Медиана - это число, которая будет находиться в середине последовательности после ее сортировки. Например, A={5,1,3}, медиана будет равна 3

Ограничения: 1<=N<=100000, 1<=M<=N

Пожалуйста, решите эту задачу!

Перейти к разделу: Problems

58 Тема от aza_inf

(5 ответов, оставленных в Problems)

кто знает как сделать сортировку по углам
если дано N точек (x1,y1; x2,y2; ... ; xn,yn) или вообще зачем нужна сортировка по углам

Перейти к разделу: Problems

59 Тема от aza_inf

(1 ответов, оставленных в OlympNews)

Кто знает, как сдавать задачи на TopCoder.
Скажем на С++ задачу нахождения суммы двух чисел или одну задачу из Single Match

Перейти к разделу: OlympNews

60 Тема от aza_inf

(3 ответов, оставленных в Problems)

Задан целочисленный прямоугольный массив MxN. Необходимо определить прямоугольную область данного массива, сумма элементов которого максимальна. Кто сможет решить задачу за O(MN) или за O(MNMN)

Перейти к разделу: Problems

61 Ответ от aza_inf

(15 ответов, оставленных в Algo)

Определение проблемы
Для начала, вспомним, что существует так называемоерешето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
    int primesCount = 0;
    int sqrt_n = (int)sqrt((double)n);
    for (int i = 2; i <= n; ++i) {
        if (!notPrime[i]) {
            primes[primesCount++] = i;
            if (i <= sqrt_n) {
                for (int j = i * i; j <= n; j += i) {
                    notPrime[j] = true;
                }
            }
        }
    }
    return primesCount;
}

Почему решето работает не за линейное время? Потому что одно число в нем может вычеркиваться несколько раз (во внутреннем цикле) . Если добиться, чтобы каждое число вычеркивалось не более одного раза, то, очевидно, алгоритм будет линейным.
Решение
Чтобы сделать это, нам понадобится заменить массив 

notPrime[]

на массив 

int leastPrime[MAXN + 1]

. 

leastPrime[x]

будет хранить индекс минимального простого числа в 

primes[]

, на которое делится x. Очевидно, что 

primes[leastPrime[x]] = x

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

k * i,

где i - простое, будем вычеркивать числа вида

 primes[k] * i

, где i - это любое число, а 

primes[k] <= primes[leastPrime[i]]

:

int leastPrime[MAXN + 1];
int primes[MAXN];
 
int advancedSieve(int n) {
    int primesCount = 0;
    for (int i = 2; i <= n; ++i) {
        if (!leastPrime[i]) {
            primes[primesCount++] = i;
            leastPrime[i] = primesCount;
        }
        for (int j = 0; j < leastPrime[i]; ++j) {
            int t = primes[j] * i;
            if (t <= n) leastPrime[t] = j + 1;
            else break;
        }
    }
    return primesCount;
}

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

primes[k] * i,

где 

primes[k] <= primes[leastPrime[i]],

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

Перейти к разделу: Algo

62 Тема от aza_inf

(9 ответов, оставленных в Problems)

Надо найти кол-во подстрок в строке (длина строки <= 50000)
Например:

text = 'ababa'
s = 'aba'

Ответом будет 4.

ababa
ababa
ababa
ababa

Перейти к разделу: Problems

63 Тема от aza_inf

(3 ответов, оставленных в Problems)

Как можно решить эту задачу?
Дан неориентированный связный граф без циклов. Надо найти в нем самый длинный путь из i в j (вершину).
Мне кажется тут надо использовать, чтобы найти самую глубокую вершину. А как все это обобщить и реализовать пока не знаю!

Перейти к разделу: Problems

64 Ответ от aza_inf

(21 ответов, оставленных в Problems)

А точное условии задачи вот такое:

Пример
E.in
3
0 0 0 3 4 0
E.out
1

--------------
E.in
4
0 0 0 1 1 0 0 -2
E.out
2

-------------

Задача E Треугольник
Вам даны координаты N различных точек. Требуется вычислить, сколько различных прямо-
угольных треугольников можно составить из заданных точек, используя их в качестве вершин
треугольников. Треугольники считаются разными, если у них различна хотя бы одна вершина.

Формат входных данных
Первая строка входного файла содержит число N (1 ? N ? 5000). Следующие N строк содержат
по два целых числа - координаты точек. Координаты точек - целые числа, по абсолютному зна-
чению не превосходящие 10000. Числа в строках разделены пробелами.

Формат выходных данных
Выходной файл должен содержать одно целое неотрицательное число - количество прямоуголь-
ных треугольников.

Перейти к разделу: Problems

65 Тема от aza_inf

(21 ответов, оставленных в Problems)

Вам дано (N<=5000) точек (xi,yi). Надо найти количество правильных треугольников с разными вершинами.
Ограничение по времени 2 секунды

Перейти к разделу: Problems

66 Тема от aza_inf

(15 ответов, оставленных в Algo)

Можете написать Алгоритм Дейкстры с помощью кучи на языке Pascal

Перейти к разделу: Algo