Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/8: Рейтинг темы: голосов - 8, средняя оценка - 5.00
5 / 5 / 0
Регистрация: 06.09.2022
Сообщений: 31

Определить сколькими способами можно восстановить изначальную надпись

06.09.2022, 15:59. Показов 1836. Ответов 18
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Антипа наткнулся на брошенную кем-то книгу. Не сумев сдержать своего любопытства, он подобрал её и начал медленно пролистывать.

К огромному сожалению Антипы, все страницы, кроме одной, были выдраны, а оставшаяся страница не подлежала восстановлению. Однако тщательно присмотревшись, Антипа смог разглядеть, что кое-что всё-таки смогло уцелеть — внизу была крошечная надпись: «Страница kn».

Антипа догадался, что надпись изначально представляла собой строку «Страница k из n», как это часто бывает в книгах, но под воздействием времени «из» исчезло, а числа слились в одну строку. Точно установить, сколько изначально было страниц, стало решительно невозможно, вариантов может быть очень много.

Антипа всегда был любопытной натурой, и ему стало интересно, сколько всего существует вариантов того, какая изначально надпись была на этой странице. В этом ему понадобится ваша помощь.

Входные данные:
Первая строка содержит строку s, состоящую из N цифр. Страницы книги нумеруются от 1 до n, числа k и n записываются без ведущих нулей (1≤N≤200000).



Выходные данные:
Помогите Антипе найти количество корректных надписей вида «Страница k из n», при удалении из которых всех символов кроме цифр получается заданная во входном файле строка.



Примеры:
входные данные
14609655
выходные данные
3
входные данные
1
выходные данные
0


Примечание:
В первом примере существует только три варианта:

«Страница 1 из 4609655»
«Страница 14 из 609655»
«Страница 1460 из 9655»

Добавлено через 35 секунд
только ненадо файловый вход и выход, вход и выход обычный
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
06.09.2022, 15:59
Ответы с готовыми решениями:

Определить сколькими способами можно разместить здание биржи
Поле для игры Петя создает поле для своей новой игры. Поле разделено на клетки и представляет собой прямоугольник размером N на M клеток....

Определить сколькими способами можно купить ровно n пирожных
Пирожные Для праздничного чаепития необходимо купить n пирожных. В магазине продается всего два вида пирожных, причем пирожных одного...

Определить, сколькими способами можно разменять купюру
Очень срочно нужна программа!!!Задание задано по дискретной математике, а точнее по комбинаторике: Реализовать программу для решения задачи...

18
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38189 / 21124 / 4307
Регистрация: 12.02.2012
Сообщений: 34,731
Записей в блоге: 14
06.09.2022, 16:22
Цитата Сообщение от turhojoba Посмотреть сообщение
он подобрал её и начал медленно пролистывать
Цитата Сообщение от turhojoba Посмотреть сообщение
все страницы, кроме одной, были выдраны
- что же он пролистывал, болезный?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n=int(input())
 
s=str(n)
ls=len(s)
c=0
for i in range(1,ls):
    h=s[0:i]
    t=s[i:]
    if int(t) >= int(h):
        c+=1
    else:
        break
print(c)
2
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
06.09.2022, 16:58
Тут у тебя на 1 тесте облом, там только 3 варианта
не может быть
146 из 09655 страниц

Добавлено через 15 минут
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
s = str(n)
ls = len(s)
c = 0
for i in range(1, ls):
    h = s[0:i]
    t = s[i:]
    if str(str(h)[-1]) == 0 or str(str(h)[-1]) == "0":
        c = c - 1
    if int(t) >= int(h):
        c += 1
    else:
        break
print(c)
Добавлено через 8 секунд
можно так попробовать
0
5 / 5 / 0
Регистрация: 06.09.2022
Сообщений: 31
06.09.2022, 20:08  [ТС]
Нет, слишком долго выполняется не проходит по времени

Добавлено через 1 минуту
Просто если число 200000значное, как в условии задачи, то не проходит естественно

Добавлено через 29 минут
надо подумать как уменьшить время работы программы

Добавлено через 19 минут
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
s = str(n)
ls = len(s)
c = 0
if ls % 2 != 0:
    ls = ls - 1
c = ls / 2
a = str(n)
b = (a.count('0'))
d = round(c - b)
if d < 0:
    d = 0
print(d)
Я попробовал так, но пишет неправильный ответ где-то

Добавлено через 2 часа 18 минут
Catstail там по времени не проходит
2 сек 256 мб ограничено
1
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
07.09.2022, 01:57
Добавил недостающее условие в код Catstail
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
 
s = str(n)
ls = len(s)
c = 0
for i in range(1, ls):
    h = s[0:i]
    t = s[i:]
    if t[0] == '0':
        continue
    if int(t) >= int(h):
        c += 1
    else:
        break
print(c)
2
5 / 5 / 0
Регистрация: 06.09.2022
Сообщений: 31
07.09.2022, 08:24  [ТС]
Code
1
Превышено ограничение времени на тесте 32
Добавлено через 18 минут
Просто там может быть число от 1 значного до 200000-значного. и в 32 тесте именно 200000-значное число(ну максимум из условия задачи) такое за 1.5 сек программа не решает
1
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
07.09.2022, 12:08
Python
1
2
3
4
5
6
7
8
9
# n = input()
n = '73402748237480' * 20000
res = 0
if len(n) > 1:
    middle = len(n) // 2
    while int(n[:middle]) > int(n[middle:]) or n[middle] == '0':
        middle -= 1
    res = len(n[:middle]) - n[:middle].count('0')
