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

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

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

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

• $\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}$

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

import java.util.*;import java.io.*;
 public class a { public static void main(String[] args) throws Exception {
  Scanner in=new Scanner(new File ("lazy.in"));  PrintWriter out=new PrintWriter(new File("lazy.out"));     char a[]={'a','b','d','e','g','o','p','q'};    String s=in.nextLine();    int q=0;
for(int i=0;i<s.length();i++) for(int j=0;j<a.length;j++){ if(s.charAt(i)==a[j]) q++; }
 out.print(q); in.close(); out.close(); }
}

gf

include

using namespace std; int main(){ ifstream fin("sum.in"); ofstream fout("sum.out"); int a,b; fin>>a>>b; if((a>-32000&&a<32000)||(b>-32000&&b<32000)) { fout<<a+b; } return 0; }

Ограничения в этой задаче $N \le 10^{2000}$.

Пусть длина $N$ равна n.

Для длины $k$, количество палиндромов будет $10^[k/2]$, где $[x]$ = округленное значение $x$.

Надо сложить все значения для $k = 1..n-1$.

Теперь рассмотрим палиндромы длины n. Будем считать количество палиндромов так:

если $N = abc...xyz$, то прибавляем к ответу:

$(a-1)$99 ... 9 (до середины, так как это палиндром)

$a$$(b - 1)$99 ... *9 (так же до середины)

... И так далее.

Cложность будет примерно $O(n^2)$.

Надо найти количество построений дорог между $N$ центрами, где $N \le 100$.

Можно представить сеть центров, как ориентированный граф с $N$ вершинами.

Максимум дорог(неориентированных) между вершинами такого графа может быть $C_N^2 = \frac{N(N-1)}{2}$.

И у каждой дороги($u - v$) будет три состояния:

$u \to v$.

$v \to u$.

дорог между $u$ и $v$ вообще нет.

То есть ответ: $3^{\frac{N(N-1)}{2}}$. Так как ответ может быть большим, надо использовать

длинную арифметику.

Сперва надо отсортировать все окружности по углу(угловая сортировка). Можно было сортировать по

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

две последовательные окружности. Точную формулу можете вывести сами, для этого нужно знать, как

вычислять расстояние между двумя точками в декартовой системе координат, и знать теорему

косинусов.

Сложность будет $O(NlogN)$.

Надо найти количество таких заполнений бланков ответа из $N$ вопросов по $K$ ответов, чтобы ни в

одном варианте заполнения не было ни одного правильного ответа.

Нам дано какое-то множество правильных ответов к каждому вопросу, и мы можем выбрать любой

вариант ответа, кроме правильного. Т.е., если есть $K$ ответов, то один из них правильный, а

остальные $K-1$ неправильные. Всего вопросов $N$ и мы можем выбрать любые $K-1$ неправильных

ответов. Значит ответ: $(K-1)^{N}$. Здесь также нужно воспользоваться длинной арифметикой.

В данной задаче надо быстро проверять, находиться ли в таблице Менделеева

элемент $s_i + s_{i+1}$(конкатенация двух символов строки $s$).

Для этого в C++, можно воспользоваться map'ом. Сложность будет $O(NlogM)$

Так же можно завести буленовый массив 26x26(в паскале можно сделать array['a'..'z', 'a'..'z'] of

boolean). И для каждого элемента хранить true, если он есть в таблице Менделеева, иначе false.

Или можно просто хранить элементы в хэш-таблице. Тут ограничения не большие и методов много. То

есть сложность при таких методах будет $O(N)$

Сперва решетом находим все простые числа от $1$ до $N$. Понятно, что все эти числа и есть

делители $N!$,

потому что $N! = 1 * 2 * ... * N$.

И записываем простые числа в массив $p[]$.

То есть он будет выглядеть так: $p[1] = 2, p[2] = 3, p[3] = 5, \dots$

Требуется посчитать, с какой степенью простой делитель $p$ входит в число $N!$,

т.е. найти наибольшее $x$ такое, что $N!$ делится на $p^x$.

Теперь как надо искать $x$ для $p$?

$x = [{\frac{N}{p}}] + [{\frac{N}{p^2}}] + [{\frac{N}{p^3}}] +\dots$

Конечно, не до бесконечности, потому что берем только целую часть.

Сложность нахождения степени делителя факториала $ O(log_{p}N) $

Итоговая сложность $\approx O(NlogN)$, если считать грубо.

Как оказалось, задача не такая сложная.

Первое что надо сделать в предлагаемом мной решении, это найти наибольший палиндром, который меньше или равен нашему числу. Сделать это можно за $O(n)$, применяя простые проходы по строке. Некоторые случаи, которые могут вызвать трудности:

1. 1221(и так палиндром),
2. 12331(просто начиная с последней тройки можно поменять числа так, как нам нужно),
3. 3516(из-за 1, которая меньше чем 5, мы уменьшаем 5 на один и дальше забиваем число так, как нам нужно)
4. 10000(нужно уменьшить размер числа и забить 9)

После этого у нас есть готовый палиндром.

Подсчитаем все палиндромы длины меньше, чем наше число. Это делается одним проходом по циклу и каждый раз это $9*10^{(i-1)/2}$, поэтому достаточно знать все степени десяти, тем более они нам еще понадабятся. 

Пройдемся циклом за $O(n)$ до половины нашего числа и подсчитаем все палиндромы,  которые были бы меньше начиная с этого разряда. Не трудно заметить, что это степень 10ти, какая  именно, подумайте сами.

И последний штрих: все лучше сделать с длинной арифметикой. Удачи!

There is nothing to think. Just read number as 'long' then convert it to 'String' then divide it to chars then put them to array then first sort in decreasing order then sort in increasing order then print their difference as a result. It doesn't compile slow and true in any case, but I don't know why can not see word 'accepted' on display)))

Бізге ең ұзын ұзындықты табу керек.Ол үшін:

1.Ең қысқа қабырғаны табу керек

2.Геронның формуласын қолданып,ауданын табу керек.

А=$\sqrt{s(s-a)(s-b)(s-c)}$, $s = \frac{a+b+c}{2}$;

 толық мәлімет  http://en.wikipedia.org/wiki/Heron's_formula

3.Келесі формула: Аудан тең ұзындық көбейтілген  ұзындық түскен қабырға.Екеуін теңестіріп ұзындықты табамыз.

А.Қ.Ж.Ал,іске сәт!!!!!!!!

А.Қ.Ж.(аяғына қосқан жазу)