e-olymp 555. Ближайшие точки

30/03/2019 by Кирилл Веремйов

Задача

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

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

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

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

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

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Тесты

Входные данные	Выходные данные
5 10 3 6 2 5	1 2 4
6 10 3 6 1 5 11	1 3 5
9 14545690 4343 -6 10 500 1100 -1 2 10	0 4 9
2 1 5	4 2 1
2 -1000000000 1000000000	2000000000 2 1
9 1 5 9 15 3 100 -1 4 10	1 8 5
10 0 1 5 10 20 100 120 250 -100 55	1 2 1

Решение

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

int main() {
    long long n;
    cin >> n;
    map<long long, long long> Ox;
    long long dis = 0,A = 0,B = 0;//dis- distance
    bool zero_dis = 0;
    for(long long i = 1;i <= n && !zero_dis;i++){
        long long tmp;
        cin >> tmp;
        if(Ox[tmp] != 0){
            zero_dis = true;
            A = Ox[tmp];
            B = i;
            dis = 0;
        }
        else Ox[tmp] = i;
    }
    
    if(!zero_dis){
        dis = -1;
        for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){
            long long tmp_dis = j->first - i->first;
            if(dis>tmp_dis || dis<0){
                dis = tmp_dis;
                A = j->second;
                B = i->second;
            }
        }
    }
    cout << dis << "\n" << A << " " << B;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

long long n;

cin >> n;

map<long long, long long> Ox;

long long dis = 0,A = 0,B = 0;//dis- distance

bool zero_dis = 0;

for(long long i = 1;i <= n && !zero_dis;i++){

long long tmp;

cin >> tmp;

if(Ox[tmp] != 0){

zero_dis = true;

A = Ox[tmp];

B = i;

dis = 0;

}

else Ox[tmp] = i;

}

if(!zero_dis){

dis = -1;

for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){

long long tmp_dis = j->first - i->first;

if(dis>tmp_dis || dis<0){

dis = tmp_dis;

A = j->second;

B = i->second;

}

cout << dis << "\n" << A << " " << B;

return 0;

}

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации

e-olymp

ideone

Related Images:

e-olymp 8571. Подсчитать буквы

24/02/2019 by Кирилл Веремйов

Задача

Задана строка s и буква c. Сколько раз буква встречается в строке?

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

Первая строка содержит строку s с не более чем $100$ символами. Вторая строка содержит прописную букву латинского алфавита c.

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

Выведите сколько раз буква c встречается в строке s. Одна и та же заглавная и прописная буква считаются одинаковыми. То есть «a» и «A» считаются одинаковыми буквами.

Тесты

Programming Principles 1 p	3
This is a cat sitting on a tablet	5
Some english text e	3
sSstring s	3
Another SoME eNGliSh tExT e	4
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac b	18
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac a	36
aAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAab a	70

Решение через string

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

int main() {
    string s;
    getline(cin, s);
    char c;
    cin >> c;
    int L = s.length(), k = 0;
    for(int i = 0; i < L; i++){
        if(s[i] == c || s[i] == c - 32)k++;
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

char c;

cin >> c;

int L = s.length(), k = 0;

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

if(s[i] == c || s[i] == c - 32)k++;

}

cout << k;

return 0;

}

Решение через Null-terminated String

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char s[100], c;
    cin.getline(s,100);
    cin >> c;
    int k = 0, i = 0;
    while(s[i] != '\0'){
        if(s[i] == c || s[i] == c - ('a' - 'A')) k++;
        i++;
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[100], c;

cin.getline(s,100);

cin >> c;

int k = 0, i = 0;

while(s[i] != '\0'){

if(s[i] == c || s[i] == c - ('a' - 'A')) k++;

i++;

}

cout << k;

return 0;

}

Объяснение

Сначала считывается строка, затем, интересующая буква. Потом посматриваем каждый символ строки, и если он совпадает с нужной буквой (Код символа «A» в ASCII— 65, «a»—97. Соответственно, разница между символами прописной и заглавной латинской буквы— $32$ (в ASCII буквы английского алфавита идут по порядку), и символ отличающийся на $32$ от искомого— его заглавная версия, и нужно его учитывать), увеличиваем счётчик $k$. Затем, выводим результат.

e-olymp

ideone (string)

ideone (null-terminated string)

Related Images:

e-olymp 45. Топливо

26/12/2018 by Кирилл Веремйов

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

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

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

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

Единственное число — искомое время.

Тесты

5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4	102
8 10 8 10 8 11 8 0 8 12 8 12 7 8 2 7 6 4 6 2 3 2 1 4 2 3 1 3 1 2 1 5 9 3 5 6 3 4 5 4 5 2	690
11 10 9 5 9 9 9 9 4 9 12 10 10 9 13 3 1 9 1 2 5 2 8 6 2 7 4 1 4 8 4 5 4 4 6 8 1 9 6 9 10 3 10 11 3	520
2 1 3 1 0 6 1 2 10	30
50 50 43 50 44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1 41 42 1 42 43 1 43 44 1 44 45 1 45 46 1 46 44 1 46 48 1 48 49 1 49 50 1 50 1 1	8400
3 3 1 2 3 0 1 1 3 1 2 3 2 1 2 4	6

Решение 1

#include <iostream>
#include <vector>
using namespace std;
    
int n,m,b,c;

struct boil{
    int mass=0;
    int number=0;
    vector<boil*> address;
    vector<int> distance;
};

int empty=0;
int near_tube=0;
vector<int> visit;

int Min_way(boil* A, int i, int from){
    
    if(A[i].mass>b){
        near_tube=A[i].number;
        return 0;
    }

    int min=0;
    
    bool t=0;
    for(int j=0; j< A[i].distance.size(); j++){
        bool t2=true,t1=true;
        for(int u=0; u<visit.size();u++){
            if(visit[u]==A[i].address[j]->number) t2=false;
            if(visit[u]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;
        if(A[i].address[min]->number==empty ||  A[i].address[min]->number==from)t1=false;
        
        if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){
            min=j;
            t=1;
        }
    }
    
    if(t==0){
        if(A[i].distance.size()==1){
            if(A[i].address[0]->mass>b){
                near_tube=A[i].address[0]->number;
                return A[i].distance[0];
            }
            else{
                return -1;
            }
        }
        else return -1;
    }
    else if(A[i].address[min]->mass==b){
        visit.push_back(A[i].number);
        
        bool t1=true;
        long long min2=-1;
        
        for(int k=0; k<visit.size() && t1; k++){
            if(visit[k]==A[i].address[min]->number)t1=false;
        }
        if(A[i].address[min]->number==from)t1=false;
        
        if(t1)  min2=Min_way(A,A[i].address[min]->number,A[i].number);
        if(min2>=0)min2+=A[i].distance[min];
            
        int n1=near_tube;
        
        for(int j=0; j<A[i].distance.size(); j++){
            if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){
                visit.push_back(A[i].number);
                long long a=0;
                bool t3=true;
                for(int k=0; k<visit.size() && t3; k++){
                    if(visit[k]==A[i].address[j]->number)t3=false;
                }
                
                if(A[i].address[j]->number==A[empty].number)t3=false;
                
                
                if(t1 && t3){
                    a=Min_way(A,A[i].address[j]->number,A[i].number);
                }
                else return-1;
                if(a>=0)a+=(A[i].distance[j]);
                
                if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){
                    min2=a;
                    n1=near_tube;
                }
                visit.clear();
            }
        }
        near_tube=n1;
        return min2;
    }
    else if(A[i].address[min]->mass<b){
        return -1;
    }
    else{
        near_tube= A[i].address[min]->number;
        return A[i].distance[min];
    }
}

int main() {
    cin>>n>>m>>b>>c;
    boil A[n];
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        A[i].mass=a;
        A[i].number=i;
        if(A[empty].mass>a)empty=i;
    }
    
    int d,k,g;
    while(cin>>d>>k>>g){
            A[d-1].address.push_back(&A[k-1]);
            A[k-1].address.push_back(&A[d-1]);
            A[k-1].distance.push_back(g);
            A[d-1].distance.push_back(g);
    }

    unsigned long long s=0;
    while(A[empty].mass<b){      
        unsigned long long a=Min_way(A,A[empty].number, A[empty].number);
        if(A[near_tube].mass-b+A[empty].mass<b){
            A[empty].mass+=A[near_tube].mass-b;
            s+=a*(A[near_tube].mass-b);
            A[near_tube].mass=b;
        }
        else{
            int tmp=b-A[empty].mass;
            A[near_tube].mass-=tmp;
            A[empty].mass=b;
            s+=a*tmp;
        }
    }
    
    cout<<s*c;
    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

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include <iostream>

#include <vector>

using namespace std;

int n,m,b,c;

struct boil{

int mass=0;

int number=0;

vector<boil*> address;

vector<int> distance;

};

int empty=0;

int near_tube=0;

vector<int> visit;

int Min_way(boil* A, int i, int from){

if(A[i].mass>b){

near_tube=A[i].number;

return 0;

}

int min=0;

bool t=0;

for(int j=0; j< A[i].distance.size(); j++){

bool t2=true,t1=true;

for(int u=0; u<visit.size();u++){

if(visit[u]==A[i].address[j]->number) t2=false;

if(visit[u]==A[i].address[min]->number)t1=false;

}

if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;

if(A[i].address[min]->number==empty || A[i].address[min]->number==from)t1=false;

if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){

min=j;

t=1;

}

if(t==0){

if(A[i].distance.size()==1){

if(A[i].address[0]->mass>b){

near_tube=A[i].address[0]->number;

return A[i].distance[0];

}

else{

return -1;

}

else return -1;

}

else if(A[i].address[min]->mass==b){

visit.push_back(A[i].number);

bool t1=true;

long long min2=-1;

for(int k=0; k<visit.size() && t1; k++){

if(visit[k]==A[i].address[min]->number)t1=false;

}

if(A[i].address[min]->number==from)t1=false;

if(t1) min2=Min_way(A,A[i].address[min]->number,A[i].number);

if(min2>=0)min2+=A[i].distance[min];

int n1=near_tube;

for(int j=0; j<A[i].distance.size(); j++){

if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){

visit.push_back(A[i].number);

long long a=0;

bool t3=true;

for(int k=0; k<visit.size() && t3; k++){

if(visit[k]==A[i].address[j]->number)t3=false;

}

if(A[i].address[j]->number==A[empty].number)t3=false;

if(t1 && t3){

a=Min_way(A,A[i].address[j]->number,A[i].number);

}

else return-1;

if(a>=0)a+=(A[i].distance[j]);

if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){

min2=a;

n1=near_tube;

}

visit.clear();

}

near_tube=n1;

return min2;

}

else if(A[i].address[min]->mass<b){

return -1;

}

else{

near_tube= A[i].address[min]->number;

return A[i].distance[min];

}

int main() {

cin>>n>>m>>b>>c;

boil A[n];

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

int a;

cin>>a;

A[i].mass=a;

A[i].number=i;

if(A[empty].mass>a)empty=i;

}

int d,k,g;

while(cin>>d>>k>>g){

A[d-1].address.push_back(&A[k-1]);

A[k-1].address.push_back(&A[d-1]);

A[k-1].distance.push_back(g);

A[d-1].distance.push_back(g);

}

unsigned long long s=0;

while(A[empty].mass<b){

unsigned long long a=Min_way(A,A[empty].number, A[empty].number);

if(A[near_tube].mass-b+A[empty].mass<b){

A[empty].mass+=A[near_tube].mass-b;

s+=a*(A[near_tube].mass-b);

A[near_tube].mass=b;

}

else{

int tmp=b-A[empty].mass;

A[near_tube].mass-=tmp;

A[empty].mass=b;

s+=a*tmp;

}

cout<<s*c;

return 0;

}

Решение 2

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

struct boil{
    int mass = 0;
    int len = 0;
    char n/*new*/='y';//yes
    char visit = 'n';//no
    vector <int> link;
    vector <int> dis;
};

int main() {
    int N,M,B,C;
    cin >> N >> M >> B >> C;
    boil A[N];
    int need;
    for(int i = 0; i < N ; i++){
        cin >> A[i].mass;
        if(A[i].mass < B)need = i;
    }
    int a, b, s;
    while(cin >> a >> b >> s){
        a--;
        b--;
        A[a].link.push_back(b);
        A[a].dis.push_back(s);
        A[b].link.push_back(a);
        A[b].dis.push_back(s);
    }
    queue <int> A_tmp;
    A_tmp.push(need);
    A[need].n = 'n';
    int ans = 0;
    while(!(A_tmp.empty())){
        int u = A_tmp.front();
        A_tmp.pop();
        A[u].visit = 'y';//yes
            for(int i = 0;i < A[u].link.size(); i++){ 
                if(A[A[u].link[i]].visit == 'n')
                        A_tmp.push(A[u].link[i]);
                if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){
                    A[A[u].link[i]].len = A[u].len + A[u].dis[i];
                    A[A[u].link[i]].n = 'n';
            }
        }
    }
    while(A[need].mass < B){
        int m = 0;
        for(int i = 0; i < N; i++){
            if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)
                m = i;
        }
        if(A[need].mass + (A[m].mass - B) <= B){
            ans += A[m].len * (A[m].mass - B);
            A[need].mass += A[m].mass - B;
            A[m].mass = B;
        }
        else{
            ans += A[m].len * (B - A[need].mass);
            int b = B - A[need].mass;
            A[need].mass = B;
            A[m].mass -= B - A[need].mass;
        }
    }
    cout << ans * C;
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct boil{

int mass = 0;

int len = 0;

char n/*new*/='y';//yes

char visit = 'n';//no

vector <int> link;

vector <int> dis;

};

int main() {

int N,M,B,C;

cin >> N >> M >> B >> C;

boil A[N];

int need;

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

cin >> A[i].mass;

if(A[i].mass < B)need = i;

}

int a, b, s;

while(cin >> a >> b >> s){

a--;

b--;

A[a].link.push_back(b);

A[a].dis.push_back(s);

A[b].link.push_back(a);

A[b].dis.push_back(s);

}

queue <int> A_tmp;

A_tmp.push(need);

A[need].n = 'n';

int ans = 0;

while(!(A_tmp.empty())){

int u = A_tmp.front();

A_tmp.pop();

A[u].visit = 'y';//yes

for(int i = 0;i < A[u].link.size(); i++){

if(A[A[u].link[i]].visit == 'n')

A_tmp.push(A[u].link[i]);

if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){

A[A[u].link[i]].len = A[u].len + A[u].dis[i];

A[A[u].link[i]].n = 'n';

}

while(A[need].mass < B){

int m = 0;

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

if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B)

m = i;

}

if(A[need].mass + (A[m].mass - B) <= B){

ans += A[m].len * (A[m].mass - B);

A[need].mass += A[m].mass - B;

A[m].mass = B;

}

else{

ans += A[m].len * (B - A[need].mass);

int b = B - A[need].mass;

A[need].mass = B;

A[m].mass -= B - A[need].mass;

}

cout << ans * C;

return 0;

}

Объяснение 1

Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp

ideone(1)

ideone(2)

Related Images:

e-olymp 8529. Преобразование Капрекара

29/11/2018 by Кирилл Веремйов

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

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

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

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

Выведите $K(x)$.

Тесты

Входные данные	Выходные данные
100	099
1000000000	0999999999
2414	3177
6174	6174
5	0
7272	5445
142857	750843
495	495
55	00
56	09
554	099
12345	41976

Решение

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

int main() {
	long long x, K = 0, xm = 0, xM = 0;
	//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр
	cin >> x;
	int N[11];
	int n = 0;
	
	while(x != 0){//Количество цифр в числе, запись их в массив цифр
		N[n] = abs(x % 10);
		n++;
		x /= 10;
	}
	
	bool t = true;

	sort(N , N+n);//Сортировка цифр по возрастанию

	long long ten = 1;
	
	for(int j = 0; j < n-1; j++){
		ten *= 10;
	}
	
	long long ten_copy = ten;
	
	for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число
		xm += N[i] * ten;
		ten /= 10;
	}
	
	for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число
		xM += N[i] * ten_copy;
		ten_copy /= 10;
	}
	
	K = xM - xm;
	int c = 0;
	
	long long K_tmp = K;
	//Проверка на равенство количества цифр исходного числа и числа K
	while(K_tmp != 0){
		c++;
		K_tmp /= 10;
	}
	
	//Добавление недостающих ведущих нулей
	for(int i = 0; i < n-c; i++) cout << 0;
	
	if(K!=0)//Если K==0, то нули были выведены предыдущим циклом
		cout << K;//Вывод числа K
		
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long x, K = 0, xm = 0, xM = 0;

//Вводимое число, искомое число, максимальное и минимальное из комбинации цифр

cin >> x;

int N[11];

int n = 0;

while(x != 0){//Количество цифр в числе, запись их в массив цифр

N[n] = abs(x % 10);

n++;

x /= 10;

}

bool t = true;

sort(N , N+n);//Сортировка цифр по возрастанию

long long ten = 1;

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

ten *= 10;

}

long long ten_copy = ten;

for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число

xm += N[i] * ten;

ten /= 10;

}

for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число

xM += N[i] * ten_copy;

ten_copy /= 10;

}

K = xM - xm;

int c = 0;

long long K_tmp = K;

//Проверка на равенство количества цифр исходного числа и числа K

while(K_tmp != 0){

c++;

K_tmp /= 10;

}

//Добавление недостающих ведущих нулей

for(int i = 0; i < n-c; i++) cout << 0;

if(K!=0)//Если K==0, то нули были выведены предыдущим циклом

cout << K;//Вывод числа K

return 0;

}

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

Related Images:

e-olymp 8358. Среднее значение — 1

07/11/2018 by Кирилл Веремйов

Задача

Проект «Средний вес школьника школы» решили выполнить Мамед с Самедом. Что они будут делать с этим числом, они не раскрывают. Они попросили взвеситься всех учеников школы и занесли результаты в таблицу. Помогите им подсчитать средний вес учеников. Но они просят, чтобы учеников с самым большим и с самым маленьким весом не учитывать. Единственное их упущение, они не подсчитали общее количество учеников, но это, конечно, не помешает вам подсчитать то, что они просят.

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

В нескольких строках заданы веса учеников в килограммах, разделенных пробелами (одним или несколькими) или символом конца строки. Читать веса учеников до конца ввода.

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

Средний вес учеников школы без учета учеников с самым большим и самым маленьким весом. Ответ выводить с точностью до килограмм.

Тесты

Входные данные	Выходные данные
40 23 27 59 68 23 84 27 53 46	46
5 5 5 5 5 5 5 5 5 5 6 6 5 6 5 6 6 5 6 5 6 5 5 5 5 5 5 5 5 6 6 5 6 8	6
1 3 3 4 5 4 6 10 4 58	5
1 2	0
50 51 52 53 54 55 56 57 58 59 40 34 32 90 91 92 93 94 95 96 97 98 99	70
5 5 5 5 5 5 5 5 5 5 6 6 5 6 5 6 6 5 6 5 6 5 5 5 5 5 5 5 5 6 6 5 6	0
80 99 81 98 82 97 83 96 84 95 85 95	90

Решение

#include <iostream>
using namespace std;

int main() {
    
    long long sum = 0, kM = 0, km = 0, n = 0;
    int mass = 0, M = 0, m = 0;

    while(cin >> mass){
        if(n == 0){
            M = mass;
            m = mass;
            km = 1;
            kM = 1;
        }
        else{
            if(mass > M){
                M = mass;
                kM = 1;
            }   
            else if(mass == M) kM++;
            
            if(mass < m){
                m = mass;
                km = 1;
            }
            else if(mass == m) km++;
        }
        sum += mass;
        n++;
    }
    n == kM + km? cout << 0 : cout << (2*(sum-kM*M-km*m)+n-kM-km)/(2*(n-kM-km));
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long sum = 0, kM = 0, km = 0, n = 0;

int mass = 0, M = 0, m = 0;

while(cin >> mass){

if(n == 0){

M = mass;

m = mass;

km = 1;

kM = 1;

}

else{

if(mass > M){

M = mass;

kM = 1;

}

else if(mass == M) kM++;

if(mass < m){

m = mass;

km = 1;

}

else if(mass == m) km++;

}

sum += mass;

n++;

}

n == kM + km? cout << 0 : cout << (2*(sum-kM*M-km*m)+n-kM-km)/(2*(n-kM-km));

return 0;

}

Объяснение

Для решения задачи создаём переменные, в которых будем хранить значение суммы всех ве́сов учеников, количество взвешенных, максимальное и минимальное значение из их ве́сов, и количество учеников с таковыми значениями. Далее считываем значения, сразу обрабатывая их. При получении первой переменной ($n=0$), записываем значение и как минимум, и как максимум. Потом сравниваем остальные значения с данным. Если следующие значения больше или меньше, перезаписываем значение соответствующей переменной, также сбрасываем счётчик, который считает, сколько учеников с такой массой. Для каждого случая прописано отдельное условие, поскольку минимум может быть одновременно и максимумом.

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

ideone

e-olymp

Related Images:

e-olymp 2061. Юные программисты

19/10/2018 by Кирилл Веремйов

Задача

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

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

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

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

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

Тесты

Входные данные	Выходные данные
20 30 4 5	27 15 12
5 10000 54 44	98 44 54
1 10000 100 100	200 100 100
1 2 1 1	2 1 1
100 120 2 3	100 60 40
50 50 25 25	50 25 25
9900 10000 99 56	9920 3584 6336
9999 10000 9998 2	10000 2 9998
101 110 2 3	105 63 42

Решение

#include <iostream>
using namespace std;
 
int main() {
    int k1, k2, m, n; 
    int x = 0, y = 0, M = 10001; 
//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла) 
    cin >> k1 >> k2 >> n >> m; 
 
    for(int i = 0; i <= k2; i++){
        for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет
/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.
 k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно
 быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/
            if(M > i + j && i * n == j * m  && k1 <= i + j && i + j <= k2 && i>=m && j>=n){ 
                x = i; 
                y = j;
                M = i+j;
            }
        }
    }   
    cout<< x + y << " " << x << " " << y << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, m, n;

int x = 0, y = 0, M = 10001;

//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла)

cin >> k1 >> k2 >> n >> m;

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

for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет

/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.

k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно

быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/

if(M > i + j && i * n == j * m && k1 <= i + j && i + j <= k2 && i>=m && j>=n){

x = i;

y = j;

M = i+j;

}

cout<< x + y << " " << x << " " << y << endl;

return 0;

}

Объяснение

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

e-olymp

ideone

Related Images:

e-olymp 4716. Делёж яблок — 1

14/09/2018 by Кирилл Веремйов

Задача:
[latex]n[/latex] школьников делят [latex]k[/latex] яблок поровну, неделящийся остаток остаётся в корзинке. Сколько яблок достанется каждому школьнику?

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

Два положительных целых числа [latex]n[/latex] и [latex]k[/latex], не превышающие [latex]1500[/latex] — редко в школе бывает больше учеников, да и много яблок тоже кушать вредно…

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

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

Тесты:

Входные данные	Выходные данные
3;14	4
10;100	10
20;20	1
1500;1500	1
120;1500	12

Решение:

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k; //n-количество школьников, k-количество яблок
    cout << k / n;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k; //n-количество школьников, k-количество яблок

cout << k / n;

return 0;

}

Объяснение:

Поскольку все числа, используемые в задаче,— целые, и каждое из них меньше [latex]1500 [/latex] то переменные создаём типа «int». Далее разделив число яблок ([latex]k [/latex]) на количество школьников ([latex]n [/latex]), получаем количество яблок, которое получит каждый школьник. Формула, соответственно, [latex]\frac{k}{n} [/latex]. Остаток от деления в решении не учитывается, что соответствует условию, ведь он остаётся в корзине.

e-olymp

ideone