algoprog.kz

Задача в том чтобы выбрать м сказок из к. С(а, б) = б! / ((б-а)!а!) = количество способов выбрать а чисел из б. С(м, к) = ответ = к!/((к-м)!м!)

Задача на BFS. Сначала находим исходную и конечную точку и направление солдата. Легче будет если создать структуру для солдата(i, j, направление). Добавляем начального солдата в очередь. От каждого солдата(вершины) исходит 4 ребра - менять 3 направление, 1 ход вперед. У нас всё хранится в матрице из 4-х чисел на ячейку (дистанций до каждого направление). И если дистанция до конечного солдата с таким же направлением не найдена -1, иначе выводим дистанцию. Ответ будет что-то типо такого:

result = d[finalx][finaly].direction[finaldir];

Здесь достаточно хранить последнее число при возведении в степень. То есть умножить а на саму себя b раз и на каждом ходу а брать по модулю 10. Типо что-то этого:

int modpow (int a, int b) {
  int r = 1;
  for (int i = 0; i < b; i++) r *= a, r %= 10;
  return r; 
}

Или же можете взять функцию ModPow из разбора задачи Степень :)

Тут можно просто отсортировать строки и проверить одинаковые ли они. Из всех возможных решений этот пишется быстро и легко (на С++). Потому что в С++ есть структура данных string и функция sort. С помощью них решение занимает всего 5-6 строк.

Нам даны p, q, a, b, p1, q1.

Если

$p \times b = q \times a$

Мы можем найти такой a что

$\frac{p}{q} = \frac{a}{b}$

$a = \frac{p \times b}{q}$

Но, нам надо найти такой а что

$\frac{p}{q} < \frac{a}{b}$

Мы просто увеличеваем а.(а = а + 1).
Тогда мы получим такой а что

$\frac{p}{q} < \frac{a}{b}$

Осталось проверить

$\frac{a}{b} < \frac{p1}{q1}$

Если да то ответ - а. Иначе ответ -1

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

Возьмем l как дистанция между двумя центрами ($\sqrt{(x-x1)^2 + (y-y1)^2}$).

Если l = r+r1 или l = |r-r1| они пересекаются в одной точке, если же |r-r1| < l и l < r+r1 они пересекаются в двух точках, если центры и радиусы одинаковы они одинаковые и ответом будет бесконечно точек.

И так, переходим к нахождению точек. По теореме косинусов найдем длину |OH|.

$r^2 + l^2 - 2lr \times cos(alfa) = \frac{r^2 + l^2 - r1^2}{2*l}$

И по теореме Пифагора $|HP| = \sqrt{r^2 - |OH|^2}$;

Теперь находим вектор v|OH| = |OH| / l * v|O1O2|. v|O1O2| = вектор между двумя центрами (x1-x, y1-y).

Теперь находим перпендикуляр к вектору O1O2. V(y1-y, x1-x). Потом Находим вектор |HP| = |HP|/|V| * V. |V| = длина вектора V.

Ответами будет:

1. O.x + OH.x - HP.x

2. O.y + OH.y - HP.y

3. O.x + OH.x + HP.x

4. O.y + OH.y + HP.y

В этой задаче мы должны использовать быстрое возведение числа в степень. Быстрое возведение в степень работает за О(logn) с помощью деление степень на два. То есть:

a^b = a^b/2*a

Если b четное b делим на 2 и возводим a в квадрат

Если b нечетное уменьшаем b на 1 запомним a (p = p *a)

Ответ будет p * a;

Данные ограничение не дают нам умножать эти числа. Как нам известно $(X * Y) \mod Z = ((X \mod Z) * (Y \mod Z)) \mod Z $

$(X + Y) \mod Z = ((X \mod Z) + (Y \mod Z)) \mod Z$

С помощью этой теории мы можем умножать эти числа по модулю.

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

Легче написать код:

typedef long long ll;
ll ModPow (ll a, ll b, ll c) {
    ll x = 1;
    while (b > 0) {
        if (b & 1) x = ModMult (x, a, c);
        a = ModMult (a, a, c);
        b>>=1;
    }
    return x;
}

функцию ModMult напишите уже сами :)
Она не очень отличается от функции ModPow

Любая коробка определяется 3мя размерами: высотой, шириной и длиной. Пусть это значения A, B и C соответственно. В силу того, что все эти значения равноправны (коробку можно вращать), то мы можем полагать, что A <= B <= C. Так же ясно, что для того, чтобы построить коробку нужно иметь набор из трех пар плиток. Плитки в каждой паре идентичны и представляют собой плитки, не имеющие общих граней (противоположные). Причем должна быть возможность стыковать плитки из разных пар друг с другом.

Формализуем вышеописанную идею. Размеры каждой из коробок отсортируем по возрастанию, т.е. будем всегда считать например, что высота меньше либо равна ширине. После чего получившиеся наборы плиток мы можем отсортировать сначала по высоте, а затем (при равных высотах) по ширине. Таким образом, мы должны получить следующую последовательность:

1. AB
2. AB
3. AC
4. AC
5. BC
6. BC

Отсортировав плитки остается лишь проверить на равенство элементов в 3х четверках. Например, если в a[i].h хранится высота, а в a[i].w соответственно длина i-й коробки, то следует проверить на равенство следующие элементы: a[1].h=a[2].h=a[3].h=a[4].h и a[1].w=a[2].w=a[5].h=a[6].h и a[3].w=a[4].w=a[5].w=a[6].w . Такое решение не является самым оптимальным как по времени выполнения, так и по объему кода программы, но тем неменее оно более понятно. Разбор с сайта acmp.ru