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

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

06.09.2022, 15:59. Показов 1806. Ответов 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
38161 / 21096 / 4306
Регистрация: 12.02.2012
Сообщений: 34,683
Записей в блоге: 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
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru