e-olymp 610. Древняя рукопись

19/05/2018 by Мороз Дима

Задача

В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно было не менее трех. С течением времени у них появились дети и разбрелись они по миру, причем как и их родители, каждый построил свой город. Опять же с течением времени количество родственников начало стремительно возрастать и решили они между некоторыми городами построить дороги, а некоторые из них, уже до этого успели построить и объездные дороги вокруг своего города. В рукописях упоминается, что количество городов в той стране не превышало $8000$. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра $1$ указывала на наличие дороги между городами, или вокруг города, или $0$ в случае отсутствия таковой.

Изучите древние рукописи и дайте ответ на вопрос: а сколько же дорог было построено между городами?

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

В первой строке задано количество городов $n$, а в последующих $n$ строках через пробел задано по $n$ чисел, которые указывают на наличие или отсутствие соответствующей дороги.

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

Количество построенных между городами дорог.

Тесты

Входные данные	Выходные данные
5 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1	7
4 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0	3
3 1 1 0 1 0 1 0 1 0	2
3 0 1 1 1 0 1 1 1 0	3
3 1 0 0 0 1 0 0 0 1	0

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

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

int main() {
    int n, k = 0;
    cin >> n;     cin.ignore(); //считываем n и игнорируем символ перевода строки
    const int N = 2 * n + 1;
    char c[N];
    for(int i = 0; i < n; i++) {
        fgets(c, N, stdin); //считываем строку
        for(int j = 0; j < i; j++) 
            k = k + c[j << 1] - 48; //переводим символ из ascii кода в число
    }
    cout << k;

    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int n, k = 0;

cin >> n; cin.ignore(); //считываем n и игнорируем символ перевода строки

const int N = 2 * n + 1;

char c[N];

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

fgets(c, N, stdin); //считываем строку

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

k = k + c[j << 1] - 48; //переводим символ из ascii кода в число

}

cout << k;

return 0;

}

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

Задача не сложная – посчитать количество ребер в графе, заданном матрицей смежности.

Сложность задачи состоит в ограничениях по времени – не более одной секунды (ощутимо при больших значенях $n$, так как $3 ≤ n ≤ 8000$). Поэтому приходится быстро вводить данные в больших количествах. Для этого используем символьный массив и любую функцию, которая читает целую строку чисел (в моем случае – fgets()), которая читает строку, пока не встретит символ перевода строки – '\n'.

Далее по одному переводим символы в числа и суммируем их в переменной k, после чего выводим.

Ссылки

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

Related Images:

e-olymp 1226. Обмен иностранцами

13/05/2018 by Мороз Дима

Задача

Ваша неприбыльная организация координирует программу по обмену студентами. И ей нужна Ваша помощь.

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

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

Тесты

Входные данные	Выходные данные
2 2 1 2 2 1 2 31 13 13 31	YES YES
1 4 17 3 28 15 15 28 3 17	YES
1 4 17 3 28 15 15 28 3 18	NO
3 2 1 2 3 4 2 47 7 7 47 2 12 34 12 34	NO YES NO

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

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

