e-olymp 1325. Васькины дорожки

27/11/2018 by Иван Киреев

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

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

Единственное число — количество различных способов для Василия попасть на нужный участок для охоты.

Тесты

№	Ввод	Вывод
1	3 2 3 4 5 3	15
2	10 5 7 1 2 3 4 5 6 7 8 9 10	210
3	4 2 1 3 4 7 8	12
4	10 8 8 1 9 6 7 5 3 8 2 4 10	2
5	1 1 1 1	1
6	10 1 10 1 1 1 1 1 1 1 1 1 10	10
7	7 5 3 2 2 2 4 4 4 5	32
8	10 1 10 10 10 10 10 10 10 10 10 10 10	10000000000
7	5 3 2 1 2 3 4 5 6 7 8 9 10	6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0$. И не превышают $10$, следовательно максимальное значение переменной rez будет $10^{10}$ что помещается в unsigned long.

Код

#include <iostream>
using namespace std;

int main() {
    int n, m, k, a, MIN, MAX;
    unsigned long rez = 1;
    cin >> n >> m >> k;
    MIN = min(m, k);
    MAX = max(m, k);
    for (int i = 1; i <= MAX; i++) {
        cin >> a;
        if (i >= MIN) rez *= a;
    }
    cout << rez;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, k, a, MIN, MAX;

unsigned long rez = 1;

cin >> n >> m >> k;

MIN = min(m, k);

MAX = max(m, k);

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

cin >> a;

if (i >= MIN) rez *= a;

}

cout << rez;

return 0;

}

Условие задачи

Решение

Код на ideone

Related Images:

Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

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

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

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

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

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

if (i != 0) cout << endl;

cout << words[index - i].first;

}

return 0;

}

Код на ideone

Related Images:

e-olymp 8519. Сумма четных цифр

21/11/2018 by Алина Гук

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

Задача

Задано длинное число. Найти сумму его четных цифр.

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

Одно натуральное число $n (n ≤ 10^{100} )$.

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

Вывести сумму четных цифр числа $n$.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2345	6
2	3458937487534533459	32
3	888888888888888888888888888888	240

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

#include <iostream>
using namespace std;

int main() {
    char c; 
    int sum = 0;
    while(cin >> c) 
        if((c - '0') % 2 == 0) 
            sum += (c - '0');
    cout << sum << '\n';
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char c;

int sum = 0;

while(cin >> c)

if((c - '0') % 2 == 0)

sum += (c - '0');

cout << sum << '\n';

return 0;

}

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

Переменная c — является переменной типа char, что означает, что cin в этом случае будет считывать по одному символу с потока. По этой причине, чтобы решить данную задачу, нужно считывать заданное число с помощью cin в цикле while до тех пор, пока происходит ввод данных с клавиатуры. Проверяя каждую цифру введенного числа на четность, будем прибавлять четные к переменной sum.
Для работы с символом c как с числом, будем писать c - '0'.

Ссылки

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

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

Related Images:

e-olymp 891. Покупка цветов

14/10/2018 by Иван Киреев

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

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

Тесты

№	Ввод	Вывод
1	5 7 0	0
2	3 5 10	9
3	2 3 11	11
4	48 64 306	304
5	17 20 100	100
6	13 15 260	260
7	29 53 999	986
8	17 28 16	0
7	75 100 1000	1000

Решение

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

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую $c$ рублей. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ($c / a$).

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

Код

#include <iostream>
using namespace std;

int main() {
    int a, b, c, max;
    cin >> a >> b >> c;
    if (c % a == 0) max = c;
    else {
        int n = c / a; // максимальное количество цветков
        max = 0;
        for (int i = 0; i <= (n / 2) && max != c; i++) {
            int first = (n - i) * b +  i * a;
            if (first > max && first <= c) max = first;
            int second = (n - i) * a +  i * b;
            if (second > max && second <= c) max = second;
        } 
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c, max;

cin >> a >> b >> c;

if (c % a == 0) max = c;

else {

int n = c / a; // максимальное количество цветков

max = 0;

for (int i = 0; i <= (n / 2) && max != c; i++) {

int first = (n - i) * b + i * a;

if (first > max && first <= c) max = first;

int second = (n - i) * a + i * b;

if (second > max && second <= c) max = second;

}

cout << max;

return 0;

}

Условие задачи

Решение

Код на ideone

Related Images:

e-olymp 2812. Уголок

08/06/2018 by Георгий Мартынюк

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

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

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.

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

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные	Выходные данные
2 2 .. ..	4
2 3 ..X .X.	1
5 4 …. X.XX …. X..X ..XX	12

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

#include <iostream>
using namespace std;
 
int main() {
    int x, y;
    cin >> x >> y;
    bool **mas = new bool*[x];
    for (int i = 0; i < x; ++i){
        mas[i] = new bool[y];
    }
    for (int i = 0; i < x; ++i){
        for (int j = 0; j < y; ++j){
            char buff;
            cin >> buff;
            if (buff == '.') mas[i][j] = true; 
            else mas[i][j] = false;
        }
        cout << endl;
    }
    int sum = 0;
    for (int i = 0; i < x; ++i){
        for (int j = 0; j < y; ++j){
            if (mas[i][j]){
                if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1])  ++sum;
                if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1])  ++sum; 
                if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1])  ++sum; 
                if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1])  ++sum; 
            }
        }
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y;

cin >> x >> y;

bool **mas = new bool*[x];

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

mas[i] = new bool[y];

}

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

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

char buff;

cin >> buff;

if (buff == '.') mas[i][j] = true;

else mas[i][j] = false;

}

cout << endl;

}

int sum = 0;

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

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

if (mas[i][j]){

if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1]) ++sum;

if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1]) ++sum;

if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1]) ++sum;

}

cout << sum;

return 0;

}

Решение

Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем соответствующий элемент значением true, когда вводится «.» и значением false в противном случае. Далее увеличиваем значение количества уголков на $1$, если существуют не пустые клетки.

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 1226. Обмен иностранцами

13/05/2018 by Мороз Дима

Задача

Ваша неприбыльная организация координирует программу по обмену студентами. И ей нужна Ваша помощь.

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

Для каждого теста в отдельной строке вывести $«YES»$ если существует возможность успешно выполнить программу обмена и $«NO»$ иначе.

Тесты

Входные данные	Выходные данные
2 2 1 2 2 1 2 31 13 13 31	YES YES
1 4 17 3 28 15 15 28 3 17	YES
1 4 17 3 28 15 15 28 3 18	NO
3 2 1 2 3 4 2 47 7 7 47 2 12 34 12 34	NO YES NO

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

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

multiset <pair <unsigned int, unsigned int>> M;
multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {
    unsigned int t, n, a, b;
    cin >> t;
    while (t != 0) {
        cin >> n;
        M.clear();
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            if ((it = M.find (make_pair(b, a))) == M.end()) {
                M.insert (make_pair(a, b));
            } else M.erase(it);
        }
        (M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;
        t--;
    }
    
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

multiset <pair <unsigned int, unsigned int>> M;

multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {

unsigned int t, n, a, b;

cin >> t;

while (t != 0) {

cin >> n;

M.clear();

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

cin >> a >> b;

if ((it = M.find (make_pair(b, a))) == M.end()) {

M.insert (make_pair(a, b));

} else M.erase(it);

}

(M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;

t--;

}

return 0;

}

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

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.

Ссылки

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

Related Images:

e-olymp 1494. Санта Клаус

09/05/2018 by Томас Пасенченко

Задача

Санта Клаус

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки [latex]n[/latex] детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими [latex]n[/latex]. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число [latex]a[/latex] — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке [latex]a[/latex] чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные	Выходные данные
2 1 1 2 1	0
3 1 2 1 2 3	0
7 2 1 7 3 1	4 2 4 5 6
100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54	82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5 2 5 8 3 7 1 4 9	2 6 10
61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25	36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3 1 2 3 11 10 8	6 4 5 6 7 9 12

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

#include <iostream>
using namespace std;

int main() {
    int n, m, k, num;
    cin >> n >> m >> k;
    bool children[n];
    for (int i = 0; i < n; i++) {
        children[i] = false;
    }
    for (int i = 0; i < m + k; i++) {
        cin >> num;
        num--;
        children[num] = true;
    }
    cout << (n - m - k) << "\n";
    for (int i = 0; i < n; i++) {
        if (!children[i]) {
            cout << (i + 1) << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, k, num;

cin >> n >> m >> k;

bool children[n];

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

children[i] = false;

}

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

cin >> num;

num--;

children[num] = true;

}

cout << (n - m - k) << "\n";

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

if (!children[i]) {

cout << (i + 1) << " ";

}

return 0;

}

Решение

Создадим массив типа bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

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

Related Images:

e-olymp 338. Моя любимая, несократимая…

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

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

Входные данные	Выходные данные
1	0
10000	30397485
5	9
80	1965
37	431
5168	8119803
9973	30237929

#include <iostream>

using namespace std;

int euler_f (int n) { 
    int result = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0) n /= i; 
            result -= result / i; 
        } 
    }
    if (n > 1) result -= result / n; 
    return result;
}

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 2; i <= n; ++i) {
        sum += euler_f(i);
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int euler_f (int n) {

int result = n;

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

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

if (n > 1) result -= result / n;

return result;

}

int main() {

int n;

cin >> n;

int sum = 0;

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

sum += euler_f(i);

}

cout << sum;

return 0;

}

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

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте E-Olymp

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

описание функции Эйлера на Wikipedia

Related Images:

e-olymp 7492. Будильник

07/05/2018 by Георгий Мартынюк

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные	Выходные данные
23	00:02
28	Impossible
0	Impossible
15	01:12

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

#include <iostream> 
using namespace std;

int main() {
    int n;
 
    while (cin >> n) {
        int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
        for (int i = 0; i < 24; i++)
            for (int j = 0; j < 60; j++) {
                int a = 0;
                a = a + seg[i / 10];
                a = a + seg[i % 10];
                a = a + seg[j / 10];
                a = a + seg[j % 10];
                if (a == n) {
                    if (i < 10) cout << '0' << i;
                    else cout << i;
                    cout << ':';
                    if (j < 10) cout << '0' << j;
                    else cout << j;
                    return 0;
                }
            }
            cout << "Impossible";
    }
}

#include <iostream>

using namespace std;

int main() {

int n;

while (cin >> n) {

int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

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

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

int a = 0;

a = a + seg[i / 10];

a = a + seg[i % 10];

a = a + seg[j / 10];

a = a + seg[j % 10];

if (a == n) {

if (i < 10) cout << '0' << i;

else cout << i;

cout << ':';

if (j < 10) cout << '0' << j;

else cout << j;

return 0;

}

cout << "Impossible";

}

Решение

Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 1489. Шоколад

13/04/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

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

Код решения

#include <iostream>
using namespace std;


bool BreakRow (int **chocolate, int n, int m){
  for (int i = 0; i < n - 1; i++){
    bool okRow = true;
    for (int j = 0; j < m; j++){
      if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}
    }
    if (okRow) return true;
  }
  return false;
}
bool BreakColumn (int **chocolate, int n, int m){
  for (int i = 0; i < m - 1; i++){
    bool okColumn = true;
    for (int j = 0; j < n; j++){
      if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}
    }
    if (okColumn) return true;
  }
  return false;
}

int check (int **chocolate, int n, int m){
  if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";
  else cout<<"No";
}

int main() {
  int n, m;
  cin >> n >> m;
  int **chocolate = new int* [n];
  for(int i = 0; i < n; ++i){
    chocolate[i] = new int[m];
  }
  for( int i = 0; i < n;  i++){
    for(int j = 0; j < m; j++){
      cin >> chocolate [i][j];
    }
  }
  check(chocolate, n, m);
  return 0;
}

#include <iostream>

using namespace std;

bool BreakRow (int **chocolate, int n, int m){

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

bool okRow = true;

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

if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}

}

if (okRow) return true;

}

return false;

}

bool BreakColumn (int **chocolate, int n, int m){

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

bool okColumn = true;

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

if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}

}

if (okColumn) return true;

}

return false;

}

int check (int **chocolate, int n, int m){

if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";

else cout<<"No";

}

int main() {

int n, m;

cin >> n >> m;

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

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

chocolate[i] = new int[m];

}

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

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

cin >> chocolate [i][j];

}

check(chocolate, n, m);

return 0;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

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

Related Images:

e-olimp 2864. Табулирование функции

04/04/2018 by Антон Джашимов

Задача

Напишите программу, которая выводит на экран таблицу значений функции [latex]y = 3\sin\left(x\right) [/latex] на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно с шагом [latex]h[/latex].

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

В одной строке через пробел заданы три вещественных числа [latex]a[/latex], [latex]b[/latex] и [latex]h[/latex].

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

В каждой строке выведите по два числа [latex]x[/latex] и [latex]y[/latex] соответственно, по возрастанию [latex]x[/latex] с тремя десятичными знаками.

Тесты

Входные данные	Выходные данные
1 2 0.5	1.000 2.524 1.500 2.992 2.000 2.728
0 0 1	0.000 0.000
20 10 5	10.000 -1.632 15.000 1.951 20.000 2.739
-3 -1 1	-3.000 -0.423 -2.000 -2.728 -1.000 -2.524

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

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
    double a, b, h;
    cin >> a >> b>> h;
    for (double x = a; x <= b; x += h) {
        cout << fixed << setprecision(3) <<x<< " " << 3 * sin(x) << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double a, b, h;

cin >> a >> b>> h;

for (double x = a; x <= b; x += h) {

cout << fixed << setprecision(3) <<x<< " " << 3 * sin(x) << endl;

}

return 0;

}

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

Подключим модули cmath, чтобы использовать функцию синус, и iomanip, для установления точности ответа. Далее, с помощью цикла от [latex]a[/latex] до [latex]b[/latex] с шагом [latex]h[/latex] выведем на экран таблицу значений функции на заданном промежутке.

Ссылки

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

Код решения

Related Images:

e-olymp 441. Наиболее круглое число

25/02/2018 by Бондаренко Кирилл

Наиболее круглое число

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

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

В первой строке входных данных задано количество чисел [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex]. Каждая из последующих N строк содержит одно число в пределах от [latex]1[/latex] до [latex]10^{9}[/latex].

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

Вывести наиболее круглое число среди заданных [latex]N[/latex] чисел.

Тесты

Входные данные	Выходные данные
4 71200 10 200 10001	200
5 711 1 2 10001 234567	1
10 7 1 2 1 2 3 4 6 8 9	1
4 100000 200000 500000 800000	100000

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

#include <iostream>
using namespace std;

int main() {
    int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;
    cin >> e;
    while (e -- > 0) {
        cin >> n;
        if (p <= n) {
            m = n;
            k = 0;
            while ((n % 10) == 0) {
                //считает нули
                n = n / 10;
                k ++;
            }
            if (maxk < k) {
                maxn = m;
                maxk = k;
                p = 1;
                for (int i = 1; i < maxk; i ++) {
                    p *= 10;
                }
            } else if (maxk == k) {
                if(maxn > m) {
                    maxn = m;
                }
            }
        }
    }
    cout << maxn;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;

cin >> e;

while (e -- > 0) {

cin >> n;

if (p <= n) {

m = n;

k = 0;

while ((n % 10) == 0) {

//считает нули

n = n / 10;

k ++;

}

if (maxk < k) {

maxn = m;

maxk = k;

p = 1;

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

p *= 10;

}

} else if (maxk == k) {

if(maxn > m) {

maxn = m;

}

cout << maxn;

return 0;

}

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем [latex]p[/latex], где [latex]p[/latex] — наименьшее число с количеством нулей равным [latex]maxk[/latex]. [latex]maxk[/latex] — текущее наибольшее количество нулей. Для того, чтобы найти [latex]p[/latex], мы в цикле умножаем [latex]1[/latex] [latex]maxk[/latex]-раз на [latex]10[/latex]. Очевидно, что [latex]p[/latex] нужно менять только тогда, когда меняется [latex]maxk[/latex], также следует до цикла полагать [latex]p=1[/latex]. Для того чтобы [latex]p[/latex] не умножалось на [latex]10[/latex] лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим [latex]maxn[/latex] — наиболее круглое число.
Так как по условию числа не могут быть больше чем [latex]10^{9}[/latex], имеет смысл изначально поставить переменную [latex]maxn=10^{9}[/latex]. Это делается для того случая, когда во всех числах [latex]m[/latex] не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную [latex]maxn[/latex] любое другое число то [latex]maxn[/latex] может быть меньше чем [latex]m[/latex] и мы не сможем выбрать ответ так как все [latex]m[/latex] будут больше его.

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

Related Images:

e-olymp 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

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

Related Images:

e-olymp 2807. Кубики — 3

31/12/2017 by Валерия Ларикова

Задача

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

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

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

#	Входные данные	Выходные данные
1	5 abcac	b
2	8 ryirhiyh	Ok
3	3 AVA	V
4	6 DjkjDk	Ok
5	7 LnCsCnL	s

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

#include <iostream>
#include <string>//данная библиотека содержит методы и переменные для работы со строками
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) cout << "Ok";
    else {
        int x[200];
        for ( int i = 65; i <= 122; i++)
            x[i] = 0;
        char c;
        while ((c = cin.get()) != EOF)
            x[c]++;
        for (int i = 'A'; i <= 'z'; i++)
            if (x[i] % 2 != 0) 
                c = i;
        cout << c;
    }
    return 0;
}

