Category Archives: 5. Массивы

Задачи на использование классических массивов и работе с ними через указатели и ссылочные типы.

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

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

cin >> x[i];

// Processing

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

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Санта Клаус
Кубики — 3 — используйте массив bool для хранения предположений о потери кубика для каждой из 26+26=52 букв.
Прямоугольник — используйте массив точек.

Опубликованные решения

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

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:

А290

08/11/2016 by Сабиров Ильдар

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n	[latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex]	[latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex]	Комментарий
4	1 4 -3 8 3 -2 -4 2	2 4 -2.5 5 2 4 -3.5 5	Пройдено
5	0 -0.5 4 -9 0.35 0 -0.5 11 0.247 1.650	0 0 7.5 81 1 0 0 7.5 0.247 1	Пройдено
3	0 3 -0.14942 -3 0 793	0 1.5 0.0223263 9 1.5 793	Пройдено

Реализация (массив структур)

#include <iostream>
using namespace std;
struct okay {
    double a,b;
};
int main() {
    int numb;
    cin>>numb;
    okay x[numb];
    for(int i=0;i<numb;i++){
        cin>>x[i].a;
    }
    for(int i=0;i<numb;i++){
        cin>>x[i].b;
    }
    for(int i=0;i<numb;i++){
        if(x[i].a<0 && x[i].b<0){
            x[i].a=x[i].a+0.5;
            x[i].b=x[i].b+0.5;
        }
        else if(x[i].a<0 && x[i].b>=0){
            x[i].a=x[i].a*x[i].a;
        }
        else if(x[i].a>=0 && x[i].b<0){
            x[i].b=x[i].b*x[i].b;
        }
        else {
            x[i].a=(x[i].a+x[i].b)/2;
            x[i].b=x[i].a;
        }
    }
    for(int i=0;i<numb;i++){
        cout<<x[i].a<<" ";
    }
    cout<<endl;
    for(int i=0;i<numb;i++){
        cout<<x[i].b<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct okay {

double a,b;

};

int main() {

int numb;

cin>>numb;

okay x[numb];

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

cin>>x[i].a;

}

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

cin>>x[i].b;

}

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

if(x[i].a<0 && x[i].b<0){

x[i].a=x[i].a+0.5;

x[i].b=x[i].b+0.5;

}

else if(x[i].a<0 && x[i].b>=0){

x[i].a=x[i].a*x[i].a;

}

else if(x[i].a>=0 && x[i].b<0){

x[i].b=x[i].b*x[i].b;

}

else {

x[i].a=(x[i].a+x[i].b)/2;

x[i].b=x[i].a;

}

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

cout<<x[i].a<<" ";

}

cout<<endl;

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

cout<<x[i].b<<" ";

}

return 0;

}

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

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

int main() {
    double a,b;
    vector<double> c;
    vector<double> d;
    while(cin>>a && cin>>b){
        c.push_back(a);
        d.push_back(b);
    }
    for(int i=0;i<c.size();i++){
        if(c[i]<0 && d[i]<0){
            c[i]=c[i]+0.5;
            d[i]=d[i]+0.5;
        }
        else if(c[i]<0 && d[i]>=0){
            c[i]=c[i]*c[i];
        }
        else if(c[i]>=0 && d[i]<0){
            d[i]=d[i]*d[i];
        }
        else {
            c[i]=(c[i]+d[i])/2;
            d[i]=c[i];
        }
    }
    for(int i=0;i<c.size();i++){
        cout<<c[i]<<" ";    
    }
    cout<<endl;
    for(int i=0;i<d.size();i++){
        cout<<d[i]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

double a,b;

vector<double> c;

vector<double> d;

while(cin>>a && cin>>b){

c.push_back(a);

d.push_back(b);

}

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

if(c[i]<0 && d[i]<0){

c[i]=c[i]+0.5;

d[i]=d[i]+0.5;

}

else if(c[i]<0 && d[i]>=0){

c[i]=c[i]*c[i];

}

else if(c[i]>=0 && d[i]<0){

d[i]=d[i]*d[i];

}

else {

c[i]=(c[i]+d[i])/2;

d[i]=c[i];

}

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

cout<<c[i]<<" ";

}

cout<<endl;

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

cout<<d[i]<<" ";

}

