Просто 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:

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

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

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

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

Тесты

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

Код задачи

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

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

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n;

cin>>n;

long long x[n];

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

{

cin>>x[i];

}

int ind=0;

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

{

if(x[i]!=0)

{

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

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

x[ind]=0;

}

return 0;

}

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

Related Images:

AL1

13/09/2016 by Станислав Коциевский

Условие задачи

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные	Результат
4 a b b c c d b d	полный порядок
3 2 a 8 c c b	порядок неполный
3 2 a 8 c a 8	полный порядок
4 2 a 8 c c 2 a c	Порядок противоречив
10 a 5 5 4 b 3 3 4 5 3 b 5 a b 4 * * 0 4 0	полный порядок

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

#include <iostream>
#include <algorithm> //для использования функции sort
using namespace std;

int main()
{
    const int lch = 256;
    int n;
    cin>>n;
    
    char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.
    for (int i = 0; i < n; i++)
    {
        p[i] = new char [2];
    }
        
    for (int i = 0; i < n; i++)
    {
        cin >> p[i][1]>>p[i][2];
    }
    
    int chars[lch];
    for (int i = 0; i<lch; i++)
    {
        chars[i] = -1;
    }
    int K = 0;
    for (int i = 0; i<n; i++)
    {
        if (chars [ p[i][1]] == -1)
            K++;
        if (chars [ p[i][2]] == -1)
            K++;
        chars [ p[i][1]] = 0;
        chars [ p[i][2]] = 0;
    }
    
    bool change;
    char x, y;
    int M;
    for (int i = 0; i < n; i++)
    {
        change = false;
        for (int j = 0; j < n; j++)
        {
            x = p[j][1];
            y = p[j][2];
            M = max(chars[x] + 1, chars [y]);
            if (M > (K-1))
            {
                cout<<"Порядок противоречив";
                return 0;
            }
            if (chars[y] != M)
            {
                change = true;
            }
            chars[y] = M;
        }
        if (!change)
        {
            sort(chars, chars+lch);
            int previous = K;
            int i = lch-1;
            while (chars [i] > -1)
            {
                if (chars[i] == previous - 1)
                {
                    previous--;
                }
                else
                {
                    cout<<"порядок неполный";
                    return 0;
                }
                i--;
            }
            cout<<"полный порядок";
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm> //для использования функции sort

using namespace std;

int main()

{

const int lch = 256;

int n;

cin>>n;

char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.

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

{

p[i] = new char [2];

}

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

{

cin >> p[i][1]>>p[i][2];

}

int chars[lch];

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

{

chars[i] = -1;

}

int K = 0;

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

{

if (chars [ p[i][1]] == -1)

K++;

if (chars [ p[i][2]] == -1)

K++;

chars [ p[i][1]] = 0;

chars [ p[i][2]] = 0;

}

bool change;

char x, y;

int M;

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

{

change = false;

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

{

x = p[j][1];

y = p[j][2];

M = max(chars[x] + 1, chars [y]);

if (M > (K-1))

{

cout<<"Порядок противоречив";

return 0;

}

if (chars[y] != M)

{

change = true;

}

chars[y] = M;

}

if (!change)

{

sort(chars, chars+lch);

int previous = K;

int i = lch-1;

while (chars [i] > -1)

{

if (chars[i] == previous - 1)

{

previous--;

}

else

{

cout<<"порядок неполный";

return 0;

}

i--;

}

cout<<"полный порядок";

return 0;

}

return 0;

}

Решение

Общая идея решения

Эта часть решения взята отсюда.

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строки возможно несколько вариантов.

Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

Нам необходимо будет несколько раз просматривать все пары, поэтому их не получится обрабатывать поточно. Будем хранить их в отдельном двумерном массиве.

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив. Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

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

ссылка на код на ideone

ссылка на условие задачи

Related Images:

Интересная последовательность

22/09/2015 by Сплошнов Кирилл

Условие (OCPC-2015)

Дана последовательность из [latex]n[/latex] чисел: [latex]x_0[/latex], [latex]x_1[/latex], [latex]x_2, \ldots, x_{n-1}[/latex], где [latex]x_0[/latex] — кол-во чисел [latex]0[/latex] в данной последовательности, [latex]x_1[/latex] — кол-во чисел [latex]1[/latex], и так далее…

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

Число [latex]n[/latex] — количество членов последовательности.

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

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

Размышления над решением:

Обратим внимание, что сумма всех чисел данной последовательности является кол-вом используемых в ней чисел, что равно кол-ву членов последовательности. Иными словами, должно выполняться равенство:

[latex]x_0 + x_1 + [/latex]…[latex] + x_{n-1} = n[/latex] (1)

Далее заметим, что [latex]x_0[/latex] не может равняться нулю (ведь записав туда [latex]0[/latex], мы сразу же увеличиваем кол-во нулей до одного). Тогда [latex]x_0[/latex] равняется другому числу [latex]k[/latex], положим, большему чем 2. Тогда, [latex]x_k = 1[/latex].

Далее, положив [latex]x_1 = 2[/latex] и [latex]x_2 = 1[/latex], получаем последовательность, не нуждающуюся в дальнейших преобразованиях, в чем легко убедиться. Для наглядности:

Член последовательности	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	…	[latex]x_k[/latex]	…
Чему равен	k	2	1	0	1	0
Комментарий	[latex]k[/latex] будет найдено ниже	Количество чисел [latex]1[/latex] равно двум	Количество чисел [latex]2[/latex] равно одному	На этом промежутке только нули	[latex]k[/latex] больше двух	На этом промежутке только нули

Теперь вычислим [latex]k[/latex]. По формуле (1):

[latex]k + 2 + 1 + 1 = n[/latex]; [latex]k = n — 4[/latex]

(Примечание: При попытки подставить другие значения вместо [latex]x_1[/latex] или [latex]x_2[/latex] получится нестабильная последовательность, членам которой не получится присвоить значения согласно условию. Положив, например, [latex]x_1 = 3[/latex], нам придется увеличить кол-во единиц, что приведет к необходимости использовать другие числа последовательности, что в итоге обязательно приведет к нарушению необходимого условия (1) — сумма уже присвоенных ненулевых чисел попросту превысит количество ее оставшихся членов. Аналогично, если присвоить [latex]x_2 = 2[/latex], и уж тем более, при внесении более «крупных» изменений в последовательность. Таким образом, найденное решение является единственным.)

Очевидно, минимальное «рабочее» значение [latex]n[/latex] равно семи (при [latex]k = 2 + 1 = 3[/latex]).

Тесты (1) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]	[latex]x_6[/latex]	[latex]x_7[/latex]	[latex]x_8[/latex]	…
7	3	2	1	1	0	0	0
8	4	2	1	0	1	0	0	0
9	5	2	1	0	0	1	0	0	0
…	[latex]n — 4[/latex]	2	1	0	…	…	…	…	…	…

Для [latex]n[/latex] меньше семи, решение (или их отсутствие) было найдено подбором.

Тесты (2) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]
1	Решений нет
2	Решений нет
3	Решений нет
4	1 2	2 0	1 2	0 0
5	2	1	2	0	0
6	Решений нет

Теперь, зная алгоритм, можно написать программу, выполняющую необходимые действия.

Код данной программы :

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n < 4 || n == 6) // особые случаи (1)
		cout << "Решений нет" << endl;
	else if (n == 4) // особые случаи (2)
    {
        cout << "1 2 1 0" << endl;
        cout << "2 0 2 0" << endl;
    }
	else if (n == 5) // особый случай (3)
		cout << "2 1 2 0 0" << endl;
	else // алгоритм для общего случая
	{
		int number[n]; // создаем массив членов последовательности
		for (int i = 0; i < n; i++) // приравниваем все числа к нулю
			number[i] = 0;
		number[0] = n - 4; // выставляем значения для ненулевых членов
		number[1] = 2;
		number[2] = 1;
		number[n - 4] = 1;
		for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран
			cout << number[i] << " ";
		cout << endl; 
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n < 4 || n == 6) // особые случаи (1)

cout << "Решений нет" << endl;

else if (n == 4) // особые случаи (2)

{

cout << "1 2 1 0" << endl;

cout << "2 0 2 0" << endl;

}

else if (n == 5) // особый случай (3)

cout << "2 1 2 0 0" << endl;

else // алгоритм для общего случая

{

int number[n]; // создаем массив членов последовательности

for (int i = 0; i < n; i++) // приравниваем все числа к нулю

number[i] = 0;

number[0] = n - 4; // выставляем значения для ненулевых членов

number[1] = 2;

number[2] = 1;

number[n - 4] = 1;

for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран

cout << number[i] << " ";

cout << endl;

}

return 0;

}

Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:

Ideaone.com

Related Images:

Ю4.12

14/09/2015 by Сабиров Ильдар

Задача: Все ненулевые элементы матрицы [latex]D(k,l)[/latex] расположить в начале массива [latex]E(k \times l)[/latex] и подсчитать их количество.

K	L	Матрица D	Ненулевые элементы матрицы E	Количество ненулевых элементов
2	3	2 7 0 1 4 9	2 7 1 4 9	5
3	4	6 7 4 2 9 0 1 3 0 8 0 19	6 7 4 2 9 1 3 8 19	9
4	2	8 9 0 1 5 2 7 26	8 9 1 5 2 7 26	8

#include <iostream>
#include <stdlib.h>
#include <ctime>

using namespace std;
int main() {
    int K;
    int L;
    cin>>K;
    cin>>L;
    int M=K*L;
    int D[K][L];
    int E[M];
    int count = 0;
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < L; ++j) {
            cin>>D[i][j];
            if (D[i][j] != 0) {
                E[count++] = D[i][j];
                cout << D[i][j] << " "; 
            }
        }
    }
    cout << " количество ненулевых элементов матрицы E = " << count << endl;
    for (int u = 0; u < K; ++u) {
        for (int y = 0; y < L; ++y) {
            cout<<D[u][y]<<" ";
        }
        cout<<"\n";
    }
    return 0 ;
}

#include <iostream>

#include <stdlib.h>

#include <ctime>

using namespace std;

int main() {

int K;

int L;

cin>>K;

cin>>L;

int M=K*L;

int D[K][L];

int E[M];

int count = 0;

for (int i = 0; i < K; ++i) {

for (int j = 0; j < L; ++j) {

cin>>D[i][j];

if (D[i][j] != 0) {

E[count++] = D[i][j];

cout << D[i][j] << " ";

}

cout << " количество ненулевых элементов матрицы E = " << count << endl;

for (int u = 0; u < K; ++u) {

for (int y = 0; y < L; ++y) {

cout<<D[u][y]<<" ";

}

cout<<"\n";

}

return 0 ;

}

Заполняем матрицу с клавиатуры посредством циклов.
Выводим ненулевые элементы.
Выводим их количество.
Выводим матрицу D.

Ссылка на код

Related Images:

А404

29/06/2015 by Танащук Григорій Русланович

Задача:

Даны натуральные числа [latex]{i}, {j}[/latex], действительная матрица размера [latex]{18}\times{24}[/latex] [latex](1\leq i\leq j\leq 24)[/latex]. Поменять местами в матрице [latex]{i}[/latex]-й и [latex]{j}[/latex]-й столбцы.

Тест:

Вводим матрицу (размером [latex]{18}[/latex] — строк, [latex]{24}[/latex] — столбцов) в [latex]{input}[/latex], в следующей строке вписываем номера столбцов которые хотим поменять.

Пример:

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

Программа:

#include <iostream>
using namespace std;
 
void input(double a[18][24]){
	for(int i = 0; i < 18; i++){
		for(int j = 0; j < 24; j++){
			cin >> a[i][j];
		}
	}
}
void output(double a[18][24]){
	for(int i = 0; i < 18; i++){
		for(int j = 0; j < 24; j++){
			cout << a[i][j] <<((j == 23)? "\n": " ");
		}
	}
}
int main() {
	double a[18][24];
	input(a);
	int i , j;
	cin >> i >> j;
	for(int k = 0; k < 18; k++){
		swap(a[k][i-1], a[k][j-1]);
	}
	output(a);
	return 0;
}

#include <iostream>

using namespace std;

void input(double a[18][24]){

for(int i = 0; i < 18; i++){

for(int j = 0; j < 24; j++){

cin >> a[i][j];

}

void output(double a[18][24]){

for(int i = 0; i < 18; i++){

for(int j = 0; j < 24; j++){

cout << a[i][j] <<((j == 23)? "\n": " ");

}

int main() {

double a[18][24];

input(a);

int i , j;

cin >> i >> j;

for(int k = 0; k < 18; k++){

swap(a[k][i-1], a[k][j-1]);

}

output(a);

return 0;

}

Ввод самого массива;
Перевод строки после каждого 24 элемента;
Ограничение по вводу до 18 строк;
Замена местами обозначенных столбцов.
Ссылка на программу
P.S Хотел в тесте ввести матрицу красиво но [latex]{latex}[/latex] не воспринимал пробелы, пришлось бы вводить каждый элемент отдельно или же можно как то иначе.

Related Images:

Ю4.8

27/06/2015 by Танащук Григорій Русланович

Задача:

В массиве C(m) заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов.

Тест:

Количество элементов	Элементы	Результат
3	5 9 1	5 3 7
6	8 7 6 9 4 0	8 7 7,5 9 4,5 6,5
9	2 5 7 3 6 9 4 6	2 4,5 3,5 3 6 4,5 4 5,5 5

Программа:

#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double a[n];
	for(int i = 0; i < n ; ++i){
		cin >> a[i];
	}
	if(n >= 3){
		for(int i = 2; i < n; i+=3){
			double tmp = a[i - 1];
			a[i - 1] = (a[i] + a[i - 2])/2;
			a[i] = (tmp + a[i - 2])/2;
		}
		for(int i = 0; i < n ; ++i){
		cout << a[i] <<((i == n - 1)? "\n" : " ");
		}
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double a[n];

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

cin >> a[i];

}

if(n >= 3){

for(int i = 2; i < n; i+=3){

double tmp = a[i - 1];

a[i - 1] = (a[i] + a[i - 2])/2;

a[i] = (tmp + a[i - 2])/2;

}

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

cout << a[i] <<((i == n - 1)? "\n" : " ");

}

return 0;

}

Задаем массив;
Выбираем числа кратные трем;
Меняем каждый третий элемент начиная со второго;
Находим полусумму двух предыдущих элементов;
Берем число стоящее перед числом кратным трем;
Заменяем его на полусумму стоящих рядом элементов.
Ссылка на программу

Related Images:

e-olymp 1872. Снеговики

18/06/2015 by Карагяур Мілан Сергійович

Задача:

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий n (1 ≤ n ≤ 200000). В строке номер i+1 содержится описание действия:

t m — клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);
t 0 — клонировать снеговика номер t (0 ≤ t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия i, описанного в строке i+1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

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

Выведите суммарную массу построенных снеговиков.

Решение: Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2]. Указываем значение первого элемента равное 0 и нулевого элемента равного -1, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна 0, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно 0, то мы клонируем снеговика и добавляем ему шар массой m. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Задача на e-olymp.

Код:

#include <cstdlib>
#include <iostream>

using namespace std;
int main()
{
	
	int n;
	cin >> n;
	int a[n+1][2];
	
	int  count=0;
	a[count][1] = 0;
	a[count][0] = -1;
	count++;
	
	int t, m;
	long long sumr=0;
	
	for( int i=0 ; i<n ; i++ ){
		cin >> t >> m;
		if(m==0){
			a[count][1] = a[ a[t][0] ][1];
			a[count][0] = a[ a[t][0] ][0];
		}else{
			a[count][1] = a[t][1]+m;
			a[count][0] = t;
		}
		sumr+=a[count][1];
		count++;
	}
	cout << sumr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int a[n+1][2];

int count=0;

a[count][1] = 0;

a[count][0] = -1;

count++;

int t, m;

long long sumr=0;

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

cin >> t >> m;

if(m==0){

a[count][1] = a[ a[t][0] ][1];

a[count][0] = a[ a[t][0] ][0];

}else{

a[count][1] = a[t][1]+m;

a[count][0] = t;

}

sumr+=a[count][1];

count++;

}

cout << sumr << endl;

}

Тесты:

Input	Output
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74
4 0 3 1 2 2 1 1 1	18

Related Images:

А136о

30/01/2015 by Сабиров Ильдар

Даны натуральное число [latex]n,[/latex] действительные числа [latex]a_{1},\ldots,a_{n}[/latex].
Вычислить: [latex]\sqrt{10+a_{1}^{2}}+\ldots+\sqrt{10+a_{n}^{2}}[/latex]

n	[latex]a_{1}[/latex]	[latex]a_{2}[/latex]	[latex]a_{3}[/latex]	[latex]a_{4}[/latex]	[latex]a_{5}[/latex]	[latex]a_{6}[/latex]	sum	Комментарий
6	1	0.5	7	19	-9	8	51.6024	Пройден.
5	16	14.3	2	27	19	—	81.1426	Пройден.
2	61	-5	—	—	—	—	66.998	Пройден.
3	28.8	0.34	20.9	31.5	—	—	53.2915	Пройден.
1	-65.9242	—	—	—	—	—	66	Пройден.

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int i;
    int n;
    double sum=0;
    cin>>n;
    double a;
    for(i=1;i<=n;++i)
    {
        cin>>a;
        sum+=sqrt(10+a*a);
    }
    cout<<sum;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

int i;

int n;

double sum=0;

cin>>n;

double a;

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

{

cin>>a;

sum+=sqrt(10+a*a);

}

cout<<sum;

return 0;

}

Вводим числа( n, [latex]a_{1},\ldots,a_{k}.[/latex])
Подсчитываем указанную сумму([latex]\sqrt{10+a_{1}^{2}}[/latex]+…+[latex]\sqrt{10+a_{n}^{2}}.[/latex])
Выводим сумму.

Ссылка на код .

Related Images:

Ю4.15

21/12/2014 by Носуленко Марк

Заданы массивы [latex]A(n)[/latex] и [latex]B(m)[/latex]. Получить массив [latex]C(m+n)[/latex], расположив в начале его элементы массива [latex]A[/latex], а затем элементы массива [latex]B[/latex].

Из выше написанного ясно что нам нужно сделать. Все пояснения максимально детально расписаны в самом коде.

Тесты:

n	m	A[n]	B[m]	Результат:
3	4	0 1 2	5 7 8 4	A={0 1 2} B={5 7 8 4} C={0 1 2 5 7 8 4}
2	9	9 3.6	7.4 3.6 4.6666 7.99702 1 1 1 1 1	A={9 3.6} B={7.4 3.6 4.6666 7.99702 1 1 1 1 1} C={9 3.6 7.4 3.6 4.6666 7.99702 1 1 1 1 1}

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

int main() {
	int n,m; //Задаем размерность обоих массивов.
	cin >>n>>m; //Считываем их.
	double *A=new double [n]; //Выделяем память для 1-го массива.
	double *B=new double [m]; //Выделяем память для 2-го массива.
	double *C=new double [n+m]; //Выделяем память для массива, который объединит в себе 1-й и 2-й массивы.
	cout <<"A={";
	for(int i=0;i<n;++i){ //Заполняем 1-й масив и сразу выводим его.
		cin >>A[i];
		cout <<A[i];
		if(i<n-1)
			cout <<" ";
		else
			cout <<"}";
	}
	cout <<endl<<"B={";
	for(int j=0;j<m;++j){ //Заполняем 2-й масив и сразу выводим его.
		cin >>B[j];
		cout <<B[j];
		if(j<m-1)
			cout <<" ";
		else
			cout <<"}";
	}
	cout <<endl<<"C={";
	memcpy(C,A,n*sizeof (A[0])); //С помощью функции "memcpy"(из библиотеки string.h) копируем данные из 1-го массива(A) в массив(C). По условию задачи в массиве C сначала идут элементы массива A.
	//Задаем данные в функцию: "в какой массив","из какого массива", "размер массива"(размер типа одного элемента массива, умноженный на число элементов(n)).
    memcpy(C+n,B,m*sizeof (B[0])); //"C+n"-n первых элементов массива(C) уже скопированы из 1-го массива(A), оставшиеся m будут скопированы из 2-го массива(B).
    for(int k=0;k<n+m;++k){ 
    	cout <<C[k]; //Выводим массив(C) - объединение 1-го(A) и 2-го(B) массивов.
    	if(k<n+m-1)
    		cout <<" ";
    	else
    		cout <<"}";
    }
	return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main() {

int n,m; //Задаем размерность обоих массивов.

cin >>n>>m; //Считываем их.

double *A=new double [n]; //Выделяем память для 1-го массива.

double *B=new double [m]; //Выделяем память для 2-го массива.

double *C=new double [n+m]; //Выделяем память для массива, который объединит в себе 1-й и 2-й массивы.

cout <<"A={";

for(int i=0;i<n;++i){ //Заполняем 1-й масив и сразу выводим его.

cin >>A[i];

cout <<A[i];

if(i<n-1)

cout <<" ";

else

cout <<"}";

}

cout <<endl<<"B={";

for(int j=0;j<m;++j){ //Заполняем 2-й масив и сразу выводим его.

cin >>B[j];

cout <<B[j];

if(j<m-1)

cout <<" ";

else

cout <<"}";

}

cout <<endl<<"C={";

memcpy(C,A,n*sizeof (A[0])); //С помощью функции "memcpy"(из библиотеки string.h) копируем данные из 1-го массива(A) в массив(C). По условию задачи в массиве C сначала идут элементы массива A.

//Задаем данные в функцию: "в какой массив","из какого массива", "размер массива"(размер типа одного элемента массива, умноженный на число элементов(n)).

memcpy(C+n,B,m*sizeof (B[0])); //"C+n"-n первых элементов массива(C) уже скопированы из 1-го массива(A), оставшиеся m будут скопированы из 2-го массива(B).

for(int k=0;k<n+m;++k){

cout <<C[k]; //Выводим массив(C) - объединение 1-го(A) и 2-го(B) массивов.

if(k<n+m-1)

cout <<" ";

else

cout <<"}";

}

return 0;

}

Ссылка на код.

Related Images:

Ю4.3

26/11/2014 by Щебетовський Дмитро Геннадійович

Задача:

Центрирование массива. От каждого из заданных чисел x1, x2,…, xn отнять их среднее арифметическое.

xср= 1/m

E от m при i=1 (x1); xi= xi-xср; i=1,2,…, m

Результаты разместить на месте исходных данных.

Тесты:

Введите M (количество элементов в массиве)	Введите первое число	Введите следующее число	Результат	Вывод
2	2	5	-1 2	Тест пройден
2	1	2	0 1	Тест пройден
2	0	2	-1 1	Тест пройден
2	0	3	-1 2	Тест пройден
2	0	1	0 1	Тест пройден

Код:

    #include <iostream>
    using namespace std;
     
    int main()
    {
    	int m;
    	cout << "Введите M (количество элементов в массиве): ";
    	cin >> m;
    	int i; // счетчик цикла
    	int arr[100]; //массив не более 100 элементов
    	int sum = 0; // сумма чисел массива
    	cout << "Введите первое число: " ;
    	cin >> arr[1];
    	sum = arr[1];
    	for (i = 2; i <= m; i++) // цикл
    	{
    		cout << "Введите следующее число: " ;
    		cin >> arr[i];
    		sum = sum + arr[i];
    	}
    	cout << "Если вычесть из введённых вами чисел их среднее арифметическое, получим: " << endl;
     
    	for (int i = 1; i <=m; ++i) 
    	{
    		cout << arr[i] - (sum / m) << " ";
    	}
     
    	cout << endl;
     
     
    return 0;
    }

#include <iostream>

using namespace std;

int main()

{

int m;

cout << "Введите M (количество элементов в массиве): ";

cin >> m;

int i; // счетчик цикла

int arr[100]; //массив не более 100 элементов

int sum = 0; // сумма чисел массива

cout << "Введите первое число: " ;

cin >> arr[1];

sum = arr[1];

for (i = 2; i <= m; i++) // цикл

{

cout << "Введите следующее число: " ;

cin >> arr[i];

sum = sum + arr[i];

}

cout << "Если вычесть из введённых вами чисел их среднее арифметическое, получим: " << endl;

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

{

cout << arr[i] - (sum / m) << " ";

}

cout << endl;

return 0;

}

Решение:

объявляем массив m;

int i; // счетчик цикла

int arr[100]; //массив не более 100 элементов

int sum = 0; // сумма чисел массива

cout << «Введите первое число: »

Циклы и условия:

for (i = 2; i <= m; i++) // цикл

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

cout << arr[i] — (sum / m) << » «;

Код в ideone: http://ideone.com/vB6l0Y

Related Images:

А99

26/11/2014 by Щебетовський Дмитро Геннадійович

Задача: Пусть [latex]a_{1}=4[/latex], b1=v, an=2bk-1+ak-1. bk=2a^2k-1+bk-1, k=2,3…

Даны действительные u, v, натуральное n.

Найти Е от n при k=1 (ak*bk)/(k+1)!

Тесты:

N	U	V	Результат	Вывод
2	4	3	64	тест пройден
1	4	2	4	тест пройден
2	1	2	4	тест пройден
0	3	1	1	тест пройден
1	2	3	3	тест пройден

Код:

    #include <iostream>
    using namespace std;
     
    long int fact(int M)
    {
    	if (M == 0) //
    	return 1; // возвращаем факториал от нуля, это 1 =)
    	else // Во всех остальных случаях
    	return M * fact(M - 1); // делаем рекурсию.
    }
     
    int main()
    {
    	int n, u, v, a, b, t, sum;
    	cout << "Введите n: ";
    	cin >> n;
    	cout << "Введите u: ";
    	cin >> u;
    	cout << "Введите v: ";
    	cin >> v;
    	int k; // счетчик цикла
    	a = u;
    	b = v;
    	k = 1;
    	sum = a * b / fact(k + 1);
    	for (k = 2; k <= n; k++) // цикл
    	{
    		t = a;
    		a = 2*b + a;
    		b = 2 * t * t + b;
    		sum = sum + (a * b / fact(k + 1));
    	}
    	cout << "Сумма ряда равна: " << sum << endl;
    return 0;
    }

#include <iostream>

using namespace std;

long int fact(int M)

{

if (M == 0) //

return 1; // возвращаем факториал от нуля, это 1 =)

else // Во всех остальных случаях

return M * fact(M - 1); // делаем рекурсию.

}

int main()

{

int n, u, v, a, b, t, sum;

cout << "Введите n: ";

cin >> n;

cout << "Введите u: ";

cin >> u;

cout << "Введите v: ";

cin >> v;

int k; // счетчик цикла

a = u;

b = v;

k = 1;

sum = a * b / fact(k + 1);

for (k = 2; k <= n; k++) // цикл

{

t = a;

a = 2*b + a;

b = 2 * t * t + b;

sum = sum + (a * b / fact(k + 1));

}

cout << "Сумма ряда равна: " << sum << endl;

return 0;

}

Решение:
if (M == 0) // массив
return 1; // возвращаем факториал от нуля, это 1
else // Во всех остальных случаях
return M * fact(M — 1); // делаем рекурсию.

Пишем условия и формулы:

sum = a * b / fact(k + 1);
for (k = 2; k <= n; k++) // цикл

Цикл:
t = a;
a = 2*b + a;
b = 2 * t * t + b;
sum = sum + (a * b / fact(k + 1));

код задачи в ideone: http://ideone.com/1fNmWc

Related Images:

А407

26/11/2014 by Бронфен-Бова Роман

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm	r	Матрица	Результат	Комментарий
2х2	2.5	[latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]	3.5	Пройдено
3×4	3.14	[latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]	70.1	Пройдено
2×4	2.71	[latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]	27.1	Пройдено

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

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int n,m; scanf("%d %d",&n,&m);
	double r; scanf("%lf",&r);
	double a[n][m];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%lf", &a[i][j]);
	double sum = 0;
	for(int i = 0; i < n; i++) {
		double b = 0.5;
		for(int j = 0; j < m; j++)
			if(a[i][j]>0) {
				b = a[i][j];
				break;
			}
		sum += b*pow(r,n-i-1);
	}
	printf("%lf",sum);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n,m; scanf("%d %d",&n,&m);

double r; scanf("%lf",&r);

double a[n][m];

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

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

scanf("%lf", &a[i][j]);

double sum = 0;

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

double b = 0.5;

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

if(a[i][j]>0) {

b = a[i][j];

break;

}

sum += b*pow(r,n-i-1);

}

printf("%lf",sum);

return 0;

}

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

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

class Main
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		double r = sc.nextDouble();
		double[][] a = new double[n][m];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				a[i][j] = sc.nextDouble();
			}
		}
		double sum = 0;
		for(int i = 0; i < n; i++){
			double b = 0.5;
			for(int j = 0; j < m; j++){
				if(a[i][j] > 0){
					b = a[i][j];
					break;
				}
			}
			sum += b*Math.pow(r, n-i-1);
		}
		System.out.println(sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

double r = sc.nextDouble();

double[][] a = new double[n][m];

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

for(int j = 0; j < m; j++){

a[i][j] = sc.nextDouble();

}

double sum = 0;

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

double b = 0.5;

for(int j = 0; j < m; j++){

if(a[i][j] > 0){

b = a[i][j];

break;

}

sum += b*Math.pow(r, n-i-1);

}

System.out.println(sum);

}

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке, брать 0.5. В конце вывести результат.

Related Images:

Ю 4.37

23/11/2014 by Байков Дмитро

Задача

Автостоп-2. Из пункта А в пункт В, между которыми [latex]s[/latex] км, выехал велосипедист с постоянной скоростью [latex]v_{0}[/latex] км/ч. Навстречу ему — из пункта В — другой путешественник решил добраться «автостопом» — на разных видах попутного транспорта. Перед каждым участком он [latex]\tau _{i}[/latex] минут «голосует», ожидая попутного транспорта, затем движется [latex]t _{i}[/latex] часов со скоростью [latex]v _{i}[/latex] км/час ( величины [latex]\tau _{i}, t _{i}, v _{i}, i=1,2,\ldots,n[/latex] заданы в соответствующих массивах). Через какое время после старта и на каком расстоянии от пункта А путники встретятся?

Тесты

s	[latex]v_{0}[/latex]	n	[latex]\tau _{i}[/latex]	[latex]t _{i}[/latex]	[latex]v _{i}[/latex]	place, км	time, ч	Комментарий
100.0	30.0	1	60.0	1.0	40.0	60.0	2.0	Пройден
100.0	10.0	1	0.0	1.0	40.0	Путники не доехали до места встречи		Не пройден
130.0	15.0	2	0.0 3.0	1.0 2.6	40.0 33.3	2.587267	38.809006	Пройден

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