#include <iostream>

#include <string>//данная библиотека содержит методы и переменные для работы со строками

using namespace std;

int main() {

int n;

cin >> n;

if (n % 2 == 0) cout << "Ok";

else {

int x[200];

for ( int i = 65; i <= 122; i++)

x[i] = 0;

char c;

while ((c = cin.get()) != EOF)

x[c]++;

for (int i = 'A'; i <= 'z'; i++)

if (x[i] % 2 != 0)

c = i;

cout << c;

}

return 0;

}

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Related Images:

e-olymp 247. Несчастливый автобус

26/12/2017 by Георгий Мартынюк

Задача

Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя — очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит «двойка» …

Помогите Вите составить список автобусов, которые он считает «несчастливыми» автобусами.

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

В первой строке записано число [latex]N (0 ≤ N ≤ 100000)[/latex] — количество автобусов, далее указаны номера автобусов [latex]m_i (0 ≤ m_i ≤ 2^{31}-1)[/latex] по одному в строке.

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

Выведите количество «несчастливых» автобусов.

Тесты

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

#include <iostream> 
using namespace std;
int main() {
    int n, number, count = 0;
    cin >> n;
    for (int i = 0;i < n; i++){
         cin>>number;
         if ((number / 2) % 2 == 1) count++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, number, count = 0;

cin >> n;

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

cin>>number;

if ((number / 2) % 2 == 1) count++;

}

cout << count;

return 0;

}

Решение

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

Ссылки

e-olymp
Ideone

Related Images:

MS12. Линейные уравнения

24/12/2017 by Сытников Дан

Условие задачи

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

Линейное_уравнение

Тесты

№	Входные данные	Выходные данные
1	0 0 1 0 0 1	Infinite set of roots; 0.0; No roots;
2	2.02134 -0.52412 15.578 0 5.302 -89 -431.345 9.43 7 49	0.25929334006154336; 0.0; 16.786118445869484; 0.021861850722739336; -7.0;
3	1 1 -6 -2 1 -2 10 0	-1.0; -0.3333333333333333; 2.0; 0.0;

Код на языке C++

#include <iostream>
using namespace std;

