e-olymp 481. И опять: сколько можно?

24/12/2017 by Алиса Ворохта

Задача

Задано натуральное число [latex]N[/latex]. От данного числа вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. Данную операцию будем продолжать до тех пор, пока полученное число положительно. Сколько раз будем выполнять данную операцию?

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

Во входной строке находится число [latex]N[/latex], которое не превышает [latex]2147483647[/latex].

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

Количество выполненных операций.

Тесты

Входные данные	Выходные данные
[latex]23[/latex]	[latex]3[/latex]
[latex]55555[/latex]	[latex]3000[/latex]
[latex]1234567[/latex]	[latex]49877[/latex]
[latex]999999999[/latex]	[latex]25632473[/latex]
[latex]2147483647[/latex]	[latex]54682584[/latex]

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

#include <iostream>
using namespace std;
 
int main()
{
    unsigned long long N, sum, subsidiary = 0, quantity = 0;
    cin >> N;
    while (N > 999999999)
    {
        sum = 0;
        subsidiary = N;
        while (subsidiary!=0)
        {
            sum += subsidiary%10;
            subsidiary /= 10;
         }
         N -= sum;
         quantity++;
    }
    if (N == 999999999)
    {
        N = 0;
        quantity += 25632473;
    }
    while (N > 0)
    {
        sum = 0;
        subsidiary = N;
        while (subsidiary != 0)
        {
            sum += subsidiary%10;
            subsidiary /= 10;
         }
         N -= sum;
         quantity++;
    }
    cout << quantity << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long N, sum, subsidiary = 0, quantity = 0;

cin >> N;

while (N > 999999999)

{

sum = 0;

subsidiary = N;

while (subsidiary!=0)

{

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

if (N == 999999999)

{

N = 0;

quantity += 25632473;

}

while (N > 0)

{

sum = 0;

subsidiary = N;

while (subsidiary != 0)

{

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

cout << quantity << endl;

return 0;

}

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

Данную задачу можно решить, вычитая от данного числа [latex]N[/latex] суммы цифр, пока само число не станет равным [latex]0[/latex], с помощью циклов. Но этого нам не позволяет ограничение по времени.
Поэтому мы найдем максимально возможное число, которое мы можем получить при вычитании из больших чисел сумм цифр и которое проходит по времени. Это число — [latex]999999999[/latex] (найдено экспериментальным путем). Из него необходимо вычесть суммы цифр [latex]25632473[/latex] раз, чтобы получился [latex]0[/latex].
Тогда из чисел, которые больше данного, достаточно вычитать суммы цифр, пока они не станут равными [latex]999999999[/latex] и прибавить к количеству вычитаний [latex]25632473[/latex].
Если [latex]N[/latex] меньше найденного нами числа, то можно из него просто вычитать суммы цифр, пока оно не станет равным [latex]0[/latex].

Ссылки

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

Related Images:

А329. Квадрат суммы цифр числа

13/11/2016 by Тимур Фирсов

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа [latex]n[/latex], [latex]m[/latex]. Получить все меньшие [latex]n[/latex] натуральные числа, квадрат суммы цифр которых равен [latex]m[/latex].

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

Два положительных числа [latex]n[/latex] и [latex]m[/latex].

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

Все целые числа из [latex]\left( 0,n \right)[/latex], удовлетворяющие условию.

Тесты

№	Входные данные		Выходные данные
№	[latex]n[/latex]	[latex]m[/latex]
1	1234	9	3 12 21 30 102 111 120 201 210 300 1002 1011 1020 1101 1110 1200
2	100	4	2 11 20
3	49	49	7 16 25 34 43
4	1000	1	1 10 100

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

#include <iostream>
using namespace std;

int main() {
    unsigned n, m, t, sum, i=1;
    cin>>n>>m;
    for(i;i<n;i++){
        t=i;
        sum=0;
        while(t!=0){
            sum+=t%10;
            t/=10;
        }
        if(sum*sum==m)cout<<i<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, m, t, sum, i=1;

cin>>n>>m;

for(i;i<n;i++){

t=i;

sum=0;

while(t!=0){

sum+=t%10;

t/=10;

}

if(sum*sum==m)cout<<i<<" ";

}

return 0;

}

Решение

Для того, чтоб найти каждую цифру числа будем искать остаток от деления на [latex]10[/latex], которым является последняя цифра числа, а затем делить число нацело на [latex]10[/latex], чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно [latex]0[/latex]. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от [latex]1[/latex] до [latex]n-1[/latex], параллельно возводя полученную сумму в квадрат, а результат сравнивая с [latex]m[/latex].

Ссылки

Код программы.
Условие задачи (страница 135).

Related Images:

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

10/11/2015 by Антон Локтев

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

Сколько натуральных чисел из промежутка [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

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

#include <iostream>
using namespace std;

int sumOfDigits(int a){
	int sum = 0;
	while (a > 0){
		sum += a%10;
		a /= 10;
	}
	return sum;
}

int main() {
	int m, n, sumMin, counter = 1;
	cin >> m >> n;
	sumMin = sumOfDigits(m);
	for(int i = m + 1; i <= n; i++){
		if (sumOfDigits(i) < sumMin){
			sumMin = sumOfDigits(i);
			counter = 1;
		}
		else if (sumOfDigits(i) == sumMin)   
		    counter++;
	}
	cout << counter;
	return 0;
}

#include <iostream>

using namespace std;

int sumOfDigits(int a){

int sum = 0;

while (a > 0){

sum += a%10;

a /= 10;

}

return sum;

}

int main() {

int m, n, sumMin, counter = 1;

cin >> m >> n;

sumMin = sumOfDigits(m);

for(int i = m + 1; i <= n; i++){

if (sumOfDigits(i) < sumMin){

sumMin = sumOfDigits(i);

counter = 1;

}

else if (sumOfDigits(i) == sumMin)

counter++;

}

cout << counter;

return 0;

}

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

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

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

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

Related Images:

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. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным.

Related Images:

e-olymp 7338. Постоянная сумма цифр

30/09/2015 by Максим Носов

Задача

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

В единственной строке задано целое одно цифровое число.

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

Количество чисел.

Код

#include <iostream>
using namespace std;

int main() {
    int n,a,b,c,k=0;  // задаем переменные
    cin>>n; //вводим число, на которое будут умножаться все двухзначные числа
    for (int i=10;i<=99;i++) {  //задаем цикл от 10 до 99(все двухзначные числа)
        c=i*n;  //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового
        a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа
        b=(c/10)%10+c%10+c/100;   // и вычисляем сумму цифр числа с
        if (a==b) k++;  //если  суммы чисел а и с равны то добавляем 1 на "счетчик"
    }
    cout<<k;  //выводим на экран количество чисел 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a,b,c,k=0; // задаем переменные

cin>>n; //вводим число, на которое будут умножаться все двухзначные числа

for (int i=10;i<=99;i++) { //задаем цикл от 10 до 99(все двухзначные числа)

c=i*n; //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового

a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа

b=(c/10)%10+c%10+c/100; // и вычисляем сумму цифр числа с

if (a==b) k++; //если суммы чисел а и с равны то добавляем 1 на "счетчик"

}

cout<<k; //выводим на экран количество чисел

return 0;

}

Тесты

№	Входные данные	Выходные данные
1	2	10
2	0	0
3	1	90
4	9	6
5	5	10

Решение

Для начала задаем переменные и вводим с клавиатуры число, на которое будут умножаться все двухзначные числа. Задаем цикл от 10 до 99. Для удобства вводим переменную [latex]c[/latex], которая равна произведению двухзначного числа на входное число и переменную [latex]a[/latex], которая равна сумме цифр входного числа. Далее находим сумму цифр числа с — [latex](c/10)%10+c%10+c/100[/latex]. Если сумма цифр входного числа равна сумме цифр [latex]c[/latex], то добавляем 1 на «счетчик». В конце выводим на экран количество чисел, которые не меняют свою сумму цифр при умножении на число, которое мы ввели с клавиатуры.

Ссылку на код здесь.

Задача взята с сайта.

Related Images:

e-olymp 128. Счастливые билеты

21/09/2015 by Женя Максимова

Задача. Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

Тесты

Число [latex]N[/latex]	3	27	26	1	10
Количество билетов	100	1	9	9	3969

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

#include <iostream>
using namespace std;
int main() 
{
  int N, c = 0;
  cin >> N;
  for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  {
     for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     {
        if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры
        { c++; } //подсчет подходящих номеров
     }
  }
  cout << c*c; //увеличение количества в c раз для шестизначного числа
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N, c = 0;

cin >> N;

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры

{ c++; } //подсчет подходящих номеров

}

cout << c*c; //увеличение количества в c раз для шестизначного числа

return 0;

}

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

Рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух вложенных циклов. Для третьей цифры введем специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], а также быть именно цифрой, то есть меньшей 10.

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

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