e-olymp 8569. Длина строки

27/03/2019 by Александр Мога

Задача

Задана строка. Найдите ее длину.

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

Одна строка, содержащая не более 100 символов.

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

В первой строке выведите входную строку. Во второй строке выведите ее длину.

Тесты

Вход	Выход
Deus Vult! Ave Nikita!	Deus Vult! Ave Nikita! 22
Vive La France	Vive La France 14
Benjamin Franklin could not read.	Benjamin Franklin could not read. 33
Evolution Theory False!	Evolution Theory False! 39
Programming Principles 1	Programming Principles 1 24

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

C-String

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

int main() {
    char s[101];
    cin.getline(s,100);
    cout << s << endl << strlen(s);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[101];

cin.getline(s,100);

cout << s << endl << strlen(s);

return 0;

}

String

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

int main() {
    string s;
    getline(cin, s);
    cout << s << endl << s.size();
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

cout << s << endl << s.size();

return 0;

}

Решение

Формулировка задачи сама по себе диктует решение. Вводим строку, а после считаем длину.

Ссылки

e-olymp

ideone(cstring)

ideone(string)

Related Images:

e-olymp 1463. На перекрёстке

29/01/2019 by Александр Мога

Задача

Дано таблицу [latex] n \times n [/latex]. Возбуждённостью строки или столбца назовём сумму чисел в нём. Необходимо определить число, находящееся на перекрёстке наиболее возбуждённой строки и наименее возбуждённого столбца. Причём, чем выше будет этот перекрёсток (а среди них левее), тем большей будет вероятность прохождения теста.

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

Первая строка входного файла содержит число [latex]n (1 \le n \le 100)[/latex], последующие $n$ строк содержат саму таблицу. Числа в таблице натуральные и не превышают $100000$.

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

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

В выходной файл выведите единственное число – ответ к задаче.

Тесты

Вход	Выход
2 4 3 2 1	3
3 1 1 1 1 1 1 1 1 1	1
4 3 2 5 8 13 32 51 9 12 22 3 17 2 1 1 5	13
2 32 19 65 11	11
3 3 9 2 13 1 0 3 1 7	2

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

#include <iostream>
using namespace std;

int main() {
    int n; 
    int mer=0;          // most excited row
    int lec=0;          // least excited column
    cin >> n;
    int **table=new int *[n];
    for (int i=0; i<n; i++)
        table[i]= new int [n];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin >> table[i][j];
    int *exc= new int [n];      // excitation of the rows / columns
    for (int l=0; l<n; l++){
        exc[l]=0;
        for (int i=0; i<n; i++)
            exc[l]+=table[l][i];
    }
    for (int i=0; i<n; i++){
        if (exc[mer] < exc[i]){
            exc[mer]=exc[i];
            mer=i;
        }
    }
    for (int k=0; k<n; k++){
        exc[k]=0;
        for (int j=0; j<n; j++)
            exc[k]+=table[j][k];
    }
    for (int i=0; i<n; i++){
        if (exc[lec] > exc[i]){
            exc[lec]=exc[i];
            lec=i;
        }
    }
    cout << table[mer][lec];
    for (int i = 0; i < n; i++) 
        delete []table[i];
    delete []table;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int mer=0; // most excited row

int lec=0; // least excited column

cin >> n;

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

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

table[i]= new int [n];

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

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

cin >> table[i][j];

int *exc= new int [n]; // excitation of the rows / columns

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

exc[l]=0;

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

exc[l]+=table[l][i];

}

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

if (exc[mer] < exc[i]){

exc[mer]=exc[i];

mer=i;

}

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

exc[k]=0;

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

exc[k]+=table[j][k];

}

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

if (exc[lec] > exc[i]){

exc[lec]=exc[i];

lec=i;

}

cout << table[mer][lec];

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

delete []table[i];

delete []table;

return 0;

}

Решение

Создаем динамический массив, в котором вводим числа.

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

Ссылки

e-olymp

ideone

Related Images:

e-olymp 4751. Диагонали

08/01/2019 by Александр Мога

Задача

В квадратной таблице [latex] n × n [/latex] подсчитать сумы чисел, стоящих на главной и побочной диагоналях.

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

Вводится число [latex]n (1 \le n \le 500)[/latex], а затем матрица [latex] n × n [/latex]. Элементы матрицы — числа по модулю не больше [latex]10^5[/latex].

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

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

Вывести сумму чисел сначала на главной, а затем на побочной диагонали.

Тесты