int main() {
    double a, b, x;
    int n = 0;
    while (cin >> a >> b) {
        cout << ++n << ") ";    
        if (a == 0) {
            if (b == 0) cout << "Infinite set of roots; \n";
            else        cout << "No roots; \n";
        } else {
            x = (-b/a == -0)? b/a : -b/a;
            cout << x << "; \n";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, b, x;

int n = 0;

while (cin >> a >> b) {

cout << ++n << ") ";

if (a == 0) {

if (b == 0) cout << "Infinite set of roots; \n";

else cout << "No roots; \n";

} else {

x = (-b/a == -0)? b/a : -b/a;

cout << x << "; \n";

}

return 0;

}

Код на языке Java

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

class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        double a, b, x;
        Scanner in = new Scanner(System.in);
        while (in.hasNextDouble()) {
            a = in.nextDouble();
            b = in.nextDouble();
            if (a == 0) {
                if (b == 0) System.out.println("Infinite set of roots; ");
                else        System.out.println("No roots; ");
            } else {
                x = (-b/a == -0)? b/a : -b/a; // Тернарная операция, чтобы избежать выражения "-0"
                System.out.println(x + "; ");
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

double a, b, x;

Scanner in = new Scanner(System.in);

while (in.hasNextDouble()) {

a = in.nextDouble();

b = in.nextDouble();

if (a == 0) {

if (b == 0) System.out.println("Infinite set of roots; ");

else System.out.println("No roots; ");

} else {

x = (-b/a == -0)? b/a : -b/a; // Тернарная операция, чтобы избежать выражения "-0"

System.out.println(x + "; ");

}

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

Линейное уравнение, зависящее от двух параметров, в общей форме имеет вид: [latex] ax + b = 0 [/latex]. Количество решений зависит от параметров [latex]a[/latex] и [latex]b[/latex].

Если [latex] a = b = 0 [/latex], то уравнение имеет бесконечное множество решений, поскольку [latex]\forall x\in \mathbb {R} :x\cdot 0=0[/latex].
Если [latex] a=0,b\neq 0[/latex], то уравнение не имеет решений, поскольку [latex] \not \exists x\in \mathbb {R} :0\cdot x=-b\neq 0[/latex].
Если [latex] a\neq 0[/latex], то уравнение имеет единственное решение [latex] x=-{\frac {b}{a}} [/latex].

Условие задачи.
Код программы на языке C++;
Код программы на языке Java.

Related Images:

D2549. Сумма ряда

24/12/2017 by Алла Марокко

Условие задачи:
Найти сумму сходящегося ряда:
[latex]\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + … + \frac{1}{n(n + 1)} + …[/latex]

Входные данные:
Целое число [latex]n[/latex] — номер искомой частичной суммы.

Выходные данные:
Искомая частичная сумма.

Тесты:

№	Вход	Выход
1	1	0.5
2	500	0.998004
3	100000	0.999965

Код на языке C++ (первый вариант):

#include <iostream>
using namespace std;
 
int main() {
    int n;
    double S = 0;
    cin >> n;
    for (int i = 1; i <= n; i++){
        S += 1.0/(i*(i + 1)); 
    }
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double S = 0;

cin >> n;

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

S += 1.0/(i*(i + 1));

}

cout << S;

return 0;

}

Код на языке Java (первый вариант):

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

class Main
{
    public static void main (String[] args) throws java.lang.Exception{
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n=in.nextInt();
        double S = 0;
        for (int i = 1; i <= n; i++){
            S += 1.0/(i*(i + 1)); 
        }
        System.out.println(S);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n;

n=in.nextInt();

double S = 0;

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

S += 1.0/(i*(i + 1));

}

System.out.println(S);

}

Код на языке C++ (второй вариант):

#include <iostream>
using namespace std;
 
int main() {
    int n;
    double S = 0;
    cin >> n;
    S = 1-(1/n); 
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double S = 0;

cin >> n;

S = 1-(1/n);

cout << S;

return 0;

}

Код на языке Java (второй вариант):

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

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n=in.nextInt();
        double S = 0;
        S=1-(1/n);
        System.out.println(S);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n;

n=in.nextInt();

double S = 0;

S=1-(1/n);

System.out.println(S);

}

Решения:
Вариант первый (решение с циклом): Зададим цикл с счетчиком [latex]i[/latex] от 1 до заданного пользователем числа [latex]n.[/latex] Именно такое количество необходимых слагаемых [latex]\frac{1}{n(n + 1)}[/latex] будет найдено на каждом шаге цикла для последующего суммирования и нахождения искомой частичной суммы.

Вариант второй (решение без цикла): Ряд сводится к ряду: [latex](1 — \frac{1}{2}) + (\frac{1}{2} — \frac{1}{3}) + … + (\frac{1}{n} — \frac{1}{n + 1})[/latex]. От сюда имеем: [latex]1 — \frac{1}{n + 1}.[/latex]

Ссылки:
Условие задачи (стр.248).
Первый вариант C++ .
Первый вариант Java .
Второй вариант C++ .
Второй вариант Java .

Related Images:

e-olymp 7367. Спортсмен

21/12/2017 by Иван Мясоедов

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9	1
2	45	4
3	324	16
4	1234	28
5	213213123	153

Код программы №1 (с использованием цикла):

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
   double k = 1, T = 10, N, S = 10;
   cin >> N;
   while (N > T) {
       S = S * 1.1;
       T = S + T;
       k++;
   }
   cout << k;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double k = 1, T = 10, N, S = 10;

cin >> N;

while (N > T) {

S = S * 1.1;

T = S + T;

k++;

}

cout << k;

return 0;

}

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

Ссылки

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

Код программы №2(с использованием линейных вычислений):

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
   double s;
   cin >> s;
   cout << ceil (log(s / 100 + 1) / log(1.1));
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double s;

cin >> s;

cout << ceil (log(s / 100 + 1) / log(1.1));

return 0;

}

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]

Ссылки

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

Related Images:

e-olymp 2612. Разрезание на квадраты

14/12/2017 by Александр Волынец

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

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

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

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

Требуется вывести количество квадратов.

Тесты

Входные данные	Выходные данные
12 4	3
15 3	5
20 20	1
8 12	3

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

#include <iostream>
using namespace std;

int main() {
    int a, b, temp = 0;
    bool need = 1;
    cin >> a >> b;
    while (need) {
        if (a >= b) {
            temp = temp + a / b;
            a = a%b;
        }
        else
        {
            temp = temp + b / a;
            b = b%a;
        }
        if (a == 0 || b == 0) {
            need = 0;
        }
    }
    cout << temp;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, temp = 0;

bool need = 1;

cin >> a >> b;

while (need) {

if (a >= b) {

temp = temp + a / b;

a = a%b;

}

else

{

temp = temp + b / a;

b = b%a;

}

if (a == 0 || b == 0) {

need = 0;

}

cout << temp;

return 0;

}

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

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

Высота равна ширине
Высота больше ширины
Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

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

Related Images:

A321. Циклы

13/12/2017 by Сытников Дан

Задача

Даны натуральные числа [latex]m, n[/latex], действительные числа [latex] a_1, a_2, …, a_{mn}[/latex]. Вычислить [latex]a_1 a_2 … a_m + a_{m+1} a_{m+2} … a_{2m} + a_{(n – 1) m + 1} a_{(n – 1) m + 2} … a_{nm}[/latex].

Входные данные:
[latex]m, n[/latex] — натуральные числа.
В следующей строке содержится [latex]m \cdot n[/latex] действительных чисел.

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

Тесты:

№	Входные данные	Выходные данные
1	3 3 1.1342 2.82113 3.5431 4.541 5.081 6.761 7.35781 8.456451 9.6461 10.9321	767.5218903911781
2	5 4 23.2312 -13.016 0.78 1.0 73.48992 -3441.32150 39.94 87.04 0.1 -0.02 94.094 23.0001 0.005 -2.0 -1.0 0.004 -1.01 42.0 0.454 1.5	6593.637250058031
3	3 2 1.1 2.2 3.3 4.4 5.5 6.6	327.426

Код на языке C++:

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

int main()
{
    int m, n;
    cin >> m >> n;
    double a[m*n];
    double sum1 = 1, sum2 = 1, sum3 = 1;
    double sum = 0;
    for (int i = 1; i <= m*n; i++)
    {
        cin >> a[i];
        if (i <= m)
        {
            sum1 *= a[i];
        }
        if ((i > m) && (i <= 2*m))
        {
            sum2 *= a[i];
        }
        if ((i > (n - 1)*m) && (i <= n*m)) 
        {
            sum3 *= a[i];
        }
    }
    cout << setprecision(15) << sum1 + sum2 + sum3;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

int m, n;

cin >> m >> n;

double a[m*n];

double sum1 = 1, sum2 = 1, sum3 = 1;

double sum = 0;

for (int i = 1; i <= m*n; i++)

{

cin >> a[i];

if (i <= m)

{

sum1 *= a[i];

}

if ((i > m) && (i <= 2*m))

{

sum2 *= a[i];

}

if ((i > (n - 1)*m) && (i <= n*m))

{

sum3 *= a[i];

}

cout << setprecision(15) << sum1 + sum2 + sum3;

return 0;

}

Код на языке Java:

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

class Ideone {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int m, n;
        m = in .nextInt();
        n = in .nextInt();
        double[] a = new double[m * n + 1];
        double sum1 = 1, sum2 = 1, sum3 = 1;
        for (int i = 1; i <= m * n; i++) {
            a[i] = in .nextDouble();
            if (i <= m) {
                sum1 *= a[i];
            }
            if ((i > m) && (i <= 2 * m)) {
                sum2 *= a[i];
            }
            if ((i > (n - 1) * m) && (i <= n * m)) {
                sum3 *= a[i];
            }
        }
        System.out.println(sum1 + sum2 + sum3);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

Scanner in = new Scanner(System.in);

int m, n;

m = in .nextInt();

n = in .nextInt();

double[] a = new double[m * n + 1];

double sum1 = 1, sum2 = 1, sum3 = 1;

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

a[i] = in .nextDouble();

if (i <= m) {

sum1 *= a[i];

}

if ((i > m) && (i <= 2 * m)) {

sum2 *= a[i];

}

if ((i > (n - 1) * m) && (i <= n * m)) {

sum3 *= a[i];

}

System.out.println(sum1 + sum2 + sum3);

}

Решение задачи:
Заведём массив для хранения чисел. Пользуясь циклом [latex]for[/latex] от [latex]1[/latex] до [latex]m \cdot n[/latex], по мере заполнения массива будем считать слагаемые нашего выражения. Для этого воспользуемся оператором [latex] if [/latex], проверяя индексы элементов массива.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 321