e-olimp 1310. Наибольший блок

28/06/2016 by Аня Шохина

Задача

Блоком строки [latex]S[/latex] в позиции [latex]i[/latex] назовём наибольшую подстроку [latex]S[/latex], которая начинается в позиции [latex]i[/latex] и совпадает с префиксом [latex]S[/latex]. Длину блока в позиции 0 считать равной нулю. Вычислить длину наибольшего блока заданной строки [latex]S[/latex].

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

Единственная строка [latex]S[/latex] [latex]\left(\left|S\right|\leq{10}^{6}\right)[/latex].

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

Длина наибольшего блока строки [latex]S[/latex].

Тесты

Входные данные	Выходные данные
abaabaab	5
aaaaa	4
aaabaab	2

Реализация

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

int main() {
    string s;
    getline(cin,s); // используем данную функцию, так как это выгодно по времени
    int n =  s.length();
    vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции
    int l=0, r=0; //левая и правая граница "отрезка совпадения"
    for (int i=1; i<n; i++) { 
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    int max=z[0];
    for (int i=1; i<z.size(); i++){
        if (max<z[i]){
            max=z[i];
        }
    }
    cout<<max<<endl;
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main() {

string s;

getline(cin,s); // используем данную функцию, так как это выгодно по времени

int n = s.length();

vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции

int l=0, r=0; //левая и правая граница "отрезка совпадения"

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

if (i <= r)

z[i] = min (r-i+1, z[i-l]);

while (i+z[i] < n && s[z[i]] == s[i+z[i]])

z[i]++;

if (i+z[i]-1 > r){

l = i;

r = i+z[i]-1;

}

int max=z[0];

for (int i=1; i<z.size(); i++){

if (max<z[i]){

max=z[i];

}

cout<<max<<endl;

return 0;

}

Код на ideone.com

Засчитанное решение на e-olimp.com

Решение

Для решения данной задачи необходимо рассмотреть алгоритм эффективного вычисления [latex]Z[/latex]-функции. Создадим массив [latex]z[/latex], где [latex]i[/latex]-ый элемент равен наибольшему числу символов, начиная с [latex]i[/latex]-ой позиции, совпадающих с первыми символами заданной строки [latex]s[/latex]. Эффективность алгоритма состоит в том, что при вычислении очередного элемента массива [latex]z[/latex] мы будем использовать уже вычисленные ранее значения. Назовем отрезком совпадения подстроку, совпадающую с префиксом заданной строки. Тогда искомое значение [latex]z\left [ i \right ][/latex] — это длина самого длинного отрезка совпадения, начинающегося в позиции [latex]i[/latex]. Из всех найденных отрезков совпадения будем хранить тот, который оканчивается правее всего. Положим, что [latex]l[/latex] и [latex]r[/latex] — индексы начала и конца данного отрезка соответственно. Тогда при вычислении [latex]z\left [ i \right ][/latex] возможны две ситуации: [latex]i>r[/latex] и [latex]i\leq r[/latex]. В первом случае позиция [latex]i[/latex] лежит за пределами проанализированной части строки . Тогда ищем значение [latex]Z[/latex]-функции перебором до тех пор, пока не дойдем до несовпадения или конца заданной строки. Стоит отметить, что если [latex]z\left [ i \right ]>0[/latex], следует изменить индексы отрезка совпадений. Во втором случае текущая позиция [latex]i[/latex] лежит внутри отрезка совпадений [latex]\left [ l,r \right ][/latex]. Так как подстроки [latex]s\left [ l\ldots r \right ][/latex] и [latex]s\left [ 0\ldots r-l \right ][/latex] совпадают, то в качестве значения [latex]z\left [ i \right ][/latex] можно взять значение [latex]z\left [ i-l \right ][/latex]. Однако, значение [latex]z\left [ i-l \right ][/latex] может быть слишком большим для данного блока (суффикс строки будет меньше, чем данное значение, чего быть не может). Следовательно, [latex]z\left [ i \right ][/latex]-ому элементу будем присваивать значение минимума из длины суффикса [latex]\left ( r-i+1 \right )[/latex] и [latex]z\left [ i-l \right ][/latex]. Далее используем вышеописанный перебор. В конечном итоге максимальный элемент массива — длина наибольшего блока заданной строки.

Related Images:

e-olimp 4852. Кратчайшее расстояние

27/06/2016 by Аня Шохина

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex] [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты

Входные данные	Выходные данные
3 1 0 1 0 0 0 0 0 0 0	0 1 -1
6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3 1 0 1 0 1 0 1 0 1 0	0 1 2

Реализация

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    const int inf=4000; // задаем бесконечность 
    int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности 
    cin>>n>>start_position;
    start_position--; // в условии счет начинается с единицы, а в программе с нуля 
    vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины
    for (int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>x;
            if (x==1){
                verges[i].push_back(j);
            }
        }
    }
    bool *used = new bool [n];
    for (int i=0; i<n; i++){
        used[i]=false;
    }
    int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до  i-ой
    for (int i=0; i<n; i++){
        distances[i]=inf; 
    }
    distances[start_position] = 0;
    for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины 
        int minimum=inf;
        int position = 0;
        for (int j=0; j<n; j++){
            if (distances[j]<minimum && !used[j]){
                minimum=distances[j];
                position=j;
            }
        }
        used[position]=true; //запоминаем, что применили алгоритм для вершины 
        for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры 
            distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
        }
    }
    for (int i=0; i<n; i++) {
        cout<<((distances[i]==inf)?-1:distances[i])<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

const int inf=4000; // задаем бесконечность

int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности

cin>>n>>start_position;

start_position--; // в условии счет начинается с единицы, а в программе с нуля

vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины

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

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

cin>>x;

if (x==1){

verges[i].push_back(j);

}

bool *used = new bool [n];

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

used[i]=false;

}

int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой

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

distances[i]=inf;

}

distances[start_position] = 0;

for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины

int minimum=inf;

int position = 0;

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

if (distances[j]<minimum && !used[j]){

minimum=distances[j];

position=j;

}

used[position]=true; //запоминаем, что применили алгоритм для вершины

for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры

distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));

}

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

cout<<((distances[i]==inf)?-1:distances[i])<<" ";

}

return 0;

}

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

Related Images:

А291б

18/06/2016 by Аня Шохина

Задача

Даны действительные числа [latex]{a}_{1},\ldots,{a}_{30}[/latex].

Получить: [latex]\min\left({a}_{1}{a}_{16},{a}_{2}{a}_{17},\ldots,{a}_{15}{a}_{30}\right)[/latex]

Тесты

Входные данные	Выходные данные
2 4 8 1 3 5 4 8 1 10 5 2 4 9 3 9 1 5 4 3 7 8 2 11 1 4 5 10 3 8	4
0 8 9 6 11 2 5 3 6 9 8 8 5 20 1 4 8 12 15 7 6 31 0 5 14 5 0 14 11 2	0
8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2	16

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

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

int main() {
    vector <double> a;
    double b;
    
    while (cin >> b){
        a.push_back(b);
    }
    double min=a[0]*a[a.size()/2];
    for(int i=0; i<(a.size())/2; i++){
        if (a[i]*a[(a.size()/2+i)]< min){
            min = a[i]*a[(a.size()/2+i)];
        }
    }
    cout << min;

    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> a;

double b;

while (cin >> b){

a.push_back(b);

}

double min=a[0]*a[a.size()/2];

for(int i=0; i<(a.size())/2; i++){

if (a[i]*a[(a.size()/2+i)]< min){

min = a[i]*a[(a.size()/2+i)];

}

cout << min;

return 0;

}

Код на ideone.com

Решение

Для решения задачи мы условно разделяем исходную последовательность действительных чисел на две подпоследовательности.: [latex]{a}_{1},\ldots,{a}_{15}[/latex] и [latex]{a}_{16},\ldots,{a}_{30}[/latex]. Длина подпоследовательностей в два раза меньше длины исходной последовательности. Таким образом, разность индексов элементов, которые необходимо перемножить, равна длине подпоследовательности. Тогда перемножаем необходимые элементы и находим минимальное значение из полученных результатов.

Related Images:

e-olymp 506. Новый компилятор

18/06/2016 by Аня Шохина

Задача взята с сайта e-olymp.com.

Постановка задачи

Вам необходимо преобразовать множество старых программ для новой версии компилятора. Для этого необходимо заменить «->» на «.» везде, кроме комментариев. Комментарии в данном языке программирования начинаются с символов «//» и продолжаются до конца строки. Напишите программу, выполняющую такое преобразование.

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

Входной файл содержит от 1 до 500 строк длиной не более 50 символов с ASCII-кодами от 32 до 127 – текст программы, которую нужно преобразовать.

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

В выходной файл вывести преобразованный текст программы.

Тесты

Исходный текст программы

Преобразованный текст программы

Test* t = new Test( );
t--> = 1;
t->b = 2
t->go() ; // a=1, b=2 -> a=2, b=3
t--> = 1;

Test* t = new Test( );

t--> = 1;

t->b = 2

t->go() ; // a=1, b=2 -> a=2, b=3

t--> = 1;

Test* t = new Test( );
t-. = 1;
t.b = 2
t.go() ; // a=1, b=2 -> a=2, b=3
t-. = 1;

Test* t = new Test( );

t-. = 1;

t.b = 2

t.go() ; // a=1, b=2 -> a=2, b=3

t-. = 1;

 Test* t = new Test();
t->a = 1;
t->b = 2;
t->go(); // a=1, b=2 -> a=2, b=3

Test* t = new Test();

t->a = 1;

t->b = 2;

t->go(); // a=1, b=2 -> a=2, b=3

 Test* t = new Test();
t.a = 1;
t.b = 2;
t.go(); // a=1, b=2 -> a=2, b=3

Test* t = new Test();

t.a = 1;

t.b = 2;

t.go(); // a=1, b=2 -> a=2, b=3

 Test* t = new Test( );
//t--> = 1;
t----->b = 2
t->-go() ;
t--> = 1;

Test* t = new Test( );

//t--> = 1;

t----->b = 2

t->-go() ;

t--> = 1;

 Test* t = new Test( );
//t--> = 1;
t----.b = 2
t.-go() ;
t-. = 1;

Test* t = new Test( );

//t--> = 1;

t----.b = 2

t.-go() ;

t-. = 1;

Реализация

#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int c;
    int a;
    char b;
    c = getchar();
    while ((a = getchar()) != EOF) {
        if (c == '-') { //проверяем на наличие комбинации "->"
            if (a == '>') {
                cout << ".";
                a = getchar();
            } else {
                putchar(c);
            }
        } else if (c == '/') { //проверяем на наличие комбинации "//"
            putchar(c);
            if (a == '/') {
                putchar(a);
                while ((b = getchar()) != '\n') {
                    putchar(b); //печатаем комментарий не изменяя до конца строки
                }
                cout << endl;
                a = getchar();
            }
        } else putchar(c);
        c = a;
    }
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int c;

int a;

char b;

c = getchar();

while ((a = getchar()) != EOF) {

if (c == '-') { //проверяем на наличие комбинации "->"

if (a == '>') {

cout << ".";

a = getchar();

} else {

putchar(c);

}

} else if (c == '/') { //проверяем на наличие комбинации "//"

putchar(c);

if (a == '/') {

putchar(a);

while ((b = getchar()) != '\n') {

putchar(b); //печатаем комментарий не изменяя до конца строки

}

cout << endl;

a = getchar();

}

} else putchar(c);

c = a;

}

Код на ideone.com

Засчитанное решение на e-olymp.com

Ход решения

Для решения данной задачи используем функцию getchar, так как данная функция может работать с управляющими символами (когда программа находит комментарий, необходимо печатать без изменений до конца строки). Так как по условию задачи нам нужно найти такие комбинации символов, как «//» и «->» , мы при каждом проходе цикла, сравнивая символы входных данных с теми, что надо найти, запоминаем два соседних символа.

Related Images:

MLoops15

15/04/2016 by Аня Шохина

Задача. Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]m>0[/latex] (количество столбцов) и [latex]n>0[/latex] (количество строк). При чем [latex]k<m[/latex]. Многоточие означает продолжение последовательности.

