Определить количество натуральных чисел, не больше N, в десятичной записи которых нет тройки - C (СИ)
Формулировка задачи:
Имя входного файла: new_game2.in
Имя выходного файла: new_game2.out
Ограничение времени: 100 мс
Ограничение памяти: 128 M
Після гри зі словами Степан вирішив придумати ще й гру з цифрами. До того ж не з усіма - а тільки з трійкою.
Задано натуральне число N. Необхідно визначити кількість натуральних чисел, не більших за N, у десятковому запису яких немає трійки.
Допоможіть Степану - напишіть програму яка вирішить його проблему.
Формат вхідних даних:
У вхідному файлі знаходиться одне натуральне число N (1 ≤ N ≤ 1018).
Формат вихідних даних:
Вихідний файл має містити одне число – відповідь на поставлену задачу.
Решение задачи: «Определить количество натуральных чисел, не больше N, в десятичной записи которых нет тройки»
textual
Листинг программы
#include <stdio.h>
#include <math.h>
int hasThree(_int64 num)
{ while(num>0)
{ if(num % 10 == 3)
return 1;
num /= 10;
}
return 0;
}
_int64 pow9(int p)
{ _int64 res = 1;
while(p-- > 0)
res *= 9;
return res;
}
_int64 pow10(int p)
{ _int64 res = 1;
while(p-- > 0)
res *= 10;
return res;
}
int main()
{ unsigned _int64 N, i, count;
int len;
scanf("%I64u", &N);
len = (int) log10(N*1.);
for(i = pow10(len), count = pow9(len) - 1; i<=N; i++)
if(!hasThree(i))
count++;
printf("%I64u",count);
getchar();getchar();
return 0;
}