e-olymp 4751. Диагонали

08/01/2019 by Александр Мога

Задача

В квадратной таблице [latex] n × n [/latex] подсчитать сумы чисел, стоящих на главной и побочной диагоналях.

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

Вводится число [latex]n (1 \le n \le 500)[/latex], а затем матрица [latex] n × n [/latex]. Элементы матрицы — числа по модулю не больше [latex]10^5[/latex].

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

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

Вывести сумму чисел сначала на главной, а затем на побочной диагонали.

Тесты

Вход	Выход
4 134 475 30 424 303 151 419 235 248 166 90 42 318 237 184 36	411 1327
7 -59 21 7 5 12 868 -565 32 19 52 3 7 11 0 3 -123 -52 -99 -857 -4621 -561 11 232 86 652 46 3244 572 857 -1242 -6767 923 -575 12 1 552 232 2 63 -76 23 0 12 34 87 20 -7 767 959	967 -7282
3 1 45 82 96 29 90 757 23 12	42 868
2 12 32 99 71	83 131
5 12 32 54 76 12 95 23 21 123 0 65 32 1 773 992 5 32 155 866 912 134 44 74 11 23	36 136

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

#include <iostream>
using namespace std;

int main() {
    int n;
    int m=0;
    int c=0;
    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];
    }
    for (int i = 0; i < n; i++){
        m+=x[i][i];
        c+=x[i][n-1-i];
    }
    for (int i = 0; i < n; i++) 
        delete []x[i];
    delete []x;
    cout <<  m << " " << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int m=0;

int c=0;

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

}

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

m+=x[i][i];

c+=x[i][n-1-i];

}

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

delete []x[i];

delete []x;

cout << m << " " << c;

return 0;

}

Решение

Создаем динамический массив.

Чтобы найти сумму главной диагонали берём, лишь те элементы массива, в которых номер строки и столбца равны.

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

Ссылки

e-olymp

ideone

Related Images:

e-olymp 396. Дождь

15/04/2018 by Мороз Дима

Задача

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

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$_$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y = 0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$_$0$ точки появления капли $(0 < X$_$0$ $< 10000)$ и количество отрезков-препятствий $N (0 ≤ N ≤ 100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$_$1$, $y$_$1$, $x$_$2$, $y$_$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$, $x$_$1$ $ < x$_$2$, $y$_$1$ $≠$ $y$_$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

#include <iostream>
using namespace std;
 
int main () 
{
    int x, n;
    cin >> x >> n;
    int N[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> N[i][j];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            for (int q = 0; q < 4; q++)
                if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )
                    swap(N[i][q], N[j][q]);
    for (int i = 0; i < n; i++) {
        if (x >= N[i][0] && x <= N[i][2]) 
            N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];
        for (int j = 0; j < 4; j++)
            N[i][j] = 0;
    }
    cout << x;
 
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

int x, n;

cin >> x >> n;

int N[n][4];

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

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

cin >> N[i][j];

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )

swap(N[i][q], N[j][q]);

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

if (x >= N[i][0] && x <= N[i][2])

N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];

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

N[i][j] = 0;

}

cout << x;

return 0;

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X$ $ ∈ [x$_$1$$, x$_$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y$_$1$ и $y$_$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$_$1$ или $x$_$2$ координате нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

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

Related Images:

e-olimp 6130. Дек неограниченного размера.

01/04/2015 by Карташов Денис Геннадійович

Задача:

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер дека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

Результат на C++

Результат на Java

Код на C++:

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

class Deque{
	private:
	int *a = new int [100];
	int size_;
	int front_;
	int back_;
	int capacity;
	void resize(int);
	public:
	Deque(): size_(0), front_(1), back_(0), capacity(100){}
	void push_back(int);
	void push_front(int);
	void pop_back();
	void pop_front();
	int size() const;
	int back() const;
	int front() const;
	void clear();
};

void Deque::resize(int newcapacity){  //Функция изменения размера.
	int* tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
	int j = front_;                     //Присваиваем начальное значение счетчику.
	for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
		tmp[i] = a[j];
		j = (j+1)%capacity;
	}
	tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
	delete []a;                   //Удаляем лишнюю память.
	a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
	capacity = newcapacity;       //Меняем значение вместимости.
	front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
	back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
}

void Deque::push_back(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	back_ = (back_ + 1)%capacity;
	a[back_] = b;
	size_++;
}
void Deque::push_front(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	front_ = (front_ - 1 + capacity)%capacity;
	a[front_] = b;
	size_++;
}

void Deque::pop_back(){
	back_ = (back_ - 1 + capacity)%capacity;
	size_--;
}
void Deque::pop_front(){
	front_ = (front_ + 1)%capacity;
	size_--;
}
int Deque::size() const{
	return size_;
}

int Deque::front() const{
	return a[front_];
}

int Deque::back() const{
	return a[back_];
}

void Deque::clear(){
	back_ = 0;
	front_ = 1;
	size_ = 0;
}
	
