e-olymp 4749. Выручка театра

25/06/2019 by Никита Семерня

Задача

В театре $n$ рядов по $m$ мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ($1$ — соответствующий билет продан, $0$ — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число $n$, затем число $m$ $(n, m \le 500)$. После задана матрица стоимостей билетов ($n$ строк по $m$ чисел, каждое из чисел от $0$ до $10000$). Далее задана матрица проданных билетов — снова $n$ строк по $m$ чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 4 5 6 7 8 9 1 0 1 0 1 0 1 0 1	25
1 1 1 0	0
1 1 1 1	1

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

#include <iostream>
using namespace std;

int main() {
    int n, m, totalRevenue = 0;
    cin >> n >> m;
    int* tickets = new int[n * m];
    for (int i = 0; i < n * m; i++) {
        cin >> tickets[i];
    }
    for (int i = 0, isSold; i < n * m; i++) {
        cin >> isSold;
        totalRevenue += tickets[i] * isSold;
    }
    cout << totalRevenue;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, totalRevenue = 0;

cin >> n >> m;

int* tickets = new int[n * m];

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

cin >> tickets[i];

}

for (int i = 0, isSold; i < n * m; i++) {

cin >> isSold;

totalRevenue += tickets[i] * isSold;

}

cout << totalRevenue;

return 0;

}

Решение

Считаем выручку, суммируя цену каждого билета, умноженную на $1$ либо $0$ в зависимости от того продан он или нет соответственно.

Ссылки

Ideone
e-olymp

Related Images:

e-olymp 178. Каждый третий бесплатно

20/10/2018 by Никита Семерня

Задача

Барлимен Баттербар — владелец небезызвестного трактира «Гарцующий пони», расположенного в городке Бри. Именно сюда частенько наведываются уставшие после сражений орки, чтобы отведать кружечку-другую своего любимого напитка – гномоукладчика. Однако в последнее время стали появляться другие заведения, что привело к уменьшению количества клиентов трактира. Чтобы вернуть себе клиентов, Барлимен решил сделать в своем трактире акцию, что каждый заказавший определенное количество кружек гномоукладчика, получает еще один бесплатно. Естественно, чем меньше будет это количество, тем более привлекательной будет эта акция для клиентов, но с другой стороны, если оно будет слишком маленьким, то хозяин не сможет получать прибыль (а может даже и будет терпеть убытки).

Помогите трактирщику определить минимальное количество кружек, за которое может он давать бесплатную так, чтобы получать хоть какую-нибудь прибыль.

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

Каждый тест задан в одной строке и содержит два целых числа: цену закупки одной кружки гномоукладчика $b$ и цену $c$ [latex](0 \leq b \lt c \leq 10^9)[/latex], по которой трактирщик ее продает. Последний тест содержит [latex]b = c = 0[/latex] и не обрабатывается.

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

Для каждого теста вывести в отдельной строке искомое минимальное количество кружек.

Тесты

Входные данные	Выходные данные
5 8 100 1000 13 18 0 0	2 1 3
10 11 1 10 10 20 0 0	11 1 2
4 5 2 5 0 5 0 0	5 1 1

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

#include <iostream>

using namespace std;

