Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:

модифицировать [latex]i[/latex]-ый элемент последовательности
для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]

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

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, a_n[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:

[latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
[latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]

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

    #include <iostream>
    #include <cmath>
    using namespace std;
    struct data {
        int sum, pref, suff, ans;
    };
    data combine (data l, data r) {
        data res;
        res.sum = l.sum + r.sum;
        res.pref = max (l.pref, l.sum + r.pref);
        res.suff = max (r.suff, r.sum + l.suff);
        res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
        return res;
    }
    data make_data (int val) {
        data res;
        res.sum = val;
        res.pref = res.suff = res.ans = val;
        return res;
    }
    void build (int a[], int v, int tl, int tr, data t[]) {
        if (tl == tr)
            t[v] = make_data (a[tl]);
        else {
            int tm = (tl + tr) / 2;
            build (a, v*2, tl, tm, t);
            build (a, v*2+1, tm+1, tr, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    void update (int v, int tl, int tr, int pos, int new_val, data t[]) {
        if (tl == tr)
            t[v] = make_data (new_val);
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update (v*2, tl, tm, pos, new_val, t);
            else
                update (v*2+1, tm+1, tr, pos, new_val, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    data query (int v, int tl, int tr, int l, int r, data t[]) {
        if (l == tl && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        if (r <= tm)
            return query (v*2, tl, tm, l, r, t);
        if (l > tm)
            return query (v*2+1, tm+1, tr, l, r, t);
        return combine (
            query (v*2, tl, tm, l, tm, t),
            query (v*2+1, tm+1, tr, tm+1, r, t)
        );
    }
     
    int main() {
        int n, m, x, y;
        cin >> n;
        int* a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        data* t = new data[4*n];
        build(a, 1, 0, n-1, t);
        cin >> m ;
        bool oper;
        for(int i = 0; i < m; i++) {
            cin >> oper >> x >> y;
            if(!oper) {
                update (1, 0, n-1, x-1, y, t);
            } else if(oper) {
                cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;
     
            }
        }
        return 0;
    }

#include <iostream>

#include <cmath>

using namespace std;

struct data {

int sum, pref, suff, ans;

};

data combine (data l, data r) {

data res;

res.sum = l.sum + r.sum;

res.pref = max (l.pref, l.sum + r.pref);

res.suff = max (r.suff, r.sum + l.suff);

res.ans = max (max (l.ans, r.ans), l.suff + r.pref);

return res;

}

data make_data (int val) {

data res;

res.sum = val;

res.pref = res.suff = res.ans = val;

return res;

}

void build (int a[], int v, int tl, int tr, data t[]) {

if (tl == tr)

t[v] = make_data (a[tl]);

else {

int tm = (tl + tr) / 2;

build (a, v*2, tl, tm, t);

build (a, v*2+1, tm+1, tr, t);

t[v] = combine (t[v*2], t[v*2+1]);

}

void update (int v, int tl, int tr, int pos, int new_val, data t[]) {

if (tl == tr)

t[v] = make_data (new_val);

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, new_val, t);

else

update (v*2+1, tm+1, tr, pos, new_val, t);

t[v] = combine (t[v*2], t[v*2+1]);

}

data query (int v, int tl, int tr, int l, int r, data t[]) {

if (l == tl && tr == r)

return t[v];

int tm = (tl + tr) / 2;

if (r <= tm)

return query (v*2, tl, tm, l, r, t);

if (l > tm)

return query (v*2+1, tm+1, tr, l, r, t);

return combine (

query (v*2, tl, tm, l, tm, t),

query (v*2+1, tm+1, tr, tm+1, r, t)

);

}

int main() {

int n, m, x, y;

cin >> n;

int* a = new int[n];

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

cin >> a[i];

}

data* t = new data[4*n];

build(a, 1, 0, n-1, t);

cin >> m ;

bool oper;

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

cin >> oper >> x >> y;

if(!oper) {

update (1, 0, n-1, x-1, y, t);

} else if(oper) {

cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;

}

return 0;

}

Для запроса на выполнение программы нажать здесь.

Ссылка на использованный алгоритм.

Ссылка на засчитанное решение.

Related Images:

e-olimp 5079. Транзитивность ориентированного графа

11/05/2016 by Таня Корнилова

Задача e-olimp 5079.

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин [latex]u[/latex], [latex]v[/latex] и [latex]w[/latex] из того, что из [latex]u[/latex] в вершину [latex]v[/latex] ведет ребро и из вершины [latex]v[/latex] в вершину [latex]w[/latex] ведет ребро, следует, что из вершины [latex]u[/latex] в вершину [latex]w[/latex] ведет ребро.

Проверьте, что заданный ориентированный граф является транизитивным.

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

Входной файл содержит число [latex]n (1 \le n \le100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл YES если граф является транзитивным и NO в противном случае.

Тесты

Входные данные	Выходные данные
3 0 1 1 0 0 1 0 0 0	YES
3 0 1 1 1 0 0 0 1 0	NO

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool arr[n][n];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            // если существует ориентированное ребро, соединяющее вершины i и j
            if(arr[i][j]) { 
                for(int z = 0; z < n; z++) {
                    // если из вершины j в вершину z ведёт ребро, но из i в z - нет, то граф нетранзитивен
                    if(arr[j][z] && !arr[i][z]) { 
                        cout << "NO";
                        return 0;
                    }   
                }   
            }
        }
    }
    cout << "YES";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

bool arr[n][n];

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

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

cin >> arr[i][j];

}

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

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

// если существует ориентированное ребро, соединяющее вершины i и j

if(arr[i][j]) {

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

// если из вершины j в вершину z ведёт ребро, но из i в z - нет, то граф нетранзитивен

if(arr[j][z] && !arr[i][z]) {

cout << "NO";

return 0;

}

cout << "YES";

return 0;

}

Ссылка на засчитанное решение.
Для запроса на выполнение нажать здесь.

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если [latex]a[i][j] = 1[/latex], то из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро и из вершины [latex]j[/latex] в вершину [latex]z[/latex], то граф транзитивен, если есть ребро [latex]a[i][z][/latex].

Related Images:

e-olymp 6122. Простой стек

20/03/2016 by Таня Корнилова

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

push [latex]n[/latex] — Добавить в стек число [latex]n[/latex] (значение [latex]n[/latex] задается после команды). Вывести ok.
pop — Удалить из стека последний элемент. Программа должна вывести его значение.
back — Вывести значение последнего элемента, не удаляя его из стека.
size — Вывести количество элементов в стеке.
clear — Очистить стек и вывести ok.
exit — Вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Тесты

№	Входные данные	Выходные данные
1	push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye
2	push 7 size push 1 pop back exit push 4 pop	ok 1 ok 1 7 bye

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

#include <iostream>
#include <string>
using namespace std;
#define SIZE 100

struct stack {
    int storage[SIZE];
    int cursor = 0; // указатель на верхнюю незаполненную ячейку
    void push (int n) {
        storage[cursor] = n;
        cursor++;
    }
    int pop () {
        return storage[--cursor];
    }
    int back () {
        return storage[cursor-1];
    }
    unsigned int size () {
        return cursor;
    }
    void clear () {
        cursor = 0;
    }
};
int main () {
    stack s;
    string str;
    int n;
    while (cin >> str) {
        if (str == "push") {
            cin >> n;
            s.push(n);
            cout << "ok" << endl;
        }
        else if (str == "pop") cout << s.pop() << endl;
        else if (str == "back") cout << s.back() << endl;
        else if (str == "size") cout << s.size() << endl;
        else if (str == "clear") {
            s.clear();
            cout << "ok" << endl;
        }
        else if (str == "exit") {
            cout << "bye" << endl;
            break;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

#define SIZE 100

struct stack {

int storage[SIZE];

int cursor = 0; // указатель на верхнюю незаполненную ячейку

void push (int n) {

storage[cursor] = n;

cursor++;

}

int pop () {

return storage[--cursor];

}

int back () {

return storage[cursor-1];

}

unsigned int size () {

return cursor;

}

void clear () {

cursor = 0;

}

};

int main () {

stack s;

string str;

int n;

while (cin >> str) {

if (str == "push") {

cin >> n;

s.push(n);

cout << "ok" << endl;

}

else if (str == "pop") cout << s.pop() << endl;

else if (str == "back") cout << s.back() << endl;

else if (str == "size") cout << s.size() << endl;

else if (str == "clear") {

s.clear();

cout << "ok" << endl;

}

else if (str == "exit") {

cout << "bye" << endl;

break;

}

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Реализуем стек с помощью массива, указателя на на верхнюю незаполненную ячейку массива ([latex]cursor[/latex]) и функций, с помощью которых выполняются команды push, pop, back, size, clear:

функция push выполняет запись в ячейку с номером [latex]cursor[/latex] элемента [latex]n[/latex];
функция pop возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом удаляя его из стека;
функция back возвращает последний помещённый в стек элемент, то есть элемент с номером [latex]cursor-1[/latex], при этом не удаляя его из стека;
функция size возвращает значение [latex]cursor[/latex], то есть размер стека;
функция clear присваивает [latex]cursor[/latex] значение [latex]0[/latex].

Команда exit выполнена с помощью оператора [latex]break[/latex], который заканчивает выполнение цикла, в котором запрашиваются команды.

Ссылка на засчитанное решение.

Related Images:

А286

13/03/2016 by Таня Корнилова

Задача

Даны целые числа [latex]a_1,\cdots, a_{n}[/latex]. Получить новую последовательность, выбросив из исходной все члены со значением [latex]max(a_1,\cdots,a_{n})[/latex].

Тесты

№	Входные данные	Выходные данные
1	0 0 0 0 0 0 0 0
2	998 103678 3333 800000 542 2 48 132 9 745	998 103678 3333 542 2 48 132 9 745
3	1 2 42 -138 0 99 1 242 70 21	1 2 42 -138 0 99 1 70 21
4	-144 -789342454657 -155 -923 -7	-144 -789342454657 -155 -923
5	8 8 8 8 11 11 11 11 8 8 8 8	8 8 8 8 8 8 8 8

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

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	long long a;
	long long n = 0; // номер максимального по значению элемента
	vector <long long> x;
	while (cin >> a) x.push_back(a);
	int counter = 0; // счётчик равных по значению элементов последовательности
	for (int i = 0; i < x.size(); i++) { // находим элемент с максимальным значением
		if (x[i] > x[n]) n = i; 
		else if (x[i] == x[n]) counter++;
	}
	if (counter != x.size()) { // если вся последовательность не состоит из равных элементов
		long long temp = x[n];
		for (int i = 0; i < x.size(); i++) { // удаляем все элементы с максимальным значением
			if (x[i] == temp) {
				x.erase(x.begin() + i);
				i--;
			}
		}
	} else x.clear(); // если последовательность из равных чисел
	for (int i = 0; i < x.size(); i++) {
		cout << x[i] << " ";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

long long a;

long long n = 0; // номер максимального по значению элемента

vector <long long> x;

while (cin >> a) x.push_back(a);

int counter = 0; // счётчик равных по значению элементов последовательности

for (int i = 0; i < x.size(); i++) { // находим элемент с максимальным значением

if (x[i] > x[n]) n = i;

else if (x[i] == x[n]) counter++;

}

if (counter != x.size()) { // если вся последовательность не состоит из равных элементов

long long temp = x[n];

for (int i = 0; i < x.size(); i++) { // удаляем все элементы с максимальным значением

if (x[i] == temp) {

x.erase(x.begin() + i);

i--;

}

} else x.clear(); // если последовательность из равных чисел

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

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

}

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

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

Related Images:

Mif 18

20/12/2015 by Таня Корнилова

Задача Mif 18.

Условие

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

Тесты

Входные данные	Выходные данные
0	zero
-7284	minus seven thousand two hundred and eighty-four
900000000000000010	nine hundred billiard ten
4561230057773	four billion five hundred and sixty-one milliard two hundred and thirty million fifty-seven thousand seven hundred and seventy-three
599999990999999900	five hundred and ninety-nine billiard nine hundred and ninety-nine billion nine hundred and ninety milliard nine hundred and ninety-nine million nine hundred and ninety-nine thousand nine hundred

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

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

void number (long long n) {
	if(abs(n) < 1000){// сотни, десятки, единицы
		if(n < 0) { 
			cout << "minus ";
			n = abs(n);
			number(n);
		} 
		else if(n == 0) cout << "zero";
		else {// натуральные числа
			int safe = n;// сохраняем значение числа, так как дальше его изменяем,
			if((n / 100) != 0) {// если есть сотни
				n = n / 100;
			}
			switch(n){
				case 1: cout << "one "; break; 
				case 2: cout << "two "; break; 
				case 3: cout << "three "; break; 
				case 4: cout << "four "; break; 
				case 5: cout << "five "; break;
				case 6: cout << "six "; break; 
				case 7: cout << "seven "; break; 
				case 8: cout << "eight "; break; 
				case 9: cout << "nine "; break; 
			}
			if(((safe / 100) == 0) && ((safe % 100) / 10 == 0)){
				n = -1e90;// чтобы не продолжать выводить нули
			}
			if((safe / 100) > 0) {
				cout << "hundred ";
				n = safe % 100;
				safe = 0;
				if(n > 0){
				cout << "and ";
				}
			}
			if((n / 10) == 0){
				number(n);
			} else if((n / 10) == 1) {
				switch(n) {
					case 10: cout << "ten "; break;
					case 11: cout << "eleven "; break;
					case 12: cout << "twelve "; break;
					case 13: cout << "thirteen "; break;
					case 14: cout << "fourteen "; break;
					case 15: cout << "fifteen "; break;
					case 16: cout << "sixteen "; break;
					case 17: cout << "seventeen "; break;
					case 18: cout << "eighteen "; break;
					case 19: cout << "nineteen "; break;
				}
			} else if((n / 10) > 1) {
				switch(n / 10) {
					case 2: cout << "twenty"; break; 
					case 3: cout << "thirty"; break; 
					case 4: cout << "forty"; break; 
					case 5: cout << "fifty"; break;
					case 6: cout << "sixty"; break; 
					case 7: cout << "seventy"; break; 
					case 8: cout << "eighty"; break; 
					case 9: cout << "ninety"; break;
				}
				n = n % 10;
				if(n != 0){
					cout << "-";
					number(n);
				}
			} 
		}
	} else {// выводим тысячи, миллионы, миллиарды и т.д.	
		if(n >= 1e15) {
			number(n / 1e15);
			cout << "billiard ";
			n %= (long long) 1e15;
			if(n != 0) number(n);
		} else if(n >= 1e12) {
			number(n / 1e12);
			cout << "billion ";
			n %= (long long) 1e12;
			if(n != 0) number(n);
		} else if(n >= 1e9) {
			number(n / 1e9);
			cout << "milliard ";
			n %= (int) 1e9;
			if(n != 0) number(n);
		} else if(n >= 1e6) {
			number(n / 1e6);
			cout << "million ";
			n %= (int) 1e6;
			if(n != 0) number(n);
		} else if(n >= 1e3) {
			number(n / 1e3);
			cout << "thousand ";
			n %= (int) 1e3;
			if(n != 0) number(n);// чтоб не выводить ноль после тысяч
		}
	}
}



int main() {
	long long n;
	cin >> n;
	number(n);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include <iostream>

#include <cmath>

using namespace std;

void number (long long n) {

if(abs(n) < 1000){// сотни, десятки, единицы

if(n < 0) {

cout << "minus ";

n = abs(n);

number(n);

}

else if(n == 0) cout << "zero";

else {// натуральные числа

int safe = n;// сохраняем значение числа, так как дальше его изменяем,

if((n / 100) != 0) {// если есть сотни

n = n / 100;

}

switch(n){

case 1: cout << "one "; break;

case 2: cout << "two "; break;

case 3: cout << "three "; break;

case 4: cout << "four "; break;

case 5: cout << "five "; break;

case 6: cout << "six "; break;

case 7: cout << "seven "; break;

case 8: cout << "eight "; break;

case 9: cout << "nine "; break;

}

if(((safe / 100) == 0) && ((safe % 100) / 10 == 0)){

n = -1e90;// чтобы не продолжать выводить нули

}

if((safe / 100) > 0) {

cout << "hundred ";

n = safe % 100;

safe = 0;

if(n > 0){

cout << "and ";

}

if((n / 10) == 0){

number(n);

} else if((n / 10) == 1) {

switch(n) {

case 10: cout << "ten "; break;

case 11: cout << "eleven "; break;

case 12: cout << "twelve "; break;

case 13: cout << "thirteen "; break;

case 14: cout << "fourteen "; break;

case 15: cout << "fifteen "; break;

case 16: cout << "sixteen "; break;

case 17: cout << "seventeen "; break;

case 18: cout << "eighteen "; break;

case 19: cout << "nineteen "; break;

}

} else if((n / 10) > 1) {

switch(n / 10) {

case 2: cout << "twenty"; break;

case 3: cout << "thirty"; break;

case 4: cout << "forty"; break;

case 5: cout << "fifty"; break;

case 6: cout << "sixty"; break;

case 7: cout << "seventy"; break;

case 8: cout << "eighty"; break;

case 9: cout << "ninety"; break;

}

n = n % 10;

if(n != 0){

cout << "-";

number(n);

}

} else {// выводим тысячи, миллионы, миллиарды и т.д.

if(n >= 1e15) {

number(n / 1e15);

cout << "billiard ";

n %= (long long) 1e15;

if(n != 0) number(n);

} else if(n >= 1e12) {

number(n / 1e12);

cout << "billion ";

n %= (long long) 1e12;

if(n != 0) number(n);

} else if(n >= 1e9) {

number(n / 1e9);

cout << "milliard ";

n %= (int) 1e9;

if(n != 0) number(n);

} else if(n >= 1e6) {

number(n / 1e6);

cout << "million ";

n %= (int) 1e6;

if(n != 0) number(n);

} else if(n >= 1e3) {

number(n / 1e3);

cout << "thousand ";

n %= (int) 1e3;

if(n != 0) number(n);// чтоб не выводить ноль после тысяч

}

int main() {

long long n;

cin >> n;

number(n);

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Данная программа выводит число «по частям», то есть вначале триллионы, затем биллиарды, биллионы и т.д. до единиц (за условием их наличия). Если число отрицательное, то она выводит «минус» и его абсолютную величину.

При выполнениии задания я воспользовалась длинной шкалой наименования чисел.

Программа выводит целые числа в промежутке [latex](-10^{19}; 10^{19})[/latex].

Related Images:

e-olymp 378. Таинственная записка

27/11/2015 by Таня Корнилова

Задача e-olymp 378.

Условие

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

Закодированное сообщение: HPC PJVYMIY

Декодированное сообщение: ACM CONTEST

В этом примере выполнены следующие замены: H=A, P=C, C=M, J=O, V=N, Y=T, M=E и I=S.

Чтобы не заниматься кодированием и декодированием вручную, подруги просят Вас написать программу. Помогите девочкам!

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

В первой строке входного файла записано закодированное сообщение. Вторая строка — 26 латинских букв верхнего регистра, представляющих собой код для соответствующего символа алфавита: первый символ дает код для A, второй для B и так далее. Используются только буквы верхнего регистра. В закодированном сообщении могут появиться пробелы, которые должны быть сохранены в выходной строке.

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

В выходной файл вывести одну строку, в которой содержится расшифрованное сообщение.

Тесты

Входные данные	Выходные данные
HPC PJVYMIY BLMRGJIASOPZEFDCKWYHUNXQTV	ACM CONTEST
FDY GAI BG UKMY KIMHOTSQYRLCUZPAGWJNBVDXEF	THE SKY IS BLUE
LJBSLJL IJWWDEJ KCFAGWRZMEXDNUYHVBOIJLSTPQ	DECODED MESSAGE

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

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

        //функция, которая определяет номер введённого символа в данном массиве
        int find(const char* str, char c) {
        	for(int i = 0; str[i] != '\0'; i++) {
        		if(str[i] == c) {
        			return i;
        		}
        	}
        	return -1;//если в введённой строке есть пробелы
        }
     
        int main() {
        	int n = 27, k = 1024;
        	const char *a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        	char b[k];
        	char c[n];
        	cin.getline(b, k);
        	cin.getline(c, n);
        	for(int i = 0; b[i] != '\0'; i++) {
        		int index = find(a, b[i]);
        		if(index != -1) {
        			cout << c[index];
        		} else {
        			cout << b[i];
        		}
        	}
        	return 0;
        }

#include <iostream>

#include <cstring>

using namespace std;

//функция, которая определяет номер введённого символа в данном массиве

int find(const char* str, char c) {

for(int i = 0; str[i] != '\0'; i++) {

if(str[i] == c) {

return i;

}

return -1;//если в введённой строке есть пробелы

}

int main() {

int n = 27, k = 1024;

const char *a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

char b[k];

char c[n];

cin.getline(b, k);

cin.getline(c, n);

for(int i = 0; b[i] != '\0'; i++) {

int index = find(a, b[i]);

if(index != -1) {

cout << c[index];

} else {

cout << b[i];

}

return 0;

}

Для запроса на выполнение нажать здесь.

Ссылка на засчитанное решение.

Код программы с использованнием класса «string»

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

int main() {
	string b, c;
	getline(cin, b);
	getline(cin, c);
	for(int i = 0; i < b.length(); i++) {
		cout << (b[i] - 'A' < 0? ' ': c[b[i] - 'A']);
	}
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string b, c;

getline(cin, b);

getline(cin, c);

for(int i = 0; i < b.length(); i++) {

cout << (b[i] - 'A' < 0? ' ': c[b[i] - 'A']);

}

return 0;

}

Для запроса на выполнение нажать здесь.

Ссылка на засчитанное решение.

Решение

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

Related Images:

MLoops 10

19/11/2015 by Таня Корнилова

Задача MLoops 10

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

123...k...321+123...k...3
23...k...321+123...k...32
3...k...321+123...k...321
...k...321+123...k...321+
..k...321+123...k...321+1
.k...321+123...k...321+12
k...321+123...k...321+123
...321+123...k...321+123.

123...k...321+123...k...3

23...k...321+123...k...32

3...k...321+123...k...321

...k...321+123...k...321+

..k...321+123...k...321+1

.k...321+123...k...321+12

k...321+123...k...321+123

...321+123...k...321+123.

Тесты

Входные данные	Выходные данные
3 6 2	121+12 21+121 1+121+
5 5 4	12343 23432 34321 4321+ 321+1
4 19 9	12345678987654321+1 2345678987654321+12 345678987654321+123 45678987654321+1234
7 14 10	123456789109876 234567891098765 345678910987654 456789109876543 567891098765432 678910987654321 78910987654321+

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

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

int main() {
	int m, n, k;
	cin >> m >> n >> k;
	for (int i = 1; i <= m; i++) {
		int num = i % (2*k) <= k ? i % (2*k) : 2*k - i % (2*k);// определяем первый символ каждой строки
		if (num == 2*k) num = 0;
		bool up = i % (2*k) < k ? true : false;// определяем возрастает или убывает последовательность
		for (int j = 1; j <= n; j ++) {
			if (num == 0) cout << "+";
			else cout << num;
			if (num == k) up = false;
			else if (num == 0) up = true;
			num = up ? num + 1 : num - 1;
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int m, n, k;

cin >> m >> n >> k;

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

int num = i % (2*k) <= k ? i % (2*k) : 2*k - i % (2*k);// определяем первый символ каждой строки

if (num == 2*k) num = 0;

bool up = i % (2*k) < k ? true : false;// определяем возрастает или убывает последовательность

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

if (num == 0) cout << "+";

else cout << num;

if (num == k) up = false;

else if (num == 0) up = true;

num = up ? num + 1 : num - 1;

}

cout << endl;

}

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Дано [latex]m[/latex] строк, в каждой из которых определены последовательности, каждая из которых состоит из чисел, возрастающих от 1 до [latex]k[/latex], затем спадающих до 1 и знак «+». Закономерность данной задачи состоит в последовательном сдвиге вправо каждой последующей строки и её выведении с элемента стоящего на первом месте.

Последовательность знаков каждой строки повторяется через каждые [latex]2k[/latex] знаков. Именно поэтому на [latex]2k[/latex]-ом месте будет стоять «+» (так как отсчёт начинается с 1, а не с 0).

Определяем первый знак каждой строки сравнением номера строки [latex]i[/latex] с [latex]k[/latex]: если он меньше или равен [latex]k[/latex], то он и будет первым знаком данной строки, в противном случае — первым знаком будет [latex](2k — i)[/latex].

Затем выводим цифры каждой строки:

если цифра, с которой ведётся отсчёт данной строки, меньше [latex]k[/latex], то увеличиваем каждую последующую цифру (за «+» следует 1 и далее аналогично этому условию);
если цифра равна [latex]k[/latex], то уменьшаем последующие цифры.

Related Images:

MLoop 12

02/11/2015 by Таня Корнилова

Задача. MLoop 12

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x) = \arctan x[/latex]. При вычислениях допустимо использовать только арифметические операции.

Тесты

Входные данные			Выходные данные
№	Точность	Аргумент	[latex]\arctan x[/latex]	Погрешность
1	1	0.5	0.5	0.0363524
2	10	0.82	0.669293	0.0175249
3	100	0.77	0.652823	0.00335552
4	1000	1	0.666667	0.118731

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

#include <iostream>
#include <cmath>
using namespace std;
 
double myAtan(double x, int n) {
	double a = x;
	double sum = a;
	double b = a;
	double E = 1 / n;
	for(int i = 1; a > E; i++){
		b *= - x * x;
		a *= b / (2 * i + 1);
		sum += a;
	}
	return sum;
}
 
int main() {
	double x;
	int n;
	cin >> x >> n;
	cout << "my arctg: " << myAtan(x, n) << endl;
    cout << "arctg: " << atan(x) << endl;
    cout << "|arctg - my arctg| = " << abs(myAtan(x, n) - atan(x)) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double myAtan(double x, int n) {

double a = x;

double sum = a;

double b = a;

double E = 1 / n;

for(int i = 1; a > E; i++){

b *= - x * x;

a *= b / (2 * i + 1);

sum += a;

}

return sum;

}

int main() {

double x;

int n;

cin >> x >> n;

cout << "my arctg: " << myAtan(x, n) << endl;

cout << "arctg: " << atan(x) << endl;

cout << "|arctg - my arctg| = " << abs(myAtan(x, n) - atan(x)) << endl;

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Для того, чтобы найти приблизительное значение [latex]\arctan x[/latex] возпользуемся формулой ряда Тейлора: [latex]\arctan x = x — \frac{x^3}{3} + \frac{x^5}{5} -[/latex] … [latex]= \sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}\cdot x^{2n+1}[/latex] для всех [latex]|x| \le 1[/latex]. Представим каждый член суммы как [latex]a_n = \frac{(-1)^n\cdot a^{2n+1}}{2n+1}[/latex], и будем рекурсивно вычислять числитель данной дроби [latex]m_n = m_{n-1} \cdot (- a^2)[/latex]. Тогда, будем находить значение очередного члена ряда по формуле [latex]a_n = \frac{m_n}{2n + 1}[/latex], пока [latex]a_n > \frac{1}{\varepsilon}[/latex].

Related Images:

Mif 17.13

07/10/2015 by Таня Корнилова

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K)	Выходные данные
(3;4)	no
(1;1)	yes
(1;4)	yes
(3;0)	yes
(0;6)	no
(-13; -3)	no
(-4.5; -3)	yes

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

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

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){
	return (k.x - a.x) * (b.y - a.y) - (k.y - a.y) * (b.x - a.x);
} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){
	return g(a, b, c) * g(a, b, k) >= 0;
} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {
	struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };
	double x, y;
	struct point k { k.x, k.y };
	cin >> k.x >> k.y;
	cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");
	return 0;

}

#include <iostream>

#include <stdio.h>

using namespace std;

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){

return (k.x - a.x) * (b.y - a.y) - (k.y - a.y) * (b.x - a.x);

} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){

return g(a, b, c) * g(a, b, k) >= 0;

} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {

struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };

double x, y;

struct point k { k.x, k.y };

cin >> k.x >> k.y;

cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

Related Images:

e-olymp 10. Садовник

07/10/2015 by Таня Корнилова

Задача e-olymp №10

Ссылка на засчитанное решение.

Условие

Садовник посадил за день [latex]n[/latex] деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то [latex]k[/latex]-го дня.

Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил [latex]\frac{1}{n}[/latex] часть воды из ведра, в предпоследний [latex]\frac{1}{n-1}[/latex]часть, и т.д., а всего под каждое из деревьев вылил не более, чем по половине ведра воды?

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

Количество деревьев [latex]n[/latex]. [latex]0 < n \le 1000000[/latex]

Тесты

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

(количество деревьев)

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

(искомое количество дней)

1000000

606531

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

#include <iostream>
using namespace std;

int main() {
	int n, k;
	double waterPerTree = 0;
	cin >> n;
	int days = 0;
	while(waterPerTree <= 0.5) {
		waterPerTree += (double) 1 / (n - days++);
	}
	k = n - days +1;
	cout << k;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

double waterPerTree = 0;

cin >> n;

int days = 0;

while(waterPerTree <= 0.5) {

waterPerTree += (double) 1 / (n - days++);

}

k = n - days +1;

cout << k;

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Пускай в переменной [latex]days[/latex] будет храниться количество дней, в которые садовник поливал деревья, но так как отсчёт начинает с [latex]days = 0[/latex], ([latex]\frac{1}{n}[/latex]), то количество всех дней, когда садовник поливал деревья будет равно максимальному значению [latex]days[/latex] в цикле плюс 1; в переменной [latex]waterPerTree[/latex] — количество вёдер воды, вылитых на одно дерево. Количество вёдер воды, вылитых под одно дерево в определённый день: [latex]\frac{1}{n — days}[/latex]. Так как под каждое дерево садовник вылил не больше [latex]\frac{1}{2}[/latex] ведра воды, то будем выполнять цикл, пока [latex]waterPerTree[/latex] не будет равно этому значению.

Чтоб найти количество дней, на протяжении которых садовник поливал деревья, разделим количество воды, потраченное садовником за всё время поливки [latex]\frac{1}{2}[/latex] на количество вёдер воды, вылитых под одно дерево в определённый день [latex]\frac{1}{n — days}[/latex]. Тогда получим, что [latex]\frac{n — days}{2}[/latex].

По условию задачи, садовник должен был вылить по ведру воды под каждое деревцо, но вылил всего по половине из-за дождя. Из этого следует, что количество воды, выпавшей на каждое деревцо, пиблизительно равно [latex]\frac{1}{2}[/latex] ведра воды. Тогда если всего под каждым деревом по 1 ведру воды за [latex]x[/latex] дней, а садовник вылил по [latex]\frac{1}{2}[/latex] ведра воды за [latex]days + 1[/latex] дней, то [latex]x = 2n — 2days[/latex]. В итоге, [latex]k = \frac{1}{2}x = n — days[/latex]. Но, так как в последнем действии цикла вычисленное [latex]waterPerTree[/latex] будет больше [latex]\frac{1}{2}[/latex], то [latex]k = n — (days — 1)[/latex].

Related Images:

Mif13

30/09/2015 by Таня Корнилова

Задача Mif 13. Фазовая диаграмма воды

Фазовая диаграмма воды

Условие

По заданным значениям температуры [latex]t[/latex]и давления [latex]p[/latex] определите в каком состоянии находится вода. Для решения воспользуйтесь фазовой диаграммой воды и её приближённым описанием.

Тесты

Входные данные		Выходные данные
[latex]p[/latex](Па)	[latex]t[/latex](К)	Выходные данные
0	0	Solid
103856284537	623	Solid
302758463	333	Liquid
423	600	Vapor
8827443265	891	Supercritical water

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

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

int main() {
	long long p, t; //задаём переменные давления и температуры воды
	cin >> p >> t;
	if((0 <= p && p < pow(10,10)) &&
		(0 <= t && t <= 300) ||
		(pow(10,10) <= p &&
		p < pow(10,11)) &&
		(0 <= t && t <= 600) || 
		(pow(10,11) <= p &&
		p <= pow(10,12)) && 
		(0 <= t && t <= 1000))
		 cout << "Solid";
	else if((pow(10,6) < p && p < pow(10,10)) &&
		(300 < t && t <= 600))
		cout << "Liquid"; 
	else if((0 <= p && 
		p <= pow(10,6)) && 
		(300 < t && t <= 600) || 
		(0 <= p && p <= pow(10,7)) &&
		(600 < t && t <= 1000))
		cout << "Vapor";
	else if((pow(10,7) < p && 
		p < pow(10,11)) &&
		(600  < t && t <= 1000))
		cout << "Supercritical water";
	else {cout <<"not exist";}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long long p, t; //задаём переменные давления и температуры воды

cin >> p >> t;

if((0 <= p && p < pow(10,10)) &&

(0 <= t && t <= 300) ||

(pow(10,10) <= p &&

p < pow(10,11)) &&

(0 <= t && t <= 600) ||

(pow(10,11) <= p &&

p <= pow(10,12)) &&

(0 <= t && t <= 1000))

cout << "Solid";

else if((pow(10,6) < p && p < pow(10,10)) &&

(300 < t && t <= 600))

cout << "Liquid";

else if((0 <= p &&

p <= pow(10,6)) &&

(300 < t && t <= 600) ||

(0 <= p && p <= pow(10,7)) &&

(600 < t && t <= 1000))

cout << "Vapor";

else if((pow(10,7) < p &&

p < pow(10,11)) &&

(600 < t && t <= 1000))

cout << "Supercritical water";

else {cout <<"not exist";}

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

Пользуясь фазовой диаграммой воды, сравниваем значение введённого [latex]p[/latex](Па) и [latex]t[/latex](К) со значениями, при которых вода в жидком, твёрдом. газообразном и сверхкитическом жидком состоянии.

Related Images:

e-olymp 388. Превращение

27/09/2015 by Таня Корнилова

Задача e-olimp.com №388

Ссылка на засчитанное решение.

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.

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

Число N (1 ≤ N ≤ 10⁹).

Тесты

Входные данные(N)	Выходные данные
11	6
43	9
1	0

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

#include <iostream>
using namespace std;

int main() {
	int N, counter=0;
	cin >> N;
	while(N!=1){
		counter++;
		if(N%2==0){ 
			N = N/2;
		} 
		else{
			N++;
		}
	}		
	cout << counter << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, counter=0;

cin >> N;

while(N!=1){

counter++;

if(N%2==0){

N = N/2;

}

else{

N++;

}

cout << counter << endl;

return 0;

}

Для запроса на выполнение нажать здесь .

Решение

Пусть [latex]N[/latex] — это число, которое мы будем изменять, а [latex]counter[/latex] — количество превращений. Цикл должен выполняться до того момента, пока [latex]N \neq 1[/latex]. Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число — чётное, то делим его на 2, в противном случае — добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

Related Images:

ML13

23/09/2015 by Таня Корнилова

Условие:

Дана сторона равностороннего треугольника. Найти площадь этого треугольника.

Тесты:

Входные данные	Выходные данные
5	2.1650635094
1.7237891231	0.74642258566
9223372036854773806	3.9938372461e+18

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

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

int main() {
	long double a, s;
	cin >> a;
	s = sqr(a) * 1.7320508075 / 4;
	cout.precision(11);//Выводим площадь треугольника до 10 (включительно) знака после запятой
	cout << s << endl;
	return 0;
}

#include <iostream>

#include <cmath>

#define sqr

using namespace std;

int main() {

long double a, s;

cin >> a;

s = sqr(a) * 1.7320508075 / 4;

cout.precision(11);//Выводим площадь треугольника до 10 (включительно) знака после запятой

cout << s << endl;

return 0;

}

Для запроса на выполнение нажать здесь.

Решение:

Пусть [latex]a[/latex] — длина стороны равносторонннего треугольника, а [latex]s[/latex] — площадь. Тогда [latex]s = \frac{a^2\sqrt{3}}{4}[/latex].

Формула для нахождения площади равностороннего треугольника.

Related Images:

e-olymp 67. New food for Anfisa — 2

14/09/2015 by Таня Корнилова

Задача e-olimp.com №67

Ссылка на засчитанное решение.

Условие:

При разрезании сыра в задаче «Сыр для Анфисы» у хозяина оставались куски сыра в виде прямоугольного параллелепипеда с разными целыми длинами сторон. Готовя новое блюдо из сыра для Анфисы хозяину приходилось разрезать эти куски на кубики со стороной 1. Какое наименьшее количество разрезов приходилось ему делать для того, чтобы разрезать заданные куски сыра, если он каждый раз разрезал один кусок сыра на две части.

Тесты

Входные данные			Выходные данные
a	b	c	Выходные данные
2	3	4	23
1	2	3	5

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

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

int main() {
	long A, B, C;
	cin >> A >> B >> C;
	cout << (A*B*C - 1);
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long A, B, C;

cin >> A >> B >> C;

cout << (A*B*C - 1);

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

При разрезании сторон a, b, c мы получаем a, b, c количество частей соответственно. Следовательно, при разрезании стороны A, мы выполняем [latex](a-1)[/latex] разрезов. Тогда, при разрезании стороны B, делаем [latex]a*(b-1)[/latex]; при разрезании стороны C — [latex]a*b*(c-1)[/latex] соответственно. Всего мы совершаем [latex](a-1)+a*(b-1)+a*b*(c-1)[/latex] разрезов. В итоге, получаем формулу [latex]a*b*c — 1[/latex].