Решение задачи Странное округление с Codeforces

С пояснением   Просмотров: 29


Поликарп без ума от круглых чисел. Особенно ему нравятся числа, которые делятся на 10 k.

В заданном числе n Поликарп хочет удалить наименьшее количество цифр, чтобы получилось число, которое делится на 10 k. Например, если k = 3, то в числе 30020 достаточно удалить одну цифру (цифру 2). В таком случае результат будет равен 3000, что делится на 103 = 1000.

Напишите программу, которая выведет минимальное количество цифр, которые надо удалить из числа n, чтобы результат делился на 10 k. Результат не должен начинаться с ненужного лидирующего нуля (то есть с нуля может начинаться только число 0, которое обязано быть записано ровно одной цифрой).

Гарантируется, что ответ существует.

Код

#include <cstdio>
using namespace std;
int main() {
	int k,cnt=0,l,cnt2=0; char s[15];
	scanf("%s%d",s,&k);
	for (l=0;s[l];l++)
		cnt+=s[l]=='0';
	if (cnt<k) cnt2=l-1;
	else while (k)
		if (s[--l]=='0') k--;
		else cnt2++;
	printf("%d\n",cnt2);
}

         

Администратор Photo Автор: Администратор


Для решения данной задачи нам нужно добиться того, чтобы в числе n в конце было k нулей, а перед ними хотя бы одна ненулевая цифра. Будем рассматривать число n как строку и пройдем по ней, начиная с конца (то есть с самого младшего разряда). Пусть cnt равно количеству цифр, которые мы уже рассмотрели. Если очередной символ строки не равен нулю, увеличим ответ на единицу. Если cnt стало равно k и мы рассмотрели не все цифры в строке n — выводим ответ.

В противном случае, нужно удалить из строки все символы, кроме одного, который равен нулю (если таковых несколько, то нужно оставить ровно один из них). Таковой символ обязательно найдется, так как гарантируется, что ответ существует.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться