OCPC-2021. Задача D. Столовая (код решения)

20/01/2024 by Александр Мармалюк

Условие

В столовой заведения «Покосившийся Скворечник» имеется ровно $k$ тарелок, а в самом заведении – $n$ палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

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

Первая строка ввода содержит два целых числа $n$ и $k$ $(1 \leqslant n \leqslant 10^5, 1 \leq k \leqslant 10^5)$ – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа $a_i$ и $bi$ $(0 \leqslant a_i + b_i \leqslant k)$ – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

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

Тесты

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

2 4 1 2 1 1	3
4 10 2 6 4 5 1 1 2 2	8
3 12 2 8 1 4 0 1	5
3 5 2 2 1 3 0 5	0

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

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int dirty = 0;
    for (int i = 0; i < n; ++i) {
        int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев
        cin >> wash >> not_wash;
        if (not_wash < dirty) {
            int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки
            dirty -= min(wash, free_dirty);
        }
        else
        if (not_wash > dirty)
            dirty = not_wash;
    }
    cout << k - dirty;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int dirty = 0;

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

int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев

cin >> wash >> not_wash;

if (not_wash < dirty) {

int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки

dirty -= min(wash, free_dirty);

}

else

if (not_wash > dirty)

dirty = not_wash;

}

cout << k - dirty;

return 0;

}

Решение

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

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

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

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 7095. Факторіали

13/12/2020 by Федяєва Євгенія

Задача

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

Вхідні дані

Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

Вихідні дані

Вихідний файл має містити рівно три цифри — шуканий код.

Тесты

№	Входные данные	Выходные данные
1	7	504
2	17	096
3	50	512
4	1000000000	144

Код

#include <iostream>

#define COEF 10000000
#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,
                       68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,
                       37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,
                       21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,
                       72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,
                       91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,
                       98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,
                       709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,
                       48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,
                       21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,
                       84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,
                       3398144 };
int main()
{
    int N;
    unsigned long long factorial = 1;
    cin >> N;
    int idx = N/COEF;
    factorial = arr[idx];
    int start = !N%COEF ? idx*COEF : idx*COEF + 1;
    if (N % COEF != 0)
    {
        for(int i = start; i <= N; i++)
        {
            factorial *= i;
            while(factorial % TEN == 0) factorial /= TEN;
            factorial %= COEF;
        }
    }
    factorial %= TEN*TEN*TEN;
    cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;
    return  0;
}

#include <iostream>

#define COEF 10000000

#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,

68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,

37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,

21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,

72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,

91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,

98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,

709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,

48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,

21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,

84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,

3398144 };

int main()

