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

Работа с прямоугольными массивами.

Массивы

Опубликовано: 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 балл):

Шоколад

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

e-olymp 7504. Три прямоугольника

19/01/2019 by Николай Козиний

Задача взята с сайта e-olymp

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 1 1 1 2 2 0 0 2 2	4
2	2 -2 -2 2 -1 -1 1 1 40 40 41 41	17
3	-1 2 2 -1 1 0 4 2 1 0 3 6	21
4	-100 -100 -99 -99 100 100 99 99 -100 -100 100 100	40000
5	3 0 4 1 1 0 3 3 1 0 3 3	7

Решение

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

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

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

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

#include <iostream>
#include <cmath>
using namespace std;
struct point{int x;int y;};
struct rect{point a;point b;};
rect getrect(point a, point b, rect c){
    if(a.x > b.x)swap(a.x,b.x);
    if(a.y > b.y)swap(a.y,b.y);
    c.a = a;
    c.b = b;
    return c;
}
rect getrekt(rect c){
    point a,b;
    cin >> a.x >> a.y >> b.x >> b.y;
    return getrect(a,b,c);
}
int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){
    rect cr;
    point a1,b1;
    a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));
    a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));
    b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));
    b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));
    return getrect(a1,b1,cr);
}
int farea(rect *q){
    return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));
}
int main() {
    rect *q = new rect [3];
    for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);
    cout<<farea(q);
}

#include <iostream>

#include <cmath>

using namespace std;

struct point{int x;int y;};

struct rect{point a;point b;};

rect getrect(point a, point b, rect c){

if(a.x > b.x)swap(a.x,b.x);

if(a.y > b.y)swap(a.y,b.y);

c.a = a;

c.b = b;

return c;

}

rect getrekt(rect c){

point a,b;

cin >> a.x >> a.y >> b.x >> b.y;

return getrect(a,b,c);

}

int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){

rect cr;

point a1,b1;

a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));

a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));

b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));

b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));

return getrect(a1,b1,cr);

}

int farea(rect *q){

return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));

}

int main() {

rect *q = new rect [3];

for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);

cout<<farea(q);

}

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

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

#include <iostream>
#include <cmath>
#define N 100
using namespace std;
 
int main() {
    int rect[3][4];
    int field[2*N][2*N];
    int count = 0;
    for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;
    for(int i = 0;i < 3;i++){
        for(int k = 0;k < 4;k++){
            cin >> rect[i][k];
            rect[i][k] = rect[i][k] + N;
        }
    }
    for(int k = 0;k<3;k++){
        for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){
            for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){
                field[i][j]=1;
            }
        }
    }
    for(int i = 0;i < 2*N;i++){
        for(int k = 0;k < 2*N;k++){
            if(field[i][k] & 1)count++;
        }
    }
    cout<<count;
}

#include <iostream>

#include <cmath>

#define N 100

using namespace std;

int main() {

int rect[3][4];

int field[2*N][2*N];

int count = 0;

for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;

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

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

cin >> rect[i][k];

rect[i][k] = rect[i][k] + N;

}

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

for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){

for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){

field[i][j]=1;

}

for(int i = 0;i < 2*N;i++){

for(int k = 0;k < 2*N;k++){

if(field[i][k] & 1)count++;

}

cout<<count;

}

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

Related Images:

e-olymp 2507. Граница

08/01/2019 by Михаил Бутник

Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

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

Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

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

Выведите одно целое число — длину границы между государствами в километрах.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 AAABB ABBBB AAABB AAAAB AAAAB AABBB	13
2	4 3 AAAA AAAA AAAB	2
3	5 9 BBBBB ABBBB AABBB AAABB AAAAB AAABB AABBB ABBBB BBBBB	15
4	2 1 AB	1
5	6 5 AABBBB BBBBBB BBBAAA AAAAAA AAAAAA	10

Код

#include <iostream>
using namespace std;

int main() {
    int w, h, res = 0;
    cin >> w >> h;
    char **x = new char *[h];
    for (int i = 0; i < h; i++) x[i] = new char[w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> x[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            if (x[i][j] != x[i][j + 1]) res++;
        }
    }
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            if (x[i][j] != x[i + 1][j]) res++;
        }
    }
    cout << res << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int w, h, res = 0;

cin >> w >> h;

char **x = new char *[h];

for (int i = 0; i < h; i++) x[i] = new char[w];

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

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

cin >> x[i][j];

}

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

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

if (x[i][j] != x[i][j + 1]) res++;

}

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

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

if (x[i][j] != x[i + 1][j]) res++;

}

cout << res << endl;

return 0;

}

Решение

Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

Запустить код (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 45. Топливо

26/12/2018 by Кирилл Веремйов

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

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

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

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

Единственное число — искомое время.

Тесты

5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4	102
8 10 8 10 8 11 8 0 8 12 8 12 7 8 2 7 6 4 6 2 3 2 1 4 2 3 1 3 1 2 1 5 9 3 5 6 3 4 5 4 5 2	690
11 10 9 5 9 9 9 9 4 9 12 10 10 9 13 3 1 9 1 2 5 2 8 6 2 7 4 1 4 8 4 5 4 4 6 8 1 9 6 9 10 3 10 11 3	520
2 1 3 1 0 6 1 2 10	30
50 50 43 50 44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1 41 42 1 42 43 1 43 44 1 44 45 1 45 46 1 46 44 1 46 48 1 48 49 1 49 50 1 50 1 1	8400
3 3 1 2 3 0 1 1 3 1 2 3 2 1 2 4	6

Решение 1

#include <iostream>
#include <vector>
using namespace std;
    
int n,m,b,c;

struct boil{
    int mass=0;
    int number=0;
    vector<boil*> address;
    vector<int> distance;
};

int empty=0;
int near_tube=0;
vector<int> visit;

int Min_way(boil* A, int i, int from){
    
    if(A[i].mass>b){
        near_tube=A[i].number;
        return 0;
    }

    int min=0;
    
    bool t=0;
    for(int j=0; j< A[i].distance.size(); j++){
        bool t2=true,t1=true;
        for(int u=0; u<visit.size();u++){
            if(visit[u]==A[i].address[j]->number) t2=false;
            if(visit[u]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;
        if(A[i].address[min]->number==empty ||  A[i].address[min]->number==from)t1=false;
        
        if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){
            min=j;
            t=1;
        }
    }
    
    if(t==0){
        if(A[i].distance.size()==1){
            if(A[i].address[0]->mass>b){
                near_tube=A[i].address[0]->number;
                return A[i].distance[0];
            }
            else{
                return -1;
            }
        }
        else return -1;
    }
    else if(A[i].address[min]->mass==b){
        visit.push_back(A[i].number);
        
        bool t1=true;
        long long min2=-1;
        
        for(int k=0; k<visit.size() && t1; k++){
            if(visit[k]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[min]->number==from)t1=false;
        
        if(t1)  min2=Min_way(A,A[i].address[min]->number,A[i].number);
        if(min2>=0)min2+=A[i].distance[min];
            
        int n1=near_tube;
        
        for(int j=0; j<A[i].distance.size(); j++){
            if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){
                visit.push_back(A[i].number);
                long long a=0;
                bool t3=true;
                for(int k=0; k<visit.size() && t3; k++){
                    if(visit[k]==A[i].address[j]->number)t3=false;
                }
                
                if(A[i].address[j]->number==A[empty].number)t3=false;
                
                
                if(t1 && t3){
                    a=Min_way(A,A[i].address[j]->number,A[i].number);
                }
                else return-1;
                if(a>=0)a+=(A[i].distance[j]);
                
                if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){
                    min2=a;
                    n1=near_tube;
                }
                visit.clear();
            }
        }
        near_tube=n1;
        return min2;
    }
    else if(A[i].address[min]->mass<b){
        return -1;
    }
    else{
        near_tube= A[i].address[min]->number;
        return A[i].distance[min];
    }
}

int main() {
    cin>>n>>m>>b>>c;
    boil A[n];
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        A[i].mass=a;
        A[i].number=i;
        if(A[empty].mass>a)empty=i;
    }
    
    int d,k,g;
    while(cin>>d>>k>>g){
            A[d-1].address.push_back(&A[k-1]);
            A[k-1].address.push_back(&A[d-1]);
            A[k-1].distance.push_back(g);
            A[d-1].distance.push_back(g);
    }

    unsigned long long s=0;
    while(A[empty].mass<b){      
        unsigned long long a=Min_way(A,A[empty].number, A[empty].number);
        if(A[near_tube].mass-b+A[empty].mass<b){
            A[empty].mass+=A[near_tube].mass-b;
            s+=a*(A[near_tube].mass-b);
            A[near_tube].mass=b;
        }
        else{
            int tmp=b-A[empty].mass;
            A[near_tube].mass-=tmp;
            A[empty].mass=b;
            s+=a*tmp;
        }
    }
    
    cout<<s*c;
    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

#include <iostream>

#include <vector>

using namespace std;

int n,m,b,c;

struct boil{

int mass=0;

int number=0;

vector<boil*> address;

vector<int> distance;

};

int empty=0;

int near_tube=0;

vector<int> visit;

int Min_way(boil* A, int i, int from){

if(A[i].mass>b){

near_tube=A[i].number;

return 0;

}

int min=0;

bool t=0;

for(int j=0; j< A[i].distance.size(); j++){

bool t2=true,t1=true;

for(int u=0; u<visit.size();u++){

if(visit[u]==A[i].address[j]->number) t2=false;

if(visit[u]==A[i].address[min]->number)t1=false;

}

if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;

if(A[i].address[min]->number==empty || A[i].address[min]->number==from)t1=false;

if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){

min=j;

t=1;

}

if(t==0){

if(A[i].distance.size()==1){

if(A[i].address[0]->mass>b){

near_tube=A[i].address[0]->number;

return A[i].distance[0];

}

else{

return -1;

}

else return -1;

}

else if(A[i].address[min]->mass==b){

visit.push_back(A[i].number);

bool t1=true;

long long min2=-1;

for(int k=0; k<visit.size() && t1; k++){

if(visit[k]==A[i].address[min]->number)t1=false;

}

if(A[i].address[min]->number==from)t1=false;

if(t1) min2=Min_way(A,A[i].address[min]->number,A[i].number);

if(min2>=0)min2+=A[i].distance[min];

int n1=near_tube;

for(int j=0; j<A[i].distance.size(); j++){

if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){

visit.push_back(A[i].number);

long long a=0;

bool t3=true;

for(int k=0; k<visit.size() && t3; k++){

if(visit[k]==A[i].address[j]->number)t3=false;

}

if(A[i].address[j]->number==A[empty].number)t3=false;

if(t1 && t3){

a=Min_way(A,A[i].address[j]->number,A[i].number);

}

else return-1;

if(a>=0)a+=(A[i].distance[j]);

if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){

min2=a;

n1=near_tube;

}

visit.clear();

}

near_tube=n1;

return min2;

}

else if(A[i].address[min]->mass<b){

return -1;

}

else{

near_tube= A[i].address[min]->number;

return A[i].distance[min];

}

int main() {

cin>>n>>m>>b>>c;

boil A[n];

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

int a;

cin>>a;

A[i].mass=a;

A[i].number=i;

if(A[empty].mass>a)empty=i;

}

int d,k,g;

while(cin>>d>>k>>g){

A[d-1].address.push_back(&A[k-1]);

A[k-1].address.push_back(&A[d-1]);

A[k-1].distance.push_back(g);

A[d-1].distance.push_back(g);

}

unsigned long long s=0;

while(A[empty].mass<b){

unsigned long long a=Min_way(A,A[empty].number, A[empty].number);

if(A[near_tube].mass-b+A[empty].mass<b){

A[empty].mass+=A[near_tube].mass-b;

s+=a*(A[near_tube].mass-b);

A[near_tube].mass=b;

}

else{

int tmp=b-A[empty].mass;

A[near_tube].mass-=tmp;

A[empty].mass=b;

s+=a*tmp;

}

cout<<s*c;

return 0;

}

Решение 2

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

struct boil{
    int mass = 0;
    int len = 0;
    char n/*new*/='y';//yes
    char visit = 'n';//no
    vector <int> link;
    vector <int> dis;
};

int main() {
    int N,M,B,C;
    cin >> N >> M >> B >> C;
    boil A[N];
    int need;
    for(int i = 0; i < N ; i++){
        cin >> A[i].mass;
        if(A[i].mass < B)need = i;
    }
    int a, b, s;
    while(cin >> a >> b >> s){
        a--;
        b--;
        A[a].link.push_back(b);
        A[a].dis.push_back(s);
        A[b].link.push_back(a);
        A[b].dis.push_back(s);
    }
    queue <int> A_tmp;
    A_tmp.push(need);
    A[need].n = 'n';
    int ans = 0;
    while(!(A_tmp.empty())){
        int u = A_tmp.front();
        A_tmp.pop();
        A[u].visit = 'y';//yes
            for(int i = 0;i < A[u].link.size(); i++){ 
                if(A[A[u].link[i]].visit == 'n')
                        A_tmp.push(A[u].link[i]);
                if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){
                    A[A[u].link[i]].len = A[u].len + A[u].dis[i];
                    A[A[u].link[i]].n = 'n';
            }
        }
    }
    while(A[need].mass < B){
        int m = 0;
        for(int i = 0; i < N; i++){
            if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)
                m = i;
        }
        if(A[need].mass + (A[m].mass - B) <= B){
            ans += A[m].len * (A[m].mass - B);
            A[need].mass += A[m].mass - B;
            A[m].mass = B;
        }
        else{
            ans += A[m].len * (B - A[need].mass);
            int b = B - A[need].mass;
            A[need].mass = B;
            A[m].mass -= B - A[need].mass;
        }
    }
    cout << ans * C;
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct boil{

int mass = 0;

int len = 0;

char n/*new*/='y';//yes

char visit = 'n';//no

vector <int> link;

vector <int> dis;

};

int main() {

int N,M,B,C;

cin >> N >> M >> B >> C;

boil A[N];

int need;

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

cin >> A[i].mass;

if(A[i].mass < B)need = i;

}

int a, b, s;

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

a--;

b--;

A[a].link.push_back(b);

A[a].dis.push_back(s);

A[b].link.push_back(a);

A[b].dis.push_back(s);

}

queue <int> A_tmp;

A_tmp.push(need);

A[need].n = 'n';

int ans = 0;

while(!(A_tmp.empty())){

int u = A_tmp.front();

A_tmp.pop();

A[u].visit = 'y';//yes

for(int i = 0;i < A[u].link.size(); i++){

if(A[A[u].link[i]].visit == 'n')

A_tmp.push(A[u].link[i]);

if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){

A[A[u].link[i]].len = A[u].len + A[u].dis[i];

A[A[u].link[i]].n = 'n';

}

while(A[need].mass < B){

int m = 0;

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

if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)

m = i;

}

if(A[need].mass + (A[m].mass - B) <= B){

ans += A[m].len * (A[m].mass - B);

A[need].mass += A[m].mass - B;

A[m].mass = B;

}

else{

ans += A[m].len * (B - A[need].mass);

int b = B - A[need].mass;

A[need].mass = B;

A[m].mass -= B - A[need].mass;

}

cout << ans * C;

return 0;

}

Объяснение 1

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

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp

ideone(1)

ideone(2)

Related Images:

e-olymp 458. Черно-белая графика

24/12/2018 by Юлиана Боурош

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

	Входные данные	Выходные данные
1	5 3 01000 11110 01000 10110 00010 10110 0110	11110 11100 11110
2	2 3 010 111 000 101 1010	11 10 10
3	4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011	1111 0101 0000 1110
4	3 6 100011 000111 000000 111011 001100 010101 1000	000 100 110 000 101 010

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

( использован одномерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h, n;
    bool truth_t[4];
    cin >> w >> h;
    n = w * h;
    bool *first_t = new bool [n];
    bool *second_t = new bool [n];
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        first_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        cin >> c;
        second_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        if (i != 0 && i % w == 0)
        cout << endl;
        cout << my_operation(first_t[i], second_t[i], truth_t);
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h, n;

bool truth_t[4];

cin >> w >> h;

n = w * h;

bool *first_t = new bool [n];

bool *second_t = new bool [n];

char c;

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

cin >> c;

first_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

second_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

if (i != 0 && i % w == 0)

cout << endl;

cout << my_operation(first_t[i], second_t[i], truth_t);

}

return 0;

}

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

(использован двумерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h;
    bool truth_t[4];
    cin >> w >> h;
    bool **first_t = new bool *[h];
    bool **second_t = new bool *[h];
    for (int i = 0; i < h; i++) {
        first_t[i] = new bool [w];
        second_t[i] = new bool [w];
    }
    char c;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            cin >> c;
            first_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < h; i++){ 
        for (int j = 0; j < w; j++) {
            cin >> c;
            second_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << my_operation(first_t[i][j], second_t[i][j], truth_t);
        }
        if (i < h - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h;

bool truth_t[4];

cin >> w >> h;

bool **first_t = new bool *[h];

bool **second_t = new bool *[h];

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

first_t[i] = new bool [w];

second_t[i] = new bool [w];

}

char c;

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

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

cin >> c;

first_t[i][j] = (c == '1' ? true : false);

}

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

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

cin >> c;

second_t[i][j] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

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

cout << my_operation(first_t[i][j], second_t[i][j], truth_t);

}

if (i < h - 1) cout << endl;

}

return 0;

}

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Одномерный массив
- ideone.com
- e-olymp.com
Двумерный массив
- ideone.com
- e-olymp.com

Related Images:

e-olymp 5090. На перекрёстке

24/12/2018 by Наталья Федина

Задача

Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.

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

В первой строке находится число $n (1 \leq n \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$

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

Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.

Тесты

	Входные данные	Выходные данные
1	2 4 3 2 1	3
2	3 1 1 1 1 1 1 1 1 1	1
3	5 13 15 17 2 9 4 56 8 90 0 4 3 5 7 5 23 4 5 71 4 5 6 7 8 10	0
4	4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1	1

Код

С помощью одномерного массива

#include <iostream>
using namespace std;
 
int main() {
    int n, ns;
    cin >> n;
    ns = n*n;
    int *x = new int[ns];
    for (int i = 0; i < ns; i++)
        cin >> x[i];
    int I, J, min, max;
    for (int i = 0; i < ns; i += n) {
        int lmax = 0;
        for (int j = 0; j < n; j++)
            lmax += x[i + j];
        if (lmax > max || i == 0) {
            max = lmax;
            I = i;
        }
    }
    for (int j = 0; j < n; j++) {
        int lmin = 0;
        for (int i = 0; i < ns; i += n)
            lmin += x[i + j];
        if (lmin < min || j == 0) {
            min = lmin;
            J = j;
        }
    }
    cout << x[I + J];
    delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, ns;

cin >> n;

ns = n*n;

int *x = new int[ns];

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

cin >> x[i];

int I, J, min, max;

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

int lmax = 0;

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

lmax += x[i + j];

if (lmax > max || i == 0) {

max = lmax;

I = i;

}

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

int lmin = 0;

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

lmin += x[i + j];

if (lmin < min || j == 0) {

min = lmin;

J = j;

}

cout << x[I + J];

delete []x;

return 0;

}

С помощью двумерного массива

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int **x = new int*[n];
    for (int i = 0; i < n; i++) 
        x[i] = new int [n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) 
            cin >> x[i][j];
    int I, J, min, max;
    for (int i = 0; i < n; i++) {
        int lmax = 0;
        for (int j = 0; j < n; j++)
            lmax += x[i][j];
        if (lmax > max || i == 0) {
           max = lmax;
           I = i;
        }
    }
    for (int j = 0; j < n; j++) {
        int lmin = 0;
        for (int i = 0; i < n; i++)
            lmin += x[i][j];
        if (lmin < min || j == 0) {
            min = lmin;
            J = j;
        }
    }
    cout << x[I][J];
    for (int i = 0; i < n; i++)
        delete []x[i];
        delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int **x = new int*[n];

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

x[i] = new int [n];

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

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

cin >> x[i][j];

int I, J, min, max;

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

int lmax = 0;

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

lmax += x[i][j];

if (lmax > max || i == 0) {

max = lmax;

I = i;

}

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

int lmin = 0;

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

lmin += x[i][j];

if (lmin < min || j == 0) {

min = lmin;

J = j;

}

cout << x[I][J];

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

delete []x[i];

delete []x;

return 0;

}

Решение

Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$

Ссылки

С помощью одномерного массива
- e-olymp
- ideone
С помощью двумерного массива
- ideone
- e-olymp

Related Images:

e-olymp 5057. Спиралька

24/12/2018 by Николь Метри

Задача

Выведите двумерный массив, размерами [latex]n \times n[/latex], заполненный числами от [latex]1[/latex] до [latex]n^2[/latex] по спирали. Числовая спираль начинается в левом верхнем углу и закручивается по часовой стрелке.

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

Одно число [latex]n (1 \leqslant n \leqslant 10)[/latex].

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

Выведите [latex]n^2[/latex] чисел – заполненный по спирали массив.

Тесты

№	Ввод	Вывод
1	1	1
2	2	1 2 4 3
3	3	1 2 3 8 9 4 7 6 5
4	5	1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
5	9	1 2 3 4 5 6 7 8 9 32 33 34 35 36 37 38 39 10 31 56 57 58 59 60 61 40 11 30 55 72 73 74 75 62 41 12 29 54 71 80 81 76 63 42 13 28 53 70 79 78 77 64 43 14 27 52 69 68 67 66 65 44 15 26 51 50 49 48 47 46 45 16 25 24 23 22 21 20 19 18 17

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

#include <iostream>

using namespace std;

int main() {
    int **x, n;
    cin >> n;
    x = new int *[n];
    for (int i = 0; i < n; i++) x[i] = new int[n];
    int nc = n, num = 1;
    for (int z = 0; z < nc; z++) {
        for (int i = z; i < nc; i++) {
            x[z][i] = num;
            num++;
        }
        for (int i = z + 1; i < nc; i++) {
            x[i][nc - 1] = num;
            num++;
        }
        for (int i = nc - 2; i >= z; i--) {
            x[nc - 1][i] = num;
            num++;
        }
        for (int i = nc - 2; i >= z + 1; i--) {
            x[i][z] = num;
            num++;
        }
        nc--;
    }
    for (int l = 0; l < n; l++) {
        for (int k = 0; k < n; k++) {
            cout << x[l][k];
            if (k != n - 1) cout << " ";
        }
        if (l != n - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int **x, n;

cin >> n;

x = new int *[n];

for (int i = 0; i < n; i++) x[i] = new int[n];

int nc = n, num = 1;

for (int z = 0; z < nc; z++) {

for (int i = z; i < nc; i++) {

x[z][i] = num;

num++;

}

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

x[i][nc - 1] = num;

num++;

}

for (int i = nc - 2; i >= z; i--) {

x[nc - 1][i] = num;

num++;

}

for (int i = nc - 2; i >= z + 1; i--) {

x[i][z] = num;

num++;

}

nc--;

}

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

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

cout << x[l][k];

if (k != n - 1) cout << " ";

}

if (l != n - 1) cout << endl;

}

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 8525. Четные отрицательные в матрице

24/12/2018 by Наталья Федина

Задача

Задана матрица размера $n \times n.$ Найдите количество и сумму ее четных отрицательных чисел.

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

Первая строка содержит число $n (1 \leq n \leq 100).$ Следующие строки содержат матрицу $n \times n.$ Элементы матрицы по модулю не больше $100.$

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

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

Тесты

	Входные данные	Выходные данные
1	3 4 -2 5 1 -4 -12 0 1 -3	3 -18
2	2 4 -7 2 9	0 0
3	5 3 4 -5 7 2 1 2 3 4 -2 -2 -4 -6 -8 4 2 -4 0 -1	6 -26
4	4 1 2 3 4 -1 -2 -4 -3 4 -5 -8 -12 -4 -5 -7 0	5 -30