#include <iostream>
using namespace std;

int main() 
{
	int n; cin >> n;
	double  place, time, wait [n], mov [n], speed [n], s, v0, timee = 0.0, 
	delta, ss = 0.0, dist = 0.0;
	cin >> s; cin >> v0;
	for (int i = 0 ; i < n; i++)
	{
		cin >> wait[i];
		wait[i] /= 60;
	}
	for (int i = 0 ; i < n; i++)
	{
		cin >> mov[i];
	}
	for (int i = 0 ; i < n; i++)
	{
		cin >> speed[i];
	}
	
	for (int i = 0 ; i < n; i++)
	{
		delta = v0 * wait[i] ;
		timee += wait[i] ;
		if ( s <= delta ) 
		{
			time = s / v0; 
			place = s;
			printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);
			break;
		}
		ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];
		if (ss >= s )
		{
			time = ( s - dist - delta ) / ( v0 + speed[i]) + timee ;  
			place = time * v0 ; 
			printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);
			break;
		} 
		else
		{
			dist = ss;
		}
		timee += mov[i];
	}
	if ( ss < s ) printf("Путники не доехали до места встречи"); 
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n; cin >> n;

double place, time, wait [n], mov [n], speed [n], s, v0, timee = 0.0,

delta, ss = 0.0, dist = 0.0;

cin >> s; cin >> v0;

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

{

cin >> wait[i];

wait[i] /= 60;

}

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

{

cin >> mov[i];

}

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

{

cin >> speed[i];

}

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

{

delta = v0 * wait[i] ;

timee += wait[i] ;

if ( s <= delta )

{

time = s / v0;

place = s;

printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);

break;

}

ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];

if (ss >= s )

{

time = ( s - dist - delta ) / ( v0 + speed[i]) + timee ;

place = time * v0 ;

printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);

break;

}

else

{

dist = ss;

}

timee += mov[i];

}

if ( ss < s ) printf("Путники не доехали до места встречи");

return 0;

}

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

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

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

Код на Java

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

class Hitchhiking
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		double  place, time, delta, timee = 0.0, ss = 0.0, dist = 0.0;
		double[] wait = new double[n], mov = new double[n], speed = new double[n];
		double s = in.nextDouble();
		double v0 = in.nextDouble();
		for (int i = 0; i < n; i++)
			wait[i] = in.nextDouble() / 60;
		for (int i = 0; i < n; i++)
			mov[i] = in.nextDouble();
		for (int i = 0; i < n; i++)
			speed[i] = in.nextDouble();
		for (int i = 0; i < n; i++)
		{
			delta = v0 * wait[i] ;
			timee += wait[i] ;
			if (s <= delta) 
			{
				time = s / v0; 
				place = s;
				System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");
				break;
			}
			ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];
			if (ss >= s)
			{
				time = (s - dist - delta) / (v0 + speed[i]) + timee;  
				place = time * v0 ; 
				System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");
				break;
			} 
			else
			{
				dist = ss;
			}
			timee += mov[i];
		}
		if (ss < s) System.out.printf("Путники не доехали до места встречи"); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Hitchhiking

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double place, time, delta, timee = 0.0, ss = 0.0, dist = 0.0;

double[] wait = new double[n], mov = new double[n], speed = new double[n];

double s = in.nextDouble();

double v0 = in.nextDouble();

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

wait[i] = in.nextDouble() / 60;

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

mov[i] = in.nextDouble();

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

speed[i] = in.nextDouble();

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

{

delta = v0 * wait[i] ;

timee += wait[i] ;

if (s <= delta)

{

time = s / v0;

place = s;

System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");

break;

}

ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];

if (ss >= s)

{

time = (s - dist - delta) / (v0 + speed[i]) + timee;

place = time * v0 ;

System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");

break;

}

else

{

dist = ss;

}

timee += mov[i];

}

if (ss < s) System.out.printf("Путники не доехали до места встречи");

}

Related Images:

Ю4.7

03/11/2014 by Фесенко Катерина Володимирівна

Задача. В матрице [latex] z(n,n)[/latex] каждый элемент разделить на диагональный, стоящий в том же столбце.

Тест

при [latex] n=3[/latex] (элементы главной диагонали выделены )

5	4	9
3	1	7
8	6	2

↓

1	4	4.5
0.6	1	3.5
1.6	6	1

Проверим совсем простой вариант, для наглядности:

при [latex] n=2[/latex]

4	5
2	10

↓

1	0.5
0.5	1

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

#include <iostream>
# include <math.h>
using namespace std;


int main() {
	int n;
	cin >> n;
	double z[n][n], c;
	
	// Ввод матрицы z
	for( int i = 0; i < n; i++)
	{
		for( int j = 0; j < n; j++)
		{
			cin >> z[i][j];
		}
	}
			
		
		// Вывод матрицы z
		for (int  j = 0; j < n; j++)
    	{
			c = z[j][j];
			for (int i = 0; i < n; i++)
			{
				z[i][j] = z [i][j] / c;
				cout << z[i][j] << " ";
			}
			cout << endl;
		}
	
	return 0;
 }

#include <iostream>

# include <math.h>

using namespace std;

int main() {

int n;

cin >> n;

double z[n][n], c;

// Ввод матрицы z

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

{

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

{

cin >> z[i][j];

}

// Вывод матрицы z

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

{

c = z[j][j];

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

{

z[i][j] = z [i][j] / c;

cout << z[i][j] << " ";

}

cout << endl;

}

return 0;

}

Ссылка на программу: http://ideone.com/ecqIxL

Решение:

Вводим квадратную матрицу [latex] z(n,n)[/latex].Потом описываем элемент, который будет делиться диагональным:

for( int i = 0; i < n; i++)
	{
		for( int j = 0; j < n; j++)
		{
			cin >> z[i][j];
		}
	}

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

{

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

{

cin >> z[i][j];

}

Следующим шагом будет описание диагонального элемента во вложенном цикле, который определяет элемент в столбце и непосредственно деление диагонального элемента на элемента, стоящий в том же столбце.

for (int  j = 0; j < n; j++)
    	{
			c = z[j][j];
			for (int i = 0; i < n; i++)
			{
				z[i][j] = z [i][j] / c;
				cout << z[i][j] << " ";
			}
			cout << endl;
		}

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

{

c = z[j][j];

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

{

z[i][j] = z [i][j] / c;

cout << z[i][j] << " ";

}

cout << endl;

}

Выводим значение полученной матрицы.

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) {
		int n;
		double c;
	    Scanner sc = new Scanner (System.in);
		n = sc.nextInt();	
		double[][] z = new double [n][n];
	for( int i = 0; i < n; i++)
	{
		for( int j = 0; j < n; j++)
		{
		 	z[i][j] = sc.nextInt();
		}
	}	
	for (int  j = 0; j < n; j++)
    	{
    		System.out.println();
			c = z[j][j];
			for (int i = 0; i < n; i++)
			{
				z[i][j] = z [i][j] / c;
				System.out.print(z[i][j]+" ");
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) {

int n;

double c;

Scanner sc = new Scanner (System.in);

n = sc.nextInt();

double[][] z = new double [n][n];

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

{

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

{

z[i][j] = sc.nextInt();

}

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

{

System.out.println();

c = z[j][j];

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

{

z[i][j] = z [i][j] / c;

System.out.print(z[i][j]+" ");

}

Ссылка на программу: http://ideone.com/dT5GVl

Related Images:

e-olimp 2392. Интересная сумма

27/10/2014 by Ілларіонова Марія Валеріївна

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

Дано трёхзначное натуральное число [latex]N[/latex]. Определить сумму наибольшего и наименьшего трёхзначных чисел, которые могут быть образованы из числа [latex]N[/latex] перестановкой цифр.

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

Натуральное число [latex]N[/latex] [latex]\left(100\leq N\leq 999 \right)[/latex].

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

Ответ к задаче.

Пройденные тесты (C++).

Java.

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

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

int main() {
	int N, b[3], c[3];
	cin >> N;
	for (int i=0; i<3; i++) {
		b[i]=N%10; c[i]=N%10;
		N=N/10;
	}
	sort(b,b+3);
	sort(c,c+3); reverse (c,c+3);
	if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);
	else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);
	int b1=100*b[0]+10*b[1]+b[2];
	int c1=100*c[0]+10*c[1]+c[2];
	cout << b1+c1 << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int N, b[3], c[3];

cin >> N;

for (int i=0; i<3; i++) {

b[i]=N%10; c[i]=N%10;

N=N/10;

}

sort(b,b+3);

sort(c,c+3); reverse (c,c+3);

if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);

else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

cout << b1+c1 << endl;

return 0;

}

Java:

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

class Main
{
	public static void swap (int []a, int i, int j) {
		int tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}
	public static void main (String[] args)
	{
		int N;
		int []b = new int [3];
		int []c = new int [3];
		Scanner in = new Scanner (System.in);
		N=in.nextInt();
		for (int i=0; i<3; i++) {
			b[i]=N%10; 
			c[i]=N%10;
			N/=10;
		}
		Arrays.sort(b);
		Arrays.sort(c);
		swap (c,0,2);
		if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);
		else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);
		int b1=100*b[0]+10*b[1]+b[2];
		int c1=100*c[0]+10*c[1]+c[2];
		System.out.println (b1+c1);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap (int []a, int i, int j) {

int tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

public static void main (String[] args)

{

int N;

int []b = new int [3];

int []c = new int [3];

Scanner in = new Scanner (System.in);

N=in.nextInt();

for (int i=0; i<3; i++) {

b[i]=N%10;

c[i]=N%10;

N/=10;

}

Arrays.sort(b);

Arrays.sort(c);

swap (c,0,2);

if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);

else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

System.out.println (b1+c1);

}

Когда я увидела эту задачу, то мне в голову сразу пришло решение с применением массивов. Изначально пользователю предлагается ввести трёхзначное число, которое я впоследствии раскладываю на отдельные элементы массивов, один из которых определяет минимальное трёхзначное число, а второй, в свою очередь, — максимальное.

Затем я сортирую первый массив по возрастанию, а второй по убыванию.

Далее проблема возникает именно с первым массивом, так как его первым элементом может оказаться 0, что нам не подходит, так как наше минимальное число, образованное перестановкой, обязано быть трёхзначным по условию. Для этого я делаю 2 несложных проверки, в результате которых первый элемент массива меняется местами либо со вторым, либо с третьим.

После чего я перевожу элементы массива в одно трёхзначное число и наконец-то получаю сумму.

Сложность задачи 66%.

Related Images:

Ю4.29

27/10/2014 by Зелінський Вячеслав Олександрович

Текущий минимум. Каждый из элементов [latex] t_{i}[/latex] массива [latex]T(m)[/latex] заменить минимальным среди первых [latex]i[/latex] элементов этого массива.

[latex]m[/latex]	[latex]t_{1}, t_{2},\ldots,t_{i}[/latex]	Результат:
6	9 7 8 5 14 1	9 7 7 5 5 1
5	3 -2 5 -3 8	3 -2 -2 -3 -3
4	12 0 4 -7	12 0 0 -7

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

#include <iostream>
using namespace std;
 
int main() {
	int m;	//Переменная определяющая количество элементов массива.
	cin >> m;   // Чтение из стандартного потока.
	int T[m];    // Описание массива.
    cin>>T[0];  // Чтение из стандартного потока.
    int min=T[0];
	for(int i=1; i<m; i++) { 		
        cin >> T[i];   // Чтение из стандартного потока.
		if(T[i]<min) {
		      min=T[i];
		}
		T[i]=min;
	}
	for(int i=0; i<m; i++) {
		cout<<T[i]<<endl;	
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m; //Переменная определяющая количество элементов массива.

cin >> m; // Чтение из стандартного потока.

int T[m]; // Описание массива.

cin>>T[0]; // Чтение из стандартного потока.

int min=T[0];

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

cin >> T[i]; // Чтение из стандартного потока.

if(T[i]<min) {

min=T[i];

}

T[i]=min;

}

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

cout<<T[i]<<endl;

}

return 0;

}

По условию задачи необходимо выводить текущий минимум введенных элементов массива.
Для этого опишем количество элементов, которое вводится с клавиатуры (так как это целое число, оно имеет тип «int»). Затем описав массив, считываем первый элемент массива и присваиваем переменной минимум его значение. После необходимо создать цикл для ввода остальных элементов массива. При условии, что текущий элемент меньше предыдущего, переприсваиваем минимум. Все элементы массива заменяем минимальным. Остается только вывести все текущие минимумы.
Для проверки работы программы можно воспользоваться объектом.

Код на 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 m;	
		m = in.nextInt(); 
		int []T = new int[m];
		   
	    T[0] = in.nextInt(); 
	    int min=T[0];
		for(int i=1; i<m; i++) { 		
	        T[i] = in.nextInt();  
			if(T[i]<min) {
			      min=T[i];
			}
			T[i]=min;
		}
		for(int i=0; i<m; i++) {
			System.out.println(T[i]);
		}
	}
}

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 m;

m = in.nextInt();

int []T = new int[m];

T[0] = in.nextInt();

int min=T[0];

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

T[i] = in.nextInt();

if(T[i]<min) {

min=T[i];

}

T[i]=min;

}

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

System.out.println(T[i]);

}

Related Images:

Ю4.25

27/10/2014 by Карагяур Мілан Сергійович

Задача: Заполнить матрицу заданного размера [latex]M(k,l)[/latex] числами 1,2,3,4 так, чтобы по горизонтали, вертикали и диагонали не было одинаковых рядом стоящих чисел.

[latex]k[/latex]	[latex]l[/latex]	Output
6	6	1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5	5	1 2 3 4 1 3 4 1 2 3 1 2 3 4 1 3 4 1 2 3 1 2 3 4 1

#include <iostream>
using namespace std;

int main() {
	int k, l;
	cin >> k >> l;
	int a[k][l];

	for(int i = 0; i < k; i++) {
		for(int j = 0; j < l; j++) {
			a[i][j] = (j + 2 * (i % 2)) % 4 + 1;
			cout << a[i][j] << " ";
		}  
		cout << "\n";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int k, l;

cin >> k >> l;

int a[k][l];

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

for(int j = 0; j < l; j++) {

a[i][j] = (j + 2 * (i % 2)) % 4 + 1;

cout << a[i][j] << " ";

}

cout << "\n";

}

return 0;

}

Код на Ideone.

Заполняем массив с помощью формулы (j + 2 * (i % 2)) % 4 + 1. При i четном 2 * (i % 2) будет обращаться в 0. То есть в нечетных строках будут числа 1, 2, 3, 4 подряд, а в четных строках будут меняться цифры 1 на 3, 2 на 4, 3 на 1, 4 на 2.

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

class Main {
	public static void main (String[] s) throws java.lang.Exception {
		java.util.Scanner in = new java.util.Scanner(System.in);
		int k = in.nextInt();
		int l = in.nextInt();  
		int[][]a = new int[k][l];
		for(int i = 0; i < k; i++) {
			for(int j = 0; j < l; j++) {
				a[i][j] = (j + 2 * (i % 2)) % 4 + 1;
				System.out.print(a[i][j]);
				System.out.print(" ");
			}  
			System.out.print("\n");
		}
	}
}

class Main {

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

java.util.Scanner in = new java.util.Scanner(System.in);

int k = in.nextInt();

int l = in.nextInt();

int[][]a = new int[k][l];

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

for(int j = 0; j < l; j++) {

a[i][j] = (j + 2 * (i % 2)) % 4 + 1;

System.out.print(a[i][j]);

System.out.print(" ");

}

System.out.print("\n");

}

Код на Ideone.

Related Images:

Ю11.16

24/10/2014 by Іванов Вячеслав Володимирович

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex] где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:

Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex]	[latex]A[/latex]	[latex]A^{-1}[/latex]	Результат
3	1 2 3 5 5 7 11 13 7	-0.964771 0.430661 -0.017183 0.723533 -0.447973 0.137884 0.172358 0.155200 -0.086211	Пройден
2	1 2 2 1	-0.333067 0.666400 0.666400 -0.333067	Пройден
5	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	Пройден
3	1 2 3 4 5 6 7 8 9	Матрица вырождена	Пройден

Программный код:

#include <cstdio>
#include <algorithm>
#include <cmath>
//очистить выделенную память
void clear(double **arr, int n)
{
    for(int i = 0; i < n; i++)
        delete[] arr[i];
    delete[] arr;
}
//создать копию массива
double** clone(double **arr, int n)
{
    double **newArr = new double*[n];
    for(int row = 0; row < n; row++)
    {
        newArr[row] = new double[n];
        for(int col = 0; col < n; col++)
            newArr[row][col] = arr[row][col];
    }
    return newArr;
}
//print the matrix
void show(double **matrix, int n)
{
    for(int row = 0; row < n; row++){
            for(int col = 0; col < n; col++)
                printf("%lf\t", matrix[row][col]);
            printf("\n");
    }
    printf("\n");
}
//матричное умножение матриц
double** matrix_multi(double **A, double **B, int n)
{
    double **result = new double*[n];
    //заполнение нулями
    for(int row = 0; row < n; row++){
        result[row] = new double[n];
        for(int col = 0; col < n; col++){
            result[row][col] = 0;
        }
    }

    for(int row = 0; row < n; row++){
        for(int col = 0; col < n; col++){
            for(int j = 0; j < n; j++){
                result[row][col] += A[row][j] * B[j][col];
            }
        }
    }
    return result;
}
//умножение матрицы на число
void scalar_multi(double **m, int n, double a){
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++){
            m[row][col] *= a;
        }
}
//вычисление суммы двух квадратных матриц
void sum(double **A, double **B, int n)
{
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++)
            A[row][col] += B[row][col];
}

//вычисление определителя
double det(double **matrix, int n) //квадратная матрица размера n*n
{
    double **B = clone(matrix, n);
    //приведение матрицы к верхнетреугольному виду
    for(int step = 0; step < n - 1; step++)
        for(int row = step + 1; row < n; row++)
        {
            double coeff = -B[row][step] / B[step][step]; //метод Гаусса
            for(int col = step; col < n; col++)
                B[row][col] += B[step][col] * coeff;
        }
    //Рассчитать определитель как произведение элементов главной диагонали
    double Det = 1;
    for(int i = 0; i < n; i++)
        Det *= B[i][i];
    //Очистить память
    clear(B, n);
    return Det;
}