int main() {
	Deque a;
	string s;
	int n;
	while(cin >> s){
		if(s == "push_back"){
			cin >> n;
			a.push_back(n);
			cout << "ok\n";
		}
		else if(s == "push_front"){
			cin >> n;
			a.push_front(n);
			cout << "ok\n";
		}
		else if(s == "pop_back"){
			if(a.size()){
				cout << a.back() << endl;
				a.pop_back();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "pop_front"){
			if(a.size()){
				cout << a.front() << endl;
				a.pop_front();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "front"){
			if(a.size()){
				cout << a.front() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "back"){
			if(a.size()){
				cout << a.back() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "size"){
			cout << a.size() << endl;
		}
		else if(s == "clear"){
			cout << "ok\n";
			a.clear();
		}
		else if(s == "exit"){
			cout << "bye\n";
			return 0;
		}
	}
	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 <string>

using namespace std;

class Deque{

private:

int *a = new int [100];

int size_;

int front_;

int back_;

int capacity;

void resize(int);

public:

Deque(): size_(0), front_(1), back_(0), capacity(100){}

void push_back(int);

void push_front(int);

void pop_back();

void pop_front();

int size() const;

int back() const;

int front() const;

void clear();

};

void Deque::resize(int newcapacity){ //Функция изменения размера.

int* tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

tmp[size_ - 1] = a[back_]; //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.

delete []a; //Удаляем лишнюю память.

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

void Deque::push_back(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

void Deque::push_front(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

void Deque::pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

void Deque::pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

int Deque::size() const{

return size_;

}

int Deque::front() const{

return a[front_];

}

int Deque::back() const{

return a[back_];

}

void Deque::clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

int main() {

Deque a;

string s;

int n;

while(cin >> s){

if(s == "push_back"){

cin >> n;

a.push_back(n);

cout << "ok\n";

}

else if(s == "push_front"){

cin >> n;

a.push_front(n);

cout << "ok\n";

}

else if(s == "pop_back"){

if(a.size()){

cout << a.back() << endl;

a.pop_back();

}

else{

cout << "error\n";

}

else if(s == "pop_front"){

if(a.size()){

cout << a.front() << endl;

a.pop_front();

}

else{

cout << "error\n";

}

else if(s == "front"){

if(a.size()){

cout << a.front() << endl;

}

else{

cout << "error\n";

}

else if(s == "back"){

if(a.size()){

cout << a.back() << endl;

}

else{

cout << "error\n";

}

else if(s == "size"){

cout << a.size() << endl;

}

else if(s == "clear"){

cout << "ok\n";

a.clear();

}

else if(s == "exit"){

cout << "bye\n";

return 0;

}

return 0;

}

Код на Java:

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

 
class Deque{
	private int[] a = new int [100];
	private int size_;
	private int front_;
	private int back_;
	private int capacity;
	private void resize(int newcapacity){  //Функция изменения размера.
		int[] tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
		int j = front_;                     //Присваиваем начальное значение счетчику.
		for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
			tmp[i] = a[j];
			j = (j+1)%capacity;
		}
		tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
		a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
		capacity = newcapacity;       //Меняем значение вместимости.
		front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
		back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
	}
	public Deque()
	{
		size_ = 0; front_ = 1; back_ = 0; capacity = 100;
	}
	public void push_back(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		back_ = (back_ + 1)%capacity;
		a[back_] = b;
		size_++;
	}
	public void push_front(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		front_ = (front_ - 1 + capacity)%capacity;
		a[front_] = b;
		size_++;
	}
	public void pop_back(){
		back_ = (back_ - 1 + capacity)%capacity;
		size_--;
	}
	public void pop_front(){
		front_ = (front_ + 1)%capacity;
		size_--;
	}
	public int size(){
		return size_;
	}
	public int back(){
		return a[back_];
	}
	public int front(){
		return a[front_];	
	}
	public void clear(){
		back_ = 0;
		front_ = 1;
		size_ = 0;
	}
};

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		Deque a = new Deque();
		String s;
		String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};
		int n;
		am:while(true){
			s = in.next();
			if(s.equals(oper[0])){
				n = in.nextInt();
				a.push_back(n);
				out.println("ok");
			}
			else if(s.equals(oper[1])){
				n = in.nextInt();
				a.push_front(n);
				out.println("ok");
			}
			else if(s.equals(oper[2])){
				if(a.size() != 0){
					out.println(a.back());
					a.pop_back();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[3])){
				if(a.size() != 0){
					out.println(a.front());
					a.pop_front();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[4])){
				if(a.size() != 0){
					out.println(a.front());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[5])){
				if(a.size() != 0){
					out.println(a.back());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[6])){
				out.println(a.size());
			}
			else if(s.equals(oper[7])){
				out.println("ok");
				a.clear();
			}
			else if(s.equals(oper[8])){
				out.println("bye");
				//System.exit(0);
				break am;
			}
		}
		out.flush();
	}
}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Deque{

private int[] a = new int [100];

private int size_;

private int front_;

private int back_;

private int capacity;

private void resize(int newcapacity){ //Функция изменения размера.

int[] tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

public Deque()

{

size_ = 0; front_ = 1; back_ = 0; capacity = 100;

}

public void push_back(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

public void push_front(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

public void pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

public void pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

public int size(){

return size_;

}

public int back(){

return a[back_];

}

public int front(){

return a[front_];

}

public void clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

};

public class Main

{

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

Deque a = new Deque();

String s;

String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};

int n;

am:while(true){

s = in.next();

if(s.equals(oper[0])){

n = in.nextInt();

a.push_back(n);

out.println("ok");

}

else if(s.equals(oper[1])){

n = in.nextInt();

a.push_front(n);

out.println("ok");

}

else if(s.equals(oper[2])){

if(a.size() != 0){

out.println(a.back());

a.pop_back();

}

else{

out.println("error");

}

else if(s.equals(oper[3])){

if(a.size() != 0){

out.println(a.front());

a.pop_front();

}

else{

out.println("error");

}

else if(s.equals(oper[4])){

if(a.size() != 0){

out.println(a.front());

}

else{

out.println("error");

}

else if(s.equals(oper[5])){

if(a.size() != 0){

out.println(a.back());

}

else{

out.println("error");

}

else if(s.equals(oper[6])){

out.println(a.size());

}

else if(s.equals(oper[7])){

out.println("ok");

a.clear();

}

else if(s.equals(oper[8])){

out.println("bye");

//System.exit(0);

break am;

}

out.flush();

}

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

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