There is no Spoon — Episode 1

15/04/2017 by Вадим Гордийчук

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

You give an incorrect neighbor for a node.
You give the neighbors for an empty cell.
You compute the same node twice.
You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

( x1, y1) the coordinates of a node.
( x2, y2) the coordinates the closest neighbor on the right of the node.
( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input	Output
2 2 00 0.	0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1
4 4 .0.. .000 000. ..0.	1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1

The code of the program

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

int main()
{
    short width; // the number of cells on the X axis
    cin >> width; cin.ignore();
    short height; // the number of cells on the Y axis
    cin >> height; cin.ignore();
    string *node = new string[height];
    short x, y;
    for (y = 0; y < height; ++y)
    {
        getline(cin, node[y]);
    }
    for (y = 0; y < height; ++y)
    {
        for (x = 0; x < width; ++x)
        {
            if (node[y][x] == '0')
            {
                cout << x << ' ' << y << ' ';
                short x2, y2, ansX = -1, ansY = -1;
                for (x2 = x+1; x2 < width; ++x2)
                {
                    if (node[y][x2] == '0')
                    {
                        ansX = x2;
                        ansY = y;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << ' ';
                ansX = -1; ansY = -1;
                for (y2 = y+1; y2 < height; ++y2)
                {
                    if (node[y2][x] == '0')
                    {
                        ansX = x;
                        ansY = y2;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << '\n';
                x = x2-1;
            }
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

short width; // the number of cells on the X axis

cin >> width; cin.ignore();

short height; // the number of cells on the Y axis

cin >> height; cin.ignore();

string *node = new string[height];

short x, y;

for (y = 0; y < height; ++y)

{

getline(cin, node[y]);

}

for (y = 0; y < height; ++y)

{

for (x = 0; x < width; ++x)

{

if (node[y][x] == '0')

{

cout << x << ' ' << y << ' ';

short x2, y2, ansX = -1, ansY = -1;

for (x2 = x+1; x2 < width; ++x2)

{

if (node[y][x2] == '0')

{

ansX = x2;

ansY = y;

break;

}

cout << ansX << ' ' << ansY << ' ';

ansX = -1; ansY = -1;

for (y2 = y+1; y2 < height; ++y2)

{

if (node[y2][x] == '0')

{

ansX = x;

ansY = y2;

break;

}

cout << ansX << ' ' << ansY << '\n';

x = x2-1;

}

import java.util.*;
import java.io.*;
import java.math.*;

class Player
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        short width = in.nextShort(); // the number of cells on the X axis
        short height = in.nextShort(); // the number of cells on the Y axis
        
        if (in.hasNextLine()) {
            in.nextLine();
        }

        String node[] = new String[height];
        
        for(short y = 0; y < height; ++y)
        {
            node[y] = in.nextLine();
        }
        
        for(short y = 0; y < height; ++y)
        {
            for(short x = 0; x < width; ++x)
            {
                if (node[y].charAt(x) == '0')
                {
                    out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");
                    short x2, y2, ansX = -1, ansY = -1;
                    for (x2 = (short)(x+1); x2 < width; ++x2)
                    {
                        if (node[y].charAt(x2) == '0')
                        {
                            ansX = x2;
                            ansY = y;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");
                    ansX = -1;
                    ansY = -1;
                    
                    for(y2 = (short)(y+1); y2 < height; ++y2)
                    {
                        if (node[y2].charAt(x) == '0')
                        {
                            ansX = x;
                            ansY = y2;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");
                    x = (short)(x2-1);
                }
            }
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short width = in.nextShort(); // the number of cells on the X axis

short height = in.nextShort(); // the number of cells on the Y axis

if (in.hasNextLine()) {

in.nextLine();

}

String node[] = new String[height];

for(short y = 0; y < height; ++y)

{

node[y] = in.nextLine();

}

for(short y = 0; y < height; ++y)

{

for(short x = 0; x < width; ++x)

{

if (node[y].charAt(x) == '0')

{

out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");

short x2, y2, ansX = -1, ansY = -1;

for (x2 = (short)(x+1); x2 < width; ++x2)

{

if (node[y].charAt(x2) == '0')

{

ansX = x2;

ansY = y;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");

ansX = -1;

ansY = -1;

for(y2 = (short)(y+1); y2 < height; ++y2)

{

if (node[y2].charAt(x) == '0')

{

ansX = x;

ansY = y2;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");

x = (short)(x2-1);

}

out.flush();

}

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Related Images:

Код Хаффмана

15/04/2017 by Вадим Гордийчук

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

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

Некоторая последовательность символов и endl.

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

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

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

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

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

for (int j = 0; ; ++j)

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

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

{

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

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

for (unsigned int i = 0; i < S.size(); ++i)

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

Код программы на ideone.com.

Related Images:

Просто RSQ

15/04/2017 by Вадим Гордийчук

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

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

Примеры

rsq.in	rsq.out
5 3 1 2 3 4 5 0 1 5 1 1 -14 0 1 5	15 0
8 2 7 3 -10 4 1 2 5 6 0 2 4 0 5 7	-3 8

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

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

int main()
{
    ifstream cin("rsq.in");
    ofstream cout("rsq.out");
    ios::sync_with_stdio(false);
    unsigned int n, m, i;
    long long sum = 0, sum_k;
    int *a, x, y;
    bool t;
    cin >> n >> m; n++;
    a = new int[n];
    for (i = 1; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    const unsigned int ndiv2 = n/2;
    while (m--)
    {
        cin >> t >> x;
        if (t)
        {
            sum -= a[x];
            cin >> a[x];
            sum += a[x];
        }
        else
        {
            cin >> y;
            y++;
            if (y - x > ndiv2)
            {
                sum_k = sum;
                for (i = 1; i < x; i++)
                {
                    sum_k -= a[i];
                }
                for (i = y; i < n; i++)
                {
                    sum_k -= a[i];
                }
            }
            else
            {
                sum_k = 0;
                for (; x < y; x++)
                {
                    sum_k += a[x];
                }
            }
            cout << sum_k << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream cin("rsq.in");

ofstream cout("rsq.out");

ios::sync_with_stdio(false);

unsigned int n, m, i;

long long sum = 0, sum_k;

int *a, x, y;

bool t;

cin >> n >> m; n++;

a = new int[n];

for (i = 1; i < n; i++)

{

cin >> a[i];

sum += a[i];

}

const unsigned int ndiv2 = n/2;

while (m--)

{

cin >> t >> x;

if (t)

{

sum -= a[x];

cin >> a[x];

sum += a[x];

}

else

{

cin >> y;

y++;

if (y - x > ndiv2)

{

sum_k = sum;

for (i = 1; i < x; i++)

{

sum_k -= a[i];

}

for (i = y; i < n; i++)

{

sum_k -= a[i];

}

else

{

sum_k = 0;

for (; x < y; x++)

{

sum_k += a[x];

}

cout << sum_k << endl;

}

return 0;

}

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

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

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

Ссылки

Related Images:

D2574. Сумма ряда

27/02/2017 by Андреев Даниил

Задача

Найти сумму сходящегося ряда: [latex]\sum \limits_{n=1}^{n}\frac{\sin{nx}}{2^{n}}[/latex].

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

[latex]n[/latex] — количество шагов;
[latex]x[/latex] — значение [latex]x[/latex].

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

Сумма ряда [latex]\sum \limits_{n=1}^{n}\frac{sin(nx)}{2^{n}}[/latex].

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]x[/latex]
10	0.523598	0.651170
25	3.141592	0
15	1.570796	0.399994

Код программы на C++

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    int e=1, n;
    double x, t, o=0;
 
    cin >> n >> x;
 
    for (int j=1; j<(n+1); j++)
    {
        t=sin(j*x);
        e*=2;
        o+=t/e;
    }
 
    cout << fixed << o;
 
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int e=1, n;

double x, t, o=0;

cin >> n >> x;

for (int j=1; j<(n+1); j++)

{

t=sin(j*x);

e*=2;

o+=t/e;

}

cout << fixed << o;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int e=1;
        double t, o=0;
        int n = scan.nextInt();
        double x = scan.nextDouble();
        
        for (int j=1; j<(n+1); j++){
            t=Math.sin(j*x);
            e*=2;
            o+=t/e;
        }
        
        System.out.printf("%1$.6f", o);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int e=1;

double t, o=0;

int n = scan.nextInt();

double x = scan.nextDouble();

for (int j=1; j<(n+1); j++){

t=Math.sin(j*x);

e*=2;

o+=t/e;

}

System.out.printf("%1$.6f", o);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone на C++;
Ideone на Java;
WolframAlpha.

Related Images:

A320. Вложенный цикл

25/12/2016 by Андреев Даниил

Задача

Вычислить [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

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

Произвольные [latex]n[/latex] и [latex]m.[/latex]

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

Значение [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]m[/latex]
10	15	983455
2	5	150
3	6	816

Код программы на C++

#include <iostream>
using namespace std;
int main()
{
    long double sum_1=0, sum_2=0;
    int n, m;
    cin >> n >> m;
    for(int k=1;k<=n;k++)
    {
        for(int l=1;l<=m;l++)
        {
            sum_2+=(k-l)*(k-l);
        }
        sum_1+=k*k*k*sum_2;
        sum_2-=sum_2;
    }
    cout << sum_1;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

long double sum_1=0, sum_2=0;

int n, m;

cin >> n >> m;

for(int k=1;k<=n;k++)

{

for(int l=1;l<=m;l++)

{

sum_2+=(k-l)*(k-l);

}

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

cout << sum_1;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        double sum_1=0, sum_2=0;
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        for(int k=1; k<=n; k++){
            for(int l=1; l<=m; l++)  sum_2+=(k-l)*(k-l);
            sum_1+=k*k*k*sum_2;
            sum_2-=sum_2;
        }
        
        System.out.print(sum_1);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

double sum_1=0, sum_2=0;

int n = scan.nextInt();

int m = scan.nextInt();

for(int k=1; k<=n; k++){

for(int l=1; l<=m; l++) sum_2+=(k-l)*(k-l);

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

System.out.print(sum_1);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone C++;
Ideone Java;
WolframAlpha.

Related Images:

Площадь поверхности

11/12/2016 by Тимур Фирсов

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

№	[latex]f\left( x, y\right)[/latex]	Входные данные					Выходные данные
		[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]x+y[/latex]	-10	10	-10	10	0.001	692.82
2	[latex]\left\| x \right\| +\left\| y \right\|[/latex]	-2	2	-2	2	0.005	27.7128
3	[latex]1[/latex]	0	100	0	100	0.1	10000
4	[latex]{x}^{2}+{y}^{2}[/latex]	-1	1	-1	1	0.0005	7.44626

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

#include <iostream>
#include <cmath>
using namespace std;
double z(double x, double y){
    return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).
}
double dl(double x, double y, double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi, double xj, double yi, double yj){
    double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;
    zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj, yj);
    zij=z(xi, yj);
    zji=z(xj, yi);
    v1x=(yi-yj)*(zji-zii);  //Вычислим векторное произведение векторов.
    v1y=(zii-zij)*(xj-xi);
    v1z=(yj-yi)*(xj-xi);
    v2x=(yj-yi)*(zji-zjj);
    v2y=(zjj-zij)*(xi-xj);
    v2z=(yi-yj)*(xi-xj);
    return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi, xj, yi, yj, s=0, h;
    int a, b, c, d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<(d-h)){
            yj=yi+h;
            s+=ras(xi,xj,yi,yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y){

return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).

}

double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;

zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj);

zij=z(xi, yj);

zji=z(xj, yi);

v1x=(yi-yj)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zii-zij)*(xj-xi);

v1z=(yj-yi)*(xj-xi);

v2x=(yj-yi)*(zji-zjj);

v2y=(zjj-zij)*(xi-xj);

v2z=(yi-yj)*(xi-xj);

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h;

int a, b, c, d;

cin >> a >> b >> c >> d >> h;

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<(d-h)){

yj=yi+h;

s+=ras(xi,xj,yi,yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах. Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

Модифицируем данную программу для нахождения приблизительной площади поверхности, заданной функцией с корнем чётной степени.

Тесты

№	[latex]f\left( x, y\right)[/latex]	[latex]z_0[/latex]	Входные данные					Выходные данные
			[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]1[/latex]	-1	1	-1	1	0.00011	6.28734
2	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]7y[/latex]	-1	1	-1	1	0.00011	23.0803
3	[latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex]	[latex]0[/latex]	-1	1	-2	2	0.00015	8.08214
4	[latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]-1[/latex]	-2	2	-2	2	0.0005	12.5835

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

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

double z(double x,  double y,  double &z0){
    z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.
    return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).
}
long double  dl(double x,  double y,  double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi,  double xj,  double yi,  double yj){
    double zii,  zjj,  zij,  zji,  v1x=0,  v1y=0,  v1z=0,  v2x=0,  v2y=0,  v2z=0,  z0=0;
    zii=z(xi,  yi,  z0); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj,  yj,  z0);
    zij=z(xi,  yj,  z0);
    zji=z(xj,  yi,  z0);
    if(z(xi,  yi,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){//Используем функцию z(),  потому что z0 может оказаться переменной.
        v1x=(yj-yi)*(zji-zii);  //Вычислим векторное произведение векторов.
        v1y=(zij-zii)*(xj-xi);
        v1z=(yi-yj)*(xj-xi);
    }
    if(z(xj,  yj,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){
        v2x=(yi-yj)*(zji-zjj);
        v2y=(zij-zjj)*(xi-xj);
        v2z=(yj-yi)*(xi-xj);
    }
    return (dl(v1x,  v1y,  v1z)+dl(v2x,  v2y,  v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi,  xj,  yi,  yj,  s=0,  h,  z0=0;
    int a,  b,  c,  d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<=(d-h)){
            yj=yi+h;
            s+=ras(xi, xj, yi, yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y, double &z0){

z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.

return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).

}

long double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0, z0=0;

zii=z(xi, yi, z0); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj, z0);

zij=z(xi, yj, z0);

zji=z(xj, yi, z0);

if(z(xi, yi, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){//Используем функцию z(), потому что z0 может оказаться переменной.

v1x=(yj-yi)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zij-zii)*(xj-xi);

v1z=(yi-yj)*(xj-xi);

}

if(z(xj, yj, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){

v2x=(yi-yj)*(zji-zjj);

v2y=(zij-zjj)*(xi-xj);

v2z=(yj-yi)*(xi-xj);

}

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h, z0=0;

int a, b, c, d;

cin >> a >> b >> c >> d >> h;

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<=(d-h)){

yj=yi+h;

s+=ras(xi, xj, yi, yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

Related Images:

MS17. Самосинхронизирующийся скремблер

11/12/2016 by Вадим Гордийчук

Задача

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера. Начальное значение и обратные связи скремблера должны быть заданы в программе значениями двух переменных типа unsigned char. Как расшифровать полученный код.

Примечание: разобьём данную нам задачу на две подзадачи. В первой будет рассмотрено скремблирование входных данных, а во второй будет проведено дескремблирование исходных данных первой подзадачи.

Подзадача 1

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера.

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

Некая символьная последовательность.

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

Зашифрованная символьная последовательность.

Тесты

Входные данные	Выходные данные
Dogs eat meat.	ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa
Scramble it!	fc 5a 80 ef 75 43 1e 92 9b 46 57 6
Base, base, it’s cheeseburger 1. Can you hear me?	ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1

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

#include<iostream>
using namespace std;

class self_synchronizing_scrambler
{
    unsigned char key;
    unsigned char shift_register;

    bool pickbit(const unsigned char val, const short index)
    {
        return ((val >> index)%2);
    }

    public:
    self_synchronizing_scrambler() {}

    self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)
    {
        this->key = key;
        this->shift_register = shift_register;
    }

    void assign_key(unsigned char key) {this->key = key;}
    void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

    unsigned char key_value() {return key;}
    unsigned char register_value() {return shift_register;}

    void scramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for (unsigned char i = 0; i < 8; ++i)
        {
            bool newbit = pickbit(letter, 7-i);
            for (unsigned char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (key >> 1) + (newbit << 7);
        }
        letter = output;
    }

    void descramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for(unsigned char i = 0; i < 8; ++i)
        {
            bool oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(unsigned char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (key >> 1) + (oldbit << 7);
        }
        letter = output;
    }
};

int main()
{
    self_synchronizing_scrambler A(5, 17);
    unsigned char input;

    while (scanf("%c", &input))
    {
        if (input == '\n') break;
        A.scramble(input);
        printf("%x ", input);
    }
    return 0;
}

#include<iostream>

using namespace std;

class self_synchronizing_scrambler

{

unsigned char key;

unsigned char shift_register;

bool pickbit(const unsigned char val, const short index)

{

return ((val >> index)%2);

}

public:

self_synchronizing_scrambler() {}

self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)

{

this->key = key;

this->shift_register = shift_register;

}

void assign_key(unsigned char key) {this->key = key;}

void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

unsigned char key_value() {return key;}

unsigned char register_value() {return shift_register;}

void scramble(unsigned char &letter)

{

unsigned char output = 0;

for (unsigned char i = 0; i < 8; ++i)

{

bool newbit = pickbit(letter, 7-i);

for (unsigned char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (key >> 1) + (newbit << 7);

}

letter = output;

}

void descramble(unsigned char &letter)

{

unsigned char output = 0;

for(unsigned char i = 0; i < 8; ++i)

{

bool oldbit = pickbit(letter, 7-i), scrambit = 0;

for(unsigned char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (key >> 1) + (oldbit << 7);

}

letter = output;

}

};

int main()

{

self_synchronizing_scrambler A(5, 17);

unsigned char input;

while (scanf("%c", &input))

{

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

A.scramble(input);

printf("%x ", input);

}

return 0;

}

import java.util.*;
import java.io.*;

class SelfSynchronizingScrambler
{
    private char key, shift_register;

    private static int pickbit(char val, int index)
    {
        return ((val >> index)%2);
    }

    public SelfSynchronizingScrambler() {}

    public SelfSynchronizingScrambler(char key, char shift_register)
    {
        this.key = key;
        this.shift_register = shift_register;
    }

    public void assignKey(char key) {this.key = key;}
    public void assignRegister(char shift_register) {this.shift_register = shift_register;}

    public char keyValue() {return key;}
    public char registerValue() {return shift_register;}

    public char scramble(char letter)
    {
        char output = 0;
        for (char i = 0; i < 8; ++i)
        {
            int newbit = pickbit(letter, 7-i);
            for (char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (char)((key >> 1) + (newbit << 7));
        }
        return output;
    }

    public char descramble(char letter)
    {
        char output = 0;
        for(char i = 0; i < 8; ++i)
        {
            int oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (char)((key >> 1) + (oldbit << 7));
        }
        return output;
    }
};

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);
        PrintWriter out = new PrintWriter(System.out);

        char letter = (char)System.in.read();
        while(letter != '\n')
        {
            out.print((int)(A.scramble(letter)));
            out.print(' ');
            letter = (char)System.in.read();
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

class SelfSynchronizingScrambler

{

private char key, shift_register;

private static int pickbit(char val, int index)

{

return ((val >> index)%2);

}

public SelfSynchronizingScrambler() {}

public SelfSynchronizingScrambler(char key, char shift_register)

{

this.key = key;

this.shift_register = shift_register;

}

public void assignKey(char key) {this.key = key;}

public void assignRegister(char shift_register) {this.shift_register = shift_register;}

public char keyValue() {return key;}

public char registerValue() {return shift_register;}

public char scramble(char letter)

{

char output = 0;

for (char i = 0; i < 8; ++i)

{

int newbit = pickbit(letter, 7-i);

for (char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (char)((key >> 1) + (newbit << 7));

}

return output;

}

public char descramble(char letter)

{

char output = 0;

for(char i = 0; i < 8; ++i)

{

int oldbit = pickbit(letter, 7-i), scrambit = 0;

for(char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (char)((key >> 1) + (oldbit << 7));

}

return output;

}

};

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);

PrintWriter out = new PrintWriter(System.out);

char letter = (char)System.in.read();

while(letter != '\n')

{

out.print((int)(A.scramble(letter)));

out.print(' ');

letter = (char)System.in.read();

}

out.flush();

}

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

Для зашифровки будем использовать стандартный алгоритм скремблирования. Скремблером будет переменная key, которая изначально равна [latex]5[/latex]. Выбирать из скремблера будем нулевой и четвёртый биты. Входные данные будут поступать в переменную input, после чего на них и на скремблере будет применяться функция scram.
Так как входные данные имеют формат unsigned char, считывание не прекратится никогда вплоть до принудительной остановки программы, ведь любые входные данные могут быть восприняты как символы. Для предотвращения этого, необходим символ, который будет служить «сигналом» для остановки программы. В нашем случае, это будет символ перехода на следующую строку.
Основная проблема задачи заключается в выводе зашифрованных данных, так как в результате скремблирования некоторые символы могут оказаться не отображаемыми. Дабы избежать подобной ситуации, зашифрованные данные будем выводить в шестнадцатеричном (для кода на Java — в десятичном) числовом формате.

Подзадача 2

Расшифровать входные данные из предыдущей подзадачи.

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

Некие зашифрованные данные, записанные в виде последовательности чисел шестнадцатеричного (для кода на Java — десятичного) формата.

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

Расшифрованные данные.

Тесты

Входные данные	Выходные данные
ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa	Dogs eat meat.
fc 5a 80 ef 75 43 1e 92 9b 46 57 6	Scramble it!
ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1	Base, base, it’s cheeseburger 1. Can you hear me?

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

#include <iostream>
using namespace std;

class self_synchronizing_scrambler
{
    unsigned char key;
    unsigned char shift_register;

    bool pickbit(const unsigned char val, const short index)
    {
        return ((val >> index)%2);
    }

    public:
    self_synchronizing_scrambler() {}

    self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)
    {
        this->key = key;
        this->shift_register = shift_register;
    }

    void assign_key(unsigned char key) {this->key = key;}
    void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

    unsigned char key_value() {return key;}
    unsigned char register_value() {return shift_register;}

    void scramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for (unsigned char i = 0; i < 8; ++i)
        {
            bool newbit = pickbit(letter, 7-i);
            for (unsigned char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (key >> 1) + (newbit << 7);
        }
        letter = output;
    }

    void descramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for(unsigned char i = 0; i < 8; ++i)
        {
            bool oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(unsigned char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (key >> 1) + (oldbit << 7);
        }
        letter = output;
    }
};

int main()
{
    self_synchronizing_scrambler A(5,17);
    unsigned short scrambled;
    unsigned char output;

    while (cin >> hex >> scrambled)
    {
        output = scrambled;
        A.descramble(output);
        cout << output;
    }

    return 0;
}

#include <iostream>

using namespace std;

class self_synchronizing_scrambler

{

unsigned char key;

unsigned char shift_register;

bool pickbit(const unsigned char val, const short index)

{

return ((val >> index)%2);

}

public:

self_synchronizing_scrambler() {}

self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)

{

this->key = key;

this->shift_register = shift_register;

}

void assign_key(unsigned char key) {this->key = key;}

void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

unsigned char key_value() {return key;}

unsigned char register_value() {return shift_register;}

void scramble(unsigned char &letter)

{

unsigned char output = 0;

for (unsigned char i = 0; i < 8; ++i)

{

bool newbit = pickbit(letter, 7-i);

for (unsigned char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (key >> 1) + (newbit << 7);

}

letter = output;

}

void descramble(unsigned char &letter)

{

unsigned char output = 0;

for(unsigned char i = 0; i < 8; ++i)

{

bool oldbit = pickbit(letter, 7-i), scrambit = 0;

for(unsigned char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (key >> 1) + (oldbit << 7);

}

letter = output;

}

};

int main()

{

self_synchronizing_scrambler A(5,17);

unsigned short scrambled;

unsigned char output;

while (cin >> hex >> scrambled)

{

output = scrambled;

A.descramble(output);

cout << output;

}

return 0;

}

import java.util.*;
import java.io.*;

class SelfSynchronizingScrambler
{
    private char key, shift_register;

    private static int pickbit(char val, int index)
    {
        return ((val >> index)%2);
    }

    public SelfSynchronizingScrambler() {}

    public SelfSynchronizingScrambler(char key, char shift_register)
    {
        this.key = key;
        this.shift_register = shift_register;
    }

    public void assignKey(char key) {this.key = key;}
    public void assignRegister(char shift_register) {this.shift_register = shift_register;}

    public char keyValue() {return key;}
    public char registerValue() {return shift_register;}

    public char scramble(char letter)
    {
        char output = 0;
        for (char i = 0; i < 8; ++i)
        {
            int newbit = pickbit(letter, 7-i);
            for (char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (char)((key >> 1) + (newbit << 7));
        }
        return output;
    }

    public char descramble(char letter)
    {
        char output = 0;
        for(char i = 0; i < 8; ++i)
        {
            int oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (char)((key >> 1) + (oldbit << 7));
        }
        return output;
    }
};

public class Main
{

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);
        char scrambled;

        while(in.hasNextInt())
        {
            scrambled = (char)in.nextInt();
            out.print(A.descramble(scrambled));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

class SelfSynchronizingScrambler

{

private char key, shift_register;

private static int pickbit(char val, int index)

{

return ((val >> index)%2);

}

public SelfSynchronizingScrambler() {}

public SelfSynchronizingScrambler(char key, char shift_register)

{

this.key = key;

this.shift_register = shift_register;

}

public void assignKey(char key) {this.key = key;}

public void assignRegister(char shift_register) {this.shift_register = shift_register;}

public char keyValue() {return key;}

public char registerValue() {return shift_register;}

public char scramble(char letter)

{

char output = 0;

for (char i = 0; i < 8; ++i)

{

int newbit = pickbit(letter, 7-i);

for (char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (char)((key >> 1) + (newbit << 7));

}

return output;

}

public char descramble(char letter)

{

char output = 0;

for(char i = 0; i < 8; ++i)

{

int oldbit = pickbit(letter, 7-i), scrambit = 0;

for(char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (char)((key >> 1) + (oldbit << 7));

}

return output;

}

};

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);

char scrambled;

while(in.hasNextInt())

{

scrambled = (char)in.nextInt();

out.print(A.descramble(scrambled));

}

out.flush();

}

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

Для расшифровки будем применять обратный алгоритм к использованному в предыдущей задаче. Значение необходимого для расшифровки дескремблера нам известно из предыдущей задачи (а именно — [latex]5[/latex]), поэтому его мы и используем.
Входные данные будут считываться методом cin (для C++), где параметр hex будет указывать на то, что данные поданы в шестнадцатеричном формате. После считывания на входных данных будет применяться алгоритм дескремблирования, и итоговые данные будут выведены на экран.

Ссылки

Related Images:

D2631. Сумма ряда с заданной точностью

08/12/2016 by Тимур Фирсов

Задача

Найти количество членов ряда, требуемых для получения значения [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] с точностью до [latex]\varepsilon [/latex], а также найти само значение суммы с заданной точностью.

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

Точность [latex]\varepsilon [/latex].

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

Количество членов ряда [latex]n[/latex].
Значение суммы [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex].

Тесты

№	Входные данные	Выходные данные
	[latex]\varepsilon[/latex]	[latex]n[/latex]	[latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex]
1	0.01	98	4.74785
2	1e-7	4188	5.71199
3	1e-9	8900	5.71208
4	1	1	0.367879

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

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

int main() {
    double sum=0, xn=1, eps;
    int n=0;
    cin >> eps;
    while(xn>=eps){
        n++;
        xn=pow(M_E, -pow(n,1.0/3));
        sum+=xn;
    }
    cout << n << " " << sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double sum=0, xn=1, eps;

int n=0;

cin >> eps;

while(xn>=eps){

n++;

xn=pow(M_E, -pow(n,1.0/3));

sum+=xn;

}

cout << n << " " << sum;

return 0;

}

Решение

Докажем, что ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится. Обозначим общий член данного ряда [latex]x_n[/latex]. Поскольку все члены ряда положительны, воспользуемся предельным признаком сравнения рядов. Для сравнения возьмём сходящийся ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ \frac { 1 }{ { n }^{ 2 } } } [/latex], общий член которого обозначим [latex]b_n[/latex]: [latex]\lim\limits_{ n\rightarrow \infty }{ \frac { x_n }{ b_n } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=K[/latex], тогда данный ряд сходится, если [latex]0<K<\infty [/latex], либо [latex]K=0[/latex].
[latex]\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ e }^{ {2}{\ln { \left( n \right)} } } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n }+{ {2}{\ln { \left( n \right)} } } }}={ e }^{ -\infty }=0 [/latex].
[latex]K=0[/latex], а значит ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится и значение суммы является конечным числом. Тогда для сколь угодно малого [latex]\varepsilon >0[/latex] найдётся номер, начиная с которого каждый последующий член ряда меньше [latex]\varepsilon[/latex]

Ссылки

Код программы.
Условие задачи (страница 257).

Related Images:

A333. Наибольший общий делитель чисел последовательности

29/11/2016 by Вадим Гордийчук

Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).

Задача

Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.

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

Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].

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

[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].

Тесты

Входные данные					Выходные данные
2	3	4			1
2	4	8			4
4	24	23	40	90	1
4	36	48	20	24	4
3	30	738	1926		6

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

#include <iostream>
using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)
{
    return (n != 0) ? gcd(n, m%n) : m;
}

int main()
{
    unsigned long long m, n, result;
    cin >> m >> result;
    for (unsigned long long i = 2; i <= m; i++)
    {
        cin >> n;
        result = gcd(result, n);
        if (result == 1) m = 1; //same as break
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)

{

return (n != 0) ? gcd(n, m%n) : m;

}

int main()

{

unsigned long long m, n, result;

cin >> m >> result;

for (unsigned long long i = 2; i <= m; i++)

{

cin >> n;

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

cout << result << endl;

return 0;

}

import java.util.*;

public class Main
{
    public static long gcd(long m, long n)
    {
        if (n != 0)
            return gcd(n, m%n);
        else
            return m;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n, result = in.nextLong();
        
        for(long i = 2; i <= m; ++i)
        {
            n = in.nextLong();
            result = gcd(result, n);
            if (result == 1) m = 1; //same as break
        }
        System.out.println(result);
    }
}

import java.util.*;

public class Main

{

public static long gcd(long m, long n)

{

if (n != 0)

return gcd(n, m%n);

else

return m;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long m = in.nextLong(), n, result = in.nextLong();

for(long i = 2; i <= m; ++i)

{

n = in.nextLong();

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

System.out.println(result);

}

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

Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную m число [latex]m[/latex], а в result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.

Ссылки

Related Images:

A334(б). Сумма в сумме

22/11/2016 by Роман Саркисян

Условие

Вычислить [latex]\sum\limits _{ i=1 }^{ k }{ \sum\limits _{ j=1 }^{ t }{ \sin { ({ i }^{ 3 }+{ j }^{ 4 }) } } } [/latex] .

Решение

В данной задаче нам необходимо сделать два цикла, а конкретней — цикл в цикле.

Тесты

[latex]k[/latex]	[latex]t[/latex]	[latex]S[/latex]
1	1	0.9092
10	15	1.4908
20	30	8.8956
60	100	41.9133

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    double S=0;
    int k,t;
    cin >>k>>t;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=t;j++){
            S+=sin(i*i*i+j*j*j*j);
        }
    }
    cout << S;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double S=0;

int k,t;

cin >>k>>t;

for(int i=1;i<=k;i++){

for(int j=1;j<=t;j++){

S+=sin(i*i*i+j*j*j*j);

}

cout << S;

return 0;

}

Воспользуемся веб-приложением и посчитаем сумму ряда.

Ссылки

Задачник Абрамова
Код на ideone

Related Images:

A324. Делители одного числа, взаимно простые с другим

19/11/2016 by Иванна Ялымова

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex]	[latex]p[/latex]	Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40	15	1 2 4 8
87	3	1 29

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

Код программы на С++

#include <iostream>
using namespace std;
unsigned long gcd(unsigned long x, unsigned long y) {
    return (y!=0) ? gcd(y,x%y) : x;
}

int main() {
    unsigned int q = 0, p;
    cin >> q >> p;
    for (unsigned int i = 1; i <= q; i++) { 
        if((q % i) == 0) {
            if (gcd(i,p) == 1)
                cout << i << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

unsigned long gcd(unsigned long x, unsigned long y) {

return (y!=0) ? gcd(y,x%y) : x;

}

int main() {

unsigned int q = 0, p;

cin >> q >> p;

for (unsigned int i = 1; i <= q; i++) {

if((q % i) == 0) {

if (gcd(i,p) == 1)

cout << i << " ";

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int q = 0, p;
        Scanner in = new Scanner(System.in);
            
        q = in.nextInt();
        p = in.nextInt();
        
        for (int i = 1; i <= q; i++) { 
            if((q % i) == 0) {
                if (gcd(i,p) == 1)
                    System.out.print(i + " ");
            }
        }
    }
    public static long gcd(long x, long y) {
            return (y!=0) ? gcd(y,x%y) : x;
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

int q = 0, p;

Scanner in = new Scanner(System.in);

q = in.nextInt();

p = in.nextInt();

for (int i = 1; i <= q; i++) {

if((q % i) == 0) {

if (gcd(i,p) == 1)

System.out.print(i + " ");

}

public static long gcd(long x, long y) {

return (y!=0) ? gcd(y,x%y) : x;

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].
Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

Related Images:

A334(а). Вложенная сумма

16/11/2016 by Антон Куперман

Задача

Вычислить: [latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex], где [latex]m,n[/latex] — вводимые нами числа.

Тесты

Вход([latex]m,n[/latex])	Выход([latex]S[/latex])
40 20	13.6458
100 50	24.6458
200 25	31.7764
1000 282	89.8078

Код на C++

#include <iostream>
using namespace std;
 
int main() {
    double x, S=0, m, n;
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            x=1.0/(i+j*j);
            S+=x;
        }
    }
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, S=0, m, n;

cin >> m >> n;

for(int i=1;i<=m;i++)

{

for(int j=1;j<=n;j++)

{

x=1.0/(i+j*j);

S+=x;

}

cout << S;

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double S=0, m, n;
        m=in.nextInt();
        n=in.nextInt();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                S+=1.0/(i+j*j);
            }
        }
        System.out.print(S);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double S=0, m, n;

m=in.nextInt();

n=in.nextInt();

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

S+=1.0/(i+j*j);

}

System.out.print(S);

}

Решение

Вводим два оператор цикла for, один вложенный в другой. Задаем наше выражение, а затем суммируем его, согласно циклу.

Ссылки

Related Images:

A327. Простые числа

13/11/2016 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

Выходные данные:
Некоторое количество натуральных чисел.

Тесты.

№	Входные данные		Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	[latex]p[/latex]
1	1	4	2, 3
2	0	1	Not found
3	5	5	5
4	6	20	7, 11, 13, 17, 19

Код программы (C++).

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

int main() {
    cout<<"Primes: ";
    bool prime;
    int a,b;
    cin>>a>>b;
    vector<int> primes;
    for(int e=2; e<=b; e++)
    {
        prime=true;
        for(int i=0; i<primes.size(); i++)
        {
            if((e%primes[i])==0) prime=false;
        }
        if(prime==true)
        {
            primes.push_back(e);
            if(e>=a) cout<<e<<" ";
        }
    }
    if(b<2) cout<<"Not found.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

cout<<"Primes: ";

bool prime;

int a,b;

cin>>a>>b;

vector<int> primes;

for(int e=2; e<=b; e++)

{

prime=true;

for(int i=0; i<primes.size(); i++)

{

if((e%primes[i])==0) prime=false;

}

if(prime==true)

{

primes.push_back(e);

if(e>=a) cout<<e<<" ";

}

if(b<2) cout<<"Not found.";

return 0;

}

Код программы (Java).

import java.util.*;
import java.math.*;
 
class sieveOfEratosthenes
{
    public void find(int a, int b){
        boolean[] prime = new boolean[b+1];
        Arrays.fill(prime, Boolean.TRUE);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i <= b; ++i){
            if(prime[i]){
                for(int j = i*i; j <= b; j += i){
                    prime[j] = false;
                }   
            }   
        }
 
        boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?
        for(int i = a; i <= b; ++i){
            if(prime[i]){
                System.out.print(i + " ");
                primes_found = true;
            }
        }
        if(!primes_found) System.out.print("Not found");
    }
}
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        int a, b;
        a = in.nextInt();
        b = in.nextInt();
        sieveOfEratosthenes c = new sieveOfEratosthenes();
        c.find(a, b);
    }
}

import java.util.*;

import java.math.*;

class sieveOfEratosthenes

{

public void find(int a, int b){

boolean[] prime = new boolean[b+1];

Arrays.fill(prime, Boolean.TRUE);

prime[0] = false;

prime[1] = false;

for(int i = 2; i <= b; ++i){

if(prime[i]){

for(int j = i*i; j <= b; j += i){

prime[j] = false;

}

boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?

for(int i = a; i <= b; ++i){

if(prime[i]){

System.out.print(i + " ");

primes_found = true;

}

if(!primes_found) System.out.print("Not found");

}

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int a, b;

a = in.nextInt();

b = in.nextInt();

sieveOfEratosthenes c = new sieveOfEratosthenes();

c.find(a, b);

}

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)

Related Images:

А329. Квадрат суммы цифр числа

13/11/2016 by Тимур Фирсов

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа [latex]n[/latex], [latex]m[/latex]. Получить все меньшие [latex]n[/latex] натуральные числа, квадрат суммы цифр которых равен [latex]m[/latex].

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

Два положительных числа [latex]n[/latex] и [latex]m[/latex].

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

Все целые числа из [latex]\left( 0,n \right)[/latex], удовлетворяющие условию.

Тесты

№	Входные данные		Выходные данные
№	[latex]n[/latex]	[latex]m[/latex]
1	1234	9	3 12 21 30 102 111 120 201 210 300 1002 1011 1020 1101 1110 1200
2	100	4	2 11 20
3	49	49	7 16 25 34 43
4	1000	1	1 10 100

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

#include <iostream>
using namespace std;

int main() {
    unsigned n, m, t, sum, i=1;
    cin>>n>>m;
    for(i;i<n;i++){
        t=i;
        sum=0;
        while(t!=0){
            sum+=t%10;
            t/=10;
        }
        if(sum*sum==m)cout<<i<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, m, t, sum, i=1;

cin>>n>>m;

for(i;i<n;i++){

t=i;

sum=0;

while(t!=0){

sum+=t%10;

t/=10;

}

if(sum*sum==m)cout<<i<<" ";

}

return 0;

}

Решение

Для того, чтоб найти каждую цифру числа будем искать остаток от деления на [latex]10[/latex], которым является последняя цифра числа, а затем делить число нацело на [latex]10[/latex], чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно [latex]0[/latex]. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от [latex]1[/latex] до [latex]n-1[/latex], параллельно возводя полученную сумму в квадрат, а результат сравнивая с [latex]m[/latex].

Ссылки

Код программы.
Условие задачи (страница 135).

Related Images:

D2575. Сумма ряда

30/10/2016 by Валентина Андриеш

Условие задачи:
Найти сумму сходящегося ряда: [latex]\frac{\cos x-\cos 2x}{1}+\frac{\cos 2x -\cos 3x}{2}+\cdots+\frac{\cos nx-\cos(n+1)x}{n}+\cdots[/latex]

Входные данные:
[latex]x[/latex] — константа;
[latex]number[/latex] — номер искомой частичной суммы;

Выходные данные:
[latex]value[/latex] — значения необходимых слагаемых;
[latex]partial[/latex] _ [latex]amount[/latex] — искомая частичная сумма;

Тесты:

[latex]x[/latex]	[latex]number[/latex]	[latex]value[/latex]	[latex]partial[/latex] _ [latex]amount[/latex]
10	3	-1.24715 0.126915 0.27373	-0.846508
100	4	0.375131 0.254642 0.167733 0.0896382	0.887145
5	5	1.12273 -0.0396918 -0.389257 -0.14578 0.16739	0.715395

Код на языке C++:

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

int main() {
    int number;
    double x;
    cin>>x>>number;
    double value;
    double partial_amount=0;
    int n=1;
    while(n<=number){
        value=(cos((n*x))-cos(((n+1)*x)))/n;
        cout<<value<<" ";
        partial_amount+=value;
        n++;
    }
    cout<<endl;
    cout<<partial_amount;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int number;

double x;

cin>>x>>number;

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(cos((n*x))-cos(((n+1)*x)))/n;

cout<<value<<" ";

partial_amount+=value;

n++;

}

cout<<endl;

cout<<partial_amount;

return 0;

}

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int number=in.nextInt();
        double x=in.nextDouble();
        double value;
        double partial_amount=0;
        int n=1;
        while(n<=number){
            value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;
            System.out.println(value + " " );
            partial_amount+=value;
            n++;
        }
        System.out.println("\n"+partial_amount);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int number=in.nextInt();

double x=in.nextDouble();

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;

System.out.println(value + " " );

partial_amount+=value;

n++;

}

System.out.println("\n"+partial_amount);

}

Решение задачи:
Под словом «ряд» в математическом анализе понимают сумму бесконечного числа слагаемых. Зададим цикл с счетчиком [latex]n[/latex] от 1 до заданного пользователем числа [latex]number[/latex]. Именно такое количество необходимых слагаемых [latex]value=\frac{\cos nx -\cos (n+1)x}{n}[/latex] будет найдено на каждом шаге цикла для последующего суммирования и нахождения искомой частичной суммы.

Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

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

27/10/2016 by Роман Саркисян

Условие

Доказать сходимость ряда и найти его сумму
[latex]\frac { 1 }{ 2 } + \frac { 3 }{ 4 } + \frac { 5 }{ 8 } + \ldots + \frac { 2n-1 }{ { 2 }^{ n } } + \ldots [/latex]

Решение

Для начала докажем, что наш ряд сходится. Докажем это, через признак Даламбера. Суть этого признака заключается в том, что если предел отношения последующего члена к предыдущему меньше [latex]1[/latex](или в частных случаях равен [latex]0[/latex]) то данный ряд будет сходится.
Берем отношение последующего и предыдущего [latex]\lim\limits_{ n\to \infty } \frac { \frac{ 2(n+1)-1 }{ { 2 }^{ n+1 } } }{ \frac{ 2n-1 }{ { 2 }^{ n } } }[/latex] превратим нашу 4-х этажную дробь в 2-х этажную [latex]\lim\limits _{ n\to \infty } \frac { ({ 2(n+1)-1){ 2 }^{ n } } }{ { (2n-1 }){ 2 }^{ n+1 } }[/latex] раскроем скобки и применим свойство степеней, получим [latex] \lim\limits _{ n\to \infty } \frac { (2n+2-1){ 2 }^{ n } }{ (2n-1){ 2 }^{ n }2 }[/latex] далее приведем подобные сократим дробь и снова раскроим скобки, получим [latex]\lim\limits _{ n\to \infty } \frac { 2n+1 }{ 4n-2 } [/latex] далее чтобы перейти непосредственно к пределу разделим коэффициенты при старших степенях числителя на знаменатель, в ответе получаем [latex]\frac { 2 }{ 4 }[/latex] [latex]=[/latex] [latex]\frac { 1 }{ 2 }[/latex].
[latex]\frac { 1 }{ 2 }[/latex] [latex]<[/latex] [latex]1[/latex] из этого следует что данный ряд сходится!
Далее найдем сумму это ряда. [latex]\sum\limits_{ n=1 }^{ \infty } { \frac { 2n-1 }{ { 2 }^{ n } } }[/latex] Воспользуемся веб-приложением и посчитаем сумму ряда.

Тесты

[latex]n[/latex]	сумма [latex]n[/latex] элементов
1	0.5
2	1.25
3	1.875
23	2.99999
24	3

#include <iostream>
using namespace std;
int main() {
    int a,n;
    double s=0,q=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        q=q*2;  
        s+=(2*i-1)/q;
    }
    cout<<s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a,n;

double s=0,q=1;

cin>>n;

for(int i=1;i<=n;i++){

q=q*2;

s+=(2*i-1)/q;

}

cout<<s;

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
  public static void main (String[] args) throws java.lang.Exception
  {
    int a,n;
    double s=0,q=1;
    Scanner in = new Scanner(System.in);
    n=in.nextInt();
    for(int i=1;i<=n;i++){
      q=q*2;  
      s+=(2*i-1)/q;
    }
    System.out.println(s);

  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

int a,n;

double s=0,q=1;

Scanner in = new Scanner(System.in);

n=in.nextInt();

for(int i=1;i<=n;i++){

q=q*2;

s+=(2*i-1)/q;

}

System.out.println(s);

}

Код на ideone C++
Код на ideone Java

Related Images:

D2655Б. Сумма ряда с заданной точностью

23/10/2016 by Вадим Гордийчук

Задача

Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до [latex]10^{-5}[/latex], если [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex]?

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

Заданная точность.

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

Количество взятых членов ряда и их сумма.

Тесты

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

[latex]\varepsilon[/latex] [latex]k[/latex] [latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]

1e-5 11 2.194527283416172

1 2 1.666666666666667

0.5 3 2.000000000000000

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

Программа для решения задачи D2655b
C++

#include <iostream> #include <iomanip> using namespace std; int main() { double Xn = 1, Sn = 0, epsilon; unsigned int n = 0; cin >> epsilon; while (Xn >= epsilon) { n++; Xn *= 2.0 / (n+1); Sn += Xn; } cout << fixed << setprecision(15) << n << " " << Sn << endl; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

int main()
{
 double Xn = 1, Sn = 0, epsilon; unsigned int n = 0;
 cin >> epsilon;
 while (Xn >= epsilon)
 {
 n++;
 Xn *= 2.0 / (n+1);
 Sn += Xn;
 }
 cout << fixed << setprecision(15) << n << " " << Sn << endl;
 return 0;
}

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

Для удобства введём обозначение: [latex]x_{n}=\frac{2^n}{\left(n+1\right)!}[/latex].
Чтобы доказать, что данный нам ряд [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex] сходится, воспользуемся признаком Даламбера:
Пускай [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = D[/latex]. Ряд [latex]\sum\limits_{n=1}^\infty x_n[/latex] сходится, если [latex]D < 1[/latex]. В частности, если [latex]D = 0[/latex]
Найдём [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}}[/latex].
[latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = \lim\limits_{n \to \infty} \left( \frac{2^{n+1}}{\left( n+2 \right)!} \div \frac{2^{n}}{\left( n+1 \right)!} \right) = \lim\limits_{n \to \infty} \left( \frac{2 \cdot 2^{n}}{\left( n+1 \right)! \cdot \left( n+2 \right)} \cdot \frac{\left( n+1 \right)!}{2^{n}} \right) = \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex] Для доказательства последнего равенства [latex]\left( \lim\limits_{n \to \infty} \frac{2}{n+2} = 0 \right)[/latex] воспользуемся определением предела последовательности:
Число [latex]a[/latex] называют пределом последовательности, если для любой точности [latex]\varepsilon>0[/latex] найдётся/существует такой номер, зависящий от [latex]\varepsilon[/latex], начиная с которого все элементы последовательности попадают в интервал [latex]\left( a-\varepsilon; a+\varepsilon \right)[/latex].
В нашем случае число [latex]a[/latex] равно нулю. Поэтому доказательство будет следующим:
[latex]\forall \varepsilon>0[/latex] [latex]\exists N_{\varepsilon} \in \mathbb{N}[/latex]: [latex]\forall n\ge N_{\varepsilon}[/latex], [latex]\left| \frac{2}{n+2} \right| < \varepsilon[/latex]. Находим [latex]N_{\varepsilon}[/latex]:
[latex]\left| \frac{2}{n+2} \right| < \left| \frac{2}{n} \right| = \frac{2}{n} < \varepsilon [/latex]
[latex]\frac{2}{n} < \varepsilon[/latex]
[latex]n > \frac{2}{\varepsilon} \Rightarrow N_{\varepsilon} = \left[ \frac{2}{\varepsilon} \right] + 1 \Rightarrow \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex].

Итог:
Так как ряд сходится, сумма ряда стремится к некоторой константе, и можно определить точный номер [latex]k[/latex], при котором элемент (а следовательно — и сумма) ряда будет удовлетворять заданной точности. Этой точностью будет значение переменной epsilon, которое задаёт пользователь.

Ссылки

Условие задачи (страница 259);

Оригинал кода программы.

Related Images:

Входные данные	Выходные данные
[latex]\varepsilon[/latex]	[latex]k[/latex]	[latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]
1e-5	11	2.194527283416172
1	2	1.666666666666667
0.5	3	2.000000000000000

Posted in 3. Циклы. Tagged последовательность, сумма, циклы.

D2655B. Cумма ряда с заданной точностью

15/10/2016 by Эммануил Прокопов

4

Задача
Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до
[latex]\varepsilon [/latex], если [latex]\sum\limits _{ n=1 }^{ \infty }{ \frac { 1 }{ (2n-1)! } } [/latex]
Тесты

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

Точность Кол-во взятых членов ряда Значение суммы

1 1 2 1.1666666667

2 1е-5 5 1.1752011684

3 100 1 1

4 1e-10 7 1.1752011936

Код на C++

C++

#include <iostream> #include <iomanip> #include <cmath> using namespace std; double e = exp(1); double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } int main() { double eps, sum = 0, last=0; int n = 0; cin >> eps; do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

double e = exp(1);

double bin_pow(double x, int n){
 if(n == 1) return x;
 if(n%2 == 1) return bin_pow(x, n-1)*x;
 double b = bin_pow(x, n/2);
 return b*b;
}

double Rn(int n){
 double v = e/(2*n+1);
 return bin_pow(v, 2*n+1)/(1-v*v);
}

int main() {
 double eps, sum = 0, last=0;
 int n = 0;
 cin >> eps;
 do{
 n++;
 if(n > 1) last /= (2*n-2)*(2*n-1);
 else last = 1;
 sum += last;
 } while(Rn(n) > eps);
 cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum;
 return 0;
}

Код на Java

Java

import java.util.*; class Main { static double e = Math.exp(1); static double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } static double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } public static void main (String[] args) { Scanner in = new Scanner(System.in); double eps, sum = 0, last=0; int n = 0; eps = in.nextDouble(); do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum)); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.*;

class Main
{
 static double e = Math.exp(1);

 static double bin_pow(double x, int n){
 if(n == 1) return x;
 if(n%2 == 1) return bin_pow(x, n-1)*x;
 double b = bin_pow(x, n/2);
 return b*b;
 }

 static double Rn(int n){
 double v = e/(2*n+1);
 return bin_pow(v, 2*n+1)/(1-v*v);
 }

 public static void main (String[] args)
 {
 Scanner in = new Scanner(System.in);
 double eps, sum = 0, last=0;
 int n = 0;
 eps = in.nextDouble();
 do{
 n++;
 if(n > 1) last /= (2*n-2)*(2*n-1);
 else last = 1;
 sum += last;
 } while(Rn(n) > eps);
 System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum));
 }
}

Решение
Очевидно, ряд является положительным, и общий член ряда стремится к нулю. Ряд сходится по признаку Д’аламбера:
[latex] \lim\limits_{n \rightarrow \infty } \frac{ a_{n+1} }{a_{n}} = \lim\limits_{n \rightarrow \infty } \frac{ \big(2n-1\big)! }{ \big(2n+1\big)! } = \lim\limits_{n \rightarrow \infty } \frac{1}{2n \big(2n+1\big) } =0 < 1[/latex].
Оценим остаток ряда, исходя из того, что [latex]k! > \left( \frac{k}{e} \right) ^{k} , \big(k=1,2,\dots\big) [/latex]:
[latex]R_{N}<\sum\limits_{n=N+1}^\infty \left(\frac{e}{2n-1}\right)^{2n-1}\leq\sum\limits_{n=N+1}^\infty \left(\frac{e}{2N+1}\right)^{2n-1}=\left(\frac{e}{2N+1}\right)^{2N+1}\sum\limits_{i=0}^\infty \left(\frac{e}{2N+1}\right)^{2i}[/latex] Поскольку при [latex]N\geq1[/latex] [latex]\frac{e}{2N+1}<1[/latex]:
[latex]R_{N} < \left(\frac{e}{2N+1}\right)^{2N+1}\frac{1}{1-\left(\frac{e}{2N+1}\right)^2}[/latex]
В переменной sum хранится текущее значение суммы ряда, в last — последний рассмотренный член ряда. В начале работы программы вводится требуемая точность eps. Можно заметить, что для получения [latex]n[/latex]-го члена ряда достаточно разделить предыдущий на [latex]\left(2n-2\right)\cdot\left(2n-1\right)[/latex], однако необходимо отдельно рассмотреть случай, когда [latex]n = 1[/latex]. В цикле увеличиваем [latex]n[/latex], находим значение следующего члена ряда и прибавляем к sum, пока остаток ряда не станет достаточно маленьким. Оцениваем остаток ряда при помощи функции Rn(int n). Во время её работы может потребоваться возведение числа в большую степень, делаем это по алгоритму бинарного возведения в степень.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (стр. 259)

Related Images:

Posted in 3. Циклы. Tagged последовательность, сумма, факториал, циклы.

A271

24/06/2016 by Сабиров Ильдар

5

Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]
Тесты

input [latex]\tilde{a}[/latex] [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex] Комментарий

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8

4.4712

Пройдено

2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14 9

6.35834659
Пройдено

3 3 3 3 3 0 0 0 5 5 5 15 15 15 15 6 5.8554 Пройдено

А271
C++

#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { double a=0,s=0,z; int y; vector<int> x; while(cin>>z){ x.push_back(z); } for (int i=0;i<x.size();i++){ a+=x[i]; } a=a/x.size(); for (int i=0;i<x.size();i++){ s=s+(a-x[i])*(a-x[i]); } s=s/(x.size()-1); s=sqrt(s); cout<<a<<" "; cout<<s<<" "; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
 double a=0,s=0,z;
 int y;
 vector<int> x;
 while(cin>>z){
 x.push_back(z);
 }
 for (int i=0;i<x.size();i++){
 a+=x[i];
 }
 a=a/x.size();
 for (int i=0;i<x.size();i++){
 s=s+(a-x[i])*(a-x[i]);
 }
 s=s/(x.size()-1);
 s=sqrt(s);
 cout<<a<<" ";
 cout<<s<<" ";
 return 0;
}

Решение

Заполняем вектор действительными числами

Считаем их сумму (с помощью цикла прибавляем каждый элемент вектора).

Находим значение [latex]\tilde{a}[/latex].

Находим сумму под корнем второй формулы через цикл (аналогично п.2)

Производим необходимые арифметические операции для нахождения значения второй формулы.

Вывод значений.
Ссылка на код

Related Images:

Posted in 9. Последовательные контейнеры. Tagged вектор, сумма арифметической прогрессии, циклы.

MLoops15

15/04/2016 by Аня Шохина

1

Задача. Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]m>0[/latex] (количество столбцов) и [latex]n>0[/latex] (количество строк). При чем [latex]k<m[/latex]. Многоточие означает продолжение последовательности.

C++

112233...kk112233...kk1122 k112233...kk112233...kk112 kk112233...kk112233...kk11 .kk112233...kk112233...kk1 ..kk112233...kk112233...kk ...kk112233...kk112233...k

1
2
3
4
5
6

112233...kk112233...kk1122
k112233...kk112233...kk112
kk112233...kk112233...kk11
.kk112233...kk112233...kk1
..kk112233...kk112233...kk
...kk112233...kk112233...k

Тесты

[latex] m[/latex] [latex] n[/latex] [latex] k[/latex] Результат

25 4 8 1122334455667788112233445
8112233445566778811223344
8811223344556677881122334
7881122334455667788112233

8 9 3 11223311
31122331
33112233
23311223
22331122
12233112
11223311
31122331
33112233

4 4 3 1122
3112
3311
2331

Код

C++

#include <iostream> #include <cmath> using namespace std; int main() { int m, n,k; double l=1; int counter = 0; cin >> m >> n >>k; for (int i=1; i<=n; i++){ if(counter) l=k*2-(counter-1); //вычисляем первый элемент строки if(l<2) counter=0; //проверяем элемент на положительное значение for (int j=1; j<=m; j++){ if(l>k*2){ l=1; } cout << ceil(l/2) ; l++; } cout << endl; counter++; } return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

int main() {
 int m, n,k;
 double l=1;
 int counter = 0;
 cin >> m >> n >>k;
 for (int i=1; i<=n; i++){
 if(counter) l=k*2-(counter-1); //вычисляем первый элемент строки
 if(l<2) counter=0; //проверяем элемент на положительное значение
 for (int j=1; j<=m; j++){
 if(l>k*2){
 l=1;
 }
 cout << ceil(l/2) ;
 l++;
 }
 cout << endl;
 counter++;
 }
 return 0;
}

Код на ideone.com

Решение

Для решения данной задачи введем дополнительную переменную [latex]l[/latex], которая будет накапливать в себе количество напечатанных символов в строке. Каждое число в строке повторяется дважды, следовательно печатать будем число, равное целой части [latex]\left( l\div 2 \right)[/latex].

Обратим внимание на начало каждой строки. В каждой следующей строке мы сдвигаем последовательность на одно число вправо. Тогда значение переменной [latex] l[/latex] на второй строке должно быть максимально возможным [latex]\left(k\cdot2 \right)[/latex] и уменьшаться на единицу при каждом переходе на следующую строку.

Related Images:

Posted in 3. Циклы. Tagged таблица чисел, циклы.

Post navigation

← Older posts

Newer posts →

Search

1. Линейные вычисления

2. Программы с ветвлением

3. Циклы

4. Потоковая обработка

5. Массивы

6. Многомерные массивы

7. Строки c-string

8. Строки string

9. Последовательные контейнеры

A. Сортировки и жадность

B. Стеки-деки-очереди

C. Ассоциативные контейнеры

D. Графы

E. Дерево отрезков

F. Динамическое программирование

Игры программистов

Спортивное программирование

Творческие задачи

Численный анализ

⌂ Организационные

Студенты 2020

Введите адрес для отправки новостей

E-mail

Іванов Вячеслав Володимирович (22)
Ілларіонова Марія Валеріївна (20)
Вустянюк Ігор Дмитрович (19)
Зелінський Вячеслав Олександрович (19)
Сплошнов Кирилл (18)
Таран Таня (17)
Гордийчук Вадим (15)
Царев Николай Александрович (14)
Швандт Максим Альбертович (14)
Осецимський Анатолій Вадимович (14)
Студенты 2019

Студенты 2018

Студенты 2017

Студенты 2016

Студенты 2015

Студенты 2014

Proudly powered by WordPress | Theme: Sunspot by WordPress.com.

№	Входные данные	Выходные данные
	Точность	Кол-во взятых членов ряда	Значение суммы
1	1	2	1.1666666667
2	1е-5	5	1.1752011684
3	100	1	1
4	1e-10	7	1.1752011936

input	[latex]\tilde{a}[/latex]	[latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex]	Комментарий
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	8	4.4712	Пройдено
2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14	9	6.35834659	Пройдено
3 3 3 3 3 0 0 0 5 5 5 15 15 15 15	6	5.8554	Пройдено

[latex] m[/latex]	[latex] n[/latex]	[latex] k[/latex]	Результат
25	4	8	1122334455667788112233445 8112233445566778811223344 8811223344556677881122334 7881122334455667788112233
8	9	3	11223311 31122331 33112233 23311223 22331122 12233112 11223311 31122331 33112233
4	4	3	1122 3112 3311 2331