{

int N;

unsigned long long factorial = 1;

cin >> N;

int idx = N/COEF;

factorial = arr[idx];

int start = !N%COEF ? idx*COEF : idx*COEF + 1;

if (N % COEF != 0)

{

for(int i = start; i <= N; i++)

{

factorial *= i;

while(factorial % TEN == 0) factorial /= TEN;

factorial %= COEF;

}

factorial %= TEN*TEN*TEN;

cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;

return 0;

}

Решение

Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

#include <iostream>
#define TEN 10
using namespace std;
int main()
{
    int N = 1000000000, count = 1;
    unsigned long long factorial = 1;
    for(int i = 1; i <= N; i++)
    {
        factorial *= i;
        while(factorial%TEN == 0) factorial /= TEN;
        factorial %= 100000000;
        if (i % 10000000 == 0) {cout << factorial << ","; count++;}
        if (count == TEN) {cout << endl; count = 1;}
    }
    return  0;
}

#include <iostream>

#define TEN 10

using namespace std;

int main()

{

int N = 1000000000, count = 1;

unsigned long long factorial = 1;

for(int i = 1; i <= N; i++)

{

factorial *= i;

while(factorial%TEN == 0) factorial /= TEN;

factorial %= 100000000;

if (i % 10000000 == 0) {cout << factorial << ","; count++;}

if (count == TEN) {cout << endl; count = 1;}

}

return 0;

}

Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 8680. Чётные соседи

20/12/2019 by Алина Малыхина

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

Программный код

#include <iostream>
using namespace std;

int main(){
    int i=1, n, prev, pres, fut, count = 0;
    cin >> n;
    cin >> prev; //вводим предыдущий элемент
    cin >> pres; //вводим текущий элемент
    while ((cin >> fut) && (i<n)) {
        if (prev % 2 == 0 && fut % 2 == 0) 
            count++;
        prev = pres; //приравниваем предыдущий к текущему
        pres = fut; //приравниваем текущий к будущему
        i++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int i=1, n, prev, pres, fut, count = 0;

cin >> n;

cin >> prev; //вводим предыдущий элемент

cin >> pres; //вводим текущий элемент

while ((cin >> fut) && (i<n)) {

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

cout << count;

return 0;

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

Related Images:

e-olymp 9107. Не разделяйте атом!

14/12/2019 by Владислав Шиманский

Задача

Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [latex] n [/latex] атомов очень редкого элемента, которым они хотят поделиться между собой. Они решили сыграть в следующую игру:

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

Зная количество атомов [latex] n [/latex], определите, кто из злодеев выживет в игре.

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

Первая строка содержит количество тестов [latex] z [/latex] [latex]left(1 leqslant zleqslant50right)[/latex] . Далее следуют описания тестов.

Каждый тест содержит одно целое число [latex] n [/latex] [latex]left(1 leqslant n leqslant10^{6}right)[/latex] — начальное количество атомов.

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

Для каждого теста выведите строку, содержащую один символ: ‘A‘, если профессор выиграет игру, и ‘B‘, если победит доктор

Тесты

№	Входные данные	Выходные данные
1	2 5 6	B A
2	2 2 17	A B
3	2 11 15	B B
4	2 12 16	A A
5	3 101 110 111	B A B

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

#include <iostream>
using namespace std;

int main() {
    int z, n;
    cin >> z;
    for ( int i = 0; i < z; i++ ) {
        cin >> n;
        if ( n % 2 == 0 ) { // Проверка на чётность
            cout << "A" << endl;
        }
        else {
            cout << "B" << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int z, n;

cin >> z;

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

cin >> n;

if ( n % 2 == 0 ) { // Проверка на чётность

cout << "A" << endl;

}

else {

cout << "B" << endl;

}

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 8283. Музыка

14/12/2019 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

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

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

#include <iostream>  
using namespace std;

int main() {
    int quantity, instrument, counter = 1;
    cin >> quantity >> instrument;
    if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
        cout << 0;
    } else if (quantity == instrument) {
        for (int num = 1; num % quantity != 0; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    } else {
        for (int num = 1; num % quantity != instrument; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int quantity, instrument, counter = 1;

cin >> quantity >> instrument;

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

cout << 0;

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

}

return 0;

}

Решение

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

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 9081. Автомобілі

30/11/2019 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
    int t1, t2, t3; // Час, який вони їхали
    int s1, s2, s3; // І відстань
    int max_; // Також, змінну, де буде зберігатися максимальна відстань
    cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія
    cin >> v2 >> t2; 
    cin >> v3 >> t3;
    s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
    s2 = v2 * t2; 
    s3 = v3 * t3;
    max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань
    if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
        cout << "1 "; // Виводимо номер відповідного водія
    if ( s2 == max_ )
        cout << "2 ";
    if ( s3 == max_ )
        cout << 3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія

cin >> v2 >> t2;

cin >> v3 >> t3;

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

cout << "1 "; // Виводимо номер відповідного водія

if ( s2 == max_ )

cout << "2 ";

if ( s3 == max_ )

cout << 3;

return 0;

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

Related Images:

e-olymp 2322. Столбцы

28/04/2019 by Михаил Бутник

Столбцы

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

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 10⁹. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 10⁹ — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 0 1 0 0	NO YES
2	23 3 23 0 23 21 12 23 11 13 23	YES NO YES
3	7 1 0	NO
4	13 3 13 33 75 23 45 31 13 13 13	YES YES YES

Код

#include <iostream>
using namespace std; 
 
int arr[101];
int main() {
    long long x, c;
    cin >> x;
    int n, i = 0;
    cin >> n;
    while (cin >> c) {
        if (c == x) {
            arr[i % n]++;
        }
        i++;
    }
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int arr[101];

int main() {

long long x, c;

cin >> x;

int n, i = 0;

cin >> n;

while (cin >> c) {

if (c == x) {

arr[i % n]++;

}

i++;

}

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

if (arr[i] > 0) {

cout << "YES" << endl;

}

else {

cout << "NO" << endl;

}

return 0;

}

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

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

Related Images:

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

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

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

Задача

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

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

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

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

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

Тесты

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

Решение

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

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

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

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

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

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

#include <iostream>

#include <cmath>

using namespace std;

struct point{int x;int y;};

struct rect{point a;point b;};

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

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

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

c.a = a;

c.b = b;

return c;

}

rect getrekt(rect c){

point a,b;

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

return getrect(a,b,c);

}

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

rect cross(rect l,rect r){

rect cr;

point a1,b1;

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

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

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

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

return getrect(a1,b1,cr);

}

int farea(rect *q){

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

}

int main() {

rect *q = new rect [3];

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

cout<<farea(q);

}

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

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

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

#include <iostream>

#include <cmath>

#define N 100

using namespace std;

int main() {

int rect[3][4];

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

int count = 0;

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

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

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

cin >> rect[i][k];

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

}

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

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

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

field[i][j]=1;

}

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

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

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

}

cout<<count;

}

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

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

Код

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int w, h, res = 0;

cin >> w >> h;

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

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

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

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

cin >> x[i][j];

}

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

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

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

}

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

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

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

}

cout << res << endl;

return 0;

}

Решение

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

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

Related Images:

e-olymp 137. НОД

25/12/2018 by Михаил Бутник

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 15 25	5
2	3 99 358 2	1
3	5 81 99 72 108 36	9
4	2 25 50	25
5	4 132 36 66 18	6

Код

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return (a == 0) ? b: gcd(b % a, a);
}

int main() {
    int n, m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        m = gcd(m, a);
    }
    cout << m;
    return 0;
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return (a == 0) ? b: gcd(b % a, a);

}

int main() {

int n, m = 0;

cin >> n;

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

int a;

cin >> a;

m = gcd(m, a);

}

cout << m;

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

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

Related Images:

e-olymp 1753. Младший бит

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

Задача

Для заданного положительного целого $A$ $(1 \leq A \leq 100),$ вывести младший бит $A$.

Например, если $A = 26$, то его мы можем записать в двоичном виде, как $11010$, и младший бит $A$ есть $10$, и на выходе должно быть $2.$

Другой пример выглядит следующим образом: при $A = 88$, это число $A$ мы можем записать в двоичной форме $1011000$, младший бит в $A$ есть $1000,$ и на выходе должно быть $8.$

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

Каждая строка входных данных содержит только одно целое число $A$ $(1 \leq A \leq 100).$ Строка, содержащая «0» означает конец ввода, и эта строка не является частью входных данных.

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

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

Тесты

	Входные данные	Выходные данные
1	26 88 0	2 8
2	99 45 66 20	1 1 2 4
3	100 0 6	4
4	66 33 98 42 84 39	2 1 2 2 4 1

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

#include <iostream>
using namespace std;

int main() {
    int a;
    while (cin >> a && a != 0) {
        int LSB = 1; // Least Significant Bit
        while ((a & LSB) == 0){
            LSB = LSB << 1;
        }
        cout << LSB << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a;

while (cin >> a && a != 0) {

int LSB = 1; // Least Significant Bit

while ((a & LSB) == 0){

LSB = LSB << 1;

}

cout << LSB << endl;

}

return 0;

}

Решение

Объявляем переменную a. Начинается цикл while, условием окончания которого будет введённая a, неравная нулю. В цикле объявляем переменную LSB = 1, после чего начинается новый цикл while, который сдвигает бит LSB влево, пока выражение побитовой конъюнкции a & LSB нулевое. Соответственно, как только выражение будет ненулевым — будет найден первый общий бит, который и будет младшим битом числа a. Его и выводим.

Ссылки

Related Images:

e-olymp 1151. Кладоискатель

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

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

Если в конце дня ответственный преподаватель замечал, что число Роминых монет делится на $b,$ то Роме разрешалось взять с полки пирожок, который он тут же съедал. Помогите Роме посчитать, сколько пирожков он съест за время прохождения практики.

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

В выходной файл выведите число съеденных Ромой пирожков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2	1
2	2 2	2
3	10 5	5
4	56000 35	35
5	300 1000000000	100

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

#include <iostream>
using namespace std;
int GCD(int a, int b){
  if (b == 0) return a;
  else return GCD(b, a % b);
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << GCD(a,b);
  return 0;
}

#include <iostream>

using namespace std;

int GCD(int a, int b){

if (b == 0) return a;

else return GCD(b, a % b);

}

int main() {

int a, b;

cin >> a >> b;

cout << GCD(a,b);

return 0;

}

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

$a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

Код на ideone.com
Задача на e-olymp.com

Related Images:

e-olymp 8643. Иннолошадь

15/12/2018 by Дарья Найденова

Задача

В шахматном иннокоролевстве выводят специальные породы инноконей. Порода инноконя задается парой чисел $(x, y), 0 ≤ x ≤ y$. Инноконь перемещается следующим образом: сначала перемещается на $x$ клеток в одну из четырех сторон, затем поворачивает на 90 градусов влево или вправо и перемещается еще на $y$ клеток. Например, обычный шахматный конь — это инноконь породы (1, 2).

Петя и Вася недавно видели инноконя, он прыгнул с поля $A$ на поле $B$. Пете и Васе стало интересно, какой породы был этот инноконь. Помогите им ответить на этот вопрос.

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

Шахматная доска состоит из 8 строк и 8 столбцов. Строки нумеруются числами от 1 до 8, а столбцы буквами от $a$ до $h$. Таким образом, каждое поле задается парой из буквы и цифры. В двух строках ввода содержатся описания полей $A$ и $B$.

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

Выведите два целых числа $x$ и $y$, $(0 ≤ x ≤ y)$, соответствующие породе данного инноконя.

Тесты

Входные данные	Выходные данные
a1 b3	1 2
g5 d3	2 3
e1 e1	0 0
d3 d7	0 4
a2 c2	0 2

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

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

int main() {
 char f1, f2;
 int s1, s2, x, y;
 cin >> f1>> s1;
 cin >> f2 >> s2;
 x = abs(f1 - f2);
 y = abs(s1 - s2);
 cout << min(x, y) << ' ' << max(x, y);
 return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

char f1, f2;

int s1, s2, x, y;

cin >> f1>> s1;

cin >> f2 >> s2;

x = abs(f1 - f2);

y = abs(s1 - s2);

cout << min(x, y) << ' ' << max(x, y);

return 0;

}

Решение

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

e-olymp

ideone

Related Images:

e-olymp 8531. Делимость на числа

03/10/2018 by Дмитрий Калинин

Задача

Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?

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

Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]

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

Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.

Тесты

№	Ввод	Вывод
1	12 4 6	YES
2	10 5 6	NO
3	1056 22 6	YES
4	98 103 5	NO

Решение

Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ ( n % a == 0), и остаток от деления $n$ на $b$ равен $0$ ( n % b == 0).

Код с ветвлением

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << ( ( (n % a == 0) && (n % b == 0) )? "YES": "NO");
    /* Делаем проверку делимости n одновременно на a и b,
    и, в зависимости от результата, при помощи тернарной операции выводим ответ */ 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b;