Вход	Выход
4 134 475 30 424 303 151 419 235 248 166 90 42 318 237 184 36	411 1327
7 -59 21 7 5 12 868 -565 32 19 52 3 7 11 0 3 -123 -52 -99 -857 -4621 -561 11 232 86 652 46 3244 572 857 -1242 -6767 923 -575 12 1 552 232 2 63 -76 23 0 12 34 87 20 -7 767 959	967 -7282
3 1 45 82 96 29 90 757 23 12	42 868
2 12 32 99 71	83 131
5 12 32 54 76 12 95 23 21 123 0 65 32 1 773 992 5 32 155 866 912 134 44 74 11 23	36 136

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

#include <iostream>
using namespace std;

int main() {
    int n;
    int m=0;
    int c=0;
    cin >> n;
    int ** x = new int * [n];
    for (int i = 0; i < n; i++) 
        x[i] = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) 
            cin >> x[i][j];
    }
    for (int i = 0; i < n; i++){
        m+=x[i][i];
        c+=x[i][n-1-i];
    }
    for (int i = 0; i < n; i++) 
        delete []x[i];
    delete []x;
    cout <<  m << " " << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int m=0;

int c=0;

cin >> n;

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

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

x[i] = new int[n];

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

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

cin >> x[i][j];

}

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

m+=x[i][i];

c+=x[i][n-1-i];

}

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

delete []x[i];

delete []x;

cout << m << " " << c;

return 0;

}

Решение

Создаем динамический массив.

Чтобы найти сумму главной диагонали берём, лишь те элементы массива, в которых номер строки и столбца равны.

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

Ссылки

e-olymp

ideone

Related Images:

e-olymp 339. Опять несократимые

23/12/2018 by Александр Мога

Задача

Дробь $\frac{m}{n}\ $ называется правильной несократимой, если [latex] 0 < m < n [/latex] и [latex] НОД (m, n) = 1.[/latex] Найдите количество правильных несократимых дробей со знаменателем $n$.

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

Каждая строка является отдельным тестом и содержит число $n$ ([latex]n < 10^9 [/latex]). Последняя строка содержит $0$ и не обрабатывается. Количество тестов не больше $100.$

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

Для каждого $n$ в отдельной строке вывести ответ на поставленную задачу.

Тесты

Вход	Выход
12 123456 7654321 0	4 41088 7251444
552 99693 34 991 8863 0	176 56160 16 990 8862
1 5754 99291 7752 3321 0	1 1632 63272 2304 2160
99291 581293 3215788 1224262 68291 692110 0	63272 581292 1422720 565032 66792 272448
3 12 64 877 0	2 4 32 876

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

#include <iostream>
using namespace std;

int main () {
    int n, k;
    while (cin >> n and n!=0) {
        k = n;
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n/= i;
                }
                k-=k/i;
            }
        }
        if (n > 1) {
            k-=k/n;
        }
        cout << k << endl;
    }
    return 0;   
}

#include <iostream>

using namespace std;

int main () {

int n, k;

while (cin >> n and n!=0) {

k = n;

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

if (n % i == 0) {

while (n % i == 0) {

n/= i;

}

k-=k/i;

}

if (n > 1) {

k-=k/n;

}

cout << k << endl;

}

return 0;

}

Решение

Вводим поток чисел до тех пор пока не встретим $0$ и проводим над каждым числом следующую операцию.
Вычисляем количество правильных несократимых дробей с помощью функции Эйлера. Занимаемся проверкой числа на простоту. Простой, но медленный метод проверки простоты заданного числа $n$ известен как перебор делителей. Будем проверять, является ли $n$ кратным каждому целому числу от $2$ до $\sqrt{n}$.
В ходе проверки на простоту находим и другие кратные делители, если таковые имеются. При обнаружение какого то кратного найдем количество несократимым для данного несократимого. Частное, где числитель — это наше число, а знаменатель — определенный кратный делитель, будет количеством сократимых чисел, связанное с текущим кратным делителем. Естественно, если отнимем всё число от делимого, то получим число несократимых.
Повторяем цикл пока обнаруживаются новые кратные нашему числу и с каждым разом уменьшая количество несократимых.

Ссылки

Related Images:

e-olymp 4721. Отличник Вася

29/11/2018 by Александр Мога

Задача

Вася — отличник. Он радуется каждой пятёрке, которую увидит в числе. Каждое утро он едет на автобусе и считает количество пятёрок в билетике, который ему попался. По давней примете (действующей ещё со 2-го класса), он знает, что за день получит столько пятёрок, сколько их у него в билетике. По номеру сегодняшнего Васиного билетика определите, сколько пятёрок он получит в этот день.

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

