e-olymp 7457. Max-Min в двійковій системі счислення

20/12/2017 by Александра Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
$2$	$1$
$15$	$0$
$86$	$105$
$1000$	$945$
$40$	$45$

Код програми

#include <iostream>
#include <iomanip>
#include <cmath>

long long max_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n0+n1-1; i>=n0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

long long min_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n1-1; i>=0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

int main() 
{
    long long n;
    cin >> n;
    long long n1=0;
    long long n0=0;
    while (n>0)
    {
        if (n%2==1) n1++;
        else n0++;
        n/=2;
    }
    
    cout << max_number (n1, n0) - min_number (n1, n0);
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

long long max_number(long long n1, long long n0)

{

long long number;

for (int i=n0+n1-1; i>=n0; i--)

{

number+=pow(2, i);

}

return(number);

}

long long min_number(long long n1, long long n0)

{

long long number;

for (int i=n1-1; i>=0; i--)

{

number+=pow(2, i);

}

return(number);

}

int main()

{

long long n;

cin >> n;

long long n1=0;

long long n0=0;

while (n>0)

{

if (n%2==1) n1++;

else n0++;

n/=2;

}

cout << max_number (n1, n0) - min_number (n1, n0);

return 0;

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp

Related Images:

e-olymp 7337. Скидки

06/11/2017 by Мороз Дима

Задача

В супермаркете электроники, если верить телерекламе, существует система скидок: из двух купленных товаров полностью оплачивается только стоимость товара, который дороже, а другой отдается бесплатно. Какой суммы достаточно, что бы оплатить покупку трёх товаров, если известна цена каждого?
Входные данные: три натуральных числа $a, b, c$ — цены трёх товаров $\left(1 ≤ a, b, c ≤ 10000 \right).$
Выходные данные: стоимость покупки.

Тесты

Входные данные	Выходные данные
213 6554 234	6767
320 3670 5555	5875
15 47 13	60
215 30 73	245
370 53 823	876

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

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(max(a, b), c) + min(min(a, b), c);
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int a, b, c;

cin >> a >> b >> c;

cout << max(max(a, b), c) + min(min(a, b), c);

return 0;

}

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

Для нахождения самого дорогого и самого дешёвого товаров мы используем встроенные функции $\min \left(\right)$ и $\max \left(\right)$. Находим минимальное число среди чисел $a$, $b$ и $c$: $\min \left(\min \left(a, b \right), c \right)$ (пример: $\min \left(\min \left(1, 2 \right), 3 \right) = 1$). Далее проводим такую же операцию с нахождением максимального числа среди $a$, $b$ и $c$: $\max \left(\max \left(a, b \right), c \right)$ (пример: $\max \left(\max \left(1, 2 \right), 3 \right) = 3$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.

Ссылки

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

Related Images:

A297

31/03/2016 by Молоканов Юрий

Условие

Даны целые числа [latex]a_1, \ldots , a_{100}[/latex]. Получить новую последовательность из 100 целых чисел, заменяя [latex]a_i[/latex] нулями, если [latex]|a_i|[/latex] не равно [latex]\text{max} (a_1, \ldots , a_{100})[/latex], и заменяя [latex]a_i[/latex] единицей в противном случае ([latex]i = 1, \ldots , 100[/latex]).

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

Тестирование

№	Входные данные	Выходные данные
1	0	1
2	1 0 -1	1 0 1
3	-1 0 -1	0 1 0
4	-1 -1 -1	0 0 0
5	4 4 4 4	1 1 1 1
6	10 5 -1 -10 -20 0 1 2 3	1 0 0 1 0 0 0 0 0

Код

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

int main() {
    vector<int> x;
    int t;
    cin >> t; // Читаем и помещаем в вектор первое число, считая его максимумом
    int max = t;
    x.push_back(t);
    while(cin >> t) { // Заполняем вектор оставшимися числами
        x.push_back(t);
        if(t > max)  // Если очередной элемент больше текущего максимума, обновляем максимум
            max = t;
    }
    for(int i = 0; i < x.size(); i++)    // Обрабатываем вектор в соответствии с условием
        x.at(i) = abs(x.at(i)) != max ? 0 : 1;
    for(int i = 0; i < x.size(); i++)    // Печатаем вектор
        cout << x.at(i) << ' ';
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector<int> x;

int t;

cin >> t; // Читаем и помещаем в вектор первое число, считая его максимумом

int max = t;

x.push_back(t);

while(cin >> t) { // Заполняем вектор оставшимися числами

x.push_back(t);

if(t > max) // Если очередной элемент больше текущего максимума, обновляем максимум

max = t;

}

for(int i = 0; i < x.size(); i++) // Обрабатываем вектор в соответствии с условием

x.at(i) = abs(x.at(i)) != max ? 0 : 1;

for(int i = 0; i < x.size(); i++) // Печатаем вектор

cout << x.at(i) << ' ';

return 0;

}

Решение

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

Так как последовательность состоит из целых чисел и ее длина неизвестна, воспользуемся классом vector типа int:

vector<int> x;

1	vector<int> x;

Затем отдельно считаем первый элемент последовательности и возьмем его в качестве максимума, после чего поместим в вектор:

int t;
cin >> t;
int max = t;
x.push_back(t);

int t;

cin >> t;

int max = t;

x.push_back(t);

Заполним вектор оставшимися числами, попутно обновляя переменную max , если встретим число, большее хранимого максимума:

while(cin >> t) {
    x.push_back(t);
    if(t > max)
        max = t;
}

while(cin >> t) {

x.push_back(t);

if(t > max)

max = t;

}

Теперь обработаем последовательность согласно условию задачи, то есть заменим каждое число либо нулем, если его абсолютное значение не равно максимуму, либо единицей в противном случае:

for(int i = 0; i < x.size(); i++)
    x.at(i) = abs(x.at(i)) != max ? 0 : 1;

1 2	for(int i = 0; i < x.size(); i++) x.at(i) = abs(x.at(i)) != max ? 0 : 1;

Наконец, выведем ответ на задачу — полученную последовательность из нулей и единиц:

for(int i = 0; i < x.size(); i++)
    cout << x.at(i) << ' ';

1 2	for(int i = 0; i < x.size(); i++) cout << x.at(i) << ' ';

Ссылки

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

Условие задачи в сборнике задач по программированию (С. А. Абрамов).

Related Images:

e-olymp 1308. Наибольшая грань подстроки

30/11/2015 by Молоканов Юрий

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex]) и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

Тестирование

№	Входные данные	Выходные данные	Комментарий
1	abaabaab	5	abaab в исходной строке
2	abaababaabaab	6	abaaba в подстроке abaababaabaab
3	aaaaaaaa	7	aaaaaaa в исходной строке
4	YM	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5	&#%*%#&	1	& в исходной строке
6	15015105	2	15 в подстроке 15015105
7	f0A+.f0A+.f0A.+.A0f	8	f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

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

int main() {
    string s;
    getline(cin, s);
    int max = 0;    // Длина наибольшей грани
    for(int i = 1; i < s.length() && s.length() - i > max; i++) { 
        int j = 0;
        /*
        Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
        i - первый символ очередного суффикса
        j - длина текущей грани и первый символ очередного префикса
        */
        while(j < s.length() - i && s.at(j) == s.at(i + j))  // Накапливаем длину, пока символы префикса и суффикса совпадают
            j++;
        if(j > max)  // Если длина текущей грани больше хранящейся, обновляем максимум
            max = j;
    }
    cout << max;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

int max = 0; // Длина наибольшей грани

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < s.length() - i && s.at(j) == s.at(i + j)) // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

if(j > max) // Если длина текущей грани больше хранящейся, обновляем максимум

max = j;

}

cout << max;

return 0;

}

Решение

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

В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:

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

for(int i = 1; i < s.length() && s.length() - i > max; i++) {   
    int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

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

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