Код

С помощью двумерного массива

#include <iostream>
using namespace std;

int main() {
    int x[100][100];
    int n, sum = 0, count = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> x[i][j]; 
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (x[i][j] < 0 and x[i][j] % 2 == 0) {
               sum += x[i][j]; 
               count++;
            }
        }
    }
    cout << count << " " << sum; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[100][100];

int n, sum = 0, count = 0;

cin >> n;

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

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

cin >> x[i][j];

}

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

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

if (x[i][j] < 0 and x[i][j] % 2 == 0) {

sum += x[i][j];

count++;

}

cout << count << " " << sum;

return 0;

}

Без использования массива

#include <iostream>
using namespace std;

int main() {
    int n, count = 0, sum = 0, k;
    cin >> n;
    for (int i = 0; i < n * n; i++) {
        cin >> k;
        if (k < 0 && k % 2 == 0) {
            sum += k;
            count++;
        }
    }
    cout << count << " " << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0, sum = 0, k;

cin >> n;

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

cin >> k;

if (k < 0 && k % 2 == 0) {

sum += k;

count++;

}

cout << count << " " << sum;

return 0;

}

Решение

С помощью массива

Создаем массив. С помощью цикла for проверяем: если число отрицательное и чётное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Без массива

С помощью цикла for проверяем: если число отрицательное и четное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Ссылки

e-olymp (С массивом)
ideone (С массивом)
e-olymp (Без массива)
ideone (Без массива)

Related Images:

e-olymp 4557. Одинокий король

21/12/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

#	Входные данные	Выходные данные
1	5 1 2 4 7 4	4
2	5 1 2 4 6 4	Ok 2
3	3 1 2 1	Ok 5
4	3 1 5 1	2
5	8 8 8 8 8 8 8 8 8	Ok 8

Код

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

int main() {
    int *x, *y, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    x = new int [n];
    y = new int [n];
    for (int i = 1; i <= n; i ++){
        cin >> pos;
        if (pos == 1){
            x1 -= 1;
            y1 += 1;
        }
        else if (pos == 2) y1 += 1;
        else if (pos == 3){
            x1 += 1;
            y1 += 1;
        }
        else if (pos == 4) x1 += 1;
        else if (pos == 5){
            x1 += 1;
            y1 -= 1;
        }
        else if (pos == 6) y1 -= 1;
        else if (pos == 7){
            x1 -= 1;
            y1 -= 1;
        }
        else if (pos == 8) x1 -= 1;
        x[i] = x1;
        y[i] = y1;
    }
    for (int i = 1; i < n && f; i++)
        for (int j = 0; j < i; j++)
            if ((x[i] == x[j]) && (y[i] == y[j])){
                cout << i; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);
    delete []x;
    delete []y;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, *y, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

x = new int [n];

y = new int [n];

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

cin >> pos;

if (pos == 1){

x1 -= 1;

y1 += 1;

}

else if (pos == 2) y1 += 1;

else if (pos == 3){

x1 += 1;

y1 += 1;

}

else if (pos == 4) x1 += 1;

else if (pos == 5){

x1 += 1;

y1 -= 1;

}

else if (pos == 6) y1 -= 1;

else if (pos == 7){

x1 -= 1;

y1 -= 1;

}

else if (pos == 8) x1 -= 1;

x[i] = x1;

y[i] = y1;

}

for (int i = 1; i < n && f; i++)

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

if ((x[i] == x[j]) && (y[i] == y[j])){

cout << i;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);

delete []x;

delete []y;

return 0;

}

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива x = new int [n]; и y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле for (int i = 1; i <= n; i ++); заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так: abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

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

int main() {
    int *x, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};
    x = new int [2*n+2];
    for (int i = 2; i < (2 * n + 2); i += 2){
        cin >> pos;
        x1 += X[pos-1];
        y1 += Y[pos-1];
        x[i] = x1;
        x[i+1] = y1;
    }
    for (int i = 0; i < (2 * n + 2) && f; i += 2)
        for (int j = 0; j < i; j += 2)
            if ((x[i] == x[j]) && (x[i+1] == x[j+1])){
                cout << i / 2; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);
    delete []x;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

x = new int [2*n+2];

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

cin >> pos;

x1 += X[pos-1];

y1 += Y[pos-1];

x[i] = x1;

x[i+1] = y1;

}

for (int i = 0; i < (2 * n + 2) && f; i += 2)

for (int j = 0; j < i; j += 2)

if ((x[i] == x[j]) && (x[i+1] == x[j+1])){

cout << i / 2;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);

delete []x;

return 0;

}

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы if(); можно заменить массивами X[]; и Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

#include <iostream>
#include <cmath>
using namespace std;
 
int x[2001][2001];
 
int main() {
    int n;
    cin >> n;
    int pos;
    bool f = true;
    int x1 = 1001, y1 = 1001;
    for (int i = 0; i< n && f; i++){
        cin >> pos;
        if(x[x1][y1] == 1){ 
            cout << i;
            f = false;
        }
        else x[x1][y1] = 1;
        switch (pos){
            case 1: x1--; y1++; break;
            case 3: x1++;
            case 2: y1++; break;
            case 4: x1++; break;
            case 5: x1++;
            case 6: y1--; break;
            case 7: y1--; 
            case 8: x1--;
        }
    }
    if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int x[2001][2001];

int main() {

int n;

cin >> n;

int pos;

bool f = true;

int x1 = 1001, y1 = 1001;

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

cin >> pos;

if(x[x1][y1] == 1){

cout << i;

f = false;

}

else x[x1][y1] = 1;

switch (pos){

case 1: x1--; y1++; break;

case 3: x1++;

case 2: y1++; break;

case 4: x1++; break;

case 5: x1++;

case 6: y1--; break;

case 7: y1--;

case 8: x1--;

}

if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);

return 0;

}

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

