e-olymp 209. Защита от копирования

01/06/2019 by Владислав Бебик

Задача

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

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

На первой строке два числа $N (N ≤ 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 5 1 2 2 3 3 5 5 2 2 4	1
2	12 20 1 2 2 3 3 4 4 5 5 6 6 1 7 8 8 9 9 10 10 11 11 12 12 7 6 3 1 4 2 5 12 9 7 10 8 11 6 12 3 9	2

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

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

int n,m;
vector<int> vis;

bool dfs(int w0,int w,vector<vector<int>> &G) {
    vis[w0]=1;
    for (int q=1; q<=n; q++) {
        if (G[w0][q]>0 && vis[q]==0) {
            if (q==w || dfs(q,w,G)==0) {
                G[w0][q]--; 
                G[q][w0]++;
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    int u,v,i,k,res=10000000;
    scanf("%d %d\n",&n,&m);
    vector<vector<int>> G0(n+1,vector<int>(n+1,0));
    for (i=0; i<m; i++) {
        scanf("%d %d\n",&u,&v);
        G0[u][v]=1;
        G0[v][u]=1;
    }
    for (i=2; i<=n; i++) {
        k=0;
        vector<vector<int>> G=G0;
        vis=vector<int>(n+1,0);
        while (!dfs(1,i,G)) {
            k++;
            vis=vector<int>(n+1,0);
        }
        if (k<res) res=k;
    }
    printf("%d",res);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m;

vector<int> vis;

bool dfs(int w0,int w,vector<vector<int>> &G) {

vis[w0]=1;

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

if (G[w0][q]>0 && vis[q]==0) {

if (q==w || dfs(q,w,G)==0) {

G[w0][q]--;

G[q][w0]++;

return 0;

}

return 1;

}

int main() {

int u,v,i,k,res=10000000;

scanf("%d %d\n",&n,&m);

vector<vector<int>> G0(n+1,vector<int>(n+1,0));

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

scanf("%d %d\n",&u,&v);

G0[u][v]=1;

G0[v][u]=1;

}

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

k=0;

vector<vector<int>> G=G0;

vis=vector<int>(n+1,0);

while (!dfs(1,i,G)) {

k++;

vis=vector<int>(n+1,0);

}

if (k<res) res=k;

}

printf("%d",res);

return 0;

}

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

С помощью векторов будем запоминать связи между смешариками, где смешарики — это вершины. Две вершины будут смежными, если смешарики дружат между собой. Будем использовать обход в глубину. Для решения задачи воспользуемся алгоритмом Форда-Фалкерсона, чтобы найти максимальный поток. Будем искать максимальный поток от одной вершины до каждой. Из всех найденных максимальных потоков выбираем минимальный — это и будет ответом на задачу.

Ссылки

Related Images:

e-olymp 1124. Алфавитное граффити

07/04/2019 by Владислав Бебик

Задача

Граффити — один из видов современной варварской живописи. Вася, как и надлежит достойному потомку варваров, решил также заняться этим довольно перспективным с его точки зрения делом и увековечить свое пребывание в школе надписями в стиле граффити.
Так как по рисованию у Васи была твердая «двойка», а он начал еще и изучать английский, после изучения довольно тяжело давшейся ему в произношении третьей буквы английского алфавита он решил увековечивать свои муки в изучении этого опять трудного для него предмета отображением каждого этапа, связанного с изучением очередной буквы, соответствующей надписью на школьной стене.
Художественные изыскания Васи после изучения $3$-й и $7$-й букв приведены в примере выходных данных.
Так как с каждым этапом сделать правильную надпись Васе становилось всё трудней и трудней, напишите программу, которая поможет ему сделать шпаргалку для нанесения очередного узора.

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

Единственное число $N (3 ≤ N ≤ 26) -$ количество изученных букв английского алфавита.

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

Надпись на стене, сделанная Васей после изучения $N$ букв английского алфавита.

Объяснение:

Точками в примере обозначены пробелы для удобства подсчета, так как и с математикой, соответственно, у Васи тоже были проблемы… 🙂

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	3	a..a a.ab aabc
2	7	a……a a…..ab a….abc a…abcd a..abcde a.abcdef aabcdefg

Код программы (string)

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

int main() {
    string s;
    char q='a';
    int n,k,i,j;
    cin >> n;
    for (i=0, k=n-1; i<n; i++, k--) {
        s=s+q;
        q++;
        cout << 'a';
        for (j=0; j<k; j++) cout << " ";
        cout << s << "\n";
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char q='a';

int n,k,i,j;

cin >> n;

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

s=s+q;

q++;

cout << 'a';

for (j=0; j<k; j++) cout << " ";

cout << s << "\n";

}

return 0;

}

Код программы (c-string)

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

int main() {
    char s[30];
    char q='a';
    int n,k,i,j;
    cin >> n;
    for (i=0, k=n-1; i<n; i++, k--) {
        s[i]=q;
        q++;
        cout << 'a';
        for (j=0; j<k; j++) cout << " ";
        for (j=0; j<i+1; j++) cout << s[j];
        cout << "\n";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[30];

char q='a';

int n,k,i,j;

cin >> n;

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

s[i]=q;

q++;

cout << 'a';

for (j=0; j<k; j++) cout << " ";

for (j=0; j<i+1; j++) cout << s[j];

cout << "\n";

}

return 0;

}

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

В каждой строке сначала выводим букву $a$. В первой строке выводим $n-1$ количество пробелов и строку $s$, которая содержит изначально
букву $a$. При переходе на новые строки к строке $s$ будем добавлять новую букву, которая идёт следующей в алфавите от последней буквы данной строки. В каждых последующих строках выводим на один пробел меньше и строку $s$. Выводим новые строки, чтобы в итоге вывести последнюю букву под номером $n$ в алфавите.

Ссылки

Related Images:

e-olymp 8651. Браслети (Bangles)

20/03/2019 by Владислав Бебик

Задача

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). $(4 ≤ N ≤ 300)$. У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Объяснение:

Існує два варіанти з’єднання: $(3,4) – (4,2) – (2,5) – (5,3)$ та $(1,4) – (4,5) – (5,3) – (3,1)$ У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	5 8 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5	5

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

#include <iostream>
#define MAX 301
using namespace std;

int x[MAX][MAX];
int y[MAX][MAX];
int main() {
    int n,m,i,j,e,u,v,q,z,r=0;
    scanf("%d%d",&n,&m);
    for (i=0; i<m; i++) {
        scanf("%d%d",&u,&v);
        x[u-1][v-1]=1; x[v-1][u-1]=1;
    }
    for (i=0; i<n-1; i++) {
        for (j=i+1; j<n; j++) {
            q=0;
            for (e=0; e<n; e++) {
                if (x[i][e]==1 && x[j][e]==1) q++;
            }
            y[i][j]=q;
        }
    }
    for (e=0; e<n; e++) {
        for (i=e+1; i<n; i++) {
            if (x[e][i]==1) {
                for (j=i+1; j<n; j++) {
                    if (x[e][j]==1) {
                        z=y[i][j];
                        if (z>1) {
                            z--;
                            r+=z;
                            y[i][j]=z;
                        }
                    }
                }
            }
        }
    }
    printf("%d",r);
    return 0;
}

#include <iostream>

#define MAX 301

using namespace std;

int x[MAX][MAX];

int y[MAX][MAX];

int main() {

int n,m,i,j,e,u,v,q,z,r=0;

scanf("%d%d",&n,&m);

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

scanf("%d%d",&u,&v);

x[u-1][v-1]=1; x[v-1][u-1]=1;

}

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

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

q=0;

for (e=0; e<n; e++) {

if (x[i][e]==1 && x[j][e]==1) q++;

}

y[i][j]=q;

}

for (e=0; e<n; e++) {

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

if (x[e][i]==1) {

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

if (x[e][j]==1) {

z=y[i][j];

if (z>1) {

z--;

r+=z;

y[i][j]=z;

}

printf("%d",r);

return 0;

}

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

В ячейке $x[u-1][v-1]$ стоит единица тогда и только тогда, когда у нас есть звено, имеющее на одном конце замок номер $u$, а на другом $- v$. Теперь построим таблицу, где будет записано в ячейке $y[u-1][v-1]$ количество их общих пар замков, где $u$ и $v$ это пара замков. Потом в первой таблице будем проходить по каждой строке и искать все возможные пары единиц в столбиках, пусть $u$ и $v$ это индекс выбранных столбиков. И если ячейка $y[u-1][v-1]$ больше единицы, то будем отнимать единицу в этой ячейке, чтобы отбросить случай, когда в браслете первый и четвёртый замок одинаковой. Полученное число в этой ячейке будем добавлять к ответу. А запоминать в эту же ячейку на единицу меньше, чтобы потом при подсчёте результата не посчитать один и тот же браслет два раза. Рассмотрим для наглядности пример: когда дано $5$ типов замков и $7$ типов деталей: $1-3, 1-4, 2-4, 2-5, 3-4, 3-5, 4-5$. То есть для каждой пары запомним количество общих замков, так как нам нужно, чтобы количество общих замков для пар было больше единицы, выпишем для наглядности нужные: $1-5$ имеет $2$, $2-3$ имеет $2$, $3-4$ имеет $2$, $4-5$ имеет $2$ общих замка. В первой строке в первой таблице единственная пара это $3-4$, так как общих замков этой пары больше единицы, то пара нам подходит. То есть варианты браслета $1-3-4-1$ и $1-3-4-5$, поэтому отнимем единицу и получим количество нужных браслетов, то есть один браслет уже есть, это $1-3-4-5$. Смотрим дальше, во второй строке тоже одна пара $4-5$. Варианты получаемый браслетов $2-4-5-2$ и $2-4-5-3$, опять отнимем один вариант и остальные браслеты запомним, то есть браслет $2-4-5-3$. В третей строке получится пара $4-5$, но там один вариант $3-4-5-3$, что не подходит, если бы мы ранее не запоминали на единицу меньше, то сейчас мы бы посчитали второй раз тот же браслет $3-4-5-2$, который уже есть. В итоге мы получили $2$ браслета, то есть $1-3-4-5$ и $2-4-5-3$, что есть верным ответом.

Ссылки

Related Images:

e-olymp 8515. Homo or Hetero?

12/12/2018 by Владислав Бебик

Task

Consider a list of numbers with two operations:
$\cdot$ insert number— adds the specified number to the end of the list.
$\cdot$ delete number— removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number $4$ to the list $[1,2,1]$ is the list $[1,2,1,4]$. If we delete the number $1$ from this list, we get the list $[2,1,4]$, but if we delete the number $3$ from the list $[1,2,1,4]$,the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list $[2,2]$ is homogeneous, the list $[2,1,4]$ is heterogeneous, the list $[1,2,1,4]$ is both, and the empty list is neither homogeneous, nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list’s homogeneity and heterogeneity after each operation.

Input

The first line of the input file contains an integer number $N$ $(1 \leq N \leq 10^{5})$ — the number of operations to handle. Following $N$ lines contain one operation description each. The operation description consists of a word “insert” or “delete”, followed by an integer number $K$ $(-10^{9} \leq K \leq 10^{9})$ — the operation argument.

Output

For each operation output a line, containing a single word, describing the state of the list after the operation:

$\cdot$ “both” — if the list is both homogeneous and heterogeneous.
$\cdot$ “homo” — if the list is homogeneous, but not heterogeneous.
$\cdot$ “hetero” — if the list is heterogeneous, but not homogeneous.
$\cdot$ “neither” — if the list is neither homogeneous nor heterogeneous.

Tests

#	Input	Output
1	11 $insert$ 1 $insert$ 2 $insert$ 1 $insert$ 4 $delete$ 1 $delete$ 3 $delete$ 2 $delete$ 1 $insert$ 4 $delete$ 4 $delete$ 4	$neither$ $hetero$ $both$ $both$ $hetero$ $hetero$ $hetero$ $neither$ $homo$ $neither$ $neither$
2	15 $insert$ -50 $insert$ -2 $insert$ 1 $insert$ 4 $delete$ 1 $delete$ 3 $delete$ -2 $delete$ -50 $insert$ 4 $delete$ 4 $delete$ 4 $insert$ 100 $insert$ -150 $delete$ -150 $delete$ 100	$neither$ $hetero$ $hetero$ $hetero$ $hetero$ $hetero$ $hetero$ $neither$ $homo$ $neither$ $neither$ $neither$ $hetero$ $neither$ $neither$

Code 1

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

struct Key {
    int a;
    int b;
};
Key x[200000];

int main() {
    int n,k,i,i1,j1=0,j2=0,p,p1=0,p2=0,q,l,m,r;
    char s[10];
    cin >> n;
    char y[n]; int z[n]; int u[n];
    for (i=0; i<n; i++) {
        cin >> s >> k;
        y[i]=s[0]; z[i]=k;
        if (s[0]=='i') {
            u[j1]=k; j1++;
        }
    }
    sort(u,u+j1);
    for (i=0; i<j1; i++) {
        if (u[i]!=u[i+1]) {
            x[j2].a=u[i]; j2++;
        }
    }
    for (i=0; i<n; i++) {
        p=0; l=0; r=j2-1;
        while (l<=r && p==0) {
            m=(l+r)/2;
            if (z[i]==x[m].a) {
                i1=m; p=1;
            } else if (z[i]<x[m].a) r=m-1;
            else l=m+1;
        }
        if (p==1) {
            q=x[i1].b;
            if (y[i]=='i') {
                q++;
                if (q==1) p1++;
                if (q==2) p2++;
                x[i1].b=q;
            } else if (q>0) {
                q--;
                if (q==0) p1--;
                if (q==1) p2--;
                x[i1].b=q;
            }
        }
        if (p1>=2 && p2>=1) cout << "both" << endl;
        else if (p1<2 && p2>=1) cout << "homo" << endl;
        else if (p1>=2 && p2<1) cout << "hetero" << endl;
        else cout << "neither" << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct Key {

int a;

int b;

};

Key x[200000];

int main() {

int n,k,i,i1,j1=0,j2=0,p,p1=0,p2=0,q,l,m,r;

char s[10];

cin >> n;

char y[n]; int z[n]; int u[n];

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

cin >> s >> k;

y[i]=s[0]; z[i]=k;

if (s[0]=='i') {

u[j1]=k; j1++;

}

sort(u,u+j1);

for (i=0; i<j1; i++) {

if (u[i]!=u[i+1]) {

x[j2].a=u[i]; j2++;

}

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

p=0; l=0; r=j2-1;

while (l<=r && p==0) {

m=(l+r)/2;

if (z[i]==x[m].a) {

i1=m; p=1;

} else if (z[i]<x[m].a) r=m-1;

else l=m+1;

}

if (p==1) {

q=x[i1].b;

if (y[i]=='i') {

q++;

if (q==1) p1++;

if (q==2) p2++;

x[i1].b=q;

} else if (q>0) {

q--;

if (q==0) p1--;

if (q==1) p2--;

x[i1].b=q;

}

if (p1>=2 && p2>=1) cout << "both" << endl;

else if (p1<2 && p2>=1) cout << "homo" << endl;

else if (p1>=2 && p2<1) cout << "hetero" << endl;

else cout << "neither" << endl;

}

return 0;

}

Code 2 (map)

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

int main() {
    int n,k,p1=0,p2=0,q;
    char s[10];
    map <int,int> x;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> s >> k;
        q=x[k];
        if (s[0]=='i') {
            q++;
            if (q==1) p1++;
            if (q==2) p2++;
            x[k]=q;
        } else if (q>0) {
            q--;
            if (q==0) p1--;
            if (q==1) p2--;
            x[k]=q;
        }
        if (p1>=2 && p2>=1) cout << "both" << endl;
        else if (p1<2 && p2>=1) cout << "homo" << endl;
        else if (p1>=2 && p2<1) cout << "hetero" << endl;
        else cout << "neither" << endl;
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int n,k,p1=0,p2=0,q;

char s[10];

map <int,int> x;

cin >> n;

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

cin >> s >> k;

q=x[k];

if (s[0]=='i') {

q++;

if (q==1) p1++;

if (q==2) p2++;

x[k]=q;

} else if (q>0) {

q--;

if (q==0) p1--;

if (q==1) p2--;

x[k]=q;

}

if (p1>=2 && p2>=1) cout << "both" << endl;

else if (p1<2 && p2>=1) cout << "homo" << endl;

else if (p1>=2 && p2<1) cout << "hetero" << endl;

else cout << "neither" << endl;

}

return 0;

}

Solution

Let’s memorize two numbers on each step: how many of different numbers and different pairs of identical numbers in a one-dimensional array. If there are more than one different numbers in the array and more than zero different pairs of the same numbers, then print "both". If the sum of different numbers in the array is less than two and different pairs of identical numbers are more than zero, then we enter "homo". If there are more than one different numbers in the array and less than one different pairs of the same numbers, then enter "hetero". In other cases, we enter "neither". In the last case, when an array is $0$ numbers or $1$ number.

Links

Related Images:

Proggy-Buggy 2018: Задача E. Треугольник или не треугольник?

04/12/2018 by Владислав Бебик

Задача

Баги считает треугольником любые три различные точки плоскости, соединенные отрезками. Даже написал диссертацию: «Треугольник или не треугольник? Вот в чём вопрос!», которая породила множество вопросов. Его очень утомили вопросы из разряда, «а это треугольник?». Если хотите, помогите Баги: напишите программу «Баги-бот», которая вместо Баги отвечала бы на вопрос, образуют ли три заданные точки треугольник.

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

Строка содержащая три пары целых чисел, координаты $x1$, $y1$, $x2$, $y2$, $x3$, $y3$ $(0\leq xi,yi\leq1000)$, разделенных пробелом.

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

Строка «$yes$» или «$no$» (без кавычек) — ответ программы «Баги-бот».

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 0 0 1	$yes$
2	1 1 1 2 1 3	$yes$
3	1 1 1 1 1 2	$no$

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

#include <iostream>
using namespace std;

int main() {
    int x1,y1,x2,y2,x3,y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	if ((x1==x2 && y1==y2) || (x2==x3 && y2==y3) || (x3==x1 && y3==y1)) cout << "no";
	else cout << "yes";
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int x1,y1,x2,y2,x3,y3;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

if ((x1==x2 && y1==y2) || (x2==x3 && y2==y3) || (x3==x1 && y3==y1)) cout << "no";

else cout << "yes";

return 0;

}

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

В задаче главное внимательно прочитать условие. Если любые две заданные точки совпадают, то программа «Баги-бот» должна ответить no, иначе yes.

Ссылки

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

Related Images:

e-olymp 1118. Арбузы

26/11/2018 by Владислав Бебик

Задача

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

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

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

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

Вывести два числа: массу арбуза, который Иван Васильевич купит теще, и массу арбуза, который он купит себе, или вывести сообщение «$Ooops!$» (без кавычек), если кто-то останется без арбуза.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 3 5 8 4 6	$3$ $8$
2	8 6 12 9 5 8 15 7 10	$5$ $15$
3	1 10	$Ooops!$

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

#include <iostream>
using namespace std;

int main() {
    int n,min,max,x;
    cin >> n;
    if (n<2) cout << "Ooops!";
    else {
        cin >> min; 
        max=min;
        for (int i=0; i<n-1; i++) {
            cin >> x;
            if (x<min) min=x;
            if (x>max) max=x;
        }
        cout << min << " " << max;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,min,max,x;

cin >> n;

if (n<2) cout << "Ooops!";

else {

cin >> min;

max=min;

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

cin >> x;

if (x<min) min=x;

if (x>max) max=x;

}

cout << min << " " << max;

}

return 0;

}

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

Из потока данных, где $n$ чисел найдём минимальное и максимальное число. Если $n<2$, то кто-то останется без арбуза, поэтому выведем «$Ooops!$» (без кавычек).

Ссылки

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

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

Related Images:

e-olymp 8595. Собаки и обезьяны

15/11/2018 by Владислав Бебик

Задача

У Барыша есть $n$ собак и $m$ обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю $10^{9}+7$. Имейте в виду, что собаки и обезьяны между собой различаются.

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

Два числа $n$ и $m$ $\left(1 \leq n, m \leq 10^{5}\right)$.

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

Выведите количество различных вариантов построения обезьян и собак по модулю $10^{9}+7$.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2	8
2	3 2	12
3	1 8	0
4	100000 100000	530123477
5	99999 100000	768947656

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

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

int main() {
    int n,m,k;
    long long f=1,p=1000000007;
    cin >> n >> m;
    if (abs(n-m)>1) cout << "0";
    else {
        k=min(n,m);
        for (int i=1; i<=k; i++) { 
            f=f*i;
            if (f>=p) f=f%p;
        }
        f=f*f;
        if (f>=p) f=f%p;
        if (n==m) f=2*f;
        else f=f*max(n,m);
        if (f>=p) f=f%p;
        cout << f;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n,m,k;

long long f=1,p=1000000007;

cin >> n >> m;

if (abs(n-m)>1) cout << "0";

else {

k=min(n,m);

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

f=f*i;

if (f>=p) f=f%p;

}

f=f*f;

if (f>=p) f=f%p;

if (n==m) f=2*f;

else f=f*max(n,m);

if (f>=p) f=f%p;

cout << f;

}

return 0;

}

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

В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Количество размещений собак равно $n!.$ Количество размещений обезьян равно $m!.$ Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет $2n!m!$ и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом $n!m!$ и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. Поэтому после каждого умножения будем искать остаток при делении числа на $10^{9}+7$, если число будет превышать $10^{9}+7$.

Ссылки

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

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

Related Images:

e-olymp 8371. Четное или нечетное

28/10/2018 by Владислав Бебик

Задача

Задано натуральное число $n$. Определить его четность.

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

Одно натуральное число $n$ $\left(1 \leq n \leq 10^{9}\right)$.

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

Если число $n$ четное, то вывести EVEN. Если нечетное, то вывести ODD.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	ODD
2	99	ODD
3	500	EVEN
4	1000000000	EVEN

Код программы (Линейные вычисления)

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n;
  (n%2==0) && (cout << "EVEN") || (n%2==1) && (cout << "ODD");
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

(n%2==0) && (cout << "EVEN") || (n%2==1) && (cout << "ODD");

return 0;

}

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

Если число четное, то будет выполняться условие n%2==0, тогда выводим EVEN. Если число нечетное, то будет выполняться условие n%2==1, тогда выводим ODD.

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

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n;
  cout << (n % 2 == 0 ? "EVEN" : "ODD"); //проверяем на четность
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << (n % 2 == 0 ? "EVEN" : "ODD"); //проверяем на четность

return 0;

}

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

Число четное, если оно делится на $2$ без остатка, значит выполняется условие: n % 2 == 0. В противном случае, число будет нечетным.

Ссылки

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

Код программы на IdeOne (Линейные вычисления)

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