algoprog.kz

←Вернуться к задаче

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

←Вернуться к задаче

Дополню предыдущий разбор

• $\frac{2•3^n-6}{2}+3^{n+1}$
• $\frac{3^{n+1}-3}{2}$
• $\frac{(\frac{1}{3})^{n+1}-\frac{1}{3}}{\frac{1}{3}-1}$

Эти 3 формулы - ответы на задачу. Основаны они на формулах геометрической прогрессии:

• $b_1•q^{n-1}=b_n$

• $\frac{b_n•q-b_1}{q-1}$

Можно решать и динамикой

for i = 1 to n do i odna zakonomernost

mini help

Я написал функцию для вычитания для длинной арифметики, так как там работа идет проще со стрингами: нули сохраняются, и не надо переводить стринги в интейджеры и наоборот, сортировать стринги функцией sort(s.begin(),s.end())(c++).

В этой задаче у всех сотрудников кроме последнего зарплата будет одинаковой(иногда у всех).

Все создают среднюю зарплату в рублях, но только последний создают средние копейки.

Распределить зарплату невозможно, если сумма всех зарплат дробная.

Вот примеры:

input:10 20 50

output:20 20 20 20 20 20 20 20 20 25

input:10 20 3

output:0

input:10 20 0

output:20 20 20 20 20 20 20 20 20 20

Здесь не зря был дан пример с числом 9.;)

Все знают, как проверить деление на 3, если сумма числа делится на 3 то все число делится 3.

Анологичная ситуация с 9.

Дигитация факториалов больше 5 равняется 9.

6!=1•2•3•4•5•6

Почему??? Потому что делители 6и - это 2 и 3.

Разложим 6!=1•2•3•2•2•5•2•3

Здесь на 3 умножается 2 раза.

3•3=9

Получается все последуещие фaкториалы тоже делятся на 9.

←Вернуться к задаче

У числа без целого корня делителей четно, а у числа с целым корнем делителей нечетно!!!

Я хочу сказать, если возьмем два числа 16 и 15 то:

16 → 1,2,4,8,16 → 1•16, 2•8, 4•4=4^2

У 1 пара 16, у 2 пара 8, у 4 пара 4

15 → 1,3,5,15 → 1•15, 3•5

Каждая последующая V зависит от предыдущей V

v1=v0+a1t1

v2=v0+a1t1+a2t2

Здесь достаточно хранить последнее число при возведении в степень. То есть умножить а на саму себя 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 из разбора задачи Степень :)

В этой задаче мы должны использовать быстрое возведение числа в степень. Быстрое возведение в степень работает за О(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

Пишем программу проверяющая если сторона a+b>c и a+c>b и a+b>c то тогда пишем YES иначе пишем NO

Эта задача на определение последовательности. Если вывести и посчитать колличество делителей в первых 100 числах, все сразу становится понятным. Число будет иметь нечетное колличество элементов, если из него без труда можно взять подкорнем(sqrt), а в остальных случиях будет четное колличество. Например:

1 - нечетное

4 - нечетное

9 - нечетное

16 - нечетное

25 - нечетное

36 - нечетное

49 - нечетное

64 - нечетное

81 - нечетное

100 - нечетное

...

а для остальных случаев колличество элементов будет четным.

2 - четное

3 - четное

5 - четное

6 - четное

7 - четное

8 - четное

10 - четное

11 - четное

...

Думаю здесь можно применить динамику. Типа такого, если d[i][j] == true, тогда используя только первыe i элементов можно получить j единичных столбцов.

Подробности потом, когда я её решу =)

В задаче требуется выяснить, сколько элементов последовательности a, 2a, . . . , ba делится на b. Докажем, что искомое число равно наибольшему общему делителю чисел a и b.

Пусть d — наибольший общий делитель чисел a и b. Тогда a = dr, b = ds, где r и s — два взаимно простых числа.

Если все числа a, 2a, . . . , ba разделить на b, то частные можно записать в виде $\frac{r}{s} , \frac{2r}{s} , \frac{3r}{s} \dotsc \frac{(ds-1)r}{s}, \frac{(ds)r}{s}$. Так как r и s — взаимно простые, среди частных целыми числами могут быть лишь те, у которых в числителе коэффициент при r (равный 1, 2, . . . , ds) делится на s. Несложно видеть, что число таких коэффициентов равно d, что и требовалось доказать.

Для нахождения наибольшего общего делителя можно использовать алгоритм Евклида.

Источник: neerc.ifmo.ru/school