Начало
Соревнования
Разбор задачи C. Номер страницы
Тема: полный перебор, сравнение длинных целых чиселСложность: простая
В задаче нужно найти число способов разбить строку из цифр длиной `l` (`1\ ≤\ l\ ≤\ 200\ 000`) на две непустые подстроки так, чтобы ни одна подстрока не начиналась с 0 и число, соответствующее первой подстроке, было меньше или равно числу, соответствующего второй подстроке.
Число `x` меньше или равно числу `y`, если в числе `x` меньше цифр, чем в числе `y` или – при равенстве количества цифр – строка из цифр числа `x` лексикографически меньше или равна строке из цифр числа `y`.
Достаточно проверить указанные условия для вариантов длины `m` первой подстроки от 1 до `l/2`. Вторая подстрока будет иметь длину `l-m` и начинаться с символа `m+1`.
var s:string;
m,l,k:integer;
begin
readln(s);
k:=0;
l:=length(s);
for m:=1 to l div 2 do
if (s[1]<>'0') and (s[m+1]<>'0') and
((m<l-m) or (copy(s,1,m)<=copy(s,m+1,l-m))) then
inc(k);
writeln(k);
end.
