Задача

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

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [latex]N[/latex] команд по [latex]K[/latex] крыс в каждой. Соревнования проводятся в [latex]К[/latex] раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.

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

Первая строка содержит два целых числа [latex]N[/latex] и [latex]K[/latex] [latex](0 < N ≤ 20, 0 < K ≤ 100000)[/latex]. Следующие [latex]K[/latex] строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.

#	Входные данные	Выходные данные
1	3 3 20 10 30 15 20 20 30 30 20	3
2	3 3 20 -10 -30 15 25 20 30 -30 20	1
1	3 3 0 -10 -30 15 25 20 30 -30 20	2

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

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

3 3
20 10 30
15 20 20
30 30 20

3 3
20 -10 -30
15 25 20
30 -30 20

3 3
0 -10 -30
15 25 20
30 -30 20

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

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

double INF = 1e18;

int sgn(long long a){
    if(a < 0) return -1;
    else if(a == 0) return 0;
    else return 1;
}

struct logNumber{
    long long sign;
    double value;
    logNumber(int sign = 1, double value = 0){
        this->sign = sign;
        this->value = value;
    }
    void operator *= (long long a){
        sign *= sgn(a);
        if(sign == 0) value = 0;
        else value += log(abs(a));
    }
    bool operator >(logNumber a){
        return (sign > a.sign) or  (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value);
    }
    bool operator ==(logNumber a){
        return sign == a.sign and value == a.value;
    }
};

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    logNumber mult[n];
    for(int i =0; i < k; i++){
        for(int j=0; j < n; j++){
            long long temp;
            cin>>temp;
            mult[j] *= temp;
        }
    }
    logNumber maxMult = mult[0];
    int maxTeam = 0;
    for(int i = 0; i < n; i++){
        if (mult[i] > maxMult){
            maxMult = mult[i];
            maxTeam = i;
        }
        else if(mult[i]==maxMult){
            maxTeam = max(i, maxTeam);
        }
    }
    cout << maxTeam + 1;




    return 0;
}

#include <iostream>

#include <cmath>

#include <climits>

using namespace std;

double INF = 1e18;

int sgn(long long a){

if(a < 0) return -1;

else if(a == 0) return 0;

else return 1;

}

struct logNumber{

long long sign;

double value;

logNumber(int sign = 1, double value = 0){

this->sign = sign;

this->value = value;

}

void operator *= (long long a){

sign *= sgn(a);

if(sign == 0) value = 0;

else value += log(abs(a));

}

bool operator >(logNumber a){

return (sign > a.sign) or (sign == 1 and a.sign == 1 and value > a.value) or (sign == -1 and a.sign == -1 and value < a.value);

}

bool operator ==(logNumber a){

return sign == a.sign and value == a.value;

}

};

int main() {

cin.tie(NULL);

ios_base::sync_with_stdio(false);

int n,k;

cin>>n>>k;

logNumber mult[n];

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

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

long long temp;

cin>>temp;

mult[j] *= temp;

}

logNumber maxMult = mult[0];

int maxTeam = 0;

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

if (mult[i] > maxMult){

maxMult = mult[i];

maxTeam = i;

}

else if(mult[i]==maxMult){

maxTeam = max(i, maxTeam);

}

cout << maxTeam + 1;

return 0;

}

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

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

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, n, k, count=0;
    cin >> l >> n >> k;
    for(int i=0; i<n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
            count++;
        else
        {
            int a, b, c;
            int deltaX=x2-x1;
            int deltaY=y2-y1;
            a=deltaY;
            b=-deltaX;
            c=y1*deltaX-x1*deltaY;
            if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))
                count++;
        }
    }
    cout << count/k+1 << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int l, n, k, count=0;

cin >> l >> n >> k;

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

{

int x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else

{

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))

count++;

}

cout << count/k+1 << endl;

return 0;

}

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: кот

e-olymp 54. Мурзик

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

e-olymp 49. Кот учёный

Задача

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

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

Тесты

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

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

Ссылки

Related Images: