e-olymp 441. Наиболее круглое число

25/02/2018 by Бондаренко Кирилл

Наиболее круглое число

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

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

В первой строке входных данных задано количество чисел [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex]. Каждая из последующих N строк содержит одно число в пределах от [latex]1[/latex] до [latex]10^{9}[/latex].

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

Вывести наиболее круглое число среди заданных [latex]N[/latex] чисел.

Тесты

Входные данные	Выходные данные
4 71200 10 200 10001	200
5 711 1 2 10001 234567	1
10 7 1 2 1 2 3 4 6 8 9	1
4 100000 200000 500000 800000	100000

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

#include <iostream>
using namespace std;

int main() {
    int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;
    cin >> e;
    while (e -- > 0) {
        cin >> n;
        if (p <= n) {
            m = n;
            k = 0;
            while ((n % 10) == 0) {
                //считает нули
                n = n / 10;
                k ++;
            }
            if (maxk < k) {
                maxn = m;
                maxk = k;
                p = 1;
                for (int i = 1; i < maxk; i ++) {
                    p *= 10;
                }
            } else if (maxk == k) {
                if(maxn > m) {
                    maxn = m;
                }
            }
        }
    }
    cout << maxn;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;

cin >> e;

while (e -- > 0) {

cin >> n;

if (p <= n) {

m = n;

k = 0;

while ((n % 10) == 0) {

//считает нули

n = n / 10;

k ++;

}

if (maxk < k) {

maxn = m;

maxk = k;

p = 1;

for (int i = 1; i < maxk; i ++) {

p *= 10;

}

} else if (maxk == k) {

if(maxn > m) {

maxn = m;

}

cout << maxn;

return 0;

}

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

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем [latex]p[/latex], где [latex]p[/latex] — наименьшее число с количеством нулей равным [latex]maxk[/latex]. [latex]maxk[/latex] — текущее наибольшее количество нулей. Для того, чтобы найти [latex]p[/latex], мы в цикле умножаем [latex]1[/latex] [latex]maxk[/latex]-раз на [latex]10[/latex]. Очевидно, что [latex]p[/latex] нужно менять только тогда, когда меняется [latex]maxk[/latex], также следует до цикла полагать [latex]p=1[/latex]. Для того чтобы [latex]p[/latex] не умножалось на [latex]10[/latex] лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим [latex]maxn[/latex] — наиболее круглое число.
Так как по условию числа не могут быть больше чем [latex]10^{9}[/latex], имеет смысл изначально поставить переменную [latex]maxn=10^{9}[/latex]. Это делается для того случая, когда во всех числах [latex]m[/latex] не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную [latex]maxn[/latex] любое другое число то [latex]maxn[/latex] может быть меньше чем [latex]m[/latex] и мы не сможем выбрать ответ так как все [latex]m[/latex] будут больше его.

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

Related Images:

e-olymp 622. Единицы

21/01/2018 by Бондаренко Кирилл

Единицы

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

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

Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].

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

Вывести количество единиц в двоичной записи числа [latex]n[/latex].

Тесты

Входные данные	Выходные данные
20	2
0	0
1	1
5	2
2000000000	13

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

#include <iostream>
using namespace std;

int main() {
    int k=0, n;
    cin >> n;
    while (n > 0){   
        k += (n % 2);
        n = n / 2;
    }
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k=0, n;

cin >> n;

while (n > 0){

k += (n % 2);

n = n / 2;

}

cout << k;

return 0;

}

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

Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.

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

Related Images:

e-olimp 1610. Зайцы в клетках

27/12/2017 by Бондаренко Кирилл

Зайцы в клетках

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

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

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

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 10^9)[/latex].

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

Входные данные	Выходные данные
3 50	17
5 5	1
1070 589	1
34 49	2

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

#include <iostream>
using namespace std;

int main() {
    int n, m;
    double k;
    cin >> n >> m;
    k = m / n;
    if (k >= 1)cout << (m + n - 1) / n;
    else cout << 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

double k;

cin >> n >> m;

k = m / n;

if (k >= 1)cout << (m + n - 1) / n;

else cout << 1;

return 0;

}

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

Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

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

Related Images:

e-olimp 57. Бабочка-санитар

05/11/2017 by Бондаренко Кирилл

Задача

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент? Continue reading →