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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тесты

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

Реализация

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

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

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

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

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

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

#include <iostream>

#include <algorithm>

using namespace std;

struct ticket {

int id, validity, price;

};

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

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

int ticketsCount = 0;

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

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

ticketsCount++;

}

while(ticketsCount > validity) {

int cheapestTicketPosition = -1;

int cheapestTicketPrice = 101;

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

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

cheapestTicketPrice = tickets[i].price;

cheapestTicketPosition = i;

}

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

ticketsCount--;

}

return count;

}

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

return t1.id < t2.id;

}

int main() {

int count;

cin >> count;

ticket tickets[count];

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

tickets[i].id = i;

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

}

count = cutDown(tickets, count);

sort(tickets, tickets + count, comparator);

int maxProfit = 0;

do {

int profit = 0;

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

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

}

maxProfit = max(profit, maxProfit);

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

cout << maxProfit << endl;

return 0;

}

Related Images:

e-olymp 912. Количество предложений

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

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

e-olymp 912. Количество предложений

Определить количество предложений в заданном фрагменте текста.

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

В единственной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.

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

Единственное число — количество предложений в фрагменте.

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

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

Тесты

Входные данные	Выходные данные
Hello, World!	1
Those lips that Love’s own hand did make Breathed forth the sound that said ‘I hate,’ To me that languish’d for her sake: But when she saw my woeful state, Straight in her heart did mercy come, Chiding that tongue that ever sweet Was used in giving gentle doom, And taught it thus anew to greet: ‘I hate’ she alter’d with an end, That follow’d it as gentle day Doth follow night, who like a fiend From heaven to hell is flown away; ‘I hate’ from hate away she threw, And saved my life, saying — ‘not you.’	1
Winter…	1
Winter	0

Реализация

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

#include <iostream>
using namespace std;

bool isNeededChar(char c) {
	switch(c) {
		case '.':
		case '!':
		case '?':
			return true;
		default:
			return false;
	}
}

int main() {
	int counter = 0;
	string text;
	getline(cin, text);
	for(int i = 1; i < text.length(); i++) {
		if(isNeededChar(text.at(i))) {
			if(!isNeededChar(text.at(i - 1))) {
				counter++;
			}
		}
	}
	cout << counter << endl;
	return 0;
}

#include <iostream>

using namespace std;

bool isNeededChar(char c) {

switch(c) {

case '.':

case '!':

case '?':

return true;

default:

return false;

}

int main() {

int counter = 0;

string text;

getline(cin, text);

for(int i = 1; i < text.length(); i++) {

if(isNeededChar(text.at(i))) {

if(!isNeededChar(text.at(i - 1))) {

counter++;

}

cout << counter << endl;

return 0;

}

Related Images:

e-olymp 7. Римские числа

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

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

e-olymp 7. Римские числа

Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.
M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.

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

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

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

Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами.

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

Считываем два числа и представляем каждое из них в десятичной системе счисления. Чтобы перевести число из римской системы в десятичную, нужно изначально считать, что в десятичной системе оно равно нулю. Это число будет нашим результатом. Далее, нужно перебрать все цифры римского числа, следуя таким правилам:

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

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

Вспомогательные числа
В римской системе счисления	В десятичной системе счисления
1	I
4	IV
5	V
9	IX
10	X
40	XL
50	L
90	XC
100	C
400	CD
500	D
900	CM
1000	M

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

Тесты

Входные данные	Выходные данные
I+I	II
IV+VIII	XII
MM+CXC	MMCXC
CXCIX+I	CC

Реализация

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

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

int parse(char digit) {
	int result;
	switch(digit) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0;
	}
	return result;
}

int parse(char *number) {
	int result = 0, previous = parse(number[0]), current;
	for(int i = 1; (current = parse(number[i])) != 0; i++) {
		result += previous < current ? -previous : previous;
		previous = current;
	}
	result += previous;
	return result;
}

void print(int number) {
	char result[1000]{'\0'};
	const int values[] = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
	const char *symbols[] = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
	int counter = sizeof(symbols) / sizeof(symbols[0]) - 1 // last array element
	while(counter >= 0) {
		while(number >= values[counter]) {
			number -= values[counter];
			strcat(result, symbols[counter]);
		}
		counter--;
	}
	cout << result << endl;
}

int main() {
	char line[1000];
	cin >> line;
	char *a = strtok(line, "+");
	char *b = strtok(NULL, "");
	print(parse(a) + parse(b));
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int parse(char digit) {

int result;

switch(digit) {

case 'I': result = 1; break;

case 'V': result = 5; break;

case 'X': result = 10; break;

case 'L': result = 50; break;

case 'C': result = 100; break;

case 'D': result = 500; break;

case 'M': result = 1000; break;

default: result = 0;

}

return result;

}

int parse(char *number) {

int result = 0, previous = parse(number[0]), current;

for(int i = 1; (current = parse(number[i])) != 0; i++) {

result += previous < current ? -previous : previous;

previous = current;

}

result += previous;

return result;

}

void print(int number) {

char result[1000]{'\0'};

const int values[] = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };

const char *symbols[] = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };

int counter = sizeof(symbols) / sizeof(symbols[0]) - 1 // last array element

while(counter >= 0) {

while(number >= values[counter]) {

number -= values[counter];

strcat(result, symbols[counter]);

}

counter--;

}

cout << result << endl;

}

int main() {

char line[1000];

cin >> line;

char *a = strtok(line, "+");

char *b = strtok(NULL, "");

print(parse(a) + parse(b));

return 0;

}

Related Images:

MLoops 14

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

MLoops14.

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

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

123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2
++++++3++++++3++++++3++++++3
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++k++++++k++++++k++++++k
123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

++++++3++++++3++++++3++++++3

++++++.++++++.++++++.++++++.

++++++k++++++k++++++k++++++k

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

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

Легко заметить, что строки с номерами [latex]1 + i \left( k + 1 \right), i \in \mathbb{N}_0[/latex] состоят из натуральных чисел от 1 до k. Также в таблице есть столбцы, совпадающие с первой строкой. Все остальные клетки заполнены символом «+».

Тесты

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

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

[latex]n[/latex]

[latex]m[/latex]

[latex]k[/latex]

1
1

11111

121
+1+
+2+
121

121

+1+

+2+

121

1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++
1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++
+++++++++++10+++++++++++10+++++++
+++++++++++11+++++++++++11+++++++
123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

+++++++++++10+++++++++++10+++++++

+++++++++++11+++++++++++11+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

Реализация

ideone: ссылка

#include <iostream>
using namespace std;

struct point {
	
	int abscissa, ordinate;
	
	point() {
	    abscissa = 0;
	    ordinate = 0;
	}
	
	point(int x, int y) {
		abscissa = x;
		ordinate = y;
	}
	
	void setX(int x) {
	    abscissa = x;
	}
	
	void setY(int y) {
	    ordinate = y;
	}
	
	int getX() {
		return abscissa;
	}
	
	int getY() {
		return ordinate;
	}
	
};

struct size {
	
	int width, height;
	
	size() {
	    width = 0;
	    height = 0;
	}
	
	size(int w, int h) {
		width = w;
		height = h;
	}
	
	int getWidth() {
		return width;
	}
	
	int getHeight() {
		return height;
	}
	
};

struct screen {
	
	size dimension; // dimension of the screen
	point cursor; // position of the cursor
	char **arr; // array that represents characters on the screen
	
	// allocates the memory for the array and sets its dimension
	screen(size d) {
		dimension = d;
		arr = new char*[dimension.getWidth()];
		for(int i = 0; i < dimension.getWidth(); i++) {
			arr[i] = new char[dimension.getHeight()];
		}
	}
	
	// deallocates the memory for the array
	void deallocate() {
		for(int i = 0; i < dimension.getWidth(); i++) {
    		delete[] arr[i];
		}
		delete[] arr;
	}
	
	// fills each cell by character c
	void fill(char c) {
	    for(int i = 0; i < dimension.getWidth(); i++) {
	        for(int j = 0; j < dimension.getHeight(); j++) {
	            arr[i][j] = c;
	        }
	    }
	}
	
	// print integer where cursor is located and returns position of the cursor
	point print(int i) {
	    return print(to_string(i));
	}
	
	// print string where cursor is located and returns position of the cursor
	point print(string s) {
		for(int i = 0; i < s.length(); i++) {
		    arr[cursor.getX()][cursor.getY()] = s.at(i);
		    moveCursor();
		}
		return cursor;
	}
	
	// moves cursor to the right
	void moveCursor() {
		cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);
		cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());
	}
	
	
	// moves cursor to the point p
	void moveCursor(point p) {
		cursor.setX(p.getX());
		cursor.setY(p.getY());
	}
	
	// returns char located at point p
	char getChar(point p) {
	    return arr[p.getX()][p.getY()];
	}
	
	// returns dimension of the screen
	size getSize() {
		return dimension;
	}
	
};

// returns length of integer
int length(int number) {
    int result = 1;
    while((number /= 10) > 0) {
        result++;
    }
    return result;
}

// returns sum of lengths of integers from from to to
int length(int from, int to) {
    int result = 0;
    for(int i = from; i <= to; i++) {
        result += length(i);
    }
    return result;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    screen screen(size(length(1, k), k + 1));
    screen.fill('+');
    for(int i = 1; i <= k; i++) {
        screen.print(i);
    }
    for(int i = 1; i <= k; i++) {
    	screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));
    	screen.print(i);
    }
    for(int row = 0; row < m; row++) {
        for(int col = 0; col < n; col++) {
            cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));
        }
        cout << endl;
    }
    screen.deallocate();
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <iostream>

using namespace std;

struct point {

int abscissa, ordinate;

point() {

abscissa = 0;

ordinate = 0;

}

point(int x, int y) {

abscissa = x;

ordinate = y;

}

void setX(int x) {

abscissa = x;

}

void setY(int y) {

ordinate = y;

}

int getX() {

return abscissa;

}

int getY() {

return ordinate;

}

};

struct size {

int width, height;

size() {

width = 0;

height = 0;

}

size(int w, int h) {

width = w;

height = h;

}

int getWidth() {

return width;

}

int getHeight() {

return height;

}

};

struct screen {

size dimension; // dimension of the screen

point cursor; // position of the cursor

char **arr; // array that represents characters on the screen

// allocates the memory for the array and sets its dimension

screen(size d) {

dimension = d;

arr = new char*[dimension.getWidth()];

for(int i = 0; i < dimension.getWidth(); i++) {

arr[i] = new char[dimension.getHeight()];

}

// deallocates the memory for the array

void deallocate() {

for(int i = 0; i < dimension.getWidth(); i++) {

delete[] arr[i];

}

delete[] arr;

}

// fills each cell by character c

void fill(char c) {

for(int i = 0; i < dimension.getWidth(); i++) {

for(int j = 0; j < dimension.getHeight(); j++) {

arr[i][j] = c;

}

// print integer where cursor is located and returns position of the cursor

point print(int i) {

return print(to_string(i));

}

// print string where cursor is located and returns position of the cursor

point print(string s) {

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

arr[cursor.getX()][cursor.getY()] = s.at(i);

moveCursor();

}

return cursor;

}

// moves cursor to the right

void moveCursor() {

cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);

cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());

}

// moves cursor to the point p

void moveCursor(point p) {

cursor.setX(p.getX());

cursor.setY(p.getY());

}

// returns char located at point p

char getChar(point p) {

return arr[p.getX()][p.getY()];

}

// returns dimension of the screen

size getSize() {

return dimension;

}

};

// returns length of integer

int length(int number) {

int result = 1;

while((number /= 10) > 0) {

result++;

}

return result;

}

// returns sum of lengths of integers from from to to

int length(int from, int to) {

int result = 0;

for(int i = from; i <= to; i++) {

result += length(i);

}

return result;

}

int main() {

int n, m, k;

cin >> n >> m >> k;

screen screen(size(length(1, k), k + 1));

screen.fill('+');

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

screen.print(i);

}

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

screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));

screen.print(i);

}

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

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

cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));

}

cout << endl;

}

screen.deallocate();

return 0;

}

Related Images:

MLoop 16

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

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

MLoop16.

Вычислите с точностью [latex]\epsilon[/latex] значение функции [latex]f\left( x \right) = \frac{\sin 2x}{x}[/latex]. При вычислениях допустимо использовать только арифметические операции.

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

Разложим [latex]g \left( x \right) = \sin x[/latex] по формуле Тейлора с опорной точкой [latex]x_0 = 0[/latex] и остаточным членом в форме Лагранжа:
[latex]g \left( x \right) = P_n \left( x_0 ; x \right) + R_n \left( x_0 ; x \right)[/latex],
[latex]P_n \left( x_0 ; x \right) = g \left( x_0 \right) + \sum_{k = 1}^{n} \frac{g^{\left( k \right)} \left( x_0 \right) }{k!} \left( x — x_0 \right) ^k[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{g^{\left( n + 1 \right)} \left( \xi \right)}{\left( n + 1 \right) !}\left( x — x_0 \right) ^{n + 1} , x_0 < \xi < x[/latex].

Найдем производные [latex]g \left( x \right)[/latex]:
[latex]g’ \left( x \right) = \cos x = \sin \left( x + \frac{\pi}{2} \right)[/latex],
[latex]g» \left( x \right) = \cos \left( x + \frac{\pi}{2} \right) = \sin \left( x + 2 \frac{\pi}{2} \right)[/latex],
[latex]g»’ \left( x \right) = \cos \left( x + 2 \frac{\pi}{2} \right) = \sin \left( x + 3 \frac{\pi}{2} \right)[/latex],
[latex]\cdots[/latex]
[latex]g^{\left( k \right)} \left( x \right) = \cos \left( x + \left( k — 1 \right) \frac{\pi}{2} \right) = \sin \left( x + k \frac{\pi}{2} \right)[/latex].

Вычислим значение функции и ее производных в точке [latex]x_0[/latex]:
[latex]g \left( x_0 \right) = \sin x_0 = \sin 0 = 0[/latex],
[latex]g’ \left( x_0 \right) = \sin \left( x_0 + \frac{\pi}{2} \right) = \sin \frac{\pi}{2} = 1[/latex],
[latex]g» \left( x_0 \right) = \sin \left( x_0 + 2 \frac{\pi}{2} \right) = \sin \pi = 0[/latex],
[latex]g»’ \left( x_0 \right) = \sin \left( x_0 + 3 \frac{\pi}{2} \right) = \sin \frac{3 \pi}{2} = -1[/latex],
[latex]\cdots[/latex]
[latex]g ^{ \left( 2k — 1 \right) } \left( x_0 \right) = \sin \left( x_0 + \left( 2k — 1 \right) \frac{\pi}{2} \right) = \sin \left( \pi k + \frac{\pi}{2} \right) = \left( -1 \right) ^{k — 1}[/latex],
[latex]g ^{ \left( 2k \right) } \left( x_0 \right) = \sin \left( x_0 + 2k \frac{\pi}{2} \right) = \sin \pi k = 0[/latex].

Тогда
[latex]P_n \left( x_0 ; x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! }[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]g \left( x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]f \left( x \right) = \frac{ g \left( 2x \right) }{ x } = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! }[/latex].

Осталось найти такое [latex]n \in \mathbb{N}[/latex], чтобы выполнялось неравенство
[latex]\left| \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! } \right| \le \left| \frac{ \left( 2x \right) ^ {n + 1} }{ x \left( n + 1 \right) ! } \right| < \epsilon[/latex].

Для ускорения вычислений зададим реккурентную формулу для слагаемых суммы
[latex]\sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Представим каждое слагаемое суммы в виде
[latex]\alpha_k = \alpha_{k — 1} \cdot b_k = \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Выразим [latex]b_k[/latex]:
[latex]b_k = \frac{ \alpha_k }{ \alpha_{ k — 1 } } = \frac{ \left( -1 \right) ^ {k — 1} \cdot \left( 2x \right) ^ {2k — 1} \cdot x \left( 2 \left( k — 1 \right) — 1 \right) ! }{ x \left( 2k — 1 \right) ! \cdot \left( -1 \right) ^ { \left( k — 1 \right) — 1 } \cdot \left( 2x \right) ^ {2 \left( k — 1 \right) — 1} } = — \frac{4x^2}{\left( 2k — 2 \right) \left( 2k — 1 \right)}[/latex].
Тогда
[latex]\alpha_k = \begin{cases} 2 & k = 1, \\ \alpha_{k-1} \cdot b_k & k > 1. \end{cases}[/latex]

Тесты

Входные данные		Выходные данные
[latex]x[/latex]	[latex]\epsilon[/latex]	[latex]f\left( x \right) = \frac{\sin 2x}{x} + \lambda, \lambda\in\left( -\epsilon;\epsilon \right)[/latex]
[latex]\frac{5\pi}{2}[/latex]	[latex]0[/latex]	[latex]\frac{2}{5\pi}[/latex]
[latex]\pi[/latex]	[latex]0.01[/latex]	[latex]0[/latex]
[latex]0[/latex]	[latex]0.1[/latex]	[latex]\emptyset[/latex]

Реализация

ideone: ссылка

#include <iostream>
using namespace std;

double abs(double argument) {
	return argument >= 0 ? argument : -argument;
}

int ceil(double argument) {
	int result = (int) argument;
	if((double) result != argument && argument > 0) {
		result++;
	} else if((double) result == argument && argument < 0) {
		result++;
	}
	return result;
}

int determineOrderOfPolynomial(double argument, double accuracy) {
	int order = 1;
	double a = 2 * argument;
	while(abs(a) >= accuracy) {
		order++;
		a *= 2 * argument / (order + 1);
	}
	return order;
}

double function(double argument, double accuracy) {
	int order = determineOrderOfPolynomial(argument, accuracy);
	double summand = 2;
	double sum = summand;
	for(int k = 2; k <= ceil(order / 2.0); k++) {
		summand *= -4 * argument * argument / ((2 * k - 2) * (2 * k - 1));
		sum += summand;
	}
	return sum;
}

int main() {
	double argument, accuracy;
	cin >> argument >> accuracy;
	if(argument == 0) {
		cout << "empty set";
	} else {
		cout << function(argument, accuracy);
	}
	cout << endl;
	return 0;
}

#include <iostream>

using namespace std;

double abs(double argument) {

return argument >= 0 ? argument : -argument;

}

int ceil(double argument) {

int result = (int) argument;

if((double) result != argument && argument > 0) {

result++;

} else if((double) result == argument && argument < 0) {

result++;

}

return result;

}

int determineOrderOfPolynomial(double argument, double accuracy) {

int order = 1;

double a = 2 * argument;

while(abs(a) >= accuracy) {

order++;

a *= 2 * argument / (order + 1);

}

return order;

}

double function(double argument, double accuracy) {

int order = determineOrderOfPolynomial(argument, accuracy);

double summand = 2;

double sum = summand;

for(int k = 2; k <= ceil(order / 2.0); k++) {

summand *= -4 * argument * argument / ((2 * k - 2) * (2 * k - 1));

sum += summand;

}

return sum;

}

int main() {

double argument, accuracy;

cin >> argument >> accuracy;

if(argument == 0) {

cout << "empty set";

} else {

cout << function(argument, accuracy);

}

cout << endl;

return 0;

}

Related Images:

e-olymp 111. Часы

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

Часы.

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

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

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

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

Тесты

Входные данные		Выходные данные
Начальное время	Конечное время	Количество ударов
13:30	15:10	7
0:00	23:59	180
12:30	12:30	1
22:08	22:22	0

Реализация

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

#include <iostream>
using namespace std;

