e-olymp 8283. Музыка

14/12/2019 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

#include <iostream>  
using namespace std;

int main() {
    int quantity, instrument, counter = 1;
    cin >> quantity >> instrument;
    if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
        cout << 0;
    } else if (quantity == instrument) {
        for (int num = 1; num % quantity != 0; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    } else {
        for (int num = 1; num % quantity != instrument; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int quantity, instrument, counter = 1;

cin >> quantity >> instrument;

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

cout << 0;

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

}

return 0;

}

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 8654. Целочисленное умножение

22/12/2018 by Николай Козиний

Задача взята с сайта e-olymp

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 3 2	0
2	11 3 2	1
3	123456789 987654321 17	0
4	5000400000023 23000400400500 100000000070707	68238553233174
5	10000018585 10000000000005 101020304050607080	85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) & \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$ операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

include <iostream>
unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){
    if(y == 1)return x % z;
    else if(y == 0)return 0;
    else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;
    else return mult((x + x)%z,(y / 2) % z,z);
 
}
int main() {
    unsigned long long a,b,c;
    std::cin >> a >> b >> c;
    std::cout << mult(a,b,c);
}

include <iostream>

unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){

if(y == 1)return x % z;

else if(y == 0)return 0;

else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;

else return mult((x + x)%z,(y / 2) % z,z);

}

int main() {

unsigned long long a,b,c;

std::cin >> a >> b >> c;

std::cout << mult(a,b,c);

}

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

Related Images:

e-olymp 2817. Двоичные числа

28/06/2018 by Павел Жуков

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

читает натуральное число $n$,
вычисляет позиции $1$ в двоичном представлении $n$,
выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

Входные данные	Выходные данные
$3$ $17$ $7$ $5$	$0$ $4$ $0$ $1$ $2$ $0$ $2$
$4$ $1945$ $1337$ $1000000$ $999999$	$0$ $3$ $4$ $7$ $8$ $9$ $10$ $0$ $3$ $4$ $5$ $8$ $10$ $6$ $9$ $14$ $16$ $17$ $18$ $19$ $0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$	$0$ $1$ $0$ $1$ $2$ $0$ $2$ $1$ $2$ $0$ $1$ $2$ $3$ $0$ $3$

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

#include <iostream>
using namespace std;