cin >> n >> a >> b;

cout << ( ( (n % a == 0) && (n % b == 0) )? "YES": "NO");

/* Делаем проверку делимости n одновременно на a и b,

и, в зависимости от результата, при помощи тернарной операции выводим ответ */

return 0;

}

Код без использования ветвления

#include <iostream>
using namespace std;

int main() {
    int n, a, b, result;
    cin >> n >> a >> b;
    /* Используем небольшой трюк, который заключается в том,
    что cout в логических выражениях имеет значение 1 (true)*/
    ( ( (n % a == 0) && (n % b == 0) ) && (cout << "YES") );
    ( ( (n % a != 0) || (n % b != 0) ) && (cout << "NO") );
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b, result;

cin >> n >> a >> b;

/* Используем небольшой трюк, который заключается в том,

что cout в логических выражениях имеет значение 1 (true)*/

( ( (n % a == 0) && (n % b == 0) ) && (cout << "YES") );

( ( (n % a != 0) || (n % b != 0) ) && (cout << "NO") );

return 0;

}

Ссылки

Related Images:

e-olymp 108. Среднее число

19/12/2017 by Амир Аль-Омари

Задача

Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

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

Тесты

Входные данные	Выходные данные
10 4 9	9
2 256 8	8
1 2 3	2

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

#include <iostream>
using namespace std;

int main() {
    double a, b, c;
    cin >> a >> b >> c;
    if ((b > a && a > c) || (c > a && a > b)) {
        cout << a;
    }
    else if ((a > b && b > c) || (c > b && b > a)) {
        cout << b;
    }
    else {
        cout << c;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, b, c;

cin >> a >> b >> c;

if ((b > a && a > c) || (c > a && a > b)) {

cout << a;

}

else if ((a > b && b > c) || (c > b && b > a)) {

cout << b;

}

else {

cout << c;

}

return 0;

}

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

Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

Ссылки

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

Related Images:

Mif 17.1

30/09/2015 by Аня Шохина

Задача. Принадлежит ли точка [latex]\left(x;y \right)[/latex] фигуре на рисунке?

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» , если не принадлежит.

Тесты

[latex]x[/latex]	[latex]y [/latex]	Результат
4	-2	NO
2	1	YES
0	3	YES
5	0	NO
0	-1	NO

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	double x, y;
	cin>>x>>y;
	if ((abs(x)+y<=4) && (y>=0)){
		cout<<"YES";
	}
	else cout<<"NO";
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, y;

cin>>x>>y;

if ((abs(x)+y<=4) && (y>=0)){

cout<<"YES";

}

else cout<<"NO";

return 0;

}

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

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

Related Images:

Mif 1

30/09/2015 by Настя Филипчук

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

Даны действительные числа [latex] x [/latex], [latex] y [/latex]. Получить [latex]\min (x, y)[/latex].

Код

#include <iostream>
using namespace std;
 
int main(){
	double x, y;
	cin >> x >> y;
	if (x<y)
		cout << x << endl;
	else
		cout << y << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double x, y;

cin >> x >> y;

if (x<y)

cout << x << endl;

else

cout << y << endl;

return 0;

}

Код (с тернарной операцией)

#include <iostream>
using namespace std;
 
int main(){
	int x, y;
	cin >> x >> y;
	cout << (x<y? x:y);//сравниваем x и y, если x меньше либо равен y, то выводится x, иначе - y
	return 0;
}

#include <iostream>

using namespace std;

int main(){

int x, y;

cin >> x >> y;

cout << (x<y? x:y);//сравниваем x и y, если x меньше либо равен y, то выводится x, иначе - y

return 0;

}

Тесты

Входные данные		Выходные данные
[latex]x[/latex]	[latex]y[/latex]	[latex]\min (x, y)[/latex]
4	9	min=4
23	32	min=23
48	125	min=48
842	361	min=361
15	15	min=15

Решение

