Подразделы

Другие разделы

Дата и время

28/03/2024 17:06:01

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи 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.
loading