Засчитанное решение 1 на e-olymp.
Засчитанное решение 2 на e-olymp.
Засчитанное решение 3 на e-olymp.
Код 1 в ideone.
Код 2 в ideone.
Код 3 в ideone.

Related Images:

e-olymp 8530. Печать матрицы

11/11/2018 by Александр Дьяченко

Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \times c$.

Тесты

Входные данные	Выходные данные
4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
6 30 -10 30 -69 -84 75 -3 -39 60 15 75 -74 36 68 35 23 25 -44 16 42 83 15 59 -18 71 43 35 -81 -38 51 37 -49 55 26 6 33 4 5	30 -10 30 -69 -84 -3 -39 60 15 75 36 68 35 23 25 16 42 83 15 59

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

#include <iostream>
using namespace std;

int main() {
    unsigned short n, r, c;
    cin >> n;
    int ** x = new int * [n];
    for (int i = 0; i < n; i++)
        x[i] = new int[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> x[i][j];
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cout << x[i][j] << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned short n, r, c;

cin >> n;

int ** x = new int * [n];

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

x[i] = new int[n];

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

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

cin >> x[i][j];

cin >> r >> c;

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

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

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

cout << endl;

}

return 0;

}

Решение

Для того, чтобы вывести матрицу на экран, нам нужно запустить $2$ цикла, один из которых будет вложен в предыдущий:

первый цикл ($14$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
второй цикл ($15$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 1484. Серебрянная матрица

13/07/2018 by Данилов Андрей

Задача

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

Размеры матрицы [latex]n\times n[/latex].
Все элементы матрицы лежат во множестве [latex]S = [/latex]{[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Для каждого целого числа [latex]i \left(1 ≤ i ≤ n\right),[/latex] все элементы [latex]i[/latex]-ой строки и [latex]i[/latex]-го столбца образуют множество {[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Например, следующая матрица размера [latex]4×4[/latex] является серебряной:

1	2	5	6
3	1	7	5
4	6	1	2
7	4	3	1

Доказано, что серебряная матрица размером [latex]2^K\times 2^K[/latex] всегда существует. Вам следует построить серебряную матрицу [latex]2^K\times 2^K[/latex].

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

Единственное число [latex]K \left(1 ≤ K ≤ 9\right).[/latex]

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

Вывести серебряную матрицу размером [latex]2^K×2^K[/latex]. Для вывода матрицы [latex]2^K\times 2^K[/latex], следует вывести [latex]2^K[/latex] строки, каждая из которых содержит [latex]2^K[/latex] целых чисел.

Тесты

#	Входные данные	Выходные данные
1	2	3 1 7 5 4 6 1 2 7 4 3 1
2	1	1 2 3 1
3	3	1 2 5 6 9 10 13 14 3 1 7 5 11 9 15 13 4 6 1 2 12 14 9 10 7 4 3 1 15 12 11 9 8 10 13 14 1 2 5 6 11 8 15 13 3 1 7 5 12 14 8 10 4 6 1 2 15 12 11 8 7 4 3 1

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

#include <iostream>
using namespace std;

void create(int** x, int k) {
  if (k == 1) {
    x[0][0] = 1;
    x[0][1] = 2;
    x[1][0] = 3;
    x[1][1] = 1;
  } else {
    create(x, k - 1);
    int from = 1 << (k - 1), n = 1 << k;
    for (int i = from; i < n; i++)
      for (int j = from; j < n; j++)
        x[i][j] = x[i - from][j - from];
    for (int i = 0; i < from; i++)
      for (int j = 0; j < from; j++) {
        x[i + from][j] = x[i][j] + n;
        x[i][j + from] = x[i][j] + n;
      }
    for (int i = 0; i < from; i++)
      x[i + from][i]--;
  }
}

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

#include <iostream>

using namespace std;

void create(int** x, int k) {

if (k == 1) {

x[0][0] = 1;

x[0][1] = 2;

x[1][0] = 3;

x[1][1] = 1;

} else {

create(x, k - 1);

int from = 1 << (k - 1), n = 1 << k;

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

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

x[i][j] = x[i - from][j - from];

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

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

x[i + from][j] = x[i][j] + n;

x[i][j + from] = x[i][j] + n;

}

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

x[i + from][i]--;

}

int main() {

int k, n = 1;

scanf("%d", &k);

n <<= k;

int** x = new int*[n];

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

x[i] = new int[n];

create(x, k);

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

printf("%d", x[i][0]);

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

printf(" %d", x[i][j]);

printf("\n");

}

return 0;

}

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

Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая [latex]k = 1[/latex] подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю [latex]k = 1[/latex] и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

Псевдо строчная таблица

12/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$	$12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$	$10$
$2 \ 3 \ 5$
$4 \ 4$	$96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$	$6$
$2 \\ 2 \\ 2$
$5 \ 3$	$430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$	$216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$	$945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$	$5$
$5$
$3 \ 7$	$210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$	$202$
$100 \ 1 \\ 100 \ 1$

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

#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> m >> n;
    long long s[m][n], h=0;
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> s[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        h+=s[0][i];
    }
    cout << m*h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

long long s[m][n], h=0;

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

{

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

{

cin >> s[i][j];

}

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

{

h+=s[0][i];

}

cout << m*h;

return 0;

}

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Related Images:

e-olymp 48. Красные и синие квадраты

30/06/2018 by Павел Жуков

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

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

Тесты

Входные данные	Выходные данные
$3$ $1$ $2$ $2$ $1$ $3$ $1$	$3$
$3$ $1$ $1$ $2$ $2$ $1$ $3$	$6$
$10$ $1$ $1$ $2$ $2$ $1$ $3$ $2$ $4$ $1$ $5$ $2$ $6$ $1$ $7$ $2$ $8$ $1$ $9$ $2$ $10$	$90$

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

#include <iostream>
using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;
        squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;
    }
    int perimiter = 0;
    for (int i = 0; i < MAX_PAGE_SIZE; ++i){
        for (int j = 0; j < MAX_PAGE_SIZE; ++j){
            if (squares[i][j]){
                perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];
            }
        }
    }
    int max = 0;
    for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){ 
        int i = (perimiter - 2 * j) / 2; 
        if (i * j - n > max) {
            max = i * j - n;
        }
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;

squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;

}

int perimiter = 0;

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

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

if (squares[i][j]){

perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];

}

int max = 0;

for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){

int i = (perimiter - 2 * j) / 2;

if (i * j - n > max) {

max = i * j - n;

}

cout << max;

return 0;

}

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 7623. Счастливые случаи