Вводим данные [latex] x [/latex], [latex] y [/latex]. Затем сравниваем их. Если [latex] x\leq y [/latex], то выводится [latex] x [/latex]. Иначе, то есть,если [latex] y < x [/latex], то выводится [latex] y [/latex].

Ссылки

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

Код программы на Ideone.com;

Related Images:

Mif 17.19

30/09/2015 by Павел Загинайло

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Вывод
-3	0	no
-1.5	2	yes
2	5	yes
3	4	yes
3	3	no

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

#include <iostream>
using namespace std;
 
int main() {
	double x,y;
	cin >> x >> y;
	cout << ((((x>=-4)&&(x<=-1)&&(y>=1)&&(y<=7))||((x>=-1)&&(x<=3)&&(y>=4)&&(y<=7))) ? "yes" : "no");
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

cout << ((((x>=-4)&&(x<=-1)&&(y>=1)&&(y<=7))||((x>=-1)&&(x<=3)&&(y>=4)&&(y<=7))) ? "yes" : "no");

return 0;

}

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

В данной программе проверяются допустимые значения [latex]x[/latex] и [latex]y[/latex], при которых точка с данными координатами может принадлежать данной фигуре. Если координаты соблюдают все условия, то программа выводит «yes», т.е. принадлежит . В остальных случаях на экран выводится «no».

Related Images:

Ю2.28

30/09/2015 by Павел Загинайло

Задача.

Вклад. Банк предлагает 3 вида срочных вкладов: на 3 месяца под [latex]p_{1}[/latex]%, на 6 месяцев под [latex]p_{2}[/latex]% и на год под [latex]p_{3}[/latex]%. Какой из вкладов наиболее выгоден для вкладчика?

Тесты:

[latex]p1[/latex]	[latex]p2[/latex]	[latex]p3[/latex]	Вывод программы
0	0	0	Нет наиболее выгодного вклада из трех
10	10	10	Первый вклад выгоднее
10	10	50	Третий вклад выгоднее
50	10	10	Первый вклад выгоднее
5	20	20	Второй вклад выгоднее

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

#include <iostream>
using namespace std;
 
int main() {
	double p1, p2, p3, x, y, z;
	cin >> p1 >> p2 >> p3;

	x = (1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100);
	y = (1 + (p2/2)/100)*(1 + (p2/2)/100);
	z = 1 + p3/100;
	
	if ((x > y) && (x > z))
		cout << "Первый вклад выгоднее";
	else if ((y > x) && (y > z))
		cout << "Второй вклад выгоднее";
	else if ((z > x) && (z > y))
		cout << "Третий вклад выгоднее";
	else 
		cout << "Нет наиболее выгодного вклада из трех";
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double p1, p2, p3, x, y, z;

cin >> p1 >> p2 >> p3;

x = (1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100);

y = (1 + (p2/2)/100)*(1 + (p2/2)/100);

z = 1 + p3/100;

if ((x > y) && (x > z))

cout << "Первый вклад выгоднее";

else if ((y > x) && (y > z))

cout << "Второй вклад выгоднее";

else if ((z > x) && (z > y))

cout << "Третий вклад выгоднее";

else

cout << "Нет наиболее выгодного вклада из трех";

return 0;

}

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

Для решения этой задачи я пользовался следующей формулой: [latex]B = A(1 + \frac{P}{100\%})[/latex], где [latex]B[/latex] — будущая стоимость, [latex]A[/latex] — текущая стоимость, [latex]P[/latex] — процентная ставка за расчетный период, [latex]n[/latex] — количество расчетных периодов. В программе я ее представил в другом виде, так как для сравнения выгодности вкладов одинаковой суммы, саму сумму можно не учитывать.

Код на ideone.com

Related Images:

А58г

16/10/2014 by Швандт Максим Альбертович

Задача: Дано действительное число [latex]a[/latex]. Для функции [latex]f(x)[/latex], график которой представлен на рисунке, вычислить [latex]f(a)[/latex].
График:

Тесты:

a	f(a)
1	1
3.2	-0.015371
6	-0.027469
0	0
-1	1
-2.5	2.5
1.5	1
1.8	1
1.001	1

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

#include <stdio.h>

int main(void) {
	
   // Объявление переменных a, y, k, b типа float для хранения данных
   double a;
   double y;	
   double k;
   double b;	

   // Ввод пользователем значений переменной а с помощью scanf
   scanf("%lf", &a);
    
   // Вычисление и вывод результата по формуле с предварительным сравнением значения а,
   if( a <= 0 )
   { k = -1; b = 0; }
   else if ( a <= 1 )
   { k = 1; b = 0; }
   else if ( a < 2 )
   { k = 0; b = 1; }
   else 
   { k = -2; b = 5; }
   y = k*a + b;
    
   printf("result is %lf", y);
   // Завершение программы
   return 0;
}

#include <stdio.h>

int main(void) {

// Объявление переменных a, y, k, b типа float для хранения данных

double a;

double y;

double k;

double b;

// Ввод пользователем значений переменной а с помощью scanf

scanf("%lf", &a);

// Вычисление и вывод результата по формуле с предварительным сравнением значения а,

if( a <= 0 )

{ k = -1; b = 0; }

else if ( a <= 1 )

{ k = 1; b = 0; }

else if ( a < 2 )

{ k = 0; b = 1; }

else

{ k = -2; b = 5; }

y = k*a + b;

printf("result is %lf", y);

// Завершение программы

return 0;

}

Код программы на языке Java:

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

class GraphicApp
{
   public static Double scanDouble( Scanner in )
   {
       return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );
   }
   
   public static void main( String[] args )
   {
      
      // ќбъ¤вление переменных a, y, k, b типа double дл¤ хранени¤ данных
      double a;
      double y;    
      double k;
      double b;    
      
      Scanner in = new Scanner(System.in);
      
      a = scanDouble( in );
       
      in.close(); 
       
      // ¬ычисление и вывод результата по формуле с предварительным сравнением значени¤ а,
      if( a <= 0 )
      { k = -1; b = 0; }
      else if ( a <= 1 )
      { k = 1; b = 0; }
      else if ( a < 2 )
      { k = 0; b = 1; }
      else 
      { k = -2; b = 5; }
      y = k*a + b;
       
      System.out.printf("result is %f\n", y);
   }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class GraphicApp

{

public static Double scanDouble( Scanner in )

{

return ( ( in.hasNextDouble() ) ? in.nextDouble() : null );

}

public static void main( String[] args )

{

// ќбъ¤вление переменных a, y, k, b типа double дл¤ хранени¤ данных

double a;

double y;

double k;

double b;

Scanner in = new Scanner(System.in);

a = scanDouble( in );

in.close();

// ¬ычисление и вывод результата по формуле с предварительным сравнением значени¤ а,

if( a <= 0 )

{ k = -1; b = 0; }

else if ( a <= 1 )

{ k = 1; b = 0; }

else if ( a < 2 )

{ k = 0; b = 1; }

else

{ k = -2; b = 5; }

y = k*a + b;

System.out.printf("result is %f\n", y);

}

Ссылка:http://ideone.com/e6UFys

Результат вычисляем по формуле:
[latex]y = ka + b[/latex] Программа состоит из следующих частей:

Объявление переменных a, y, k, b типа float для хранения данных
Ввод пользователем значений переменной а с помощью scanf
Вычисление и вывод результата по формуле с предварительным сравнением значения а
Завершение программы

Программа сравнивает значение переменной [latex]a[/latex] с значениями переменной [latex]x[/latex] на четырёх диапазонах, и в зависимости от диапазона использует для функции [latex]y = ka + b[/latex] нужные значения [latex]k[/latex] и [latex]b[/latex]. Так вычисляется [latex]f(a)[/latex].
Ссылка на ideone.com : http://ideone.com/N2toyp