e-olymp 7824. Без повторений

22/12/2020 by Максим Алексеев

Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

Тесты

№	Входные данные	Выходные данные
1	575747	754
2	123231	321
3	314159265359	4192653
4	1092010	9210
5	112221332	213

Код

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    string current_number;
    string ansver = "";
    cin >> current_number;
    set<char> digits_set;    // Инициализируем и заполняем множество со всеми цифрами начального числа
    for (int i = 0; i < current_number.size(); i++){
        char element = current_number[i];
        digits_set.insert(element);
    }
    std::vector<char> digits;
    for (char i : digits_set){
        digits.push_back(i);
    }
    std::reverse(digits.begin(), digits.end());    // Располагаем цифры в порядке убывания
    while (digits.size() != 1){    // Повторяем, пока не нашли все цифры кроме последней
        for (int i=0; i < digits.size(); i++){    // Перебираем цифры в порядке убывания
            char local_max = digits[i];
            int position = current_number.find(local_max);
            string new_number;
            for (int j = position; j < current_number.size(); j++){    // Делаем срез по элементу
                new_number += current_number[j];
            }
            set<char> digits_on_the_right;
            for (int j = 0; j < new_number.size(); j++){    // Находим цифры нового числа
                digits_on_the_right.insert(new_number[j]);
            }
            if (digits.size() == digits_on_the_right.size()){    // Проверяем, сохранится ли ранг ответа
                ansver += local_max;
                digits.erase(digits.begin() + i);
                string number_without_digit = "";
                for (int t = 0; t < new_number.size(); t++){    // Удаляем добавленную в ответ цифру из числа
                    if (new_number[t] != local_max){
                        number_without_digit += new_number[t];
                    }
                }
                current_number = number_without_digit;
                break;    // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена
            }
        }
    }
    cout << ansver + digits[0];    // Добавляем к ответу последнюю оставшуюся цифру
    return 0;
}

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string current_number;

string ansver = "";

cin >> current_number;

set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа

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

char element = current_number[i];

digits_set.insert(element);

}

std::vector<char> digits;

for (char i : digits_set){

digits.push_back(i);

}

std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания

while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней

for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания

char local_max = digits[i];

int position = current_number.find(local_max);

string new_number;

for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу

new_number += current_number[j];

}

set<char> digits_on_the_right;

for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа

digits_on_the_right.insert(new_number[j]);

}

if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа

ansver += local_max;

digits.erase(digits.begin() + i);

string number_without_digit = "";

for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа

if (new_number[t] != local_max){

number_without_digit += new_number[t];

}

current_number = number_without_digit;

break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена

}

cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

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

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 5057. Спиралька

24/12/2018 by Николь Метри

Задача

Выведите двумерный массив, размерами [latex]n \times n[/latex], заполненный числами от [latex]1[/latex] до [latex]n^2[/latex] по спирали. Числовая спираль начинается в левом верхнем углу и закручивается по часовой стрелке.

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

Одно число [latex]n (1 \leqslant n \leqslant 10)[/latex].

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

Выведите [latex]n^2[/latex] чисел – заполненный по спирали массив.

Тесты

№	Ввод	Вывод
1	1	1
2	2	1 2 4 3
3	3	1 2 3 8 9 4 7 6 5
4	5	1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
5	9	1 2 3 4 5 6 7 8 9 32 33 34 35 36 37 38 39 10 31 56 57 58 59 60 61 40 11 30 55 72 73 74 75 62 41 12 29 54 71 80 81 76 63 42 13 28 53 70 79 78 77 64 43 14 27 52 69 68 67 66 65 44 15 26 51 50 49 48 47 46 45 16 25 24 23 22 21 20 19 18 17

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

#include <iostream>

using namespace std;

int main() {
    int **x, n;
    cin >> n;
    x = new int *[n];
    for (int i = 0; i < n; i++) x[i] = new int[n];
    int nc = n, num = 1;
    for (int z = 0; z < nc; z++) {
        for (int i = z; i < nc; i++) {
            x[z][i] = num;
            num++;
        }
        for (int i = z + 1; i < nc; i++) {
            x[i][nc - 1] = num;
            num++;
        }
        for (int i = nc - 2; i >= z; i--) {
            x[nc - 1][i] = num;
            num++;
        }
        for (int i = nc - 2; i >= z + 1; i--) {
            x[i][z] = num;
            num++;
        }
        nc--;
    }
    for (int l = 0; l < n; l++) {
        for (int k = 0; k < n; k++) {
            cout << x[l][k];
            if (k != n - 1) cout << " ";
        }
        if (l != n - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int **x, n;

cin >> n;

x = new int *[n];

for (int i = 0; i < n; i++) x[i] = new int[n];

int nc = n, num = 1;

for (int z = 0; z < nc; z++) {

for (int i = z; i < nc; i++) {

x[z][i] = num;

num++;

}

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

x[i][nc - 1] = num;

num++;

}

for (int i = nc - 2; i >= z; i--) {

x[nc - 1][i] = num;

num++;

}

for (int i = nc - 2; i >= z + 1; i--) {

x[i][z] = num;

num++;

}

nc--;

}

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

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

cout << x[l][k];

if (k != n - 1) cout << " ";

}

if (l != n - 1) cout << endl;

}

return 0;

}

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

Все решение задачи сводится к тому, чтобы постепенно заполнять крайние квадраты, «окаймляя» внутренность массива и постепенно сужая диапазон заполнения и длину стороны заполняемого квадрата. В основном цикле вложенными циклами поочередно заполняем строки и столбцы: верхнюю, крайний справа, нижнюю, крайний слева. После «сворачиваем» вправо, когда вложенные циклы заканчиваются и во внешнем(основном) счетчик увеличивается на 1. Полный цикл на n действий делать смысла не имеет в силу того, что, дойдя до половины, массив уже будет полностью заполнен в строках ниже.

Ссылки

Related Images:

e-olymp 31. Суеверный Дед Мороз

23/12/2018 by Николь Метри

Задача

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 13».

Сколько дней Дед Мороз не развозил подарки во время своего дежурства?

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

В первой строке задано количество смен $k$ дежурства Деда Мороза.

Далее в k строках указаны года $a$ и $b$ ($1920 ≤ a ≤ b ≤ 2050$ по григорианскому календарю), попадающие на очередную смену.

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

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

Тесты

№	Ввод	Вывод
1	2 1999 2000 1991 1997	13
2	3 1939 1945 1937 1938 1953 1964	37
3	3 1993 1996 2007 2017 1979 1981	32
4	4 1997 1999 1967 1972 2032 2032 1930 1933	24
5	4 1959 1960 1965 1966 1991 2011 1947 1959	63

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

#include <iostream>
#include <algorithm>

using namespace std;

int c2[12] = {16, 18, 19, 25, 1, 2, 3, 4, 7, 8, 13, 14};
int c3[4] = {21, 24, 27, 10};

int main (){
    int a, year1, year2, counter = 0;
    cin >> a;
    while (a--){
        cin >> year1 >> year2;
        for (int i = year1; i <= year2; i++){
            if (any_of(begin(c2), end(c2), [=](int n){return n == i%28;})) counter+=2;
            else if(any_of(begin(c3), end(c3), [=](int n){return n == i%28;})) counter+=3;
            else counter++;
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int c2[12] = {16, 18, 19, 25, 1, 2, 3, 4, 7, 8, 13, 14};

int c3[4] = {21, 24, 27, 10};

int main (){

int a, year1, year2, counter = 0;

cin >> a;

while (a--){

cin >> year1 >> year2;

for (int i = year1; i <= year2; i++){

if (any_of(begin(c2), end(c2), [=](int n){return n == i%28;})) counter+=2;

else if(any_of(begin(c3), end(c3), [=](int n){return n == i%28;})) counter+=3;

else counter++;

}

cout << counter;

return 0;

}

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

Сперва стоит сказать, что полный цикл чередования лет с пятницей 13 в одни и те же месяца — 28 лет. Всего в году их может быть от 1 до 3. Всего в этих 28 годах будут 4 года с тремя пятницами 13 и по 12 с одной и двумя.
Все решение задачи сводится сводится к тому, чтобы посчитать количество пятниц 13 в каждом году данного нам отрезка времени. Создадим два массива — c2 и c3 — каждый будет содержать остатки от деления лет, содержащих 2 и 3 пятницы 13 соответсвенно, на 28. Все прочие остатки от деления «достанутся» годам, в которых 1 пятница 13; отдельный массив для них, очевидно, смысла создавать нет.
Сначала, по условию, вводим число смен и после в цикле года очередной смены. Для каждого года из отдельной смены считаем количество пятниц 13 путём проверки в соответствующих массивах остатка от деления этого года на 28. Если его нет в двух массивах, то, очевидно, в этом году всего одна пятница 13 и мы прибавляем к счетчику пятниц counter 1. Если все-таки есть, то прибавляем 2 или 3 в зависимости от того, в каком массиве нашлось необходимое число. В конце выводим значение счётчика.
Отметим, что задача решается и без использования массивов, но в таком случае придётся проверить остаток от деления каждого года на 28 на равенство числам, которые в данном случае находятся в массивах.

Ссылки

код на ideone
условие задачи на e-olymp

Related Images:

e-olymp 8653. Прибавить вычесть и умножить

22/12/2018 by Николь Метри

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

add a: прибавить значение a к x;
subtract a: вычесть значение a из x;
multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

№	Ввод	Вывод
1	add 2 subtract 5 subtract 1 multiply -3	12
2	subtract 5 multiply -5 add 5	30
3	add 6 add 543 multiply 23	12627
4	multiply 45678 add 3	3
5	subtract 58 add 38 multiply -1 add 100	120

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

#include <iostream>
using namespace std;

int main() {
    int x = 0, a;
    string s;
    while (cin >> s){
        cin >> a;
        if (s == "multiply") {
            x*=a;
        }
        else if (s == "subtract") {
            x-=a;
        }
        else {
            x+=a;
        }
    }
    cout << x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x = 0, a;

string s;

while (cin >> s){

cin >> a;

if (s == "multiply") {

x*=a;

}

else if (s == "subtract") {

x-=a;

}

else {

x+=a;

}

cout << x;

return 0;

}

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

Инициализировав основную переменную x, через поток ввода считываем все действия, которые неоходимо применить по отношению к переменной. Во время этого ничего не выводим, дожидаясь, пока поток команд закончится. Заметим, что процесс ввода может длиться сколько угодно долго. В конце концов, на выходе получаем уже «преобразованный» x — результат проделанных дейсвтий.

Ссылки

Related Images:

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