OCPC2021 C: Перепись чисел

13/11/2021 by Мазурок Игорь Евгеньевич

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени:	`1 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Перепись чисел

Учительница младших классов Марь Ивановна, постоялица палаты номер 9 ³/₄ заведения «Покосившийся Скворечник», насмотрелась «Гарри Поттера» и теперь боится, что Волдеморт сотрёт у неё из памяти какое-нибудь число. Чтобы не допустить этого преступления, Марь Ивановна решила выписать все числа от 1 до n (числа, большие, чем n, ей для работы всё равно не пригодятся) подряд в одну строку на стене палаты. При этом, для экономии времени (Волдеморт уже рядом!), она решила приписывать очередное число к своей строке только в том случае, если его десятичная запись еще не содержится в уже записанной строке. Например, в строке «1234567891011» уже содержится запись числа 12, а значит, приписывать это число не нужно.

Сосед Марь Ивановны, трудовик Василий Семёныч, убеждён, что Волдеморт уже стёр какое-то число из памяти учительницы младших классов. Чтобы удостовериться в своей правоте, он требует, чтобы Вы показали ему, как должна выглядеть верная строка, составленная по правилам Марь Ивановны, для сравнения с тем, что в итоге появится на стене палаты. В награду за помощь он обещает выстрогать бузинную палочку для вас. Поскольку в руках у Василия Семёныча лобзик, лучше с ним не спорить!

На ввод поступает единственное целое число n (1 ≤ n ≤ 10⁵) – максимальное число, важное для работы учительницы младших классов.

Выведите одну строку, содержащую запись всех чисел от 1 до n по правилам Марь Ивановны.

Примеры

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

Результат работы

1234

1234567891011131415

1	1234567891011131415

Видеоразбор решения здесь.

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах

igor.mazurok.com

e-olymp 8688. Количество чисел без 8

05/06/2019 by Андрей Зиновьев

Задача

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

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные	Вывод программы
10	9
25833798135522720	4918510377816614
88888888888888	20334926626631

Continue reading →

Андрей Зиновьев

e-olymp 3867. Ленивый Мишка

23/09/2018 by Иван Киреев

Задача. Ленивый Мишка

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

На мытье посуды уйдет [latex]t_1[/latex] секунд
Пропылесосить квартиру можно за [latex]t_2[/latex] секунд
Процесс игры с Маринкой займет [latex]t_3[/latex] секунд

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

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

Три целых числа [latex]t_1[/latex], [latex]t_2[/latex], [latex]t_3[/latex] ([latex]1 ≤ t_1, t_2, t_3 ≤ 1000[/latex]).

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

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

Тесты

№	Ввод	Вывод
1	1 7 2	1
2	100 45 1	1
3	66 9 888	9
4	5 800 4	4
5	25 46 25	25
6	13 10 12	10
7	999 995 1000	995

Решение 1

Мишка выбирает мамино поручение, что занимает наименьшее количество времени. Нам дано время за которое Мишка выполнит данные поручения. Найдём из них наименьшее и выведем на экран. Воспользуемся функцией int min (int, int); из библиотеки cmath.

Код 1

#include <iostream>
#include <cmath>

using namespace std;

int main ()
{
    short t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main ()

{

short t1, t2, t3;

cin >> t1 >> t2 >> t3;

cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.

return 0;

}

Решение 2

Для нахождения минимума трёх чисел заведём переменную min и воспользуемся логическим ветвлением.

Код 2

#include <iostream>

using namespace std;

int main ()
{
    short t1, t2, t3, min;
    cin >> t1 >> t2 >> t3;
    min = t1; //Переменная отвечающая за минимальное значение.
    if (t2 < min) min = t2;
    if (t3 < min) min = t3;
    cout << min;
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

short t1, t2, t3, min;

cin >> t1 >> t2 >> t3;

min = t1; //Переменная отвечающая за минимальное значение.

if (t2 < min) min = t2;

if (t3 < min) min = t3;

cout << min;

return 0;

}

Ссылки

Первое решение

Второе решение

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

Компиляция первого решения

Компиляция второго решения

Иван Киреев

e-olymp 108. Среднее число

19/12/2017 by Амир Аль-Омари

Задача

Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

Вывести среднее среди трех чисел.

Тесты

Входные данные	Выходные данные
10 4 9	9
2 256 8	8
1 2 3	2

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

#include <iostream>
using namespace std;

int main() {
    double a, b, c;
    cin >> a >> b >> c;
    if ((b > a && a > c) || (c > a && a > b)) {
        cout << a;
    }
    else if ((a > b && b > c) || (c > b && b > a)) {
        cout << b;
    }
    else {
        cout << c;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, b, c;

cin >> a >> b >> c;

if ((b > a && a > c) || (c > a && a > b)) {

cout << a;

}

else if ((a > b && b > c) || (c > b && b > a)) {

cout << b;

}

else {

cout << c;

}

return 0;

}

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

Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Амир Аль-Омари

MS2. Сумма чисел во входном потоке

23/04/2017 by Роман Саркисян

Условие

Сосчитайте сумму чисел во входном потоке.

Тесты

Ввод	Вывод
1 2 3 4 5 6	21
12 13 14	39
1-100	5050

#include <iostream>
using namespace std;

int main() {
    double x, S=0;
    while( cin>>x){
        S+=x;
    }
    cout<<S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, S=0;

while( cin>>x){

S+=x;

}

cout<<S;

return 0;

}

import java.util.*;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner scan = new Scanner(System.in);
        double sum = 0;
        double number = 0;
        while(scan.hasNext()){
            number=scan.nextInt();
            sum+=number;
        }
        System.out.println(sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception {

Scanner scan = new Scanner(System.in);

double sum = 0;

double number = 0;

while(scan.hasNext()){

number=scan.nextInt();

sum+=number;

}

System.out.println(sum);

}

Решение

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

Код на ideone C++
Код на ideone Java

Роман Саркисян

e-olymp 474. Максимум

22/10/2015 by Станислав Коциевский

Задача.

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

Он предложил Васе находить суммы цифр последовательных чисел — 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 — и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от 1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр последовательных чисел не являются случайными, часто они идут подряд, но полностью закономерность он так и не понял.

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

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

В первой строке входных данных находится число N (1 <= N <= 2 147 483 647).

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

Выведите число от 1 до N включительно с максимальной суммой цифр. Если чисел с максимальной суммой цифр несколько, выведите наибольшее из них.

Тесты:

число N	результат
1	1
98	98
13759	9999
999756	998999
2147483647	1999999999

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

#include <iostream>
using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе
{
	int i=1;
    while ((n/=10)>0)
    {
    	i++;
    }
    return i;
}

int sc(int a) //Сумма цифр числа
{
	int sum = 0;
	while (a/1>0)
	{
		sum+=a%10;
		a/=10;
	}	
	return sum;
}

int main()
{
	int n, v, t, x;
	cin>>n;
	unsigned long long int a=10;
	t=TheNumberOfDigits(n);
	x=n;
	for (int i=1;i<t;i++)
	{
		unsigned long long int b = a*10;
		v=(n/b)*b+(n%b/a-1)*a+a-1;
		if (sc(v)>sc(x))
			x=v;
		a*=10;
	}
	cout<<x<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе

{

int i=1;

while ((n/=10)>0)

{

i++;

}

return i;

}

int sc(int a) //Сумма цифр числа

{

int sum = 0;

while (a/1>0)

{

sum+=a%10;

a/=10;

}

return sum;

}

int main()

{

int n, v, t, x;

cin>>n;

unsigned long long int a=10;

t=TheNumberOfDigits(n);

x=n;

for (int i=1;i<t;i++)

{

unsigned long long int b = a*10;

v=(n/b)*b+(n%b/a-1)*a+a-1;

if (sc(v)>sc(x))

x=v;

a*=10;

}

cout<<x<<endl;

return 0;

}

Решение.

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

Сумму цифр и их количество в числе считают две простых в написании функции, степени (i-я и i+1-я)десятки считаются непосредственно в основном цикле.

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

Ссылка на условие задачи

Ссылка на код на ideone

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

примечание: ссылка на код может выдавать старый вариант кода, где [latex]a[/latex] и [latex]b[/latex] считаются отдельно, а не [latex]b[/latex] выражается через [latex]a[/latex], как в этом коде, в связи с техническими проблемами на ideone. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным.

Станислав Коциевский

www.e-olymp.com/en/users/restaver

Mif4

30/09/2015 by Алина Гончарова

Задача

Даны действительные числа $x$ , $y$ , $z$ . Проверить, выполняются ли неравенства $x < y < z$ .

Решение

Нам даны действительные числа $x$ , $y$ , $z$ и нужно проверить выполняются ли неравенства $x < y < z$ . Для этого нам нужно проверить будут ли выполняться такие неравенства: [latex] x<y[/latex] и [latex] y<z [/latex].

Код

#include <iostream>
using namespace std;

int main() {
    double x, y, z;
    cin >> x >> y >>z;
    if (x<y && y<z){
        cout << "right";
    }
    else {
        cout << "wrong";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y, z;

cin >> x >> y >>z;

if (x<y && y<z){

cout << "right";

}

else {

cout << "wrong";

}

return 0;

}

Тесты

Входные данные	Выходные данные
3 4 6	right
9 1 3	wrong
5 4 3	wrong

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

Здесь можно найти код программы на Ideone.com.

Алина Гончарова

ML12

23/09/2015 by Катя Писова

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

Даны [latex]x,y,z[/latex]. Вычислить [latex] a = x \arctan{y} — e^{1-z}[/latex] и [latex] b = \frac{\sqrt{\left|3-x^2 \right|}- \sqrt[3]{\left|y-x \right|}}{1-\frac{x^2}{2}+\frac{y^2}{4}-\frac{z^2}{8}}.[/latex]

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

1)В условии задачи не указано какие должны быть числа [latex]x,y,z[/latex] , поэтому правильнее всего использовать диапазон long double, чтобы включить как можно больше значений.

2)Подключим библиотеку <cmath> , с помощью которой подключим математические функции и, придерживаясь правил порядка вычислений, расставим скобки.

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    long double x, y, z;
    cin>>x>>y>>z;
    long double a, b;
    a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера 
    b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);
    cout<<a<<endl;
    cout<<b<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long double x, y, z;

cin>>x>>y>>z;

long double a, b;

a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера

b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);

cout<<a<<endl;

cout<<b<<endl;

return 0;

}

Тесты:

Ввод:	#	Вывод:	#
x	1	a	0.971813
y	2	b	1.10457
z	3

Ввод:	#	Вывод:	#
x	-9	a	-16.1645
y	13	b	2.19263
z	0

Ввод:	#	Вывод:	#
x	7	a	10.361
y	11	b	-0.107389
z	21

Здесь находится код в ideone.com

Катя Писова

ML4

23/09/2015 by Алина Гончарова

Задача:
Даны два действительных положительных числа. Найти среднее арифметическое и среднее геометрическое этих чисел.

Решение:

Так как нам в задаче не указано какими будут числа по длинне, мы используем тип данных long double, который поможет охватить весь их диапозон.

Для того, чтобы найти среднее арифметическое чисел нам нужно воспользоваться формулой [latex]A=\frac{x_1+x_2+ \ldots +x_n}{n}[/latex] , но так как у нас задано всего два числа, будем пользоваться этой формулой: [latex]A=\frac{a+b}{2}[/latex]

Среднее геометрическое вычисляется по формуле :[latex]G=\sqrt[n]{x_1+x_2+ \ldots +x_n}[/latex] , но нам понадобиться формула только для двух чисел: [latex]G=\sqrt{a\cdot b }[/latex]

Тесты:

№	Входные данные	Выходные данные
1.	-1 -3	-2 1.73205
2.	5 6	5.5 5,47723
3.	4 6	5 4.89898
4.	100 2.6	51.3 16.1245

Код:

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

 int main() {
	long double a, b;
        cin >> a >> b;
        cout << (a+b)/2 << endl; //вычисляем среднее арифметическое чисел
        cout << sqrt(a*b) << endl; //вычисляем среднее геометрическое чисел
	return 0;
}