Category Archives: 5. Массивы

Задачи на использование классических массивов и работе с ними через указатели и ссылочные типы.

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

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

cin >> x[i];

// Processing

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

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Санта Клаус
Кубики — 3 — используйте массив bool для хранения предположений о потери кубика для каждой из 26+26=52 букв.
Прямоугольник — используйте массив точек.

Опубликованные решения

e-olymp 54. Мурзик

27/06/2018 by Данилов Андрей

Задача

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

Одной ночью ему приснилось, что он судья на математических соревнованиях крыс (да, в наш век цифровых технологий даже крысы не остаются за гранью научно-технического прогресса). Соревнования проводятся среди [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

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

#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;

}

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

e-olymp 634. Вклад «Антикризисный»

26/06/2018 by Яна Колчинская

Задача

Постоянные клиенты одного очень крупного банка (ООКБ) недавно получили возможность открыть новый вклад — «Антикризисный». Этот вклад отличается непростой схемой начисления процентов, поэтому вам, как единственному сотруднику ИТ-отдела банка, было поручено написание программы, которая будет вычислять сумму вклада с начисленными процентами.

Вклад «Антикризисный» может быть открыт на любой срок, но дата окончания вклада должна быть не позже $31$ декабря $2009$ года, процентная ставка по вкладу составляет $p$ процентов годовых. Это означает, что если в начале некоторого периода в $d$ дней, в течение которого сумма вклада не менялась, сумма вклада составляла $x$ рублей, то по окончании этого периода она будет составлять $x\cdot\left(1+\frac{p}{100}\cdot\frac{d}{365}\right)$.

Начисление процентов на вклад осуществляется ежемесячно, в последний день месяца (или в последний день действия вклада), при этом сумма процентов присоединяется ко вкладу. Таким образом, если на первое мая сумма вклада составляла $x$ рублей, то $31$ мая ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)$ рублей, и на первое июня сумма вклада составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)\right)$, а в июне проценты будут начисляться уже на эту сумму.

Если же последний день вклада был $20$ мая, то в этот день ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)$ рублей, а сумма вклада, которую получит клиент банка составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)\right)$. Аналогично выполняются расчеты и для случая, когда вклад был открыт не в первый день месяца. Так, например, если вклад был открыт $18$ февраля, то $28$ февраля к сумме вклада будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{11}{365}\right)$ рублей, а если же он был открыт $28$ февраля, то в тот же день $28$ февраля к сумме будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{1}{365}\right)$ рублей.

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

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

Первая строка входного файла содержит три целых числа: исходную сумму вклада $x$, процентную ставку $p$ и длительность вклада $d \left(1 ≤ x ≤ 100000, 1 ≤ p ≤ 200, 1 ≤ d ≤ 365\right)$. Вторая строка входного файла содержит дату открытия вклада в формате «день-месяц-год». День и месяц обозначаются числами, при этом у чисел, меньших десяти, присутствуют ведущие нули. Гарантируется,что вклад открыт в $2009$ году, и дата его окончания также находится в $2009$ году.

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

В выходной файл выведите ответ на задачу c точностью $6$ знаков после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	1000 10 27 18-07-2009	1007.410921
2	1000 12 70 29-06-2009	1023.172779
3	1000 12 37 17-08-2009	1012.200053
4	1000 15 37 21-10-2009	1015.253781
5	1000 15 85 12-08-2009	1035.351224

Код

#include <iostream>
#include <iomanip>
 
using namespace std;
int main() {
    double s;
    int p, d;
    int dM[12] = {31, 28, 31, 30 ,31, 30, 31, 31, 30, 31, 30, 31};
    cin>>s>>p>>d;
    int day, month;
    char a;
    cin>>day>>a>>month;
    month--;
    int dP = 0;
    for(int i = month; dP < d; i++){
        double z = 0;
        for(int j = (i==month?day : 1); j <= dM[i] && dP < d; j++){
            dP++;
            z +=  s*(p/100.0)*(1/365.0);
        }
        s += z;
    }
    cout<<fixed<<setprecision(6)<<s;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double s;

int p, d;

int dM[12] = {31, 28, 31, 30 ,31, 30, 31, 31, 30, 31, 30, 31};

cin>>s>>p>>d;

int day, month;

char a;

cin>>day>>a>>month;

month--;

int dP = 0;

for(int i = month; dP < d; i++){

double z = 0;

for(int j = (i==month?day : 1); j <= dM[i] && dP < d; j++){

dP++;

z += s*(p/100.0)*(1/365.0);

}

s += z;

}

cout<<fixed<<setprecision(6)<<s;

return 0;

}

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

Основная проблема в том, что каждый месяц вкладчик получает процент от своего вклада, который считается в цикле. Но процент берётся не от вклада, а от новой суммы, полученной в прошлом месяце, поэтому каждый раз необходимо помнить про уже имеющиеся деньги, чтобы получать каждый месяц новую сумму уже с процентом.

Ссылки

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

Related Images:

e-olymp 50. Разрезанное число

25/06/2018 by Алиса Ворохта

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные	Выходные данные
$5$ $3$ $13$ $85$ $45$	$4$
$11$ $2$ $1$ $111$	$1$
$11$ $3$ $11$ $8$ $11$	$0$
$71$ $8$ $4018916609$ $7495223237$ $3405637482$ $3166003637$ $8998228133$ $1141886496$ $9124347310$ $7736090711$	$584$

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

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long nums[9];
long long k;
long long d;
long long quantity = 0;
long long was[40320];
bool Was(long long h) {
    long long c = 0;
    for (int i = 0; i < quantity; i++) {
        if (was[i] == h) c++;
    }
    if (c == 0) {
        was[quantity] = h;
        return true; 
    }
    else
    return false;
}
void Swap(long long a,long long b)
{
    long long t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}
void Generate(long long n)
{
    if (n==k)
    {
        long long sum = 0;
        long long p = 1;
        long long h = 0;
        long long hash = 1;
        for (long long i = k - 1; i >= 0; i--) {
            long long subs = nums[i];
            sum += nums[i]%d*p;
            p *= pow(10, long(log10(nums[i]))+1);
            p = p%d;
            while (subs!= 0) {
                h += subs%10*hash;
                hash *= 101;
                subs /= 10;
            }
        }   
        if (sum%d == 0 && Was(h) == true) {
            quantity++; 
        }
    }
    else { 
        for(long long j = n; j < k;j++) {
            Swap(n,j);
                    Generate(n+1);
                    Swap(n,j);
        }
    }   
}
 
int main()
{
    cin >> d >> k;
    for(long long i = 0; i < k; i++) {
        cin >> nums[i];
    }
    Generate(0);
    cout << quantity;
    return 0;
}

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

long long nums[9];

long long k;

long long d;

long long quantity = 0;

long long was[40320];

bool Was(long long h) {

long long c = 0;

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

if (was[i] == h) c++;

}

if (c == 0) {

was[quantity] = h;

return true;

}

else

return false;

}

void Swap(long long a,long long b)

{

long long t = nums[a];

nums[a] = nums[b];

nums[b] = t;

}

void Generate(long long n)