int main() {
    int h1, m1, h2, m2, result = 0;
    cin >> h1 >> m1 >> h2 >> m2;
    while(true) {
        if(m1 == 0) {
            result += h1 > 12 ? h1 - 12 : h1 == 0 ? 12 : h1;
        } else if(m1 == 30) {
            result++;
        }
        if(h1 == h2 && m1 == m2) {
            break;
        }
        m1++;
        if(m1 == 60) {
            m1 = 0;
            h1++;
        }
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int h1, m1, h2, m2, result = 0;

cin >> h1 >> m1 >> h2 >> m2;

while(true) {

if(m1 == 0) {

result += h1 > 12 ? h1 - 12 : h1 == 0 ? 12 : h1;

} else if(m1 == 30) {

result++;

}

if(h1 == h2 && m1 == m2) {

break;

}

m1++;

if(m1 == 60) {

m1 = 0;

h1++;

}

cout << result << endl;

return 0;

}

Related Images:

А57г. Функция

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

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

Дано действительное число [latex]a[/latex]. Вычислить [latex]f(a)[/latex], если
[latex]f(x) = \begin{cases}0, & x \le 0;\\x^2 — x, & 0 < x \le 1;\\x^2 — \sin(\pi \cdot x^2), & x > 1 \end{cases}[/latex]

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

Находим промежуток, которому принадлежит [latex]a[/latex]. Если [latex]a \in (-\infty;0][/latex], то [latex]f(a) = 0[/latex], если [latex]a \in (0;1][/latex], то [latex]f(a) = a^2 — a[/latex], в остальных случаях [latex]f(a) = a^2 — \sin(\pi \cdot a ^ 2)[/latex].

График функции:

Тесты

Входные данные	Выходные данные
0	0
1	0
2	4

Реализация

ideone: ссылка

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

int main() {
	double a;
	cin >> a;
	cout << (a <= 0 ? 0 : a <= 1 ? a * a - 1 : a * a - sin(M_PI * a * a)) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a;

cin >> a;

cout << (a <= 0 ? 0 : a <= 1 ? a * a - 1 : a * a - sin(M_PI * a * a)) << endl;

return 0;

}

Related Images:

ML7. Смесь

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

Задача. Смешано [latex]v_1[/latex] литров воды температуры [latex]t_1[/latex] с [latex]v_2[/latex] литрами воды температуры [latex]t_2[/latex]. Найти объем и температуру образовавшейся смеси.

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

Из физики мы знаем, что
[latex]Q_3 = Q_1 + Q_2[/latex],
[latex]Q = m \cdot C \cdot t[/latex],
[latex]m = \rho \cdot v[/latex],
где
[latex]Q[/latex] — количество теплоты,
[latex]m[/latex] — масса,
[latex]C[/latex] — теплоемкость,
[latex]t[/latex] — температура,
[latex]\rho[/latex] — плотность,
[latex]v[/latex] — объем.
Отсюда объём образовавшейся смеси
[latex]v_3 = v_1 + v_2[/latex],
а её температура
[latex]t_3 = \frac{\rho \cdot v_1 \cdot C \cdot t_1 + \rho \cdot v_2 \cdot C \cdot t_2}{\rho \cdot v_3 \cdot C} = \frac{\rho \cdot C \cdot (v_1 \cdot t_1 + v_2 \cdot t_2)}{\rho \cdot v_3 \cdot C} = \frac{v_1 \cdot t_1 + v_2 \cdot t_2}{v_3}[/latex].

Тесты

Входные данные				Выходные данные
[latex]v_1[/latex]	[latex]t_1[/latex]	[latex]v_2[/latex]	[latex]t_2[/latex]	[latex]v_3[/latex]	[latex]t_3[/latex]
2	4	2	4	4	4
10	10	10	10	20	10
3	1	1	3	4	1.5
0	1000	1	5	1	5

Реализация

ideone: ссылка

#include <iostream>
using namespace std;
 
int main() {
	double v1, t1, v2, t2, v3, t3;
	cin >> v1 >> t1 >> v2 >> t2;
	v3 = v1 + v2;
	t3 = (v1 * t1 + v2 * t2) / v3;
	cout << v3 << " " << t3 << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double v1, t1, v2, t2, v3, t3;

cin >> v1 >> t1 >> v2 >> t2;

v3 = v1 + v2;

t3 = (v1 * t1 + v2 * t2) / v3;

cout << v3 << " " << t3 << endl;

return 0;

}

Related Images:

Mif 7. Тип треугольника

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

Тип треугольника.

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

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex], задающие длины сторон некоторого треугольника. Будет ли треугольник остроугольным, тупоугольным или прямоугольным? Какой из трёх случаев самый маловероятный?

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

По теореме косинусов
[latex]a^2 = b^2 + c^2 — 2 \cdot b \cdot c \cdot \cos\alpha[/latex],
где [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника, а [latex]\alpha[/latex] — угол между [latex]a[/latex] и [latex]b[/latex], тогда
[latex]\alpha = \arccos\frac{b^2 + c^2 — a^2}{2 \cdot b \cdot c}[/latex],
[latex]\beta = \arccos\frac{c^2 + a^2 — b^2}{2 \cdot a \cdot c}[/latex],
[latex]\gamma = \arccos\frac{a^2 + b^2 — c^2}{2 \cdot a \cdot b}[/latex],
где [latex]\alpha[/latex], [latex]\beta[/latex], [latex]\gamma[/latex] — углы треугольника.
Если самый большой угол больше [latex]\frac{\pi}{2}[/latex], то треугольник тупоугольный, если самый большой угол равен [latex]\frac{\pi}{2}[/latex], то треугольник прямоугольный, если самый большой угол меньше [latex]\frac{\pi}{2}[/latex], то треугольник остроугольный. Так как треугольник является прямоугольным только в том случае, когда самый большой угол равен [latex]\frac{\pi}{2}[/latex], этот случай является самым маловероятным.

Тесты

Входные данные			Выходные данные
[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	Выходные данные
2	2	3	Тупоугольный
3	4	5	Прямоугольный
1	1	1	Остроугольный

Реализация

ideone: ссылка

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

int main() {
	double a, b, c;
	cin >> a >> b >> c;
	double angle0 = acos((b * b + c * c - a * a) / (2 * b * c));
	double angle1 = acos((c * c + a * a - b * b) / (2 * a * c));
	double angle2 = acos((a * a + b * b - c * c) / (2 * a * b));
	double maxAngle = angle0 > angle1 ? (angle0 > angle2 ? angle0 : angle2) : (angle1 > angle2 ? angle1 : angle2);
	if(maxAngle > M_PI / 2) {
		cout << "Тупоугольный";
	} else if(maxAngle == M_PI / 2) {
		cout << "Прямоугольный";
	} else {
		cout << "Остроугольный";
	}
	cout << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, b, c;

cin >> a >> b >> c;

double angle0 = acos((b * b + c * c - a * a) / (2 * b * c));

double angle1 = acos((c * c + a * a - b * b) / (2 * a * c));

double angle2 = acos((a * a + b * b - c * c) / (2 * a * b));

double maxAngle = angle0 > angle1 ? (angle0 > angle2 ? angle0 : angle2) : (angle1 > angle2 ? angle1 : angle2);

if(maxAngle > M_PI / 2) {

cout << "Тупоугольный";

} else if(maxAngle == M_PI / 2) {

cout << "Прямоугольный";

} else {

cout << "Остроугольный";

}

cout << endl;

return 0;

}

Related Images:

e-olymp 133. Квадрат и точки

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

Квадрат и точки.

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

Какое наибольшее количество точек с целочисельными координатами на листке в клеточку можно накрыть квадратом со стороной N клеток?

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

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

Тесты

Входные данные	Выходные данные
1	4
2	9
3	16
4	25

Реализация

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

#include <iostream>
 
int main() {
    int l;
    std::cin >> l;
    std::cout << (l + 1) * (l + 1);
    return 0;
}

#include <iostream>

int main() {

int l;

std::cin >> l;

std::cout << (l + 1) * (l + 1);

return 0;

}