int main() {
    int d;
    cin >> d;
    for (int j = 0; j < d; ++j){ 
        int n; 
        bool w = false;
        cin >> n;
        for (int i = 0; n>0; ++i){
            if (n % 2 == 1){
                if(w) cout << " ";
                w = true;
                cout << i;
                        }
            n /= 2;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int d;

cin >> d;

for (int j = 0; j < d; ++j){

int n;

bool w = false;

cin >> n;

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

if (n % 2 == 1){

if(w) cout << " ";

w = true;

cout << i;

}

n /= 2;

}

cout << endl;

}

return 0;

}

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

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

Related Images:

e-olymp 949. Двузначное из четырёхзначного

21/12/2017 by Мырза Дмитрий

Задача

Из заданного четырёхзначного натурального числа образовать двузначное, состоящее из его средних цифр.

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

Одно четырёхзначное натуральное число.

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

Полученное двузначное число.

Тесты

#	Входные данные	Выходные данные
1	4765	76
2	7999	99
3	2514	51
4	9423	42
5	8234	23

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

#include <iostream>
using namespace std;

int main() {
    int a;
    cin >> a;
    a /= 10;
    cout << a % 100;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a;

cin >> a;

a /= 10;

cout << a % 100;

return 0;

}

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

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

Ссылки

Задача на сайте e-olymp

Код решения Ideone

Related Images:

e-olymp 1474. Сломанные часы

16/12/2017 by Томас Пасенченко

Задача

В электронных часах произошел сбой, и теперь каждую секунду увеличивается не счетчик секунд, а счетчик часов. При переполнении счетчика часов (то есть при достижении [latex]24[/latex]) он сбрасывается в [latex]0[/latex] и увеличивается счетчик минут. Аналогично, при переполнении счетчика минут происходит его сброс и увеличивается счетчик секунд. При переполнении счетчика секунд он также сбрасывается в [latex]0[/latex], а остальные счетчики так и остаются равными [latex]0[/latex]. Известно, что сбой произошел в [latex]h_1[/latex] часов [latex]m_1[/latex] минут [latex]s_1[/latex] секунд. В этот момент часы показывали правильное время.

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

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

В первой строке задаются три целых числа [latex]h_1[/latex], [latex]m_1[/latex], [latex]s_1[/latex], определяющие время поломки часов. Во второй строке записаны три числа [latex]h_2[/latex], [latex]m_2[/latex], [latex]s_2[/latex], которые определяют показания часов в текущий момент времени ( [latex]0\;\le\;h_1,\;h_2\;\lt\;24[/latex], [latex]0\;\le m_1,\;m_2,\;s_1,\;s_2\;\lt\;60[/latex] ).

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

В единственной строке выведите правильное время (т.е. число часов, минут и секунд) в момент, когда сломанные часы будут показывать [latex]h_2[/latex] часов [latex]m_2[/latex] минут [latex]s_2[/latex] секунд.

Тесты

Входные данные	Выходные данные
[latex]12 \; 0 \; 0\\12 \; 1 \; 0[/latex]	[latex]12 \; 0 \; 24[/latex]
[latex]13 \; 59 \; 59\\12 \; 59 \; 59[/latex]	[latex]13 \; 59 \; 58[/latex]
[latex]15 \; 12 \; 16\\15 \; 12 \; 16[/latex]	[latex]15 \; 12 \; 16[/latex]
[latex]\;0 \;\;\; 0 \;\;\; 0\\23 \; 59 \; 59[/latex]	[latex]23 \; 59 \; 59[/latex]
[latex]16 \; 0 \; 17\\16 \; 0 \; 18[/latex]	[latex]16 \; 24 \;17[/latex]
[latex]11 \;\; 0 \;\; 53\\0 \;\;\; 0 \;\;\; 0[/latex]	[latex]13 \; 48 \; 42[/latex]
[latex]1 \;\; 13 \; 18\\22 \; 51 \; 32[/latex]	[latex]7 \;\;\; 4 \;\;\; 51[/latex]

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

#include <iostream>
using namespace std;
 
int main() {
    int h1, m1, s1, h2, m2, s2;
    int sum1, sum2, sec, time1, time2;
    int h3, m3, s3;
    cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;
    sum1 = h1 + m1 * 24 + s1 * 24 * 60;
    sum2 = h2 + m2 * 24 + s2 * 24 * 60;
    sec = (sum2 - sum1 + 86400) % 86400;
    time1 = 3600 * h1 + 60 * m1 + s1;
    time2 = (time1 + sec) % 86400;
    s3 = time2 % 60;
    m3 = ((time2 - s3) / 60) % 60;
    h3 = (time2 - m3 * 60 - s3) / 3600;
    cout << h3 << " " << m3 << " " << s3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int h1, m1, s1, h2, m2, s2;

int sum1, sum2, sec, time1, time2;

int h3, m3, s3;

cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;

sum1 = h1 + m1 * 24 + s1 * 24 * 60;

sum2 = h2 + m2 * 24 + s2 * 24 * 60;

sec = (sum2 - sum1 + 86400) % 86400;

time1 = 3600 * h1 + 60 * m1 + s1;

time2 = (time1 + sec) % 86400;

s3 = time2 % 60;

m3 = ((time2 - s3) / 60) % 60;

h3 = (time2 - m3 * 60 - s3) / 3600;

cout << h3 << " " << m3 << " " << s3;

return 0;

}

Решение

Учитывая особенности хода сломанных часов, подсчитаем количество секунд в начальный и конечный моменты времени ( sum1 и sum2). Вычислим, сколько секунд прошло с момента поломки часов — для этого найдём разность sum2 - sum1, прибавим [latex]86400[/latex] — количество секунд в сутках (поскольку мог произойти переход через момент времени [latex]0 \; : \; 0 \; : \; 0[/latex]) и найдём остаток от деления полученной суммы на [latex]86400[/latex].

Теперь найдём количество секунд, прошедших с начала суток, в которых поломались часы ( time1). Прибавим к нему количество секунд, прошедших с момента поломки часов и найдём остаток от деления на [latex]86400[/latex] полученного числа. Имеем time2 — правильное время в секундах. Далее, находим значения счётчиков часов [latex]h_3[/latex], минут [latex]m_3[/latex] и секунд [latex]s_3[/latex] которые соответствуют моменту времени time2.

Ссылки

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

Related Images:

e-olymp 7365. Молоко и пирожок

16/12/2017 by Данилов Андрей

Задача

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее [latex]30[/latex] кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость [latex]200[/latex] мл, а упаковки молока – [latex]0,9[/latex] л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

В первой строке задано целое число [latex]n[/latex] [latex](0 < n ≤ 100)[/latex]. В следующей строке идут [latex]n[/latex] положительных действительных чисел – массы первоклассников.

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

В одной строе вывести два целых числа — количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты

#	Входные данные	Выходные данные
1	4 30 36 29 47	1 1
2	5 30 36 29 47 26	1 2
3	8 30 36 29 47 26 27 30 31	1 3
4	1 29	1 1
5	5 26 27 28 29 25	2 5

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

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

int main() {
    double children ; double cakes = 0 ; double milk = 0; double child ;
    cin >> children ;
    while ( cin >> child) {
        if ( child < 30) {
            cakes++; milk += 2;
        }
    }
    cout << ceil(milk/9) << " " << cakes;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double children ; double cakes = 0 ; double milk = 0; double child ;

cin >> children ;

while ( cin >> child) {

if ( child < 30) {

cakes++; milk += 2;

}

cout << ceil(milk/9) << " " << cakes;

return 0;

}

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

По условию задачи мы должны узнать сколько нужно упаковок молока и штук пирожков для детей.Для пирожков мы заводим счетчик, который увеличивает на единицу, если появился подходящий ребенок.А для молока будем использовать целые числа (0,2 домножим на 10 и 0,9 также домножим на 10).И будем считать сколько всего тратится молока,затем поделим на 9 и узнаем сколько пачек молока нужно,так как могут быть на выходе не целые числа,то округляем вверх.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

e-olymp 7366. Сколько до Нового Года?

05/12/2017 by Яна Колчинская

Задача

У Деда Мороза есть часы, которые в секундах показывают сколько осталось до каждого Нового Года. Так как Дед Мороз уже человек в возрасте, то некоторые математические операции он быстро выполнять не в состоянии. Помогите Деду Морозу определить сколько полных дней, часов, минут и секунд осталось до следующего Нового Года, если известно сколько осталось секунд, т.е. разложите время в секундах на полное количество дней, часов, минут и секунд.

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

В единственной строке целое число [latex]N \left(0 < N ≤ 31500000\right)[/latex] – количество секунд, которые остались до наступления Нового Года.

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

В одной строке через пропуск четыре целых числа – количество полных дней, часов, минут и секунд. После последнего числа пробел отсутствует.

Тесты

#	Входные данные	Выходные данные
1	5217656	60 9 20 56
2	7999	0 2 13 19
3	30123456	348 15 37 36
4	7841186	90 18 6 26
5	899650	10 9 54 10

Код

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    cout<<n/86400<<" "<<(n%86400)/3600<<" "<<((n%86400)%3600)/60<<" "<<n%60;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

cout<<n/86400<<" "<<(n%86400)/3600<<" "<<((n%86400)%3600)/60<<" "<<n%60;

return 0;

}

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

Вспомним, что:
1 сутки = 86400с;
1 час = 3600с;
1 минута = 60с.

Сперва рассчитаем кол-во полных суток в данном кол-ве секунд [latex]n[/latex]: [latex]\frac{n}{86400}[/latex].
Затем уберём кол-во секунд в полных сутках из исходного числа, а из оставшихся вычислим кол-во полных часов: [latex]\frac{n\bmod86400}{3600}[/latex].
Далее снова уберём кол-во секунд в полных часах и найдём кол-во полных минут: [latex]\frac{\left(n\bmod8640\right)\bmod3600}{60}[/latex].
Остаток от деления общего кол-ва секунд на 60 и будет искомым кол-вом секунд: [latex]n\bmod60[/latex].

Ссылки

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

Related Images:

e-olymp 2803 МаркЕрованные кубики

17/12/2015 by Холодков Юрий

Задача

У Витека есть набор кубиков, на котором изображены английские буквы, причём как маленькие, так и большие. Недавно мама подарила ему ещё и набор кубиков с цифрами, в результате чего Витек научился быстро считать в пределах 10-ти. А вот папа имел неосторожность подарить ему набор разноцветных маркеров, после чего Витек начал экспериментировать с кубиками с цифрами: он зарисовывал очередную цифру и на её месте рисовал цифру на единицу большую. Так как он прекрасно понимал, что цифры 10 не существует, он вместо числа 10 всегда писал цифру 0.

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

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

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

Единственная строка, состоящая из описанных выше символов. Длина строки не превышает 255 символов.

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

Единственная строка – результат работы Вашей программы.

Тесты

Входные данные	Выходные данные
abc1234567890ABC	abc2345678901ABC
00000000	11111111
546476756	657587867

Алгоритм решения

Проверяем, является ли элемент строки числом. Если это 9, заменяем ее на 1, иначе увеличиваем значение символа на 1.

#include <iostream>
using namespace std;

int main() {
	string str;
	getline(cin, str);
	for(int i = 0; i < str.length(); i++){
		if(str[i]>='0' && str[i]<'9'){
			str[i]++;
		}
		else if(str[i]=='9') str[i]='0';
	}
	cout << str;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

string str;

getline(cin, str);

for(int i = 0; i < str.length(); i++){

if(str[i]>='0' && str[i]<'9'){

str[i]++;

}

else if(str[i]=='9') str[i]='0';

}

cout << str;

return 0;

}

Ссылка на задачу на е-олимпе

Ссылка на засчитанное решение

Ссылка на среду с кодом

Решение через c-like string

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

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

int main() {
	int n = 256;
	char a[n];
	cin.getline(a,n);
	for(int i = 0; i < strlen(a); i++){
		a[i]-='0';
		if (a[i]>=0 && a[i]<9){
			a[i]+=1;
		}
		else if(a[i]==9) a[i]=0;
		a[i]+='0';
	}
	for(int i=0;i<strlen(a);i++){
		cout << a[i];
	}
	return 0;
}