e-olymp 8532. Печать квадратов и кубов

Задача

Заданы два целых числа $a$ и $b$. Выведите квадраты и кубы всех целых чисел от $a$ до $b$ включительно.

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

Два целых числа $a$ и $b$ [latex](0 \le a \le  b \le 10000)[/latex].

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

В первой строке выведите квадраты всех целых чисел от $a$ до $b$ включительно по возрастанию. Во второй строке выведите кубы всех целых чисел от $a$ до $b$ включительно по убыванию.

Тесты

 

Входные данные Выходные данные
5 10 25 36 49 64 81 100
1000 729 512 343 216 125
120 123 14400 14641 14884 15129
1860867 1815848 1771561 1728000
9995 10000 99900025 99920016 99940009 99960004 99980001 100000000
1000000000000 999700029999 999400119992 999100269973 998800479936 998500749875
0 3 0 1 4 9
27 8 1 0
25 27 625 676 729
19683 17576 15625

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

Решение

Ввожу $a$ и $b$, создаю цикл вывода по возрастанию квадратов чисел из промежутка, и с новой строки — кубы по убыванию.

Ссылки

Ideone

e-olymp

e-olymp 8533. Числа с разными цифрами

Задача

Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

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

Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

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

Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

Тесты

 Входные данные Выходные данные
 2000 2015  2013 2014 2015
 9875 9999  9875 9876
 1000 1234  1234
 3612 3612  3612
 8800 8888  Standart output is empty
 1000 1000  Standart output is empty

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

 

Решение

Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

Ссылки

Ideone

e-olymp

e-olymp 4482. В стране невыученных уроков 2

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

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

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

Тесты

Входные данные Выходные данные
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
wins
wins
wins
draw
5
7 7 7 7 7
4
1 1 5
2 2 1
1 1 5
1 3 5
draw
wins
draw

Задача взята отсюда.

Решенная задача на e-olymp.

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

 

e-olymp 4481. В стране невыученных уроков

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные: Выходные данные:
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
2
2
5
1

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

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

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение  НОД на отрезке и запрос на модификацию элемента являются рекурсивными.  Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

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

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 141. Минимальная сумма цифр

Условие задачи:

Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

Задачу также можно найти здесь.

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

Во входном файле два числа [latex]M[/latex] и [latex]N[/latex] ( [latex]1\le M\le N\le 1000000[/latex] ) .

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

В выходной файл нужно записать ответ — одно число.

Тесты

M N Вывод
1 1 100 3
2 2 17 1
3 32 1024 2
4 1 1000000 7
5 10 10 1

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

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

Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму (sumMin) сумме цифр первого числа [latex] M [/latex]. Теперь задаём цикл со счётчиком [latex] i [/latex] от [latex] M + 1 [/latex] до [latex]\le N[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex] M [/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.

Код программы можно найти здесь.

Ссылка на полностью засчитанное решение на сайте e-olymp.

Ю 2.31

Задача

График движения путников к задаче Ю 2.31


График движения путников к задаче Ю2.31

Встреча. Из пункта А в пункт В выехал велосипедист со скоростью [latex]v_{0} [/latex] км/час. Одновременно навстречу ему из пункта В двинулся «автостопом» другой путник.[latex]s_{1} [/latex] м он двигался со скоростью [latex]v_{1} [/latex] м/час, [latex]s_{2} [/latex] м — со скоростью [latex]v_{0} [/latex] км/час, [latex]s_{3} [/latex] м — со скоростью [latex]v_{3} [/latex] км/час. Через сколько часов после старта и в какой точке путники встретились?

 Тесты

v0, км/час v1, м/час v3, км/час s1, м s2, м s3, м place, км time, час Комментарии
40 15000 10 20000 40000 40000 66.667 1.667 Пройден (встреча на первом промежутке)
10 5000 60 10000 60000 30000 55.0 5.5 Пройден (встреча на первом промежутке)
8 5000 30 10000 10000 80000 37.368 4.671 Пройден (встреча на первом промежутке)
-300 30000 23333 22222 5454 555.1 Неправильно введены данные Не пройден
10 2222 3333 0 -4444 11.6 Неправильно введены данные Не пройден

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

Можно предположить, что весь путь в задаче представлен суммой [latex]ss=s_{1}+s_{2}+s_{3}[/latex]. Для начала переведем все величины  в единицы СИ:

Из метров в километры:

[latex]s_{1}=s_{1}*0.001 \Leftrightarrow s_{1}=\frac{s_{1}}{1000}[/latex],

[latex]s_{2}=s_{2}*0.001 \Leftrightarrow s_{2}=\frac{s_{2}}{1000}[/latex],

[latex]s_{3}=s_{3}*0.001 \Leftrightarrow s_{3}=\frac{s_{3}}{1000}[/latex].

Из метров/час в километры/час: [latex]v_{1}=v_{1}*0.001 \Leftrightarrow v_{1}=\frac{v_{1}}{1000}[/latex]

Найдем место встречи. Тут может быть три случая:

  1. Встреча двух путников на первом промежутке пути. Тогда время встречи можно вычислить по формуле: [latex]time = \frac{ss}{( v_{0} + v_{1} )}[/latex] , а место встречи —  [latex]place = time * v_{0}[/latex]
  2. Встреча двух путников на втором промежутке пути: Тогда время встречи можно вычислить по формуле: [latex]time =\frac{ss — s_{1} — ( v_{0} * t_{1} ) }{ v_{0} + v_{0} }[/latex] , а место встречи — [latex]place = ( t_{1} + time ) * v_{0}[/latex].
  3. Встреча двух путников на третьем промежутке пути: Тогда время встречи можно вычислить по формуле: [latex]time = \frac{ ss — s_{1} — s_{2} — ( v_{0} * t_{2} )}{ v_{0}+ v_{3} }[/latex], а место встречи — [latex] place = ( t_{1}+t_{2} + time ) * v_{0}[/latex].

Если путники встречаются на первом промежутке пути, то их скорости суммируются (т.к. тела движутся на встречу друг к другу), при делении всего пути на сумму этих скоростей получим время встречи, расстояние можно найти умножив время встречи на скорость первого путника.

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

Аналогично и на третьем промежутке пути. В формуле нахождения времени встречи учитывается путь, пройденный путниками за первый и за второй промежутки времени, эту разность делим на сумму скоростей и получаем время встречи.

Код на Java