e-olymp 7340. Поле-чудес

16/05/2018 by Данила Савчак

Задача

Петрик і Марічка захопились грою поле-чудес: Марічка записує слово, що складається з великих англійських букв, а Петрик старається розпізнати його, причому відгадана буква відкривається на всіх позиціях, де вона міститься. За яку найменшу кількість ходів Петрик зможе відгадати задане слово.

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані	Вихідні дані
[latex]GOOGLE[/latex]	[latex]4[/latex]
[latex]ALBUS[/latex]	[latex]5[/latex]
[latex]OOO[/latex]	[latex]1[/latex]

Код програми

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

int main() {
    char s[101];
    cin >> s;
    sort( s, s + strlen(s) );
    int k = 1;
    char c = s[0];
    for(int i = 0; i < strlen(s); i++){
        if( s[i] != c ){
            c = s[i];
            k++;
        }
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int main() {

char s[101];

cin >> s;

sort( s, s + strlen(s) );

int k = 1;

char c = s[0];

for(int i = 0; i < strlen(s); i++){

if( s[i] != c ){

c = s[i];

k++;

}

cout << k;

return 0;

}

Рішення завдання

Створимо місце для слова і прочитаємо його, далі використаємо функцію sort ( з бібліотеки algorithm ) для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква.

Код програми з классом string

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

int main() {
    string s;
    cin >> s;
    for (int j = 0; j < s.size(); j++) {
        int i = j + 1;
        while (i < s.size()) {
            if(s[j] == s[i] and i != j) {
                s.erase(i,1);
            }
            else i++;
        }
    }
    cout << s.size();
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string s;

cin >> s;

for (int j = 0; j < s.size(); j++) {

int i = j + 1;

while (i < s.size()) {

if(s[j] == s[i] and i != j) {

s.erase(i,1);

}

else i++;

}

cout << s.size();

return 0;

}

Рішення завдання

Створимо місце для слова і прочитаємо його, далі будемо перевіряти для кожної букви чи повторюється вона і якщо повторюється, то всі букви, окрім тої від якої перевіряємо, будемо видаляти. У кінці виведемо кількість елементів строки.

Код програми з множиною

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    set<char> k;
    set<char>::iterator iter;
    char s[101];
    cin >> s;
    for(int i = 0; i < strlen(s); i++){
        k.insert(s[i]);
    }
    cout << k.size();
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

set<char> k;

set<char>::iterator iter;

char s[101];

cin >> s;

for(int i = 0; i < strlen(s); i++){

k.insert(s[i]);

}

cout << k.size();

return 0;

}

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

Код рішення з классом string ideone.com.

Related Images:

e-olymp 5282. Седловые точки

24/02/2018 by Данила Савчак

Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

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

Выведите количество седловых точек.

Тесты

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

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

#include <iostream>
#define Unknown 1001
using namespace std;

int main() {
    int n, m,uf = 0,maxi;
    //input
    cin >> n >> m;
    int ** x = new int * [n];
    for (int i = 0; i < n; i++)
        x[i] = new int[m];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            cin >> x[i][j];
    //workspace
    int  max[m];
    for (int i = 0; i < m; i++){
        max[i] = Unknown;   
    }
    for (int i = 0; i < n; i++) {
        int min = x[i][0];
        for (int j = 1; j < m; j++) {
            if ( min > x[i][j] ) {
                min = x[i][j];
            }
        }
        for (int j = 0; j < m; j++) {
            if (x[i][j] == min) {
                if (max[j] != Unknown){
                    maxi = max[j];  
                }
                else {
                    maxi = x[i][j];
                    for (int l = 0; l < n; l++) {
                        if (maxi < x[l][j]){
                            maxi = x[l][j];
                        }
                    }
                    max[j] = maxi;
                }
                if ( maxi == min) {
                    uf++;
                }
            }
        }
    }
    //output
    cout << uf;
    return 0;
}

#include <iostream>

#define Unknown 1001

using namespace std;

int main() {

int n, m,uf = 0,maxi;

//input

cin >> n >> m;

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

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

x[i] = new int[m];

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

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

cin >> x[i][j];

//workspace

int max[m];

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

max[i] = Unknown;

}

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

int min = x[i][0];

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

if ( min > x[i][j] ) {

min = x[i][j];

}

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

if (x[i][j] == min) {

if (max[j] != Unknown){

maxi = max[j];

}

else {

maxi = x[i][j];

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

if (maxi < x[l][j]){

maxi = x[l][j];

}

max[j] = maxi;

}

if ( maxi == min) {

uf++;

}

//output

cout << uf;

return 0;

}

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

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!

Ссылки

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

Код решения на ideone.com.

Related Images:

e-olymp 203. Кубики-2

02/01/2018 by Данила Савчак

Задача

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

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

В первой строке – количество разложенных перед Витэком кубиков [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex], в следующей строке последовательность из [latex]N[/latex] цифр на кубиках через пробел.

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

Наименьшее количество кубиков, которое нужно правее доставить Витэку.

Тесты

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

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

#include <iostream>
using namespace std;

int main() {
    int n, h=0, k=0;
    cin >> n;
    int A[n];
    for ( int i = 0; i < n; i++ ) {
        cin >> A[i];
    }
    for ( int i = 0; i < n; i++ ) {
        if ( A[n-1] == A[i] ) {
            int t = 1;
            for ( int j = i + 1; j < n - 1; j++ ) {
                if ( A[j] != A[ n - 1 - t ] ) {
                    k++;
                }
                t++;
            }
            if ( k == 0 ) {
                h = i;
                break;
            }
            else k = 0;
        }
    }
    cout << h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, h=0, k=0;

cin >> n;

int A[n];

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

cin >> A[i];

}

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

if ( A[n-1] == A[i] ) {

int t = 1;

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

if ( A[j] != A[ n - 1 - t ] ) {

k++;

}

t++;

}

if ( k == 0 ) {

h = i;

break;

}

else k = 0;

}

cout << h;

return 0;

}

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

Читаем поток данных переводя каждое прочитанное число в элемент массива. Для каждого элемента массива проверяем его равенство с последний и если да, то через два цикла(начиная с начала и с конца) проверяем равенство остальных элементов массива по двое и если да, то увеличиваем переменную, от которой будет зависеть ответ, если она в конце будет равна [latex]0[/latex], то выведем число равное номеру элемента массива равного последнему.

Ссылки

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

Код решения на ideone.com.

Related Images:

e-olymp 1317. Дни рождения

02/01/2018 by Данила Савчак

Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

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

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

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

Для каждого значения [latex]n[/latex] в отдельной строке вывести вероятность того, что хотя бы у двух из [latex]n[/latex] людей дни рождения (число и месяц) совпадают. Искомую вероятность выводить в процентах и округлять до [latex]8[/latex] знаков после запятой как указано в примере.

Тесты

Входные данные	Выходные данные
[latex]12[/latex]	[latex]16.70247888\%[/latex]
[latex]28[/latex]	[latex]65.44614723\%[/latex]
[latex]399[/latex]	[latex]100.00000000\%[/latex]

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

#include <iostream>
using namespace std;

int main() {
    int n;
    double k = 1;
    while ( cin >> n ) {
        for ( int i = 366 - n; i <= 365; i++ ) {
            k = k * i;
            k = k / 365;
        }
        cout << fixed;
        cout.precision(8);
        cout << 100 * ( 1 - k ) << "%" << endl;
        k=1;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double k = 1;

while ( cin >> n ) {

for ( int i = 366 - n; i <= 365; i++ ) {

k = k * i;

k = k / 365;

}

cout << fixed;

cout.precision(8);

cout << 100 * ( 1 - k ) << "%" << endl;

k=1;

}

return 0;

}

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

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

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

Код решения на ideone.com.

Related Images:

e-olymp 513. Проблема Николая

28/12/2017 by Данила Савчак

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

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

Вывести искомое количество способов.

Тесты

Входные данные	Выходные данные
[latex]500[/latex] [latex]2001[/latex]	[latex]0[/latex]
[latex]4[/latex] [latex]5[/latex]	[latex]4[/latex]
[latex]4[/latex] [latex]7[/latex]	[latex]3[/latex]
[latex]15[/latex] [latex]213[/latex]	[latex]147[/latex]
[latex]10[/latex] [latex]3[/latex]	[latex]0[/latex]

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

#include <iostream>
using namespace std;

int main() {
    int n, m, k = 1;
    cin >> n >> m;
    if ( n >= m) {
        cout << 0;
    }
    else {
        for ( int i = 2; i <= n; i++ ) {
            k = ( k * i ) % m;
        }
        cout << k; 
    }
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int n, m, k = 1;

cin >> n >> m;

if ( n >= m) {

cout << 0;

}

else {

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

k = ( k * i ) % m;

}

cout << k;

}

return 0;

}

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

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

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

Код решения на ideone.com.

Related Images:

e-olymp 7410. Маршрутне таксі

17/12/2017 by Данила Савчак

Задача

У годину пік на зупинку одночасно під’їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.

Вхідні дані

Три натуральних числа, що не перевищують [latex]100[/latex] — кількості пасажирів у першій, другій і третій маршрутках відповідно.

Вихідні дані

Виведіть одне число — найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово [latex]IMPOSSIBLE[/latex] (великими літерами).

Тести

Вхідні дані	Вихідні дані
[latex]1[/latex] [latex]1[/latex] [latex]4[/latex]	[latex]2[/latex]
[latex]1[/latex] [latex]2[/latex] [latex]4[/latex]	[latex]IMPOSSIBLE[/latex]
[latex]1[/latex] [latex]3[/latex] [latex]5[/latex]	[latex]2[/latex]
[latex]9[/latex] [latex]3[/latex] [latex]9[/latex]	[latex]4[/latex]

Код програми

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

int main() {
    int m1 , m2 , m3 , x;
    cin >> m1 >> m2 >> m3;
    if ( ( m1 + m2 + m3 ) % 3 == 0 ) {
        if ( m1 != m2 and m1 != m3 and m2 != m3 ) {
            cout << ( max ( max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ) );
        }
        else if ( m1 == m2 ) { 
            int x;
            x = ( m3 - ( m1 + m2 + m3 ) / 3 );
            if ( x < 0 ) { 
                cout << -x; 
            } 
            else cout<<x;
        }
        else if ( m1 == m3 ) { 
            int x;
            x = ( m2 - ( m1 + m2 + m3 ) / 3 );
            if ( x < 0 ) { 
                cout << -x;
            } else cout << x;
        }
        else if ( m2 == m3 ) { 
            int x;
            x = ( m1 - ( m1 + m2 + m3 ) / 3 );
            if ( x < 0 ) { 
                cout << -x; 
            } 
            else cout << x;
            }
        }
    else cout << "IMPOSSIBLE";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int m1 , m2 , m3 , x;

cin >> m1 >> m2 >> m3;

if ( ( m1 + m2 + m3 ) % 3 == 0 ) {

if ( m1 != m2 and m1 != m3 and m2 != m3 ) {

cout << ( max ( max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ) );

}

else if ( m1 == m2 ) {

int x;

x = ( m3 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 ) {

cout << -x;

}

else cout<<x;

}

else if ( m1 == m3 ) {

int x;

x = ( m2 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 ) {

cout << -x;

} else cout << x;

}

else if ( m2 == m3 ) {

int x;

x = ( m1 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 ) {

cout << -x;

}

else cout << x;

}

else cout << "IMPOSSIBLE";

return 0;

}

Рішення завдання

Спочатку відріжемо усі варіанти при яких розподілити пасажирів порівну не вийде так, що коли іх загальна кількість не ділиться націло на [latex]3[/latex] виводимо [latex]IMPOSSIBLE[/latex]. Коли розподілити пасажирів можна, розглядаємо [latex]4[/latex] випадки : коли у різних маршрутках кількість людей різна та коли у будь-яких двох маршрутках кількість однакова. Коли кількість різна, від максимальної кількості людей у трьох маршрутках віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей(у кінці ми маємо отримати це число, як кількість пасажирів у всіх маршрутних таксі), коли у двох маршрутках кількість однакова , то від кількості людей(у маршрутці, де іх більше або менше) віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей. Якщо відповідь менше [latex]0[/latex] то помножуюмо на [latex]-1[/latex].

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Related Images:

e-olymp 472. Вероятность

05/11/2017 by Данила Савчак

Задача

Однорукий бандит

Вася придумал новую игру. Для игры требуется полоска из трёх стоящих в ряд клеток, фишки [latex]n[/latex] различных видов и непрозрачный мешок.

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

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

Чтобы оценить среднюю частоту выигрышей, Вася решил найти такую величину: количество выигрышных вариантов заполнения полоски разделить на количество всех вариантов заполнения полоски. Количество всех вариантов заполнения полоски Вася нашёл самостоятельно (получилось [latex] n^3[/latex] ), а вот для нахождения количества выигрышных вариантов он обратился к своему знакомому, лучше разбирающемуся в математике и программировании, т.е. к Вам. Continue reading →