multiset <pair <unsigned int, unsigned int>> M;
multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {
    unsigned int t, n, a, b;
    cin >> t;
    while (t != 0) {
        cin >> n;
        M.clear();
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            if ((it = M.find (make_pair(b, a))) == M.end()) {
                M.insert (make_pair(a, b));
            } else M.erase(it);
        }
        (M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;
        t--;
    }
    
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

multiset <pair <unsigned int, unsigned int>> M;

multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {

unsigned int t, n, a, b;

cin >> t;

while (t != 0) {

cin >> n;

M.clear();

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

cin >> a >> b;

if ((it = M.find (make_pair(b, a))) == M.end()) {

M.insert (make_pair(a, b));

} else M.erase(it);

}

(M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;

t--;

}

return 0;

}

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

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.

Ссылки

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

Related Images:

e-olymp 3912. Реверс удавов

20/04/2018 by Мороз Дима

Задача

На каждом удаве из стаи написано его имя. Имя удава написано маленькими латинскими буквами от головы к хвосту. Все удавы из стаи ползут друг за другом, ведь так легче ползти. Иногда вожак даёт команду «Реверс». В этом случае каждый удав стаи разворачивается, и стая начинает ползти в противоположном направлении. Название стаи можно прочитать, если читать от головы удава, ползущего первым, к хвосту последнего. При этом название может измениться после команды «Реверс». Имена же удавов не меняются.

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные	Выходные данные
3 abc def ghi	ghidefabc
3 zxcgh i db	dbizxcgh
4 mn kjl iu ghj	ghjiukjlmn
8 kdh jg lqwoc kfxvk iduhx nsh s kjwyv	kjwyvsnshiduhxkfxvklqwocjgkdh

Код программы (string)

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

int main () 
{
    int N;
    cin >> N;
    string flock[N];
    for (int i = 0; i < N; i++)
        cin >> flock[i];
    for (int i = N - 1; i >= 0; i--)
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main ()

{

int N;

cin >> N;

string flock[N];

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

cin >> flock[i];

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

cout << flock[i];

return 0;

}

Решение задачи (string)

Записываем каждого удава в одномерный массив flock типа string размера N, а затем выводим его, начиная с конца.

Код программы (c-string)

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

#define boa_name_size 11

int main() 
{
    int N;
    cin >> N;
    char **flock = new char *[N]; // Создаем массив в N строк
    for (int i = 0; i <= N; i++)
        flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов
    for (int i = 0; i <= N; i++)
        cin.getline(flock[i], boa_name_size);
    for (int i = N; i > 0; i--) 
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

#define boa_name_size 11

int main()

{

int N;

cin >> N;

char **flock = new char *[N]; // Создаем массив в N строк

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

flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов

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

cin.getline(flock[i], boa_name_size);

for (int i = N; i > 0; i--)

cout << flock[i];

return 0;

}

Решение задачи (c-string)

Записываем каждого удава в динамический массив flock типа char размера $N$ $\times$ boa_name_size, где boa_name_size – это константа, размером в $11$ символов, которую определяем с помощью директивы #define в начале программы. Не $10$, а $11$ потому что в нуль-терминированных строках (c-string) последний символ – символ конца строки '\0'.
Далее выводим наш массив с последней строки до первой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com (string)
Решение задачи на ideone.com (c-string)

Related Images:

e-olymp 396. Дождь

15/04/2018 by Мороз Дима

Задача

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

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$_$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y = 0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$_$0$ точки появления капли $(0 < X$_$0$ $< 10000)$ и количество отрезков-препятствий $N (0 ≤ N ≤ 100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$_$1$, $y$_$1$, $x$_$2$, $y$_$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$, $x$_$1$ $ < x$_$2$, $y$_$1$ $≠$ $y$_$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

#include <iostream>
using namespace std;
 
int main () 
{
    int x, n;
    cin >> x >> n;
    int N[n][4];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> N[i][j];
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            for (int q = 0; q < 4; q++)
                if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )
                    swap(N[i][q], N[j][q]);
    for (int i = 0; i < n; i++) {
        if (x >= N[i][0] && x <= N[i][2]) 
            N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];
        for (int j = 0; j < 4; j++)
            N[i][j] = 0;
    }
    cout << x;
 
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

int x, n;

cin >> x >> n;

int N[n][4];

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

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

cin >> N[i][j];

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

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

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) )

swap(N[i][q], N[j][q]);

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

if (x >= N[i][0] && x <= N[i][2])

N[i][1] < N[i][3] ? x = N[i][0] : x = N[i][2];

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

N[i][j] = 0;

}

cout << x;

return 0;

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X$ $ ∈ [x$_$1$$, x$_$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y$_$1$ и $y$_$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$_$1$ или $x$_$2$ координате нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

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

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 6350. Изированная вода

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

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N (1 ≤ N ≤ 10^6)$ — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^9$.

Выходные данные
Вывести единственное число — количество покупателей, услышавших от продавца ответ «Придёте завтра» и при этом ответили неправильно. Подсчитывать же тех, кто долго думал, не обязательно, за Вас это сделает проверяющая система вердиктом TL (Time Limited).

Тесты

Входные данные	Выходные данные
5 2 1 2 2 1 2 1 1 2 1	3
3 45 45 38 37 12 10	2
3 5 4 7 6 3 2	0
2 1280 1280 1900 1899	1
7 1 1 2 2 3 2 6 5 6 6 7 3 2 2	5

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

#include <iostream>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;
    unsigned int a, b, j = 0;
    for (n; n > 0; n--) {
        cin >> a >> b;
        if (b != a - 1) j++;
    }
    cout << j;
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n;

cin >> n;

unsigned int a, b, j = 0;

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

cin >> a >> b;

if (b != a - 1) j++;

}

cout << j;

return 0;

}

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

Используем это в цикле для проверки на правильность ответа покупателя. Если ответ неправильный, то увеличиваем переменную j, которая считает количество неправильных ответов, на один, и, после завершения цикла, выводим ее значение.

Ссылки

Код задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 27. Циклические сдвиги

30/12/2017 by Мороз Дима

Задача

Циклический сдвиг

Запишем целое десятичное число $n$ в двоичной системе счисления и образуем все левые циклические сдвиги числа $n$, у которых первая цифра числа переносится в конец.

Например, если $n = 11$, то в двоичной системе это $1011$_$2$, его циклические сдвиги: $0111$_$2$, $1110$_$2$, $1101$_$2$, $1011$_$2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110$_$2$ $=$ $14$_$10$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n \left(1 ≤ n ≤ 2 \cdot 10^9\right)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные	Выходные данные
11	14
23	30
256	256
257	384
34132	43664

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

#include <iostream>
using namespace std;

int main(){
    unsigned long in_val, tmp_val, power = 1;
    cin >> in_val;
    tmp_val = in_val;
    while(tmp_val){
        tmp_val /= 2;
        power *= 2;
    }
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if (max_val < in_val) max_val = in_val;
    }while (tmp_val != in_val );
    cout << max_val << endl;
    
    return 0;
}

#include <iostream>

using namespace std;

int main(){

unsigned long in_val, tmp_val, power = 1;

cin >> in_val;

tmp_val = in_val;

while(tmp_val){

tmp_val /= 2;

power *= 2;

}

tmp_val = in_val;

unsigned long max_val = in_val;

do{

in_val = in_val << 1;

in_val = in_val % power + (in_val >= power ? 1 : 0);

if (max_val < in_val) max_val = in_val;

}while (tmp_val != in_val );

cout << max_val << endl;

return 0;

}

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

Сначала мы находим степень двойки, большую данного числа;
Далее мы циклически сдвигаем влево данное число на один бит и из полученных чисел выбираем наибольшее.

Возможный вариант решения задачи

Возможно избавиться от первого цикла путем нахождения количества двоичных разрядов кратных степени двойки с помощью:
1. взятия логарифма числа по основанию $2$ с последующим округлением до целого;
2. возведение двойки в степень, полученную выше, и увеличенную на единицу.
То есть $2^{\lfloor \log_{2}n \rfloor + 1}$.

Тогда код будет выглядеть так:

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

int main(){
    unsigned long in_val, tmp_val;
    cin >> in_val;
    tmp_val = in_val;
    unsigned long power;
    power = pow(2, floor(log2(in_val)) + 1);
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if(max_val < in_val){
            max_val = in_val;
        }
    }while(tmp_val != in_val);
    cout << max_val << endl;

    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main(){

unsigned long in_val, tmp_val;

cin >> in_val;

tmp_val = in_val;

unsigned long power;

power = pow(2, floor(log2(in_val)) + 1);

tmp_val = in_val;

unsigned long max_val = in_val;

do{

in_val = in_val << 1;

in_val = in_val % power + (in_val >= power ? 1 : 0);

if(max_val < in_val){

max_val = in_val;

}

}while(tmp_val != in_val);

cout << max_val << endl;

return 0;

}

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com
Возможное решение задачи на ideone.com

Related Images:

e-olymp 43. Количество участников олимпиады

01/12/2017 by Мороз Дима

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$	$n$	$m$	$d$	Выходные данные
2	4	7	3	28
4	5	2	1	20
3	7	5	4	-1
6	6	6	1	-1
2	3	6	4	-1
3	2	5	8	-1

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    float k, n, m, d, s;
    cin >> k >> n >> m >> d;
    s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);
    if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){
    cout << "-1";
    }else{
        cout << s;
    }
    
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

float k, n, m, d, s;

cin >> k >> n >> m >> d;

s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);

if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){

cout << "-1";

}else{

cout << s;

}

return 0;

}

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

Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.

Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию floor() из встроенной библиотеки <cmath>.

Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

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

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$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.