Номер Васиного билетика [latex]n (0 \le n \le 9999)[/latex].

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

Выведите количество пятёрок, которое получит Вася.

Тесты

Вход	Выход
3533	1
5555	4
2521	1
5185	2
1682	0

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

#include <iostream>
using namespace std;

int main() {
	char c; 
	int k=0; // счётчик пятёрок
	while (cin >> c) // читаем номер билетика посимвольно
		if(c=='5') k++; // считаем количество пятёрок
	cout << k;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

char c;

int k=0; // счётчик пятёрок

while (cin >> c) // читаем номер билетика посимвольно

if(c=='5') k++; // считаем количество пятёрок

cout << k;

return 0;

}

Решение

Читаем номер билетика из потока ввода посимвольно, и в случае нахождения пятёрки — инкрементируем счётчик.

Ссылки

e-olymp

ideone

Related Images:

e-olymp 8594. Между A и B

29/10/2018 by Александр Мога

Задача

Заданы целые неотрицательные числа $a$ и $b$ [latex](a \le b)[/latex] и натуральное число $x$. Сколько существует чисел между $a$ и $b$ включительно, делящихся на $x$?

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

Три числа $a$, $b$ и $x$ [latex](0 \le a \le b \le 10^{18}, 1 \le x \le 10^{18}[/latex]).

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

Выведите ответ на задачу.

Тесты

Вход	Выход
2 6 5	1
1 200 3000	0
83 180 10	10
775 12004 312	36
13 42 7	5

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

#include <iostream>
using namespace std;
 
int main() {
    long long int a,b,x,k;
    cin >> a >> b >> x;
    k =b/x - a/x;
    if (!(a%x)) k++;
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long int a,b,x,k;

cin >> a >> b >> x;

k =b/x - a/x;

if (!(a%x)) k++;

cout << k;

return 0;

}

Решение

Объявим переменные a, b, x и k типа long long int, где a, b и x — соответствующие числа из условия, а k — количество чисел на промежутке [latex][a, b][/latex].

Для начала, обоснуем эквивалентность деления и нахождения количества кратных чисел на промежутке [latex][0, n][/latex] . Действительно, деление — это действие, по которому можно узнать сколько раз делитель содержится в делимом. А так как числа, кратные $x$, на промежутке [latex][0, n][/latex] встречаются начиная с $x$ с периодичностью $x$, то количество кратных чисел на промежутке является количеством вместимых $x$ в $n$. Эквивалентность доказана.

Тогда, разность количеств кратных $x$ чисел на промежутках [latex][0, b][/latex] и [latex][0, a][/latex] будет количеством таких чисел на полуинтервале [latex](a, b][/latex], так что придётся отдельно проверять, является ли $a$ кратным $x$, и в таком случае увеличивать k на единицу.

Ссылки

e-olymp

ideone

Related Images:

e-olymp 1289. Ланч

10/10/2018 by Александр Мога

Задача

Влад хочет взять с собой для ланча пару фруктов. У него есть $a$ различных бананов, $b$ различных яблок и $c$ различных груш. Сколькими способами он может выбрать 2 разных фрукта из имеющихся у него?

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

В одной строке заданы три неотрицательных числа: $a$, $b$, $c$. Все числа не превышают [latex]10^6[/latex].

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

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

Тесты

Вход	Выход
2 3 4	26
6 2 4	44
0 4 8	32
1052 886 225	1368122
772 621 124	652144

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

#include <iostream>
using namespace std;

int main() {
    long int a,b,c,n;
    cin >> a >> b >> c;
    n= a*b+b*c+a*c; 
    cout << n;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int a,b,c,n;

cin >> a >> b >> c;

n= a*b+b*c+a*c;

cout << n;

return 0;

}

Решение

Пусть у нас $1$ банан и $b$ различных яблок. Мы можем взять $1$ банан и одно яблоко $b$ способами. Так как бананов $a$, по одному яблоку и банану можем взять [latex](a \cdot b)[/latex] способами. Аналогично, так как груш $с$, то есть [latex](a \cdot с)[/latex] способов взять по одному банану и одну грушу, и [latex](c \cdot b)[/latex] способов взять по одному яблоку и одну грушу. То есть всего [latex](a \cdot b + b \cdot c + c \cdot a) [/latex].

Ссылки

e-olymp

ideone