int main() {
    int b, c;
    cin >> b >> c;
    while (c) {
        cout << b / (c - b) + 1 << endl;
        cin >> b >> c;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int b, c;

cin >> b >> c;

while (c) {

cout << b / (c - b) + 1 << endl;

cin >> b >> c;

}

return 0;

}

Решение

Вводим первую пару. Условием работы цикла поставим ненулевой $c$ (так как из условия $b$ больше или равно нулю, а $c$ больше $b$ строго).

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

Однако, выразив прибыль как разность цены продажи и закупки, этот способ можно интерпретировать и как поиск минимального количества «разностей», превышающих закупочную цену одной кружки. Тогда можно увидеть схожесть этого действия с делением (15 / 3 — это столько же, сколько троек вмещает в себе пятнадцать). То есть нам нужно делить закупочную цену кружки на прибыль с неё. Но так как нам нужно всегда при этом иметь прибыль, будем брать целую часть от деления, и прибавлять к ней единицу (округлять вверх — не вариант в случае, например, когда цена продажи вдвое больше цены закупки — тогда ответом будет «одна кружка», что нам не подходит, потому что хоть трактир не будет в убытке, но он не получит и прибыли). Выводим формулу:

[latex]m = \bigg \lfloor \frac{b}{c — b} \bigg \rfloor + 1[/latex],

где $m$ — минимальное количество кружек.

Ссылки

e-olymp

Ideone

Related Images:

e-olymp 8533. Числа с разными цифрами

04/10/2018 by Никита Семерня

Задача

Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

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

Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

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

Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

Тесты

Входные данные	Выходные данные
2000 2015	2013 2014 2015
9875 9999	9875 9876
1000 1234	1234
3612 3612	3612
8800 8888	Standart output is empty
1000 1000	Standart output is empty

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

#include <iostream>
using namespace std;
 
int main() {        
    int x, y;                               // границы поиска
    cin >> x >> y;                          
    for (int i = x; i < y + 1; i++){
        int a = i / 1000;                   // цифры 
        int b = (i / 100) % 10;
        int c = (i / 10) % 10;
        int d = i % 10;
        if ( (a != b) && (a != c)           // проверка разности
        && (a != d) && (b != c)
        && (b != d) && (c != d) )
            cout << i << ' ';
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y; // границы поиска

cin >> x >> y;

for (int i = x; i < y + 1; i++){

int a = i / 1000; // цифры

int b = (i / 100) % 10;

int c = (i / 10) % 10;

int d = i % 10;

if ( (a != b) && (a != c) // проверка разности

&& (a != d) && (b != c)

&& (b != d) && (c != d) )

cout << i << ' ';

}

return 0;

}

Решение

Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

Ссылки

Ideone

e-olymp

Related Images:

e-olymp 206. Турист

15/09/2018 by Никита Семерня

Задача

Гена собирается на туристический слет учеников своей школы. В своем классе он был назначен ответственным за палатки. У себя дома он нашел 3 палатки: первая их них весит [latex]a_1[/latex] килограмм и вмещает [latex]b_1[/latex] человек, вторая весит [latex]a_2[/latex] килограмм и вмещает [latex]b_2[/latex] человек, третья весит [latex]a_3[/latex] килограмм и вмещает [latex]b_3[/latex] человек.

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

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

Первая строка содержит два целых числа [latex]k[/latex] и [latex]w[/latex] ([latex]1 \le k \le 15[/latex], [latex]1 \le w \le 30[/latex]). Вторая строка содержит шесть целых чисел: [latex]a_1, a_2, a_3, b_1, b_2, b_3[/latex] ([latex]1 \le a_1, a_2, a_3 \le 15[/latex], [latex]1 \le b_1, b_2, b_3 \le 30[/latex]).

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

Выведите YES, если палатки указанным образом выбрать можно, и NO в противном случае.

Тесты

Входные данные	Выходные данные
10 10 5 5 6 6 4 5	YES
2 2 2 1 2 1 1 1	NO
15 30 10 3 10 5 11 7	NO
8 8 5 4 4 5 3 6	YES
5 30 6 1 12 2 10 1	NO

Код программы (вариант с тернарной операцией)

#include <iostream>
using namespace std;
int main() {
    unsigned short int k , w , a1 , b1 , a2 , b2 , a3 , b3;
    cin >> k >> w >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;
    bool flag = ( ( ( k <= b1 ) && ( w >= a1 ) ) 
    || ( ( k <= b2 ) && ( w >= a2 ) ) 
    || ( ( k <= b3 ) && ( w >= a3 ) ) 
    || ( ( k <= b1 + b2 ) && ( w >= a1 + a2 ) ) 
    || ( ( k <= b2 + b3 ) && ( w >= a2 + a3 ) ) 
    || ( ( k <= b1 + b3 ) && ( w >= a1 + a3 ) ) 
    || ( ( k <= b1 + b2 + b3 ) && ( w >= a1 + a2 + a3 ) ) );
    cout << ( flag ? "YES" : "NO" );
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned short int k , w , a1 , b1 , a2 , b2 , a3 , b3;

cin >> k >> w >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;

bool flag = ( ( ( k <= b1 ) && ( w >= a1 ) )

|| ( ( k <= b2 ) && ( w >= a2 ) )

|| ( ( k <= b3 ) && ( w >= a3 ) )

|| ( ( k <= b1 + b2 ) && ( w >= a1 + a2 ) )

|| ( ( k <= b2 + b3 ) && ( w >= a2 + a3 ) )

|| ( ( k <= b1 + b3 ) && ( w >= a1 + a3 ) )

|| ( ( k <= b1 + b2 + b3 ) && ( w >= a1 + a2 + a3 ) ) );

cout << ( flag ? "YES" : "NO" );

return 0;

}

Код программы (линейный вариант)

#include <iostream>
using namespace std;
int main() {
    unsigned short int k , w , a1 , b1 , a2 , b2 , a3 , b3;
    cin >> k >> w >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;
    bool flag = ( ( ( k <= b1 ) && ( w >= a1 ) ) 
    || ( ( k <= b2 ) && ( w >= a2 ) ) 
    || ( ( k <= b3 ) && ( w >= a3 ) ) 
    || ( ( k <= b1 + b2 ) && ( w >= a1 + a2 ) ) 
    || ( ( k <= b2 + b3 ) && ( w >= a2 + a3 ) ) 
    || ( ( k <= b1 + b3 ) && ( w >= a1 + a3 ) ) 
    || ( ( k <= b1 + b2 + b3 ) && ( w >= a1 + a2 + a3 ) ) );
    cout 
        << ( char )( flag * 'Y' - ( flag - 1 ) * 'N' )
        << ( char )( flag * 'E' - ( flag - 1 ) * 'O' )
        << ( char )( flag * 'S' - ( flag - 1 ) * ' ' );
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned short int k , w , a1 , b1 , a2 , b2 , a3 , b3;

cin >> k >> w >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;

bool flag = ( ( ( k <= b1 ) && ( w >= a1 ) )

|| ( ( k <= b2 ) && ( w >= a2 ) )

|| ( ( k <= b3 ) && ( w >= a3 ) )

|| ( ( k <= b1 + b2 ) && ( w >= a1 + a2 ) )

|| ( ( k <= b2 + b3 ) && ( w >= a2 + a3 ) )

|| ( ( k <= b1 + b3 ) && ( w >= a1 + a3 ) )

|| ( ( k <= b1 + b2 + b3 ) && ( w >= a1 + a2 + a3 ) ) );

cout

<< ( char )( flag * 'Y' - ( flag - 1 ) * 'N' )

<< ( char )( flag * 'E' - ( flag - 1 ) * 'O' )

<< ( char )( flag * 'S' - ( flag - 1 ) * ' ' );

return 0;

}

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

Путем полного перебора получим несколько вариантов выбора палаток: взять одну из трёх палаток, две из трёх, или все три. Зададим переменную flag типа bool, принимающую значение, равное значению логического выражения, которое истинно лишь в случае удовлетворения хотя бы одного из вариантов условиям вместимости и веса, и ложно, если ни один из вариантов не удовлетворяет этим условиям. Затем с помощью тернарной операции выведем YES, если значение flag равно true, или NO, в случае противном.

Во втором варианте кода в выводе вместо тернарной операции используются операции математические, ведь условие «если А, то B, а иначе — C» на языке математики можно представить как BA — C(A-1), A = {0,1}, и так как переменная типа boolсодержит в себе значение либо 0, либо 1, а литералы типа char содержат не сами символы, а их числовой код из таблицы ASCII, то это вполне реализуемо. В данном коде происходит последовательное выведение трёх символов типа char: «Y», «E» и «S» в случае flag = 1, и «N», «O» и пробел, если flag = 0 .