{

if (n==k)

{

long long sum = 0;

long long p = 1;

long long h = 0;

long long hash = 1;

for (long long i = k - 1; i >= 0; i--) {

long long subs = nums[i];

sum += nums[i]%d*p;

p *= pow(10, long(log10(nums[i]))+1);

p = p%d;

while (subs!= 0) {

h += subs%10*hash;

hash *= 101;

subs /= 10;

}

if (sum%d == 0 && Was(h) == true) {

quantity++;

}

else {

for(long long j = n; j < k;j++) {

Swap(n,j);

Generate(n+1);

Swap(n,j);

}

int main()

{

cin >> d >> k;

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

cin >> nums[i];

}

Generate(0);

cout << quantity;

return 0;

}

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

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

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

Related Images:

e-olymp 47. Паркет из треугольников

24/06/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

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

{

arr[i] = new int*[horSize];

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

{

arr[i][j] = new int[z];

for (int k = 0; k < 2; k++)

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

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

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

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

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

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

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

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

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

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

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

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

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

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

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

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

Search[firstNumberx - 1];

1	Search[firstNumberx - 1];

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

Related Images:

e-olymp 2670.Координаты соседей

20/06/2018 by Илья Черноморец

Задача

Для клетки с координатами $\left(x, y\right)$ в таблице размером $M\times N$ выведите координаты ее соседей. Соседними называются клетки, имеющие общую сторону.

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

Даны натуральные числа $M, N, x, y \left(1 \leqslant x \leqslant M \leqslant 109, 1 \leqslant y \leqslant N \leqslant 109\right).$

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

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

Тесты

Входные данные	Выходные данные
3 3 2 2	1 2 2 1 2 3 3 2
23 23 21 13	20 13 22 13 21 12 21 14
11 8 10 5	9 5 11 5 10 4 10 6

Код решения

#include <iostream>

using namespace std;
int x, y, n, m;
int main()
{
    cin >> n >> m >> x >> y;
    if (x > 1) cout << x - 1 << " " << y << endl;
    if (x < n) cout << x + 1 << " " << y << endl;
    if (y > 1) cout << x << " " << y - 1 << endl;
    if (y < m) cout << x << " " << y + 1 << endl;
}

#include <iostream>

using namespace std;

int x, y, n, m;

int main()

{

cin >> n >> m >> x >> y;

if (x > 1) cout << x - 1 << " " << y << endl;

if (x < n) cout << x + 1 << " " << y << endl;

if (y > 1) cout << x << " " << y - 1 << endl;

if (y < m) cout << x << " " << y + 1 << endl;

}

Решение

Для решения этой задачи стоит просмотреть все варианты координат соседних точек. То есть, нужно прибавить единицу к абсциссам и ординатам заданной точки. Но стоит учесть, что таблица у нас ограничена: $1 \leqslant x \leqslant M, 1 \leqslant y \leqslant N$

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com

Related Images:

e-olymp 930. Номер мобильного телефона

09/06/2018 by Томас Пасенченко

Задача

Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.

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

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

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

В первой строке вывести количество отсутствующих в номере цифр. Во второй строке в порядке возрастания вывести отсутствующие цифры, разделенные пробелом.

Тесты

Входные данные	Выходные данные
0631562976	2 4 8
2139087	3 4 5 6
1111111111	9 0 2 3 4 5 6 7 8 9
7	9 0 1 2 3 4 5 6 8 9
4848	8 0 1 2 3 5 6 7 9
0921234567	1 8
6723545	4 0 1 8 9
9867453210	0

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

#include <iostream>
using namespace std;

int main() {
    // Номер мобильного телефона
    int c, count = 0;
    int n[] = {0,0,0,0,0,0,0,0,0,0};
    while ((c = cin.get()) != EOF) {
        n[c - 48]++;
    }
    for (int i = 0; i < 10; i++) {
        if (n[i] == 0) count++;
    }
    cout << count << "\n";
    for (int i = 0; i < 10; i++) {
        if (n[i] == 0) cout << i << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

// Номер мобильного телефона

int c, count = 0;

int n[] = {0,0,0,0,0,0,0,0,0,0};

while ((c = cin.get()) != EOF) {

n[c - 48]++;

}

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

if (n[i] == 0) count++;

}

cout << count << "\n";

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

if (n[i] == 0) cout << i << " ";

}

return 0;

}

Решение

Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.

Ссылки

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

Related Images:

e-olymp 84. Transfer

26/05/2018 by Костя Григорян

Task

Vasya has one package of mobile phone operator Ratsviyk and $S_0$ tugriks on its account. (Tugrik is the currency in Vasya’s country. $0.01$ of tugrik is a cent). Also he has $n$ packages of Eciujd which is the satellite of Ratsviyk. There are $S_i$ tugriks on the account of the $i$-th package of Eciujd. There was a new tariff plan on Ratsviyk and Vasya want to go into it. For this purpose it is necessary to have at least $S$ tugriks on the account. Vasya hasn’t any money, that is why he don’t want to buy new bill replenishment, to fill up the Ratsviyk account to the necessary sum. But the escape exists.
On Ratsviyk there is such possibility as to transfer money between each others. The transfer is the sending of some money from one account to another. It is possible to send only an integer amounts of tugriks, not smaller than $5$. The cost of the transfer is $10$ cents which is draw from the account from which money was sended. Transfer can be made only if after it on the account remains at least $5$ tugriks. Since Eciujd is the satellite of Ratsviyk, then subscribers of Eciujd also can participate in this transfers.
Giving $S_0, S, n, S_i (1 \leq i \leq n)$ find whether it is possible to go into new tariff plan without buying new bill replenishment and if so find the minimum number of transfers needed for this.

Input

In the first line of input there is an integer $n (0 \leq n \leq 1000), S_0$ and $S$. In the second line are written down through a blank numbers $S_1, S_2,$…$,S_n$. All numbers $S, S_i (0 \leq i \leq n)$ — real numbers from the interval $[0.01, 10000.00]$ with exactly with two digits after a decimal point.

Output

Output the minimum number of transfers needed to go into new tariff plan or $-1$ if it is impossible without buying a new bill replenishment.

Tests

Input	Output
[latex]2\, 10.00\, 16.00[/latex]	[latex]2[/latex]
[latex]10.10\, 6.10[/latex]
[latex]3\, 100.00\, 50.00[/latex]	[latex]0[/latex]
[latex]2.00\, 19.05\ 30.20[/latex]
[latex]3\ 10.00\ 14.00[/latex]	[latex]-1[/latex]
[latex]2.00\ 10.05\ 10.00[/latex]
[latex]2\ 142.10\ 143.00[/latex]	[latex]2[/latex]
[latex]6.05\ 7.00[/latex]

Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    double s0, s;
    double A[n], B[n];
    cin >> s0 >> s;
    if(s0>=s)
        cout << 0;
    else
    {
        for(int i=0; i<n; i++)
        {
            cin  >> A[i];
            B[i]=A[i];
        }
        sort(B, B+n);
        int ans=0;
        for(int i=n-1; i>=1; i--)
        {
            if(B[i]>=10.1)
            {
                if((int)(B[i]-5.1)+s0>=s){
                    ans++;
                    cout << ans;
                    return 0;
                }
                else
                {
                    ans++;
                    B[i-1]+=(int)(B[i]-5.1);
                }
            }
            else
            {
                break;
            }
        }
        if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))
            cout << ans+1;
        else
        {
            sort(A, A+n);
            if(s0>=10.1)
            {
                A[n-1]+=(int)(s0-5.1);
                s0-=(int)(s0-5.1);
                                s0-=0.1;
                ans=1;
                for(int i=n-1; i>=1; i--)
                {
                    if(A[i]>=10.1)
                    {
                        if((int)(A[i]-5.1)+s0>=s){
                            ans++;
                            cout << ans;
                            return 0;
                        }
                        else
                        {   
                            ans++;
                            A[i-1]+=(int)(A[i]-5.1);
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))
                    cout << ans+1;
                else
                    cout << -1;
            }
            else
                cout << -1;
        }   
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int n;

cin >> n;

double s0, s;

double A[n], B[n];

cin >> s0 >> s;

if(s0>=s)

cout << 0;

else

{

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

{

cin >> A[i];

B[i]=A[i];

}

sort(B, B+n);

int ans=0;

for(int i=n-1; i>=1; i--)

{

if(B[i]>=10.1)

{

if((int)(B[i]-5.1)+s0>=s){

ans++;

cout << ans;

return 0;

}

else

{

ans++;

B[i-1]+=(int)(B[i]-5.1);

}

else

{

break;

}

if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))

cout << ans+1;

else

{

sort(A, A+n);

if(s0>=10.1)

{

A[n-1]+=(int)(s0-5.1);

s0-=(int)(s0-5.1);

s0-=0.1;

ans=1;

for(int i=n-1; i>=1; i--)

{

if(A[i]>=10.1)

{

if((int)(A[i]-5.1)+s0>=s){

ans++;

cout << ans;

return 0;

}

else

{

ans++;

A[i-1]+=(int)(A[i]-5.1);

}

else

{

break;

}

if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))

cout << ans+1;

else

cout << -1;

}

else

cout << -1;

}

return 0;

}

Solution

To begin with, if we have enough money in our account, then we do not need to do anything. Otherwise, we have three options: when we can collect the required amount without manipulating the main account, when we can collect the necessary amount by manipulating the main account and when we can not collect the required amount at all.
For the first option, we will transfer the largest possible amount to smaller ones from large side accounts and check whether we can switch to a new tariff by transferring the current account amount to the main account. In cases of a positive answer, the problem is solved.
If in the end you did not manage to get the right amount, go to the second option. We simply transfer the maximum possible amount from the main account to the largest collateral account. Then we do everything the same as in the first version. In cases of a positive answer, the problem is solved.
Otherwise, you can not get the right amount.

References

The task at E-Olymp
My solution at ideone

Related Images:

e-olymp 2261. Защита королевства

20/05/2018 by Иван Мясоедов

Защита королевства

Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	10 10 3 1 1 2 2 3 3	49
2	15 15 4 4 4 5 5 7 8 13 15	30
3	30 30 5 13 14 16 27 29 30 5 5 10 15	132
4	100 100 2 1 1 100 100	9604
5	3 3 3 1 1 2 2 3 3	0

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

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

int main() {
    int x_max, y_max, n, a=0, b=0;
    cin>>x_max>>y_max>>n;
    int *x=new int[n+2];
    int *y=new int[n+2];
    for(int i=1;i<n+1;i++) 
       cin>>x[i]>>y[i];
    x[0] = y[0] = 0;
    x[n+1] = x_max + 1; 
    y[n+1] = y_max + 1;
    sort(x, x + n+1);
    sort(y, y + n+1);
    for(int i=0; i<n+1; i++){ 
       if(x[i+1]-x[i]>a) a=x[i+1]-x[i];
       if(y[i+1]-y[i]>b) b=y[i+1]-y[i];
    }
    cout<<(a-1)*(b-1);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int x_max, y_max, n, a=0, b=0;

cin>>x_max>>y_max>>n;

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

int *y=new int[n+2];

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

cin>>x[i]>>y[i];

x[0] = y[0] = 0;

x[n+1] = x_max + 1;

y[n+1] = y_max + 1;

sort(x, x + n+1);

sort(y, y + n+1);

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

if(x[i+1]-x[i]>a) a=x[i+1]-x[i];

if(y[i+1]-y[i]>b) b=y[i+1]-y[i];

}

cout<<(a-1)*(b-1);

return 0;

}

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

Алгоритм решения задачи состоит в том, чтобы найти максимальное количество незащищенных клеток между соседними башнями по координатам абсцисс и ординат (которые будет на [latex]1[/latex] меньше чем сама разность координат) и перемножить полученные числа тем самым найдя площадь образованного ими прямоугольника.

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex] Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 239. Треугольники

19/05/2018 by Андрей Святозар Чернецкий

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

#include <iostream>
using namespace std;
 
int main() {
    unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};
    unsigned long long c = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> x1 >> y1;
        if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;
        else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;
        else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;
        else A [3] ++;
    }
    for(int i = 0; i < 4; i ++){
        for(int  j= 0; j < 4; j ++){
            if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;
            else c += A[i] * (A[i] - 1) * A[j] / 2;
        }       
    }
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

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

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

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

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

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

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

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

Related Images:

e-olymp 922. Сдвинь элементы

15/05/2018 by Иван Василевский

Условие задачи
Задан массив целых чисел длины [latex]n[/latex]. Сдвинуть элементы массива вправо циклически на [latex]1[/latex] шаг.

Входные данные
В первой строке задано количество элементов массива [latex]n[/latex] [latex](n ≤ 100)[/latex]. Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает [latex]100[/latex].

Выходные данные
В одной строке вывести [latex]n[/latex] чисел — новые значения элементов массива.

Continue reading →

Related Images:

e-olymp 921. Отрицательные элементы

13/05/2018 by Иван Мясоедов

Отрицательные элементы

Задан одномерный массив вещественных чисел длины [latex]n[/latex]. Определить сумму и количество отрицательных элементов в массиве.

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

В первой строке задано количество элементов массива [latex]n[/latex] ([latex]n[/latex] ≤ [latex]100[/latex]). В следующей строке через пробел задано [latex]n[/latex] вещественных чисел — элементы массива, значения которых не превышают по модулю [latex]100[/latex].

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

В одной строке вывести количество отрицательных чисел и через пробел их сумму с точностью до [latex]2[/latex]-х знаков после десятичной точки.

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	5 6 -7.5 2.1 -2.0 0	2 -9.50
2	2 -1 -2	2 -3.00
3	6 1 1 1 1 1 1	0 0.00
4	7 -1.99 -5.34 9 6.43 -6.32 0 -7.43	4 -21.08
5	3 -1.992345 -5.334224 9	2 -7.33

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

#include <iostream>
using namespace std;

int main() {
    int n, m = 0;
    double k = 0;
    cin >> n;
    double *x = new double[n];
    for (int i=0; i<n; i++) 
        cin >> x[i];
    for (int i=0; i<n; i++) {
        if (x[i]<0){
             m++;
             k+=x[i];
         }
    }
    cout.precision(2);
    cout << m << " " << fixed << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m = 0;

double k = 0;

cin >> n;

double *x = new double[n];

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

cin >> x[i];

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

if (x[i]<0){

m++;

k+=x[i];

}

cout.precision(2);

cout << m << " " << fixed << k;

return 0;

}

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

Для решения данной задачи я описал две переменные: [latex]m[/latex] типа [latex]int[/latex] и [latex]k[/latex] типа [latex]double[/latex], которые изначально равны [latex]0[/latex]. Цикл ищет в массиве элементы которые меньше [latex]0[/latex]. C каждым найденным отрицательным элементом, [latex]m[/latex] увеличиваться на [latex]1[/latex], а к числу [latex]k[/latex] прибавляется сам элемент.

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 7492. Будильник

07/05/2018 by Георгий Мартынюк

Задача

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

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные	Выходные данные
23	00:02
28	Impossible
0	Impossible
15	01:12

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

#include <iostream> 
using namespace std;

int main() {
    int n;
 
    while (cin >> n) {
        int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
        for (int i = 0; i < 24; i++)
            for (int j = 0; j < 60; j++) {
                int a = 0;
                a = a + seg[i / 10];
                a = a + seg[i % 10];
                a = a + seg[j / 10];
                a = a + seg[j % 10];
                if (a == n) {
                    if (i < 10) cout << '0' << i;
                    else cout << i;
                    cout << ':';
                    if (j < 10) cout << '0' << j;
                    else cout << j;
                    return 0;
                }
            }
            cout << "Impossible";
    }
}

#include <iostream>

using namespace std;

int main() {

int n;

while (cin >> n) {

int seg[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

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

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

int a = 0;

a = a + seg[i / 10];

a = a + seg[i % 10];

a = a + seg[j / 10];

a = a + seg[j % 10];

if (a == n) {

if (i < 10) cout << '0' << i;

else cout << i;

cout << ':';

if (j < 10) cout << '0' << j;

else cout << j;

return 0;

}

cout << "Impossible";

}

Решение

Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 7809. Утренняя зарядка

25/04/2018 by Валерия Ларикова

Задача

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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9[/latex]. Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

В выходной файл нужно вывести единственное число — количество эстетических пар, которые можно сложить.

Тесты

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

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

#include <iostream>
using namespace std;
const int n = 10;
int x[n];
int main() {
  char c;
  int s = 0;
  while((c=cin.get())!= EOF){
    x[c-'0']++;//перевод символов в цифры
  }
  for(int i = 0; i < n; i++)
    s+=x[i]/2;
  cout << s << endl;
 
  return 0;
}

#include <iostream>

using namespace std;

const int n = 10;

int x[n];

int main() {

char c;

int s = 0;

while((c=cin.get())!= EOF){

x[c-'0']++;//перевод символов в цифры

}

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

s+=x[i]/2;

cout << s << endl;

return 0;

}

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

Для того, чтобы решить задачу нужно найти количество пар, которые можно составить с заданной последовательности чисел. Для этого создаем массив, состоящий из [latex]10[/latex] элементов, где будем хранить числа, которые означают цвет футболки. Далее будем считывать символы и переводить их в цифры. После прочтения входного потока, найдем числа, из которых можно составить пару,и выведем их количество на экран.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

e-olymp 907. Первый не больший чем 2.5

22/04/2018 by Карина Миловская

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива [latex]n (0 < n ≤ 100)[/latex]. В следующей строке задано [latex]n[/latex] вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные	Выходные данные
[latex]5 \\ 6 \; 7.5 \; 2.1 \; 2.0 \; 0[/latex]	[latex]3 \; 2.10[/latex]
[latex]5 \\ 6 \; 7.5 \; 5.1 \; 7.0 \; 80[/latex]	[latex]Not \; Found[/latex]
[latex]7 \\ 5 \; 4.7 \; 50 \; 8.9 \; 2.7 \; 3 \; 1.5[/latex]	[latex]7 \; 1.5[/latex]

Решение задачи с помощью массивов

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

#include <iostream>
#include <iomanip>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    double *x = new double[n];
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    bool checker = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] <= 2.5 && checker == false) {
            cout << i + 1 << ' ' << fixed << setprecision(2) << x[i];
            checker = true;
        }
    }
    if (checker == false)
        cout << "Not Found";
    delete []x;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

int n;

cin >> n;

double *x = new double[n];

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

cin >> x[i];

}

bool checker = 0;

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

if (x[i] <= 2.5 && checker == false) {

cout << i + 1 << ' ' << fixed << setprecision(2) << x[i];

checker = true;

}

if (checker == false)

cout << "Not Found";

delete []x;

return 0;

}

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

Введем обозначения: [latex]x[/latex] – имя массива, [latex]n[/latex] – количество элементов в массиве, [latex]i[/latex] – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести Not Found.

Решение задачи с помощью потоковой обработки

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

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

int main()
{
    double n;
    int size;
    cin >> size;
    for (int i = 0; i < size; i++) {
        cin >> n;
        if (n <= 2.5) {
            cout << i + 1 << ' ' << fixed << setprecision(2) << n;
            return 0;
        }
    }
    cout << "Not Found";
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

double n;

int size;

cin >> size;

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

cin >> n;

if (n <= 2.5) {

cout << i + 1 << ' ' << fixed << setprecision(2) << n;

return 0;

}

cout << "Not Found";

return 0;

}

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найдененого первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, выводим на экран Not Found.

Ссылки

Условие задачи на e-olymp
Код решения с помощью массивов на ideone
Код решения с помощью потоковой обработки на ideone

Related Images:

e-olymp 88. Месть Ли Чака

04/02/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

#include <iostream>
#include <vector>

using  namespace std;

const int INF = 10000000;
const string GAYBRASH = "GAYBRASH";
const string LICHACK = "LICHACK";

struct node{
    int x;
    int y;
};

vector<node> getChildrenBFS(char ** map, node parent, string hero){
    string bannedChars = "R";
    if(hero == LICHACK) bannedChars.push_back('e');
    vector<node> children;
    node leftChild = {parent.x - 1, parent.y};
    node rightChild = {parent.x + 1, parent.y};
    node downChild = {parent.x, parent.y + 1};
    node upChild = {parent.x, parent.y - 1};
    if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
        children.push_back(leftChild);
    }
    if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
        children.push_back(rightChild);
    }
    if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
        children.push_back(downChild);
    }
    if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
        children.push_back(upChild);
    }
    return children;
}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children) {
        if (move < moves[e.y][e.x]) {
            dfsSecondPlayer(map, moves, hero, e, move);
        }
    }
}
void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children){
        if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
            dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
        }
    }
}
int main() {
    int tests;
    cin >> tests;
    for(; tests > 0; tests--){
        int m;
        int n;
        cin >> m >> n;
        cin.ignore();
        node g;
        node l;
        node e;
        char **map = new char*[m];
        for(int i = 0; i < m; i++){
            map[i] = new char[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.get();
                switch(map[i][j]){
                    case 'g':
                        g.x = j;
                        g.y = i;
                        break;
                    case 'l':
                        l.x = j;
                        l.y = i;
                        break;
                    case 'e':
                        e.x = j;
                        e.y = i;
                        break;
                }
            }
            cin.ignore();
        }
        int **liChack = new int*[m];
        for(int i = 0; i < m; i++){
            liChack[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                liChack[i][j] = INF;
            }
        }
        dfsSecondPlayer(map, liChack, LICHACK, l, 0);
        int **gaybrash = new int*[m];
        for(int i = 0; i < m; i++){
            gaybrash[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                gaybrash[i][j] = INF;
            }
        }
        dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
        bool OK = gaybrash[e.y][e.x] != INF;
        cout << (OK ? "YES" : "NO") << endl;
        for(int i = 0; i < m; i++){
            delete[] map[i];
        }
        delete[] map;
        for(int i = 0; i < m; i++){
            delete[] gaybrash[i];
        }
        delete[] gaybrash;
        for(int i = 0; i < m; i++){
            delete[] liChack[i];
        }
        delete[] liChack;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <iostream>

#include <vector>

using namespace std;

const int INF = 10000000;

const string GAYBRASH = "GAYBRASH";

const string LICHACK = "LICHACK";

struct node{

int x;

int y;

};

vector<node> getChildrenBFS(char ** map, node parent, string hero){

string bannedChars = "R";

if(hero == LICHACK) bannedChars.push_back('e');

vector<node> children;

node leftChild = {parent.x - 1, parent.y};

node rightChild = {parent.x + 1, parent.y};

node downChild = {parent.x, parent.y + 1};

node upChild = {parent.x, parent.y - 1};

if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){

children.push_back(leftChild);

}

if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){

children.push_back(rightChild);

}

if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){

children.push_back(downChild);

}

if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){

children.push_back(upChild);

}

return children;

}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children) {

if (move < moves[e.y][e.x]) {

dfsSecondPlayer(map, moves, hero, e, move);

}

void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children){

if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){

dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);

}

int main() {

int tests;

cin >> tests;

for(; tests > 0; tests--){

int m;

int n;

cin >> m >> n;

cin.ignore();

node g;

node l;

node e;

char **map = new char*[m];

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

map[i] = new char[n];

}

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

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

map[i][j] = cin.get();

switch(map[i][j]){

case 'g':

g.x = j;

g.y = i;

break;

case 'l':

l.x = j;

l.y = i;

break;

case 'e':

e.x = j;

e.y = i;

break;

}

cin.ignore();

}

int **liChack = new int*[m];

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

liChack[i] = new int[n];

}

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

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

liChack[i][j] = INF;

}

dfsSecondPlayer(map, liChack, LICHACK, l, 0);

int **gaybrash = new int*[m];

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

gaybrash[i] = new int[n];

}

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

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

gaybrash[i][j] = INF;

}

dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);

bool OK = gaybrash[e.y][e.x] != INF;

cout << (OK ? "YES" : "NO") << endl;

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

delete[] map[i];

}

delete[] map;

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

delete[] gaybrash[i];

}

delete[] gaybrash;

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

