D2630. Сходимость ряда

13/12/2017 by Курьянов Павел

Задача
Исследовать сходимость ряда [latex]\sum_{n=1}^{\infty}\frac{ln(n!)}{n^{a}}[/latex] и вычислить его сумму при заданной точности.

Входные данные
Натуральное число [latex]a[/latex]

Выходные данные
Сумма ряда если она существует.

Тесты

входящие данные	выходящие данные
2	-nan
3	0.578615
6	0.0146958
12	0.000172786
22	1.65259e-07

#include <cmath>
#include <iostream>
using namespace std;
int poww(int a,int n) {
  return (!n)?1:a*poww(a,n-1);
}
int main() {
    int a;
    cin>>a; //ряд будет сходящимся только при a>2
    double s=0;
    long double f=1;
    double e=10;
    for(int n=2;e>0.000001;n++){
    f*=n;
    s+=log(f)/poww(n,a);
    e=log(f)/poww(n,a);
    }
    cout<<s;
    return 0;
    
}

#include <cmath>

#include <iostream>

using namespace std;

int poww(int a,int n) {

return (!n)?1:a*poww(a,n-1);

}

int main() {

int a;

cin>>a; //ряд будет сходящимся только при a>2

double s=0;

long double f=1;

double e=10;

for(int n=2;e>0.000001;n++){

f*=n;

s+=log(f)/poww(n,a);

e=log(f)/poww(n,a);

}

cout<<s;

return 0;

}

Решение задачи
Исследуем ряд на сходимость при различных значениях переменных [latex]a[/latex]. При [latex]a\leq 1[/latex] случай тривиальный — ряд будет расходиться.
Рассчитаем его при [latex]a\geq 2[/latex]. Как видно при [latex]a=2[/latex] ряд продолжает расходиться, а при [latex]a>2[/latex] он начинает сходиться и становиться возможным вычислить его сумму.

Ссылки
Условие задачи (стр. 257)
Код на ideone

Related Images:

e-olymp 6122. Простой стек

13/12/2017 by Курьянов Павел

Задача
Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку.Возможные команды для программы:

push n — Добавить в стек число n (значение n задается после команды). Вывести ok.
pop — Удалить из стека последний элемент. Программа должна вывести его значение.
back — Вывести значение последнего элемента, не удаляя его из стека.
size — Вывести количество элементов в стеке.
clear — Очистить стек и вывести ok.
exit — Вывести bye и завершить работу.

Входные данные
Каждая строка содержит одну команду.

Выходные данные
Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

входные данные	выходные данные
push 2	ok
push 3	ok
push 5	ok
baсk	5
sizе	3
pop	5
sizе	2
push 7	ok
pop	7
clear	ok
size	0
exit	bye

Код программы

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;


stack<int> s;
char str[100];
int n;
int main(void)
{
  while(scanf("%s",&str))
  {
    if (strcmp(str,"push") == 0)
    {
      cin>>n;;
      s.push(n);
      cout<<"ok"<<"\n";
    } else
    if (strcmp(str,"pop") == 0)
    {
       cout<<s.top()<<"\n";
      s.pop();
    } else
    if (strcmp(str,"back") == 0)
    {
       cout<<s.top()<<"\n";;
    } else
    if (strcmp(str,"size") == 0)
    {
       cout<<s.size()<<"\n";
    } else
    if (strcmp(str,"clear") == 0)
    {
      while(!s.empty()) 
    s.pop();
      cout<<"ok"<<"\n";
    } else
    {
      cout<<"bye"<<"\n";
      break;
    }
  }
  return 0;
}

#include <iostream>

#include <cstring>

#include <stack>

using namespace std;

stack<int> s;

char str[100];

int n;

int main(void)

{

while(scanf("%s",&str))

{

if (strcmp(str,"push") == 0)

{

cin>>n;;

s.push(n);

cout<<"ok"<<"\n";

} else

if (strcmp(str,"pop") == 0)

{

cout<<s.top()<<"\n";

s.pop();

} else

if (strcmp(str,"back") == 0)

{

cout<<s.top()<<"\n";;

} else

if (strcmp(str,"size") == 0)

{

cout<<s.size()<<"\n";

} else

if (strcmp(str,"clear") == 0)

{

while(!s.empty())

s.pop();

cout<<"ok"<<"\n";

} else

{

cout<<"bye"<<"\n";

break;

}

return 0;

}

Решение задачи
Для каждой команды вводимой в программу реализуем функцию, которую она должна выполнять в стеке.

Ссылки

Related Images:

MS9. Шифрование символов

29/08/2017 by Курьянов Павел

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

Входные данные
Последовательность символов.

Выходные данные
Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

входные данные	выходные данные
pack my box with five dozen liquor jugs	p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14

Код программы

#include <iostream>
using namespace std;

int main() {
    unsigned char a, b; 
    scanf("%c", &b); 
    cout<<b<<" ";
    while (scanf("%c", &a)) {
        if (a == '\n')  break;
        printf("%x ", a^b);
        b=a;
}
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned char a, b;

scanf("%c", &b);

cout<<b<<" ";

while (scanf("%c", &a)) {

if (a == '\n') break;

printf("%x ", a^b);

b=a;

}

return 0;

}

Решение задачи
Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не произойдет переход на следующую строку.По мере ввода запоминаем старый символ во 2 переменной и складываем их по модулю 2 и выводим результат в шестнадцатеричной системе.

Ссылки

Подзадача — дешефратор
Написать программу, которая сможешь преобразовать полученный код обратно в текст.

Входные данный
Код полученный из выполнения основной задачи.

Выходные данные
Изначальный текст.

Тесты

входные данные	выходные данные
p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14	pack my box with five dozen liquor jugs

Код задачи

#include <iostream>
using namespace std;

int main()
{
    unsigned short a;
    unsigned char b;
    cin>>b;
    cout<<b;
    while (cin >> hex >> a)
    {
        b = a^b;
        cout << b;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned short a;

unsigned char b;

cin>>b;

cout<<b;

while (cin >> hex >> a)

{

b = a^b;

cout << b;

}

return 0;

}

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

Related Images:

A 325. Простые делители числа

28/08/2017 by Курьянов Павел

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные	выходные данные
2	2
7	7
50	2 5 5
169	13 13
583	11 53
2368	2 2 2 2 2 2 37
73890	2 3 3 5 821
885066	2 3 7 13 1621
6943960340	2 2 5 97 1787 2003

Код программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    unsigned long long n;
  cin>>n;
    
    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {
        if ( n % i == 0 ){
            std::cout << i << ' ';
            n /= i;
        }
        else{
            ++i;
        }
    }
    if ( n > 1 )
        std::cout << n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

unsigned long long n;

cin>>n;

for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) {

if ( n % i == 0 ){

std::cout << i << ' ';

n /= i;

}

else{

++i;

}

if ( n > 1 )

std::cout << n;

return 0;

}

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Условие задачи(страница 135)
Код на ideone

Related Images:

Черная пятница

06/04/2017 by Курьянов Павел

Разбор задачи с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача. Завтра черная пятница — самая большая новогодняя распродажа. Степан, как владелец магазина, принял решение, что цены всех товаров будет снижено на 25%. Он выяснил, что начальные цены на все товары делились на 4, поэтому после снижения цен все цены тоже выражаются целым числом. Степан вечером перед распродажей снял ценники с всех товаров и напечатал для каждого товара еще один ценник со скидкой. Он оставил их на столе, рассчитывая утром их развесить. Но, когда он пришел утром в магазин, то выяснилось, что уборщица смешала все ценники вместе, и теперь Степану нужно отделить старые ценники от новых.
Помогите ему.
Входные данные:
Первый ряд входного файла содержит одно число N (2 ≤ N ≤ 105), N — четное. Следующие N рядов содержат положительные числа не больше чем 109, которые идут в порядке возрастания по одному в ряду — числа со всех ценников (как старых так и новых). Гарантируется, что входные данные корректны, то есть решение существует.
Выходные данные:
Вывести N/2 целых числе в порядке возрастания — стоимость товаров после снижения цен.

Тесты

входные данные	результат работы
6	30
30	40
40	45
42
45
56
60

Код задачи

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n;
    cin>>n;
    long long x[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    int ind=0;
    for(int i=0;i<n-1;i++)
    {
        if(x[i]!=0)
        {
            ind=find(x+ind,x+n,x[i]*4/3)-x;
                cout<<x[i]<<'\n';
                x[ind]=0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n;

cin>>n;

long long x[n];

for(int i=0;i<n;i++)

{

cin>>x[i];

}

int ind=0;

for(int i=0;i<n-1;i++)

{

if(x[i]!=0)

{

ind=find(x+ind,x+n,x[i]*4/3)-x;

cout<<x[i]<<'\n';

x[ind]=0;

}

return 0;

}

Решение задачи
Так как нам изначально известно, общее количество ценников, то вводим их все в массив, где как нам уже сказано по условию, они будут располагаться в порядке возрастания. Значит, уже с первого элемента мы получим новую цену так как она будет точно меньше любой наименьшей до скидки. Находим старую цену соответствующую ей и обнуляем ее (это делается для оптимизации времени работы кода, чтоб потом мы не искали старую цену от этого элемента). Так же, после первого нахождения старой цены мы начинаем поиск остальных с этого же места, потому что меньше они точно не могут быть и наш алгоритм должен продвигаться только вперед.
Таким образом, мы проходим через все цены, выписываем все новые цены, а старые «выбрасываем» из-за ненужности.
Ссылка на код задачи

Related Images:

KM63

06/10/2016 by Курьянов Павел

Задача М63 из журнала «Квант» №1 за 1971 год, стр.39. Автор А.А. Кириллов.
Можно ли из плиток размером 1х2 сложить четырехугольник размером [latex] M\times N [/latex] так, чтоб при этом не было ни одного прямого «шва», соединяющего стороны квадрата и идущие по краям плиток.

Изображение как на рисунке не годиться так как тут есть «шов» [latex] AB [/latex].

Входные данные
Размеры четырёхугольника [latex] M [/latex] и [latex] N [/latex].

Выходные данные
Возможно ли это сделать [latex] Yes [/latex] или не возможно [latex] No [/latex].

Тесты

вводимые данные		выводимые данные
M	N	возможно \|\| не возможно
2	16	no
6	6	no
66	69	yes
16	5	yes
99	71	no
7	7	no
78	77	yes
7	8	yes

Код задачи

#include <iostream>
using namespace std;

int main() {
    long long m,n;
    cin>>m>>n;
    if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {  
        if (m==6 && n==6) {
            cout<<"No";// согласно решению задачи
            return 0;
        }
        cout<<"Yes";//согласно общему решению
    }
    else{ 
        cout<<"No";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long m,n;

cin>>m>>n;

if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {

if (m==6 && n==6) {

cout<<"No";// согласно решению задачи

return 0;

}

cout<<"Yes";//согласно общему решению

}

else{

cout<<"No";

}

return 0;

}

Решение
Легко доказать, что прямоугольники [latex] {2\times m}, [/latex] [latex] {3\times m}, [/latex] [latex] {4\times m} [/latex] разрезать таким образом нельзя. Если же [latex] {m\geq{5}}, [/latex] [latex] {n\geq{5}} [/latex] и [latex] mn [/latex] четно (последнее условие разумеется необходимо), то во всех случаях кроме [latex]{6\times 6}[/latex] нужное разбиение существует.
Ссылки
ideone

Related Images:

ML33. Угол между вектором и осями координат

19/09/2016 by Курьянов Павел

Задача

Найдите углы между вектором [latex] \overrightarrow{a}=(x,y,z)[/latex] и координатными осями [latex]Ox, Oy, Oz[/latex].

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

Координаты вектора [latex]\overrightarrow{a}=(x,y,z)[/latex].

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

Угол между заданным вектором и [latex]Ox[/latex].
Угол между заданным вектором и [latex]Oy[/latex].
Угол между заданным вектором и [latex]Oz[/latex].

Тесты

Входные данные			Выходные данные
x	y	z	угол c Ox	угол c Oy	угол c Oz
0	0	1	90	90	0
0	9999.99	0	90	0	90
1	1	1	54.7456	54.7456	54.7456
-9999.5	-9999.5	-9999.5	-54.7456	-54.7456	-54.7456
0	0	0	невозможно при нулевом векторе

Код программы

#include 
#include 
using namespace std;
 
int main() {
  double x,y,z, cosx,cosy,cosz;
  cin>>x>>y>>z;//вводим координаты нашего вектора
    if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым
    {
      cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку
    }
    else
    {
      cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат
      cosy=y/(sqrt(x*x+y*y+z*z));
      cosz=z/(sqrt(x*x+y*y+z*z));
      cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах
    }
    return 0;
}

#include

using namespace std;

int main() {

double x,y,z, cosx,cosy,cosz;

cin>>x>>y>>z;//вводим координаты нашего вектора

if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым

{

cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку

}

else

{

cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат

cosy=y/(sqrt(x*x+y*y+z*z));

cosz=z/(sqrt(x*x+y*y+z*z));

cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах

}

return 0;

}

Решение задачи

Для начала проверим не является ли заданный вектор нулевым, так как он не будет образовывать угол между векторами. Если это нулевой, то выводить, что это невозможно при нулевом векторе. При другом условии решим задачу,а поскольку в условии нам даны координаты только 1 вектора, а для вычисления угла между 2 векторами нужно 2 пары координат, то будем считать, что [latex] Ox(1,0,0) [/latex], [latex] Oy(0,1,0) [/latex],[latex] Oz(0,0,1) [/latex].
Теперь мы можем вычислить угол между векторами через формулу[latex] \cos{ |\widehat { a,b } }|=\frac { \overrightarrow { a } \overrightarrow { b } }{ \left| \overrightarrow { a } \right| \left| \overrightarrow { b } \right| } [/latex], где [latex] \overrightarrow { a } \overrightarrow { b }=\ x_a\cdot{x_b}+y_a\cdot{y_b}+z_a\cdot{z_b}\[/latex] и [latex] { \left| \overrightarrow { a } \right| }=\sqrt{x_a^2+y_a^2+z_a^2} [/latex], которую можно сократить в соответствии с нашими значениями координат [latex]Ox,Oy,Oz [/latex] и в итоге получаем формулу [latex] \arccos=\frac{o}{\sqrt{x_a^2+y_a^2+z_a^2}} [/latex], где [latex] O [/latex] ось координат и [latex]o [/latex] значение по этой оси координат. В эту формулу поочередно подставляем наши значения и получаем косинусы углов между осями координат и заданным вектором. Для вычисления углов в радианах воспользуемся встроенной функцией [latex] acos [/latex], а для вычисления в градусах домножим полученный результат на 180 и разделим на встроенное значение числа [latex] \pi [/latex].

Ссылки
Ideone