112233...kk112233...kk1122
k112233...kk112233...kk112
kk112233...kk112233...kk11
.kk112233...kk112233...kk1
..kk112233...kk112233...kk
...kk112233...kk112233...k

112233...kk112233...kk1122

k112233...kk112233...kk112

kk112233...kk112233...kk11

.kk112233...kk112233...kk1

..kk112233...kk112233...kk

...kk112233...kk112233...k

Тесты

[latex] m[/latex]	[latex] n[/latex]	[latex] k[/latex]	Результат
25	4	8	1122334455667788112233445 8112233445566778811223344 8811223344556677881122334 7881122334455667788112233
8	9	3	11223311 31122331 33112233 23311223 22331122 12233112 11223311 31122331 33112233
4	4	3	1122 3112 3311 2331

Код

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int m, n,k;
    double l=1;
    int counter = 0;
    cin >> m >> n >>k;
    for (int i=1; i<=n; i++){
        if(counter) l=k*2-(counter-1); //вычисляем первый элемент строки
        if(l<2) counter=0; //проверяем элемент на положительное значение
        for (int j=1; j<=m; j++){
            if(l>k*2){ 
                l=1;
            }
            cout <<  ceil(l/2) ;
            l++;
        }
        cout << endl;
        counter++;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int m, n,k;

double l=1;

int counter = 0;

cin >> m >> n >>k;

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

if(counter) l=k*2-(counter-1); //вычисляем первый элемент строки

if(l<2) counter=0; //проверяем элемент на положительное значение

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

if(l>k*2){

l=1;

}

cout << ceil(l/2) ;

l++;

}