delete[] liChack[i];

}

delete[] liChack;

}

return 0;

}

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

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

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

Related Images:

e-olymp 1503. Вписанные треугольники

26/01/2018 by Мороз Дима

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

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

Тесты

Входные данные	Выходные данные
5 10 10 100 300 310 320 3 20 10 100 300 0 0	286 320
3 5 25 176 243 0 0	25
4 20 30 80 130 330 0 0	822
2 7 30 230 0 0	0

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

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;

int main(){
    double ang, s, sq, r2, res, M[500];
    int n, r, pts;
    while(cin >> n >> r, n + r != 0){
        for(int i = 0; i < n; i++){
                cin >> M[i];
                M[i] = M[i] * M_PI / 180;
        }
        sort(M, M + n);
        res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;
        r2 = r * r / 2.0;
        sq = M_PI * r * r;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                ang = M[j] - M[i];
                if(ang < M_PI){
                        s = r2 * (ang - sin(ang));
                }else{
                    ang = 2 * M_PI - ang;
                    s = sq - r2 * (ang - sin(ang));
                }
                pts = n - (j - i + 1);
                res = res - s * pts;
                pts = n - 2 - pts;
                res = res - (sq - s) * pts;
            }
        }
        printf("%.f\n", res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

int main(){

double ang, s, sq, r2, res, M[500];

int n, r, pts;

while(cin >> n >> r, n + r != 0){

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

cin >> M[i];

M[i] = M[i] * M_PI / 180;

}

sort(M, M + n);

res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;

r2 = r * r / 2.0;

sq = M_PI * r * r;

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

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

ang = M[j] - M[i];

if(ang < M_PI){

s = r2 * (ang - sin(ang));

}else{

ang = 2 * M_PI - ang;

s = sq - r2 * (ang - sin(ang));

}

pts = n - (j - i + 1);

res = res - s * pts;

pts = n - 2 - pts;

res = res - (sq - s) * pts;

}

printf("%.f\n", res);

}

return 0;

}

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции sort().

В переменную res изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2- $ pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной pts и выводим полученное значение.

Ссылки

Условие задачи на 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 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

Related Images:

e-olymp 179. Распределение

30/12/2017 by Даниил Крутоголов

Распределение

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

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

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
2 4 2 5 1	1
1 4 4	0
3 2 2 2 4 1 1	2
3 6 3 1 0 0 10	9

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

#include <iostream>
 
using namespace std;
 
int main()
{
    int size;
    cin >> size;
    long *arr1 = new long[size];
    long *arr2 = new long[size];
    for(int i = 0; i < size; i++){
        cin >> arr1[i];
    }
    for(int i = 0; i < size; i++){
        cin >> arr2[i];
    }
    long tmp = 0;
    for(int i = 0; i < size; i++){
        tmp+= abs(arr2[i] - arr1[i]);
    }
    cout << tmp / 2;
    delete []arr1;
    delete []arr2;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int size;

cin >> size;

long *arr1 = new long[size];

long *arr2 = new long[size];

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

cin >> arr1[i];

}

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

cin >> arr2[i];

}

long tmp = 0;

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

tmp+= abs(arr2[i] - arr1[i]);

}

cout << tmp / 2;

delete []arr1;

delete []arr2;

return 0;

}

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

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

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

A302. Количество различных цифр числа в его десятичной записи

09/05/2017 by Андреев Даниил

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные	Выходные данные
[latex]N[/latex]	[latex]sum[/latex]
12345678900987654321	sum:10
302	sum:3

Код программы с использованием deque

#include <iostream>
#include <deque>
using namespace std;
 
int main(){
    deque<int> folder;
    unsigned long long N;
    
    cin >> N;
    folder.push_back(N%10);
    N/=10;
    while (N!=0){
        for (int i=0; i<folder.size(); i++){
            if (folder.at(i) == N%10)
                i+=folder.size();   
            if (i == folder.size() -1)
                folder.push_back(N%10);
        }
        N/=10;
    }
    cout << "sum:" << folder.size();
 
    return 0;
}

#include <iostream>

#include <deque>

using namespace std;

int main(){

deque<int> folder;

unsigned long long N;

cin >> N;

folder.push_back(N%10);

N/=10;

while (N!=0){

for (int i=0; i<folder.size(); i++){

if (folder.at(i) == N%10)

i+=folder.size();

if (i == folder.size() -1)

folder.push_back(N%10);

}

N/=10;

}

cout << "sum:" << folder.size();

return 0;

}

Решение

Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].

Код программы с использованием массива

#include <iostream>
using namespace std;
 
int main(){
    int folder[10]={0}, sum=0;
    long long N;
 
    cin >> N;
    while (N!=0){
        folder[N%10]++;
        N/=10;
    }
    for (int j=0; j<10; j++)
        if(folder[j]!=0)    sum++;
    cout << "sum:" << sum;
 
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int folder[10]={0}, sum=0;

long long N;

cin >> N;

while (N!=0){

folder[N%10]++;

N/=10;

}

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

if(folder[j]!=0) sum++;

cout << "sum:" << sum;

return 0;

}

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).