return 0;

}

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

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:

e-olimp 1310. Наибольший блок

28/06/2016 by Аня Шохина

Задача

Блоком строки [latex]S[/latex] в позиции [latex]i[/latex] назовём наибольшую подстроку [latex]S[/latex], которая начинается в позиции [latex]i[/latex] и совпадает с префиксом [latex]S[/latex]. Длину блока в позиции 0 считать равной нулю. Вычислить длину наибольшего блока заданной строки [latex]S[/latex].

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

Единственная строка [latex]S[/latex] [latex]\left(\left|S\right|\leq{10}^{6}\right)[/latex].

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

Длина наибольшего блока строки [latex]S[/latex].

Тесты

Входные данные	Выходные данные
abaabaab	5
aaaaa	4
aaabaab	2

Реализация

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

int main() {
    string s;
    getline(cin,s); // используем данную функцию, так как это выгодно по времени
    int n =  s.length();
    vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции
    int l=0, r=0; //левая и правая граница "отрезка совпадения"
    for (int i=1; i<n; i++) { 
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    int max=z[0];
    for (int i=1; i<z.size(); i++){
        if (max<z[i]){
            max=z[i];
        }
    }
    cout<<max<<endl;
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main() {

string s;

getline(cin,s); // используем данную функцию, так как это выгодно по времени

int n = s.length();

vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции

int l=0, r=0; //левая и правая граница "отрезка совпадения"

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

if (i <= r)

z[i] = min (r-i+1, z[i-l]);

while (i+z[i] < n && s[z[i]] == s[i+z[i]])

z[i]++;

if (i+z[i]-1 > r){

l = i;

r = i+z[i]-1;

}

int max=z[0];

for (int i=1; i<z.size(); i++){

if (max<z[i]){

max=z[i];

}

cout<<max<<endl;

return 0;

}

Код на ideone.com

Засчитанное решение на e-olimp.com

Решение

Для решения данной задачи необходимо рассмотреть алгоритм эффективного вычисления [latex]Z[/latex]-функции. Создадим массив [latex]z[/latex], где [latex]i[/latex]-ый элемент равен наибольшему числу символов, начиная с [latex]i[/latex]-ой позиции, совпадающих с первыми символами заданной строки [latex]s[/latex]. Эффективность алгоритма состоит в том, что при вычислении очередного элемента массива [latex]z[/latex] мы будем использовать уже вычисленные ранее значения. Назовем отрезком совпадения подстроку, совпадающую с префиксом заданной строки. Тогда искомое значение [latex]z\left [ i \right ][/latex] — это длина самого длинного отрезка совпадения, начинающегося в позиции [latex]i[/latex]. Из всех найденных отрезков совпадения будем хранить тот, который оканчивается правее всего. Положим, что [latex]l[/latex] и [latex]r[/latex] — индексы начала и конца данного отрезка соответственно. Тогда при вычислении [latex]z\left [ i \right ][/latex] возможны две ситуации: [latex]i>r[/latex] и [latex]i\leq r[/latex]. В первом случае позиция [latex]i[/latex] лежит за пределами проанализированной части строки . Тогда ищем значение [latex]Z[/latex]-функции перебором до тех пор, пока не дойдем до несовпадения или конца заданной строки. Стоит отметить, что если [latex]z\left [ i \right ]>0[/latex], следует изменить индексы отрезка совпадений. Во втором случае текущая позиция [latex]i[/latex] лежит внутри отрезка совпадений [latex]\left [ l,r \right ][/latex]. Так как подстроки [latex]s\left [ l\ldots r \right ][/latex] и [latex]s\left [ 0\ldots r-l \right ][/latex] совпадают, то в качестве значения [latex]z\left [ i \right ][/latex] можно взять значение [latex]z\left [ i-l \right ][/latex]. Однако, значение [latex]z\left [ i-l \right ][/latex] может быть слишком большим для данного блока (суффикс строки будет меньше, чем данное значение, чего быть не может). Следовательно, [latex]z\left [ i \right ][/latex]-ому элементу будем присваивать значение минимума из длины суффикса [latex]\left ( r-i+1 \right )[/latex] и [latex]z\left [ i-l \right ][/latex]. Далее используем вышеописанный перебор. В конечном итоге максимальный элемент массива — длина наибольшего блока заданной строки.

Related Images:

e-olymp 6. Путёвки

21/12/2015 by Александр Коломеец

Постановка задачи

e-olymp 6. Путёвки

Туристическая фирма не успела из-за больших морозов продать [latex]n[/latex] ([latex]n < 15[/latex]) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось [latex]d_k[/latex] ([latex]d_k \le 30[/latex]) дней, продавать по номинальной стоимости – по [latex]c_k[/latex] ([latex]c_k \le 100[/latex]) грн за день только за те дни, что остались со дня продажи ([latex]k = 1..n[/latex]).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

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

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

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

Максимальная сумма прибыли.

Алгоритм решения

Решим эту задачу полным перебором (методом грубой силы). Для этого необходимо перебрать все возможные варианты реализации. К примеру, дано три путевки:

Первая путёвка

срок действия: 2
номинальная стоимость: 13

Вторая путёвка

срок действия: 1
номинальная стоимость: 33

Третья путёвка

срок действия: 3
номинальная стоимость: 7

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

Путевки	Перебор всех возможных вариантов
	Вариант 1		Вариант 2
	Очередность	Результат	Очередность	Результат
Первая	1	20	1	20
Вторая	2		3
Третья	3		2
	Вариант 3		Вариант 4
	Очередность	Результат	Очередность	Результат
Первая	2	53	2	20
Вторая	1		3
Третья	3		1
	Вариант 5		Вариант 6
	Очередность	Результат	Очередность	Результат
Первая	3	40	3	7
Вторая	1		2
Третья	2		1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

Давайте представим, что мы имеем две путевки, сроки действия которых равны единице. Очевидно, что одну из них мы точно не успеем реализовать, так как продав одну, срок действия другой на следующий день истечет, а, так как реализовать путевки необходимо за наибольшую сумму, то реализовать нужно ту, чья номинальная стоимость выше. Отсюда следует, что, когда есть две путевки, сроки действия которых равны единице, более дешевую можно игнорировать. Теперь, пусть у нас есть три путевки, сроки действия которых равны двум. Аналогично рассуждая, можно прийти к выводу, что в такой ситуации путевку с самой низкой номинальной стоимостью можно игнорировать. Это же верно для четырех, пяти и т.д. путевок. Тогда нам остается перед началом полного перебора отсечь путевки, не влияющие на ответ, при этом сократив время выполнения в разы.

Тесты

Входные данные	Выходные данные
4 2 37 3 45 1 46 4 30	232
3 1 1 2 2 3 3	11
4 1 2 3 4 5 6 7 8	84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

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

struct ticket {
	int id, validity, price;
};

int cutDown(ticket tickets[], int count) {
	for(int validity = 0; validity <= min(30, count - 1); validity++) {
		int ticketsCount = 0;
		for(int i = 0; i < count; i++) {
			if(tickets[i].validity == validity) {
				ticketsCount++;
			}
		}
		while(ticketsCount > validity) {
			int cheapestTicketPosition = -1;
			int cheapestTicketPrice = 101;
			for(int i = 0; i < count; i++) {
				if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {
					cheapestTicketPrice = tickets[i].price;
					cheapestTicketPosition = i;
				}
			}
			tickets[cheapestTicketPosition] = tickets[--count];
			ticketsCount--;
		}
	}
	return count;
}

bool comparator(const ticket t1, const ticket t2) {
	return t1.id < t2.id;
}

int main() {
	int count;
	cin >> count;
	ticket tickets[count];
	for(int i = 0; i < count; i++) {
		tickets[i].id = i;
		cin >> tickets[i].validity >> tickets[i].price;
	}
	count = cutDown(tickets, count);
	sort(tickets, tickets + count, comparator);
	int maxProfit = 0;
	do {
		int profit = 0;
		for(int i = 0; i < count; i++) {
			profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;
		}
		maxProfit = max(profit, maxProfit);
	} while(next_permutation(tickets, tickets + count, comparator));
	cout << maxProfit << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct ticket {

int id, validity, price;

};

int cutDown(ticket tickets[], int count) {

for(int validity = 0; validity <= min(30, count - 1); validity++) {

int ticketsCount = 0;

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

if(tickets[i].validity == validity) {

ticketsCount++;

}

while(ticketsCount > validity) {

int cheapestTicketPosition = -1;

int cheapestTicketPrice = 101;

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

if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {

cheapestTicketPrice = tickets[i].price;

cheapestTicketPosition = i;

}

tickets[cheapestTicketPosition] = tickets[--count];

ticketsCount--;

}

return count;

}

bool comparator(const ticket t1, const ticket t2) {

return t1.id < t2.id;

}

int main() {

int count;

cin >> count;

ticket tickets[count];

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

tickets[i].id = i;

cin >> tickets[i].validity >> tickets[i].price;

}

count = cutDown(tickets, count);

sort(tickets, tickets + count, comparator);

int maxProfit = 0;

do {

int profit = 0;

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

profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;

}

maxProfit = max(profit, maxProfit);

} while(next_permutation(tickets, tickets + count, comparator));

cout << maxProfit << endl;

return 0;

}

Related Images:

e-olymp 138. Банкомат

20/09/2015 by Женя Максимова

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма	130	999	7360	3	80	123450	567	440
Число купюр	3	-1	18	-1	3	249	-1	4

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

#include <stdio.h>
int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры
int main()
{
 int n, q, x; //q - вспомогательная переменная в цикле
 scanf("%d",&n); 
 x=0; //количество купюр,  ему по умолчанию присваивается 0
 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему
 {
    q = Q[i]; 
    x += n / q; //считаем, сколько раз входит купюра в сумму
    n %= q;  //сумме присваивается остаток от деления на данную купюру
 }
 if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать
 printf("%d",x); 
 return 0;
}

#include <stdio.h>

int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры

int main()

{

int n, q, x; //q - вспомогательная переменная в цикле

scanf("%d",&n);

x=0; //количество купюр, ему по умолчанию присваивается 0

for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему

{

q = Q[i];

x += n / q; //считаем, сколько раз входит купюра в сумму

n %= q; //сумме присваивается остаток от деления на данную купюру

}

if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать

printf("%d",x);

return 0;

}

Алгоритм

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

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

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

Решение

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

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:

А409

14/03/2015 by Осецимський Анатолій Вадимович

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

1	3	1	1	1	1	1	1	2
1	1	1	1	1	1	1	1	1
1	1	1	1	1	4	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	5
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
Ответ	14

1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

Ответ

Нету элементов с такими свойствами

Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали). Потом сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементов ([latex]bigger[/latex]) всех нижних элементов и если это число больше, то прибавляем это число к переменной [latex]summa[/latex].

#include <iostream>
using namespace std;

int main() {
    int size = 9; bool ok = false;
    double mat[size][size];//Матрица 9 на 9
    for(int vert = 0;vert < size;vert++)//вводим матрицу
    {
        for(int gor = 0;gor < size;gor++)
        {
            cin >> mat[vert][gor];
        }
    }
    double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)
    for(int vert = 1;vert < size;vert++)//(Находим этот элемент)
    {
        for(int gor = 0;gor < vert;gor++)
        {
            if(bigger < mat[vert][gor]){
                bigger = mat[vert][gor];
            }
        }
    }
    for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент
    {
        for(int gor=vert;gor < size;gor++)
        {
            if(mat[vert][gor] > bigger)
            {
                ok = true;
                summa+=mat[vert][gor];
            }
        }
    }
    if(ok)//Провека для вывода ответа
    {
        cout << summa;
    }
    else
    {
        cout << "Нету элементов с такими свойствами";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int size = 9; bool ok = false;

double mat[size][size];//Матрица 9 на 9

for(int vert = 0;vert < size;vert++)//вводим матрицу

{

for(int gor = 0;gor < size;gor++)

{

cin >> mat[vert][gor];

}

double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)

for(int vert = 1;vert < size;vert++)//(Находим этот элемент)

{

for(int gor = 0;gor < vert;gor++)

{

if(bigger < mat[vert][gor]){

bigger = mat[vert][gor];

}

for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент

{

for(int gor=vert;gor < size;gor++)

{

if(mat[vert][gor] > bigger)

{

ok = true;

summa+=mat[vert][gor];

}

if(ok)//Провека для вывода ответа

{

cout << summa;

}

else

{

cout << "Нету элементов с такими свойствами";

}

return 0;

}

link

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 size = 9; boolean ok = false;
    	double[][] mat = new double[size][size];//Матрица 9 на 9
	    for(int vert = 0;vert < size;vert++)//вводим матрицу
	    {
	        for(int gor = 0;gor < size;gor++)
	        {
	            mat[vert][gor] = in.nextDouble();
	        }
	    }
	    double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)
	    for(int vert = 1;vert < size;vert++)//(Находим этот элемент)
	    {
	        for(int gor = 0;gor < vert;gor++)
	        {
	            if(bigger < mat[vert][gor]){
	                bigger = mat[vert][gor];
	            }
	        }
	    }
	    for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент
	    {
	        for(int gor=vert;gor < size;gor++)
	        {
	            if(mat[vert][gor] > bigger)
	            {
	                ok = true;
	                summa+=mat[vert][gor];
	            }
	        }
	    }
	    if(ok)//Провека для вывода ответа
	    {
	        System.out.println(summa);
	    }
	    else
	    {
	        System.out.println("Нету элементов с такими свойствами");
	    }
	}
}

/* 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 size = 9; boolean ok = false;

double[][] mat = new double[size][size];//Матрица 9 на 9

for(int vert = 0;vert < size;vert++)//вводим матрицу

{

for(int gor = 0;gor < size;gor++)

{

mat[vert][gor] = in.nextDouble();

}

double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)

for(int vert = 1;vert < size;vert++)//(Находим этот элемент)

{

for(int gor = 0;gor < vert;gor++)

{

if(bigger < mat[vert][gor]){

bigger = mat[vert][gor];

}

{

for(int gor=vert;gor < size;gor++)

{

if(mat[vert][gor] > bigger)

{

ok = true;

summa+=mat[vert][gor];

}

if(ok)//Провека для вывода ответа

{

System.out.println(summa);

}

else

{

System.out.println("Нету элементов с такими свойствами");

}

Related Images:

А410е

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

Дана целочисленная матрица [latex][a_{ij}], ij=1,\ldots,n.[/latex] Получить [latex]b_{1},\ldots,b_{n}[/latex], где [latex]b_{i}[/latex] — это: [latex]\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}[/latex].

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex]-го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1}= 2[/latex], [latex]b_{2}= 4[/latex].

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ji}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

Тесты:

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]:	Результат:	Комментарий:
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4	Пройден.
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6	Пройден.

#include <iostream>
using namespace std;
int main() {
    int n,maxa,mina;
    cin >>n;
    int a[n][n];
    for(int i=0; i<n;++i){
        for(int j=0;j<n;++j){
            cin >>a[i][j];
        }
    }
    int b[n];
    for(int i=0;i<n;++i){
        maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
        mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
        for(int j=0;j<n;++j){
            maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        }
        b[i]=maxa*mina; //Наш результат.
    }   for(int i=0;i<n;++i){
        cout <<b[i]<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,maxa,mina;

cin >>n;

int a[n][n];

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

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

cin >>a[i][j];

}

int b[n];

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

maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.

mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.

}

b[i]=maxa*mina; //Наш результат.

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

cout <<b[i]<<" ";

}

return 0;

}

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

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.21

20/12/2014 by Ковальський Олександр Дмитрович

Задача.

Целочисленный массив K(n, n) заполнить нулями и единицами, расположив их в шахматном порядке.

Тесты.

Ввод

Вывод

1 0 1 
0 1 0 
1 0 1

1 0 1

0 1 0

1 0 1

1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

#include <iostream>
using namespace std;

int main() 
	{
		int n;
		scanf("%d",&n);
		int k[n][n];
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						if((i+j)%2==0)printf("1 ");
						else printf("0 ");
					}
				printf("\n");
			}
		return 0;
	}

#include <iostream>

using namespace std;

int main()

{

int n;

scanf("%d",&n);

int k[n][n];

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

{

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

{

if((i+j)%2==0)printf("1 ");

else printf("0 ");

}

printf("\n");

}

return 0;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt();
		int[][] k = new int[n][n];
		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
					{
						if((i + j) % 2 == 0) System.out.printf("1 ");
						else System.out.printf("0 ");
					}
				System.out.println();
			}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] k = new int[n][n];

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

{

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

{

if((i + j) % 2 == 0) System.out.printf("1 ");

else System.out.printf("0 ");

}

System.out.println();

}

Решение.

В цикле проверяем если сумма номеров элемента в массиве чётна, то печатаем единицу, в противном случае печатаем ноль.

Related Images:

А410в

11/12/2014 by Нарусевич Никита Мирославович

Дана целочисленная матрица[latex][a_{ij}]_{i,j=1,…,n}[/latex] . Получить [latex]b_{1},…,b_{n}[/latex], где [latex]b_{i}[/latex] — это [latex]\prod_{j=1}^{n}a_{ij}[/latex];

Матрица				Результат
4
1	4	6	-5	-120
5	7	8	7	1960
1	2	5	9	90
5	5	0	3	0

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[n][n];
	for(int i=0; i<=(n-1); i++){
		for(int j=0; j<=(n-1); j++){
			cin >> a[i][j];
		}
	}
	int b[n];
	for(int i=0; i<=(n-1); i++){
		b[i]=1;
		for(int j=0; j<=(n-1); j++){
			b[i]=b[i]*a[i][j];
		}
	}
	for(int i=0; i<=(n-1); i++){
		cout << b[i] << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[n][n];

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

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

cin >> a[i][j];

}

int b[n];

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

b[i]=1;

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

b[i]=b[i]*a[i][j];

}

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

cout << b[i] << " ";

}

return 0;

}

Для начала прочитаем матрицу из потока ввода используя цикл for. Потом создадим цикл, в котором сначала будем присваивать каждому [latex]b_{i}[/latex] значение 1, а после этого получать необходимое значение. В самом конце напечатаем результат используя цикл.

Related Images:

Ю4.9

27/11/2014 by Стеблинський Ігор Віталійович

Задача: В матрице [latex]A\left(m,n \right)[/latex] все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты:

n	m	Введенная матрица	Полученная матрица
3	4	2 0 3 6 1 0 1 2 9 0 7 8	-0.5 0 -0.333333 -0.166667 -1 0 -1 -0.5 -0.111111 0 -0.142857 -0.125
3	4	0 0 0 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0
3	5	-2 0 -4 5 -6 9 -8 7 -6 5 -7 3 -6 0 -9	0.5 0 0.25 -0.2 0.166667 -0.111111 0.125 -0.142857 0.166667 -0.2 0.142857 -0.333333 0.166667 0 0.111111
3	4	1 1 1 1 1 1 1 1 1 1 1 1	-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

#include <iostream>
using namespace std;
 
int main() {
	int n,m;
	cin >> n >> m;
	double A[n][m];
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			cin >> A[i][j];
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			if (A[i][j]!=0){
				A[i][j]=-(1/A[i][j]);
			}
	}	
	for (int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			cout << A[i][j] << "\t";
			cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,m;

cin >> n >> m;

double A[n][m];

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

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

cin >> A[i][j];

}

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

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

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

A[i][j]=-(1/A[i][j]);

}

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

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

cout << A[i][j] << "\t";

cout << endl;

}

return 0;

}

Ссылка на код: http://ideone.com/JX6G1b

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
	{
		int n,m; 
		Scanner in = new Scanner(System.in);
		n=in.nextInt();
		m=in.nextInt();
		double [][] A = new double [n][m];
		for (int i=0; i<n; i++){
	   		for (int j=0; j<m; j++){
				A[i][j]=in.nextDouble();
			}
		 }
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				if (A[i][j]!=0){
					A[i][j]=-(1/A[i][j]);
				}
			}	
		}
		for (int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				System.out.printf("%.6f ",A[i][j]);
			}
			System.out.println();
		}		
	}
}

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

{

int n,m;

Scanner in = new Scanner(System.in);

n=in.nextInt();

m=in.nextInt();

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

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

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

A[i][j]=in.nextDouble();

}

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

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

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

A[i][j]=-(1/A[i][j]);

}

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

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

System.out.printf("%.6f ",A[i][j]);

}

System.out.println();

}

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

Ход решения:

Вводим матрицу [latex]A[/latex] размером [latex]\left(m,n \right)[/latex]. Делаем цикл, в котором проверяем каждый элемент матрицы. Если он равен [latex]0[/latex] — мы оставляем его без изменений, если не равен [latex]0[/latex], то умножаем его на обратный по величине и противоположный по знаку [latex]\left(-\frac{1}{A\left[i \right]\left[j \right]} \right)[/latex]. Полученную матрицу выводим на печать.

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:

Ю4.16

25/11/2014 by Недомовний Владислав

Задача.

Все четные элементы целочисленного массива [latex]K(n)[/latex] поместить в массив [latex]L(n)[/latex], а нечетные — в массив [latex]M(n)[/latex]. Подсчитать количество тех и других.

Тесты.

n	K[ ]	num of L	L[ ]	num of M	M[ ]	Комментарий
6	1 2 3 4 5 6	3	2 4 6	3	1 3 5	Пройден
5	1 1 6 4 3	2	6 4	3	1 1 3	Пройден

Решение.

C++

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int n;
    cin >> n; //ввод условий
    int K[n];
    for (int i=0;i<n;i++)
    {
        cin >> K[i];
    }
    int L[n]; //описание массивов и счетчиков
    int M[n];
    int l=0;
    int m=0;
    for (int i=0;i<n;i++)
    {
        if (K[i]%2==0) // проверка четности
        {
            L[l]=K[i];
            l++;
        }
        else
        {
            M[m]=K[i];
            m++;
        }
    }
    cout << "num of L=" << l << endl;
    cout << "L:";
    for (int i=0;i<l;i++)
    {
        cout << L[i] << " ";
    }
    cout << endl;
    cout << "num of M=" << m << endl;
    cout << "M:";
    for (int i=0;i<m;i++)
    {
        cout << M[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

int n;

cin >> n; //ввод условий

int K[n];

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

{

cin >> K[i];

}

int L[n]; //описание массивов и счетчиков

int M[n];

int l=0;

int m=0;

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

{

if (K[i]%2==0) // проверка четности

{

L[l]=K[i];

l++;

}

else

{

M[m]=K[i];

m++;

}

cout << "num of L=" << l << endl;

cout << "L:";

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

{

cout << L[i] << " ";

}

cout << endl;

cout << "num of M=" << m << endl;

cout << "M:";

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

{

cout << M[i] << " ";

}

return 0;

}

Java

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

class Ideone
{
	public static void main (String[] args) 
	{
		int n;
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); //ввод условий
	    int[] K = new int[n];
	    for (int i = 0;i < n;i++)
	    {
	        K[i] = sc.nextInt();
	    }
	    int[] L = new int[n]; //описание массивов и счетчиков
	    int[] M = new int[n];
	    int l=0;
	    int m=0;
	    for (int i = 0; i < n; i++)
	    {
	        if (K[i] % 2 == 0) // проверка четности
	        {
	            L[l] = K[i];
	            l++;
	        }
	        else
	        {
	            M[m] = K[i];
	            m++;
	        }
	    }
	    System.out.printf("num of L=%d\n",l);
	    System.out.printf("L:");
	    for (int i = 0; i < l; i++)
	    {
	    	System.out.printf("%d ",L[i]);
	    }
	    System.out.println();
	    System.out.printf("num of M=%d\n",m);
	    System.out.printf("M:");
	    for (int i = 0; i < m; i++)
	    {
	        System.out.printf("%d ",M[i]);
	    }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

int n;

Scanner sc = new Scanner(System.in);

n = sc.nextInt(); //ввод условий

int[] K = new int[n];

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

{

K[i] = sc.nextInt();

}

int[] L = new int[n]; //описание массивов и счетчиков

int[] M = new int[n];

int l=0;

int m=0;

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

{

if (K[i] % 2 == 0) // проверка четности

{

L[l] = K[i];

l++;

}

else

{

M[m] = K[i];

m++;

}

System.out.printf("num of L=%d\n",l);

System.out.printf("L:");

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

{

System.out.printf("%d ",L[i]);

}

System.out.println();

System.out.printf("num of M=%d\n",m);

System.out.printf("M:");

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

{

System.out.printf("%d ",M[i]);

}

В цикле проверяем каждый элемент массива [latex]K(n)[/latex], если элемент четный, то добавляем его в массив [latex]L(n)[/latex], если нет, то добавляем его в массив [latex]M(n)[/latex]. При этом после каждого добавления увеличиваем соответствующий счетчик на 1.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

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.14

16/11/2014 by Оніщенко Олександр

Задача:

Элементы заданного массива [latex]T(k)[/latex] расположить в обратном порядке : [latex] t_k, t_{k-1}, … , t_2, t_1.[/latex]

Тесты:

[latex]k[/latex]	Вводимые значения	Результат	Комментарий
6	1 2 3 4 5 6	6 5 4 3 2 1	Пройдено
1	3	3	Пройдено
3	22 501 -1254	-1254 501 22	Пройдено

Код:

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

int main() {
	int k;
	cin >> k;
	int t[k];
	for(int i=0; i < k; i++ )
	{
		cin >> t[i];
	}
	for(int i=0; i < k; i++)
		cout << t[k-i-1] << " ";
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int k;

cin >> k;

int t[k];

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

{

cin >> t[i];

}

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

cout << t[k-i-1] << " ";

return 0;

}

В начале задаем количество элементов в массиве. Заполняем массив значениями с помощью цикла [latex]for[/latex]. С помощью цикла [latex]for[/latex] выводим элементы массива в обратном порядке.

Ссылка Ideone.

Код Java

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

class Depo
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int k;
		Scanner in = new Scanner(System.in);
		k=in.nextInt();
		double[] t;
		t= new double[k];
		for(int i=0; i < k; i++ ){
			t[i]=in.nextDouble();
		}
		for(int i=0; i < k; i++ ){
			System.out.println(t[k-i-1]);
		}
	}
}