26/06/2018 by Даниил Крутоголов

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$1$ $1$ $4$	$4$
2	$2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$12$
3	$3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$	$13$
4	$2$ $2$ $1$ $2$ $3$ $4$	$12$
5	$0$ $0$	$0$

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

#include <iostream>

using namespace std; 

int main() {
    int r, c, a, b, e, d, w = 0;
    cin >> r >> c;
    int **x = new int * [r];
    for (int i = 0; i < r; i++) x[i] = new int[c];
    for (int i = 0; i < r; i++){
        for (int j = 0; j > x[i][j];
        }
    }
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            a = b = e = d = 1;
        for (int q = 0; q < i; q++){
            if (x[i][j] <= x[q][j])
                a = 0;
        }
        for (int q = i+1; q < r; q++){
            if (x[i][j] <= x[q][j])
                b = 0;
        }
        for (int k = 0; k < j; k++){
            if (x[i][j] <= x[i][k])
                e = 0;
        }
        for (int k = j+1; k < c; k++){
            if (x[i][j] <= x[i][k])
                d = 0;
        }
        w+= a + b + e + d;
        }
    }
    cout << w;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, c, a, b, e, d, w = 0;

cin >> r >> c;

int **x = new int * [r];

for (int i = 0; i < r; i++) x[i] = new int[c];

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

for (int j = 0; j > x[i][j];

}

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

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

a = b = e = d = 1;

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

if (x[i][j] <= x[q][j])

a = 0;

}

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

if (x[i][j] <= x[q][j])

b = 0;

}

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

if (x[i][j] <= x[i][k])

e = 0;

}

for (int k = j+1; k < c; k++){

if (x[i][j] <= x[i][k])

d = 0;

}

w+= a + b + e + d;

}

cout << w;

return 0;

}

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

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

Ссылки

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

• Решение на сайте ideone.

Related Images:

e-olymp 1482. Умножение матриц

25/06/2018 by Томас Пасенченко

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

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

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

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

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные	Выходные данные
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1	2 3 7 2 15 1 10 7
3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1	3 2 7 14 3 19 13 38
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0	4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2
3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2	-1
2 3 57 -49 31 89 11 -37 3 1 19 -19 0	2 1 2014 1482

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

#include <iostream>
using namespace std;

int main() {
    int na, ma, nb, mb;
    cin >> na >> ma;
    int **a = new int *[na];
    for (int i = 0; i < na; i++) {
        a[i] = new int[ma];
    }
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < ma; j++) {
            cin >> a[i][j];
        }
    }
    cin >> nb >> mb;
    // Проверяем возможность вычисления произведения матриц
    if (ma != nb) {
        cout << -1;
        return 0;
    }
    int **b = new int *[nb];
    for (int i = 0; i < nb; i++) {
        b[i] = new int[mb];
    }
    for (int i = 0; i < nb; i++) {
        for (int j = 0; j < mb; j++) {
            cin >> b[i][j];
        }
    }
    
    int **c = new int *[na];
    for (int i = 0; i < na; i++) {
        c[i] = new int[mb];
    }
    // Вычисляем произведение
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            for (int r = 0; r < ma; r++) {
                c[i][j] += a[i][r] * b[r][j];
            }
        }
    }
    // Выводим результат
    cout << na << " " << mb << "\n";
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            cout << c[i][j];
            if (j + 1 != mb) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int na, ma, nb, mb;

cin >> na >> ma;

int **a = new int *[na];

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

a[i] = new int[ma];

}

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

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

cin >> a[i][j];

}

cin >> nb >> mb;

// Проверяем возможность вычисления произведения матриц

if (ma != nb) {

cout << -1;

return 0;

}

int **b = new int *[nb];

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

b[i] = new int[mb];

}

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

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

cin >> b[i][j];

}

int **c = new int *[na];

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

c[i] = new int[mb];

}

// Вычисляем произведение

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

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

for (int r = 0; r < ma; r++) {

c[i][j] += a[i][r] * b[r][j];

}

// Выводим результат

cout << na << " " << mb << "\n";

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

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

cout << c[i][j];

if (j + 1 != mb) cout << " ";

}

cout << "\n";

}

return 0;

}

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

Related Images:

e-olymp 47. Паркет из треугольников

24/06/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    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

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

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

{

arr[i] = new int*[horSize];

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

{

arr[i][j] = new int[z];

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

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

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

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

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

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

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

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

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

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

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

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

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

Search[firstNumberx - 1];

1	Search[firstNumberx - 1];

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

Related Images:

e-olymp 2666. Половина

20/06/2018 by Валерия Ларикова

Задача

Напишите программу, заполняющую массив [latex]n \times n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

#	Входные данные	Выходные данные
1	2	20 01
2	3	220 201 011
3	4	2220 2201 2011 0111
4	5	22220 22201 22011 20111 01111
5	10	2222222220 2222222201 2222222011 2222220111 2222201111 2222011111 2220111111 2201111111 2011111111 0111111111

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

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int A[20][20];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(i + j == n - 1) A[i][j] = 0;
            else if (i + j < n - 1) A[i][j] = 2;
            else A[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            cout << A[i][j];
            cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int A[20][20];

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

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

if(i + j == n - 1) A[i][j] = 0;

else if (i + j < n - 1) A[i][j] = 2;

else A[i][j] = 1;

}

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

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

cout << A[i][j];

cout << endl;

}

return 0;

}

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

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20[/latex]. Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

[latex]i + j = n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит на побочной диагонали;
[latex]i + j > n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит ниже побочной диагонали;
[latex]i + j < n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

e-olymp 2669. Поворот

11/06/2018 by Иван Мясоедов

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2 1 2 3 4	2 2 3 1 4 2
2	3 3 1 2 3 4 5 6 7 8 9	3 3 4 7 1 8 5 2 9 6 3
3	3 4 4 5 7 8 3 6 8 7 2 2 4 5	4 3 2 3 4 2 6 5 4 8 7 5 7 8
4	1 2 5 4	2 1 5 4
5	1 1 2	1 1 2

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

2 2

1 2

3 4

2 2

3 1

4 2

3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

1 2

5 4

2 1

1 1

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int ** x = new int *[n];
    for (int i = 0; i < n; i++) 
        x[i] = new int[m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            cin >> x[i][j];
    cout << m << " " << n;
    cout << endl;
    for (int j = 0; j < m; j++){ 
        for (int i = n - 1; i >= 0; i--)
            cout << x[i][j] << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

int ** x = new int *[n];

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

x[i] = new int[m];

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

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

cin >> x[i][j];

cout << m << " " << n;

cout << endl;

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

for (int i = n - 1; i >= 0; i--)

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

cout << endl;

}

return 0;

}

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

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

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 2671. Сапер

10/06/2018 by Андрей Святозар Чернецкий

Задача

Дан список мин. Требуется составить поле для игры в сапер.

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

Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).

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

Требуется вывести на экран поле. Формат вывода указан в примере.

Тесты

Входные данные	Выходные данные
3 2 2 1 1 2 2	* 2 2 * 1 1
2 2 0	0 0 0 0
10 10 5 1 1 3 3 5 5 7 7 9 9	* 1 0 0 0 0 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 1
1 1 1 1 1	*
32 32 10 1 1 2 2 4 4 4 3 3 4 5 5 27 28 30 30 22 31 32 32	* 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 * 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 4 * 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * * 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 *

#include <iostream>
using namespace std;
 
int main(){
    int n, m, bomb, count = 0;
    cin >> n >> m >> bomb;
    char A[34][34];
    int x, y;
    for (int i = 0; i < n + 2; i++){ 
        for (int j = 0; j < m + 2; j++){ 
            A[i][j] = '0';
        }
    }
    for (int i = 0; i < bomb; i++){
        cin >> x >> y;
        A[x][y] = '*';
    }
    for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){ 
            if (A[i][j] != '*'){
                if (A[i-1][j] == '*') count++;
                if (A[i-1][j-1] == '*') count++;
                if (A[i-1][j+1] == '*') count++;
                if (A[i+1][j+1] == '*') count++;
                if (A[i+1][j-1] == '*') count++;
                if (A[i+1][j] == '*') count++;
                if (A[i][j-1] == '*') count++;
                if (A[i][j+1] == '*') count++;
                cout << count;
                count = 0;
            }
            else cout << A[i][j];
            if (j != m) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int n, m, bomb, count = 0;

cin >> n >> m >> bomb;

char A[34][34];

int x, y;

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

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

A[i][j] = '0';

}

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

cin >> x >> y;

A[x][y] = '*';

}

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

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

if (A[i][j] != '*'){

if (A[i-1][j] == '*') count++;

if (A[i-1][j-1] == '*') count++;

if (A[i-1][j+1] == '*') count++;

if (A[i+1][j+1] == '*') count++;

if (A[i+1][j-1] == '*') count++;

if (A[i+1][j] == '*') count++;

if (A[i][j-1] == '*') count++;

if (A[i][j+1] == '*') count++;

cout << count;

count = 0;

}

else cout << A[i][j];

if (j != m) cout << " ";

}

cout << endl;

}

return 0;

}

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

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

Ссылки

Условие задачи на сайте e-olymp

код задачи на ideone

Related Images:

e-olymp 2667. Змейка

09/06/2018 by Карина Миловская

Задача

Напишите программу, которая выводит элемент из строки [latex]x[/latex] и столбца [latex]y[/latex] матрицы размера [latex]n × m[/latex], которая заполнена змейкой:

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

Даны натуральные числа [latex]n[/latex], [latex]m[/latex], [latex]x[/latex], [latex]y[/latex] [latex](1 ≤ x ≤ n ≤ 50, 1 ≤ y ≤ m ≤ 50)[/latex]. Здесь [latex]n[/latex] — количество строк матрицы, [latex]m[/latex] — количество столбцов матрицы, [latex]x[/latex] и [latex]y[/latex] — номера строки и столбца искомого элемента.

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

Вывести элемент из строки [latex]x[/latex] и столбца [latex]y[/latex].

Тесты

Входные данные	Выходные данные
[latex]5 \; 2 \; 3 \; 1[/latex]	[latex]4[/latex]
[latex]6 \; 3 \; 4 \; 3[/latex]	[latex]9[/latex]
[latex]10 \; 5 \; 10 \; 2[/latex]	[latex]48[/latex]

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

#include <iostream>
using namespace std;
 
int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int arr[n][m];
    int num = 0;
    for(int i = 0; i < n; ++i) {
        int dir, j;
        if(i % 2 == 0){
            j = 0;
            dir = 1;
        }
        else {
            j = m-1;
            dir = -1;
        }
        for(; j < m&&j >= 0; j+= dir) {
            arr[i][j] = num;
            ++num;
        }
    }
    cout << arr[x - 1][y - 1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, x, y;

cin >> n >> m >> x >> y;

int arr[n][m];

int num = 0;

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

int dir, j;

if(i % 2 == 0){

j = 0;

dir = 1;

}

else {

j = m-1;

dir = -1;

}

for(; j < m&&j >= 0; j+= dir) {

arr[i][j] = num;

++num;

}

cout << arr[x - 1][y - 1];

return 0;

}

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

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

Ссылки

Условие задачи на e-olymp
Код решения на ideone

Related Images:

e-olymp 936. Формулы Крамера

09/06/2018 by Иван Василевский

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
[latex]\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}[/latex]

Входные данные
Первая строка содержит коэффициенты первого уравнения, а вторая строка содержит коэффициенты второго. Все входные числа разделены одним пробелом и не превышают по модулю $100$.

Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.

Continue reading →