cout << endl;

counter++;

}

return 0;

}

Код на ideone.com

Решение

Для решения данной задачи введем дополнительную переменную [latex]l[/latex], которая будет накапливать в себе количество напечатанных символов в строке. Каждое число в строке повторяется дважды, следовательно печатать будем число, равное целой части [latex]\left( l\div 2 \right)[/latex].

Обратим внимание на начало каждой строки. В каждой следующей строке мы сдвигаем последовательность на одно число вправо. Тогда значение переменной [latex] l[/latex] на второй строке должно быть максимально возможным [latex]\left(k\cdot2 \right)[/latex] и уменьшаться на единицу при каждом переходе на следующую строку.

Related Images:

MLoop 15

25/11/2015 by Аня Шохина

Задача. Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x)=\csc x[/latex] . При вычислениях допустимо использовать только арифметические операции.

Тесты

[latex]x[/latex]	[latex]\varepsilon[/latex]	Результат
42	0.3	-8.09848e-05
8	0.15	-0.0117188
55.5	0.04	-3.50972e-055
-12	0.6	0.00347222
-82	0.0001	-3.23677e-08

Код

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

int main() {
    double x, e;
    cin>>x>>e;
    double sum1=x; // в случае, когда  i=0
    double sum2=-x*x*x/6; // в случае, когда i=1
    for (int i=2; abs(1/sum2-1/sum1)>=e; i++)
    {
        sum1=sum2;
        sum2*=-x*x/((2*i)*(2*i+1)); 
    }
    cout<<1/sum2<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, e;

cin>>x>>e;

double sum1=x; // в случае, когда i=0

double sum2=-x*x*x/6; // в случае, когда i=1

for (int i=2; abs(1/sum2-1/sum1)>=e; i++)

{

sum1=sum2;

sum2*=-x*x/((2*i)*(2*i+1));

}

cout<<1/sum2<<endl;

return 0;

}