int main()
{
    //Исходная матрица, динамический двухмерный массив
    int n; scanf("%d", &n);
    double **A = new double*[n];
    for(int row = 0; row < n; row++)
    {
        A[row] = new double[n];
            for(int col = 0; col < n; col++)
                scanf("%lf", &A[row][col]);
    }

    /* Численное вычисление обратной матрицы по методу Ньютона-Шульца
        1. Записать начальное приближение [Pan, Schreiber]:
            1) Транспонировать данную матрицу
            2) Нормировать по столбцам и строкам
        2. Повторять процесс до достижения заданной точности.
    */

    double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам
    double **A0 = clone(A, n);       //инициализация начального приближения
    for(size_t row = 0; row < n; row++){
        double colsum = 0, rowsum = 0;
        for(size_t col = 0; col < n; col++){
            rowsum += fabs(A0[row][col]);
            colsum += fabs(A0[col][row]);
        }
        N1 = std::max(colsum, N1);
        Ninf = std::max(rowsum, Ninf);
    }
    //транспонирование
    for(size_t row = 0; row < n - 1; row++){
        for(size_t col = row + 1; col < n; col++)
            std::swap(A0[col][row], A0[row][col]);
    }
    scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы
    //инициализация удвоенной единичной матрицы нужного размера
    double **E2 = new double*[n];
    for(int row = 0; row < n; row++)
    {
        E2[row] = new double[n];
            for(int col = 0; col < n; col++){
                if(row == col)
                    E2[row][col] = 2;
                else
                    E2[row][col] = 0;
            }
    }
    double **inv = clone(A0, n); //A_{0}
    double EPS = 0.001;   //погрешность
    if(det(A, n) != 0){ //если матрица не вырождена
        while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS
        {
            double **prev = clone(inv, n); //A[k-1]
            inv = matrix_multi(A, prev, n);   //A.(A[k-1]^(-1))
            scalar_multi(inv, n, -1);         //-A.(A[k-1]^(-1))
            sum(inv, E2, n);                   //2E - A.(A[k-1]^(-1))
            inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))
            clear(prev, n);
        }
        //вывод матрицы на экран
        show(inv, n);
    }
    else
        printf("Impossible\n");
    clear(A, n);
    clear(E2, 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

156

157

158

#include <cstdio>

#include <algorithm>

#include <cmath>

//очистить выделенную память

void clear(double **arr, int n)

{

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

delete[] arr[i];

delete[] arr;

}

//создать копию массива

double** clone(double **arr, int n)

{

double **newArr = new double*[n];

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

{

newArr[row] = new double[n];

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

newArr[row][col] = arr[row][col];

}

return newArr;

}

//print the matrix

void show(double **matrix, int n)

{

for(int row = 0; row < n; row++){

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

printf("%lf\t", matrix[row][col]);

printf("\n");

}

printf("\n");

}

//матричное умножение матриц

double** matrix_multi(double **A, double **B, int n)

{

double **result = new double*[n];

//заполнение нулями

for(int row = 0; row < n; row++){

result[row] = new double[n];

for(int col = 0; col < n; col++){

result[row][col] = 0;

}

for(int row = 0; row < n; row++){

for(int col = 0; col < n; col++){

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

result[row][col] += A[row][j] * B[j][col];

}

return result;

}

//умножение матрицы на число

void scalar_multi(double **m, int n, double a){

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

for(int col = 0; col < n; col++){

m[row][col] *= a;

}

//вычисление суммы двух квадратных матриц

void sum(double **A, double **B, int n)

{

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

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

A[row][col] += B[row][col];

}

//вычисление определителя

double det(double **matrix, int n) //квадратная матрица размера n*n

{

double **B = clone(matrix, n);

//приведение матрицы к верхнетреугольному виду

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

for(int row = step + 1; row < n; row++)

{

double coeff = -B[row][step] / B[step][step]; //метод Гаусса

for(int col = step; col < n; col++)

B[row][col] += B[step][col] * coeff;

}

//Рассчитать определитель как произведение элементов главной диагонали

double Det = 1;

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

Det *= B[i][i];

//Очистить память

clear(B, n);

return Det;

}

int main()

{

//Исходная матрица, динамический двухмерный массив

int n; scanf("%d", &n);

double **A = new double*[n];

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

{

A[row] = new double[n];

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

scanf("%lf", &A[row][col]);

}

/* Численное вычисление обратной матрицы по методу Ньютона-Шульца

1. Записать начальное приближение [Pan, Schreiber]:

1) Транспонировать данную матрицу

2) Нормировать по столбцам и строкам

2. Повторять процесс до достижения заданной точности.

double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам

double **A0 = clone(A, n); //инициализация начального приближения

for(size_t row = 0; row < n; row++){

double colsum = 0, rowsum = 0;

for(size_t col = 0; col < n; col++){

rowsum += fabs(A0[row][col]);

colsum += fabs(A0[col][row]);

}

N1 = std::max(colsum, N1);

Ninf = std::max(rowsum, Ninf);

}

//транспонирование

for(size_t row = 0; row < n - 1; row++){

for(size_t col = row + 1; col < n; col++)

std::swap(A0[col][row], A0[row][col]);

}

scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы

//инициализация удвоенной единичной матрицы нужного размера

double **E2 = new double*[n];

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

{

E2[row] = new double[n];

for(int col = 0; col < n; col++){

if(row == col)

E2[row][col] = 2;

else

E2[row][col] = 0;

}

double **inv = clone(A0, n); //A_{0}

double EPS = 0.001; //погрешность

if(det(A, n) != 0){ //если матрица не вырождена

while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS

{

double **prev = clone(inv, n); //A[k-1]

inv = matrix_multi(A, prev, n); //A.(A[k-1]^(-1))

scalar_multi(inv, n, -1); //-A.(A[k-1]^(-1))

sum(inv, E2, n); //2E - A.(A[k-1]^(-1))

inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))

clear(prev, n);

}

//вывод матрицы на экран

show(inv, n);

}

else

printf("Impossible\n");

clear(A, n);

clear(E2, n);

return 0;

}

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

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

Инициализация динамического двухмерного массива и передача его в функцию.
Вычисление определителя матрицы (с применением метода Гаусса).
Вычисление нормы матрицы.
Транспонирование матрицы.
Умножение матрицы на скаляр.
Матричное умножение матриц.
Сложение двух матриц.
Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
Вычисление определителя можно разбить на два последовательных шага:
1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
2. Вычисление определителя как произведения элементов главной диагонали.
Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
При транспонировании обмениваются местами элементы, симметричные главной диагонали.
При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().

Related Images:

Ю4.13

22/10/2014 by Осецимський Анатолій Вадимович

Задача. Дан массив [latex]A(n)[/latex]. Все положительные его элементы поместить в начало массива [latex]B(n)[/latex], а отрицательные элементы- в начало массива [latex]C(n)[/latex]. Подсчитать количество тех и других.

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

-1

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

#include <iostream>
using namespace std;

int main() {
    int n=0,otr=0,pol=0;
    scanf("%d",&n);//размеры массива
    double A[n],B[n],C[n];//создаем три массива
    for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки
    {
        cin >> A[i];
        A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С
    }
	cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n=0,otr=0,pol=0;

scanf("%d",&n);//размеры массива

double A[n],B[n],C[n];//создаем три массива

for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки

{

cin >> A[i];

A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С

}

cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел

return 0;

}

Заводим счетчик для отрицательных и положительных чисел,а также переменную для количества элементов массива типа [latex]int[/latex]. Читаем количество элементов и создаем три массива типа [latex]double[/latex](вдруг нам буду вводить действительные числа). В цикле читаем элемент [latex]A[i][/latex] и условием определяем положительное число или нет, и увеличиваем соответствующий счетчик. Выводим полученные результаты.

Ссылка на программу.

Java

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), p = 0, o = 0;
		int[] A = new int[n], B = new int[n], C = new int[n];
		for(int i = 0; i < n; i++){
			A[i] = in.nextInt();
			if(A[i] >= 0) B[p++] = A[i]; else C[o++] = A[i];
		}
		System.out.println("Positive:"+p + " Negative:"+o);
	}
}