Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.
Входные данные
Одно число $n$ $\left(10\leq n\leq 10^9\right)$.
Выходные данные
Выведите наименьшее количество операций.
Тесты
№
Входные данные
Выходные данные
1
1447
16
2
18
3
3
111
6
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
usingnamespacestd;
intmain(){
longlongn;
intk=0;
cin>>n;
while(n>0){
k+=n%3+1;
n/=3;
}
cout<<k-2;
}
Решение
Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл
while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть
k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$.
n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.
Система образования Вас снова подвела — Ваше предложение о включении модели «Плоская Земля» в программу старшей школы было отклонено в шестой раз подряд. Коррумпированные ученые Круглой Земли отказываются прислушиваться к Вашим аргументам и игнорируют кучу данных, подтверждающих Ваши заявления.
Настало время урегулировать этот конфликт раз и навсегда. Вы путешествовали по всему земному шару и встречались с ведущими учеными Плоской Земли. Вместе Вы разработали блестящий план.
Ради противоречия предположим, что Земля — это сфера в трехмерном пространстве. Тогда, если предположить, что небо является бесконечной плоскостью в пространстве, такая Земля явно бросит на него тень! Эта тень была бы ортогональной проекцией Земли на небо. Поскольку в действительности на небе нет видимой тени, мы достигаем противоречия.
Осталось только выполнить расчеты. По заданным центру и радиусу Земли, а также уравнению небесной плоскости в виде [latex]ax + by + cz + d = 0[/latex] необходимо определить площадь ортогональной проекции Земли на небо. Обратите внимание, что в некоторых Ваших экспериментах Земля может пересекать небо — Вы не хотели бы вводить слишком много ненужных предположений, не так ли?
Входные данные
Первая строка содержит количество тестов [latex]n[/latex] [latex]\left(1\leqslant n\leqslant 10\right)[/latex]. Далее следует описание тестов.
Каждый тест описывается строкой, содержащей восемь целых чисел [latex] x, y, z, r, a, b, c, d [/latex]. Они обозначают координаты центра Земли, его радиус и уравнение неба соответственно. Все числа от [latex]1[/latex] до [latex]1000[/latex] включительно.
Выходные данные
Для каждого теста выведите одно число: площадь проекции с не менее [latex]6[/latex] десятичными цифрами.
Для начала, определимся, чего от нас хотят авторы задачи. По сути, самой важной частью условия является третий абзац, из которого мы узнаем, что Земля — сфера, а также, что ортогональная проекция Земли на небо — это тень от Земли на небесную плоскость. Но, если существует тень, значит существует и светило (Солнце). Для того, что бы стало более понятно, проведём эксперимент. Представим, что Земля — это, к примеру, сфера, Солнце — это настольная лампа (Важно! Лампа будет давать параллельный пучок лучей), а небесная плоскость — это обычный лист бумаги. (Важно! В данном эксперименте размеры светила и размеры «Земли» будут совпадать). При направлении света на сферу, на лист бумаги будет отбрасываться тень (площадь которой нам и надо найти). Итак, как мы видим на рисунке, площадь проекции — это ничто иное, как площадь сечения сферы, проходящее по центральной оси этой сферы. А площадь сечения сферы по центральной оси — это площадь круга, которая вычисляется по формуле [latex]S=\pi r^2[/latex]. Таким образом, что бы рассчитать площадь проекции, из всех входящих данных нам понадобится только радиус Земли. Что бы у нас было число [latex]\pi[/latex], мы подключаем библиотеку
cmath. Чтобы вывести число с [latex]6[/latex] десятичными знаками после запятой, подключаем библиотеку
iomanip .
Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $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$.
Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:
Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.
В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.
Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.
Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.
Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.
Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).
Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.
Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.
Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.
[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.
Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].
Входные данные
Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.
Выходные данные
Количество пиратов [latex]n[/latex].
Тесты
#
ВХОДНЫЕ ДАННЫЕ
ВЫХОДНЫЕ ДАННЫЕ
1
5 25
3
2
3 24
4
3
4 38
5
4
5 55
6
5
6 75
7
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cmath>
usingnamespacestd;
intmain(){
doublea,m,n,b,c,d;
cin>>a>>m;
b=2*a+1;
c=2*a-2-2*m;
d=b*b-4*c;
n=(-b+sqrt(d))/2;
cout<<n;
return0;
}
Решение задачи
Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.
Код программы (с циклом)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
usingnamespacestd;
intmain(){
unsignedinta,m,n=0;
cin>>a>>m;
while(m-2*a!=0){
m-=a;
a++;
n++;
}
cout<<n+1;
return0;
}
Решение задачи
В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.
Код программы (с условным оператором)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
usingnamespacestd;
intf(inta,intm,intn=0){
if(m-2*a==0){
returnn+1;
}
else{
returnf(a+1,m-a,n+1);
}
}
intmain(){
inta,m;
cin>>a>>m;
cout<<f(a,m);
return0;
}
Решение задачи
В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.
Проверяем, есть ли среди введенных чисел хотя бы одно четное и хотя бы одно нечетное. При выполнении обоих условий, выводим «YES», в другом случае «NO».
По известным формулам длины окружности [latex]l = 2\pi r[/latex] и площади окружности [latex]S = \pi r^{2}[/latex] находим их. С помощью
setprecison() выводим числа с нужной нам точностью.
Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b\left(1\leq a, b\leq 1000\right)[/latex]
Выходные данные
Выведите периметр прямоугольника.
Тесты
Входные данные
Выходные данные
1 1
4
1000 1000
4000
10 20
60
12 13
50
176 37
426
Решение
C++
1
2
3
4
5
6
7
8
9
#include <iostream>;
usingnamespacestd;
intmain(){
inta,b;
cin>>a>>b;
cout<<(a+b)*2;
return0;
}
Объяснение
Поскольку стороны прямоугольника, используемые в задаче, целочисленные, и каждое из них меньше [latex]1000[/latex] то переменные создаём типа
int. Для решения этой задачи воспользуемся формулой нахождения периметра прямоугольника: [latex] (a+b) \cdot 2 [/latex]
Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?
Входные данные
Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]
Выходные данные
Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.
Тесты
№
Ввод
Вывод
1
12 4 6
YES
2
10 5 6
NO
3
1056 22 6
YES
4
98 103 5
NO
Решение
Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ (
n%a==0), и остаток от деления $n$ на $b$ равен $0$ (
n%b==0).
Код с ветвлением
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
usingnamespacestd;
intmain(){
intn,a,b;
cin>>n>>a>>b;
cout<<(((n%a==0)&&(n%b==0))?"YES":"NO");
/* Делаем проверку делимости n одновременно на a и b,
и, в зависимости от результата, при помощи тернарной операции выводим ответ */
return0;
}
Код без использования ветвления
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
usingnamespacestd;
intmain(){
intn,a,b,result;
cin>>n>>a>>b;
/* Используем небольшой трюк, который заключается в том,
что cout в логических выражениях имеет значение 1 (true)*/
По заданным длинам трех отрезков определить, можно ли из них составить невырожденный треугольник. Треугольник называется невырожденным, если его площадь больше 0.
Входные данные
Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.
Выходные данные
Вывести YES если из отрезков можно составить невырожденный треугольник и NO в противном случае.
Тесты
#
ВХОДНЫЕ ДАННЫЕ
ВЫХОДНЫЕ ДАННЫЕ
1
5 6 7
YES
2
3 7 4
NO
3
16 24 32
YES
4
54 1 100
NO
5
1 1 1
YES
Код программы (Ветвление)
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
usingnamespacestd;
intmain(){
inta,b,c;
cin>>a>>b>>c;
cout<<(a<b+c&&b<a+c&&c<a+b?"YES":"NO");
return0;
}
Код программы (Линейные вычисления)
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
usingnamespacestd;
intmain(){
inta,b,c;
cin>>a>>b>>c;
boolcondition=(a<b+c&&b<a+c&&c<a+b);
cout<<(char)(condition*'Y'+!condition*'N')
<<(char)(condition*'E'+!condition*'O')
<<(char)(condition*'S'+!condition*' ');
return0;
}
Решение задачи
Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}
Напишите программу, которая приветствует пользователя, выводя слово Hello, имя пользователя и знаки препинания в следующем виде: Hello, Harry
Входные данные
В единственной строке вводится имя пользователя.
Выходные данные
В первой строке выведите приветствие.
Тесты
#
ВХОДНЫЕ ДАННЫЕ
ВЫХОДНЫЕ ДАННЫЕ
1
Harry
Hello, Harry
2
Peter
Hello, Peter
3
Emily
Hello, Emily
4
Anna-Maria
Hello, Anna-Maria
5
Zhao Yun
Hello, Zhao Yun
Код
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
usingnamespacestd;
intmain(){
stringname;
getline(cin,name);
cout<<"Hello, "<<name;
return0;
}
Решение
Для того, чтобы задать переменную-строку, воспользуемся библиотекой
string. Далее, введём переменную, к примеру
name (имя). В строке вывода зададим неизменную часть фразы
Hello, и саму переменную.
Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:
Предположим, что некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.
В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Входные данные
В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] (1 ≤ [latex]n[/latex], [latex]m[/latex] ≤ [latex]\ 10^{9}[/latex]).
Выходные данные
Максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Тесты
#
Входные данные
Выходные данные
1
3 4
2
2
15 144
10
3
1 7
7
4
100 123456
1235
5
222 222
1
Код
C++
1
2
3
4
5
6
7
8
9
10
11
#include < iostream >
#include < cmath >
usingnamespacestd;
intmain(){
longlongn,m;
cin>>n>>m;
longlongres=ceil(m/(double)n);
cout<<res;
return0;
}
Решение
Распределяя всех [latex] m [/latex] зайцев равномерно по клеткам [latex] n [/latex] получаем что максимальное количество зайцев в одной клетке равно [latex]\lceil \frac{m}{n}\rceil[/latex]
Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.
Входные данные
Целое число [latex]N (0 < N≤ 1000)[/latex].
Выходные данные
Единственное число – количество дней.
Тесты
#
ВХОДНЫЕ ДАННЫЕ
ВЫХОДНЫЕ ДАННЫЕ
1
9
1
2
45
4
3
324
16
4
1234
28
5
213213123
153
Код программы №1 (с использованием цикла):
Код программы №1(с использованием цикла):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
usingnamespacestd;
intmain()
{
doublek=1,T=10,N,S=10;
cin>>N;
while(N>T){
S=S*1.1;
T=S+T;
k++;
}
cout<<k;
return0;
}
Решение задачи:
Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.
Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]
Код программы №2(с использованием линейных вычислений):
Код программы №2(с использованием линейных вычислений):
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <cmath>
usingnamespacestd;
intmain()
{
doubles;
cin>>s;
cout<<ceil(log(s/100+1)/log(1.1));
return0;
}
Решение задачи:
Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).
Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]
В электронных часах произошел сбой, и теперь каждую секунду увеличивается не счетчик секунд, а счетчик часов. При переполнении счетчика часов (то есть при достижении [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] секунд.
Учитывая особенности хода сломанных часов, подсчитаем количество секунд в начальный и конечный моменты времени (
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.
Работник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.
Входные данные
Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].
Выходные данные
Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.
№
Входные данные
Выходные данные
1
5
3
2
10
4
3
1000000
1414
4
555666777888
1054198
5
13
5
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cmath>
usingnamespacestd;
intmain(){
//учтём ограничение для s (s ≤ 2000000000)
longlongs;
//для k используем целочисленный тип, так как при присваивании ему дробного числа, это число автоматически округлится.
longlongk;
cin>>s;
k=sqrt(2*s+1);
cout<<k;
return0;
}
Решение
[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:
[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]
[latex]k^2<=2s+1[/latex]
[latex]k=[\sqrt{2s+1}][/latex]
Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.
Входные данные
В одной строке два целых числа [latex]h[/latex] и [latex]w[/latex] ([latex]1 ≤ h, w ≤ 1000[/latex]) — высота и ширина куска бумаги.
Выходные данные
Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex]h × w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.
Тесты
Входные данные
Выходные данные
$100$ $100$
$50.000$
$10$ $80$
$10.000$
$50$ $76$
$25.333$
$60$ $27$
$20.000$
$8$ $3$
$2.667$
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cmath>
#include <iomanip>
usingnamespacestd;
intmain()
{
cout.precision(4);
doubleh,w=0;
cin>>h;
cin>>w;
doubleb=max(h,w);
doublea=min(w,h);
doublec=min(a,max(b/3,a/2));
cout<<fixed<<c;
}
Решение задачи
Существует два варианта оптимального расположения трех квадратов — три в один ряд,
или же два, соприкасающихся одной стороной, и третий над ними
Обозначим за [latex]a[/latex] меньшую сторону листа бумаги, а за [latex]b[/latex] — большую. Если [latex]a[/latex] не больше [latex]\frac{b}{3}[/latex], то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги [latex]a[/latex]. В противном случае рассмотрим два варианта:
Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [latex]\frac{b}{3}[/latex].
Таким образом, в случае [latex]a>\frac{b}{3}[/latex] ответом будет служить большее из двух чисел [latex]\frac{a}{2}[/latex] и [latex]\frac{b}{3}[/latex].
Минимальное из [latex]\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex] и [latex]a[/latex] число и будет ответом.
Проверим нашу формулу:если [latex]a<\frac{b}{3}[/latex], то [latex] \max\left(\frac{b}{3},\frac{a}{2}\right)=\frac{b}{3} [/latex], и тогда [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=a[/latex]. Иначе [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex], что нам и требуется.
Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].
Входные данные
Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).
Выходные данные
Искомая высота с точностью до сотых.
Тесты
#
Входные данные
Выходные данные
1
20 7
3.73
2
35 3
7.00
3
12 4
3.29
4
67 9
7.92
5
135 13
11.17
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>//данная библиотека позволяет извлекать корень квадратный
#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой
usingnamespacestd;
intmain(){
ints,a;//площадь треугольника,разность основания и высоты
intd;//дискриминант
doubleh,dk;// высота треугольника, корень квадратный из дискриминанта
cin>>s>>a;
d=a*a+8*s;//формула для нахождения дискриминанта
dk=sqrt(d);//извлекаем корень квадратный из дискриминанта
h=(-a+dk)/2;//формула для нахождения высоты треугольника
cout<<fixed<<setprecision(2)<<h;// функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков
return0;
}
Алгоритм решения задачи
Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
Подставляем исходные данные в формулы, получаем результат.
Также подробное описание представлено в коде программы.
Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом [latex]i[/latex] умножением [latex]a[/latex] (которое необходимо возвести в степень [latex]i[/latex]) на индекс [latex]i[/latex] и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).
Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex]
Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].
Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.
Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.
Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.
Для отправки комментария необходимо войти на сайт.