Код программы на ideone.com

Решение :

Косеканс — это тригонометрическая функция, которою можно определить формулой [latex]\csc x=\frac{1}{\sin x}[/latex]. Таким образом, мы можем разложить функцию [latex]\sin x[/latex] в бесконечную сумму степенных функций, воспользовавшись формулой Тейлора. Получим, что [latex]\sin x=x-\frac{{x}^{3}}{3!}+\frac{{x}^{5}}{5!}-\dots=\sum_{n=0}^{\propto}\frac{{-1}^{n}\times{x}^{2n+1}}{\left(2n+1\right)!}[/latex]. Слагаемые данной суммы являются геометрической прогрессией, знаменатель который можно найти по формуле [latex]\frac{a_n}{a_{n-1}}=\frac{\frac{{-1}^{n}\times{a}^{2n+1}}{\left(2n+1 \right)!}}{\frac{{-1}^{n-1}\times{a}^{2n-1}}{\left(2n-1 \right)!}}=\frac{\left( -1\right){a}^{2}}{2n\times\left( 2n+1\right)}[/latex]. Будем вычислять сумму до тех пор, пока разность [latex]n[/latex]-го и [latex]\left ( n+1 \right )[/latex]-го слагаемых будет больше заданной точности.

Related Images:

Mif 17.1

30/09/2015 by Аня Шохина

Задача. Принадлежит ли точка [latex]\left(x;y \right)[/latex] фигуре на рисунке?

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» , если не принадлежит.

Тесты

[latex]x[/latex]	[latex]y [/latex]	Результат
4	-2	NO
2	1	YES
0	3	YES
5	0	NO
0	-1	NO

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	double x, y;
	cin>>x>>y;
	if ((abs(x)+y<=4) && (y>=0)){
		cout<<"YES";
	}
	else cout<<"NO";
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, y;

cin>>x>>y;

if ((abs(x)+y<=4) && (y>=0)){

cout<<"YES";

}

else cout<<"NO";

return 0;

}

Код программы на ideone.com

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

Related Images:

e-olymp 192. Просто Фибоначчи

30/09/2015 by Аня Шохина

Задача взята с сайта e-olymp.com.

Найти [latex]N[/latex]-е по порядку простое число Фибоначчи.

Во входном файле число [latex]N[/latex], [latex]\left(1\leq N\leq 10 \right)[/latex] В выходной файл следует записать [latex]N[/latex]-е по порядку простое число Фибоначчи.

Тесты

[latex]N[/latex]	Простое число Фибоначчи
3	5
5	89
7	1597
9	514229
10	433494437

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

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

int main() {
	int n;
	cin >> n;
	int a, b, c, d, k;
	a = 1;
	b = 1;
	c = 2;
	bool x;
	int counter = 0;
	while (counter < n){
		x = true;
		c = a + b;
		a = b;
		b = c;
		for (int j = 2; j <= sqrt(c) && x; j++) {
			if((c%j) == 0){
				x = false;
			}
		}
		if (x){
			counter ++;
		}
	}
	cout << c;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

int a, b, c, d, k;

a = 1;

b = 1;

c = 2;

bool x;

int counter = 0;

while (counter < n){

x = true;

c = a + b;

a = b;

b = c;

for (int j = 2; j <= sqrt(c) && x; j++) {

if((c%j) == 0){

x = false;

}

if (x){

counter ++;

}

cout << c;

return 0;

}

Код на ideone.com

Выполненное задание на сайте e-olimp.com здесь.

Алгоритм решения

Нам необходимо вычислить первые десять элементов последовательности Фибоначчи. Для этого будем использовать цикл. Пусть [latex] a<b<c [/latex] , где [latex] a, b, c [/latex] являются членами последовательности Фибоначчи. Обозначим, что элемент последовательности равен сумме двух ему предшествующих элементов. Далее присвоим переменным [latex]a, b[/latex] значения следующих элементов последовательности соответственно. Таким образом присваиваем переменной [latex] a [/latex] значение переменной [latex] b [/latex] , переменной [latex] b[/latex] — значение переменной [latex] c [/latex] , а переменной [latex] c [/latex] — значение равное [latex](a+b)[/latex].
Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя. Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу. А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].

Related Images:

Mif 5

26/09/2015 by Аня Шохина

Задача. Даны действительные числа [latex] x, y, z.[/latex] Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.

Тесты

[latex] x [/latex]	[latex] y [/latex]	[latex]z[/latex]	Наименьшее число	Наибольшее число
100.56	812.34	-12	-12	812.34
-722.5	812.34	-722.5	-722.5 (2)	812.34
256	145695	145695	256	145695 (2)
0	0	0	0 (3)	0(3)
-518.3	-759.3	-1995.6	-1995.6	-518.3

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

#include <iostream>
using namespace std;
 
int main() {
	long double x, y, z, min, max;
	int counter, number;
	counter = 1;
	number = 1;
	cin >> x >> y >> z;
	min = 0;
	min = x;
	if(y < min){
		min = y;
		counter = 1;
	}
	else if(y == min){
		counter ++;
	}
	if(z < min){
		min = z;
		counter = 1;
	}
	else if (z == min){
		counter++;
	}
	max = 0;
	max = y;
	if(x > max){
		max = x;
		number = 1;
	}
	else if(x == max){
		number ++;
	}
	if(z > max){
		max = z;
		number = 1;
	}
	else if(z == max){
		number ++;
	}
	if(counter !=1 ){
		cout << min << "("<<counter<<")" << endl;
	}
	else {
		cout << min << endl;
	}
	if(number != 1){
		cout << max << "("<<number<<")" << endl;
	}
	else {
		cout << max << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long double x, y, z, min, max;

int counter, number;

counter = 1;

number = 1;

cin >> x >> y >> z;

min = 0;

min = x;

if(y < min){

min = y;

counter = 1;

}

else if(y == min){

counter ++;

}

if(z < min){

min = z;

counter = 1;

}

else if (z == min){

counter++;

}

max = 0;

max = y;

if(x > max){

max = x;

number = 1;

}

else if(x == max){

number ++;

}

if(z > max){

max = z;

number = 1;

}

else if(z == max){

number ++;

}

if(counter !=1 ){

cout << min << "("<<counter<<")" << endl;

}

else {

cout << min << endl;

}

if(number != 1){

cout << max << "("<<number<<")" << endl;

}

else {

cout << max << endl;

}

return 0;

}

Здесь находится код в ideone.com

Решение

Так как по условию нам даны действительные числа, то, чтобы охватить наибольший диапазон чисел, используем тип данных long double;
Для того, чтобы решить данную задачу мы предполагаем, что одна из переменных является наименьшей[latex] (x=min)[/latex] , а потом сравниваем ее с остальными переменными.
Возможно, наше предположение верно. Тогда присваиваем счетчику значение [latex] 1 [/latex]. Если какая-либо из оставшихся переменных равна минимуму, то увеличиваем значение счетчика на единицу.
Если значение переменной [latex] y[/latex] или [latex] z[/latex] меньше минимума, то наше предположение было не верно. Тогда присваиваем значение минимального числа соответствующей переменной, а счетчику — значение [latex] 1 [/latex] . Если несколько переменных имеют наименьшее значение, то при каждом совпадении значения счетчик увеличивается на единицу.
Аналогичный подход применяем к максимальному значению.

Related Images:

ML5

22/09/2015 by Аня Шохина

Задача. Даны два действительных числа. Найти среднее арифметическое этих чисел и среднее геометрическое их модулей.

Тесты

Первое число	Второе число	Среднее арифметическое	Среднее геометрическое
156	82	119	113.102
-1158	2569	705.5	1724.79
256.3	289.5	272.9	272.395
9854.08	-493	4680.54	2204.1
-544.59	-12	-278.295	80.8398

Алгоритм решения

Так как в постановке задачи не указан диапазон чисел, то рациональнее всего использовать тип данных long double, охватывающий наибольшее количество возможных вариантов входных данных.
Нам необходимо найти среднее арифметическое чисел, которое представляет собой сумму всех зафиксированных значений, делённую на их количество. Для нашей задачи формула приобретает следующий вид: [latex]A=\frac{a+b}{2}[/latex].
Для нахождения среднего геометрического модулей двух чисел воспользуемся формулой [latex] G=\sqrt{\left|x_1\times x_2 \right|} [/latex].

Здесь находится код в ideone.com

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

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

int main() {
	long double a, b;
	cin >> a >> b;
	cout << (a + b) / 2 << endl; //среднее арифметическое чисел
	cout << sqrt(abs(a * b)) << endl; //среднее геометрическое модулей чисел
 return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long double a, b;

cin >> a >> b;

cout << (a + b) / 2 << endl; //среднее арифметическое чисел

cout << sqrt(abs(a * b)) << endl; //среднее геометрическое модулей чисел

return 0;

}

Related Images:

e-olymp 157. Зоопарк

14/09/2015 by Аня Шохина

Задача взята с сайта e-olymp.com.

Постановка задачи

В зоопарке [latex] N [/latex] клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра — очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все [latex] N [/latex] клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.

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

В первой строке входных данных находится число [latex] N [/latex] [latex](2\leq N\leq 100)[/latex] — количество клеток в зоопарке.

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

Выведите одно число — количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.

Тесты

4	6
15	182
30	812
48	2162
60	3422

Реализация

#include <iostream>
using namespace std;
 
int main() {
    int n; // количество клеток
    int c; //количество способов поселения 
    cin >> n;
    c = (n - 1) * (n - 2);
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // количество клеток

int c; //количество способов поселения

cin >> n;

c = (n - 1) * (n - 2);

cout << c;

return 0;

}

Здесь находится код в ideone.com

Решение

Рассмотрим возможные расположения клеток при условии, что одна из обезьян занимает первую клетку. Очевидно, что другая обезьяна не может занимать первую и вторую клетки, т к клетки должны быть разными и не соседними. Следовательно, существует [latex] (n — 2) [/latex] вариантов расположения второй обезьяны. Далее предположим, что первая обезьяна занимает вторую клетку. Тогда количество вариантов расположения второй обезьяны равно [latex] (n-2-1) = (n-3) [/latex] . И так далее, до тех пор пока не останется один вариант расположения второй обезьяны. Таким образом, ключ к решению задачи лежит в рассмотрении количества вариаций расположения клеток обезьян как арифметической прогрессии. Исходя из условия задачи, нам необходимо найти сумму первых [latex] n [/latex] членов прогрессии. Формула для вычислений: [latex] S=\frac{(a_1 + a_k}{2}*k [/latex], где [latex] a_1=n-2 [/latex] и [latex] a_k=1 [/latex], и [latex] k=n-2 [/latex]. Применяя математические преобразования, получаем что [latex] S=\frac{(n-1) * (n-2)}{2} [/latex]. Однако, имеет значение не только, непосредственно, какие две клетки заняты, но и какая именно из обезьян занимает определенную клетку. То есть при [latex] n=3 [/latex] мы имеем лишь пару клеток, которые можем использовать, но два способа поселения. Следовательно, полученное выражение необходимо умножить на два. Таким образом, мы вывели необходимую нам формулу.

Выполненное задание на сайте e-olimp.com здесь.