print(res)
Добавлено через 1 час 29 минут
Так лучше, но все равно могут быть ошибки.
Python
1
2
3
4
5
6
7
8
9
# n = input()
n = '1' + '0' * 200000 + '1'
res = 0
if len(n) > 1:
    middle = len(n) // 2
    while (n[middle] == '0' or int(n[:middle]) > int(n[middle:])) and middle > 1:
        middle -= 1
    res = len(n[:middle]) - n[:middle].count('0')
print(res)
0
4 / 6 / 1
Регистрация: 16.04.2022
Сообщений: 139
07.09.2022, 13:09
Не, тут тоже не то
При тесте "97" не работает

пишет 1
но не может быть 9 из 7 страниц
0
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
07.09.2022, 13:35
Python
1
2
3
4
5
6
7
8
9
10
11
12
# n = input()
# n = '1' + '0' * 20 + '1'
n = '97'
res = 0
if len(n) == 2 and int(n[0]) <= int(n[1]):
    res = 1
elif len(n) > 2:
    middle = len(n) // 2
    while (n[middle] == '0' or int(n[:middle]) > int(n[middle:])) and middle > 1:
        middle -= 1
    res = len(n[:middle]) - n[:middle].count('0')
print(res)
0
4 / 6 / 1
Регистрация: 16.04.2022
Сообщений: 139
07.09.2022, 15:29
Кстати тут тоже неточность
10015 - n
то выведет 1
Но при "10015" вообще 0 вариантов
не может быть 1 из 0015 или 100 из 15 или 10 из 015
0
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
07.09.2022, 16:09
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def f(s):
    ls = len(s)
    c = 0
    for i in range(1, ls):
        h = s[0:i]
        t = s[i:]
        if t[0] == '0':
            continue
        if int(t) >= int(h):
            c += 1
        else:
            break
    return c
 
 
# n = input()
# n = '1' + '0' * 200000 + '1'
arr = [str(i) for i in range(10000, 100000)]
 
for n in arr:
    res = 0
    if len(n) > 1:
        middle = len(n) // 2
        while n[middle] == '0' or middle > 0 and int(n[:middle]) > int(n[middle:]):
            middle -= 1
        res = len(n[:middle]) - n[:middle].count('0')
    print(res)
 
    expected = f(n)
    assert res == expected, f'{res} != {expected} (Не совпало на числе: {n})'
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
07.09.2022, 17:13
Alexarh, а зачем int в цикле? это уже не линейный алгоритм.
Python
1
2
3
4
5
6
7
8
9
10
11
12
s = input()
n = len(s)
count = 0
i = 1
while i < n - i:
    if s[i] != '0':
        count += 1
    i += 1
if n % 2 == 0:
    if int(s[:i]) <= int(s[i:]):
        count += 1
print(count)
или я не понял задачу
1
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
07.09.2022, 18:40
eaa, преобразование к int там сработает 1 раз (может 2, но небольше). Основное первое условие в цикле
Python
1
while n[middle] == '0'
, чтобы начальные "0" у второй части отсеять. Это если про вторую часть говорить, где основное решение:
Python
1
2
3
4
5
6
7
8
n = input()
res = 0
if len(n) > 1:
    middle = len(n) // 2
    while n[middle] == '0' or middle > 0 and int(n[:middle]) > int(n[middle:]):
        middle -= 1
    res = len(n[:middle]) - n[:middle].count('0')
print(res)
Функцию выше я для тестирования взял, чтобы результат сравнить.
А так да, как-то у вас более читаемое решение.
0
0 / 0 / 0
Регистрация: 08.09.2022
Сообщений: 3
08.09.2022, 12:02
ошибка на тесте 68
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
08.09.2022, 12:16
Цитата Сообщение от sugiuao Посмотреть сообщение
ошибка на тесте 68
ты это кому?
0
5 / 5 / 0
Регистрация: 06.09.2022
Сообщений: 31
08.09.2022, 20:50  [ТС]
delete
0
5 / 5 / 0
Регистрация: 06.09.2022
Сообщений: 31
09.09.2022, 21:51  [ТС]
Вообщем так и не получилось сдать
какая-то ошибка непонятная
0
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
09.09.2022, 22:04
turhojoba, а где сдаешь? Скинь ссылку, если там всем можно порешать задания.
0
09.09.2022, 22:16  [ТС]

Не по теме:

https://itmo.contest.codeforces.com/group/q7pRVvtbsf/contest/397259
задача 1E

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
09.09.2022, 22:16
Помогаю со студенческими работами здесь

Определить сколькими способами можно подняться по лестнице ?
Подскажите пожалуйста записать данную логику. Мне нужно определить сколькими способами можно подняться по лестнице, есть к примеру такая...

Определить, сколькими способами можно выдать сдачу в n рублей
Ребят помогите нарушен предел времени пишет и тест до конца не принимает. Где нужно исправить укажите Имеется неограниченное...

Определить, сколькими способами можно разложить 9 книг в 4 бандероли
Ребята нужна помощь. Не знаю как запрограммировать. Напишите код, буду весьма благодарен. Задача по теории вероятности. Сколькими...

Определить сколькими различными способами можно подняться на десятую ступеньку
Определить сколькими различными способами можно подняться на десятую ступеньку, если за шаг можно подняться следующую или через одну. ...

Определить, сколькими способами можно заменить знаки вопроса круглыми скобками
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru