10 задач с собеседований в центр



Задача на алгоритмы

Дан массив целых чисел \(A[1 \ldots N]\). Найдите сумму попарных произведений всех элементов этого массива.

Приведите оптимальный алгоритм решения предложенной задачи и запишите на своём любимом языке. Оцените время, за которое работает этот алгоритм. Аргументируйте свою оценку.

Сумма кубов

Докажите, что сумма \(1^3 + 2^3 + 3^3 + \ldots + n^3\) является точным квадратом.

Числа на доске

На доске написаны два числа \(1, 1\). Вписав между числами их сумму, мы получим числа \(1, 2, 1\). Повторив эту операцию еще раз, получим числа \(1, 3, 2, 3, 1\). После трёх операций будут числа \(1, 4, 3, 5, 2, 5, 3, 4, 1\). Какова будет сумма всех чисел на доске после \(100\) операций?

Конфеты

У сладкоежки Пети в правом и левом кармане куртки лежат конфеты. Всякий раз, когда ему хочется сладкого, он выбирает наугад один из карманов, достаёт из него конфету и съедает её. Первоначально в каждом кармане по \(n\) конфет. Найдите вероятность того, что в тот момент, когда один из карманов окажется пустым, во втором останется \(k\) конфет.

Теория чисел

На сколько нулей оканчивается число \(1\cdot 2\cdot 3\cdot \ldots \cdot98 \cdot 99 \cdot 100\)?

Делимость на 7

Сколько существует натуральных чисел \(n\), меньших \(10000\), для которых \(2^n - n^2\) делится на \(7\)?

Посчитать предел

Вычислите: $$ \lim_{x \to \frac{\pi}{4}} (\frac{1 - tg(x)}{sin(\frac{\pi}{4}- x)} ) $$

Вероятность

В первой урне находятся \(6\) белых и \(4\) черных шаров, а во второй – \(5\) белых и \(4\) черных. Из первой урны во вторую переложили один шар, после чего из второй урны извлекли один шар, оказавшийся белым. Какова вероятность того, что из первой урны во вторую был переложен белый шар?

Различные делители

Найдите все простые \(p\) такие, что число \(p^2+11\) имеет ровно \(6\) различных делителей (включая единицу и само число).

Раскрашиваем круг

Сколькими способами можно раскрасить круг, разбитый на \(p\) равных секторов с помощью \(n\) красок, если \(p\) – простое число и каждый сектор раскрашиваем одной краской? Две раскраски, совпадающие при повороте круга, считаем одинаковыми.