Задача "Магическая математика"

@VitaMinka · Регистрация: 05.06.2020

Студворк — интернет-сервис помощи студентам

В царстве фей все немного отличается от царства людей. Так, в начальной школе феи изучают магическую математику. Ее основное отличие от обычной математики в том, что числа в ней упорядочены не по возрастанию, а лексикографически, то есть как в словаре (сначала по первой цифре, затем, при равной первой цифре – по второй, и так далее). Кроме того, рассматривается не бесконечное множество натуральных чисел, а лишь первые n чисел. Так, например, если n=11, то числа в магической математике оказываются упорядоченными следующим образом: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9. Помогите ученикам в изучении этой науки – напишите программу, которая по заданному n находит место заданного числа k в порядке, определенном в странной математике. Например, если n=11 и k=2, программа должна выдать в качестве ответа 4.

Формат ввода
Первая строка входных данных содержит натуральное число n, 1 ≤ n ≤ 10¹⁰. Вторая строка входных данных содержит натуральное число k, 1 ≤ k ≤ n.

Формат вывода
Программа должна вывести единственное натуральное число – номер числа k среди первых n натуральных чисел в лексикографическом порядке.

Пример 1:
Ввод:
54
28
Вывод:
21

Пример 2:
Ввод:
335454
45878
Вывод:
275321

@avdivo · 22.03.2022, 23:20

VitaMinka,

Python
1
print(sorted(range(1, int(input()) + 1), key=str).index(int(input()) + 1))

@VitaMinka · 23.03.2022, 02:14 **[ТС]**

На первых двух примерах у меня работает код:

n = int(input())
k = input()

nums = [str(i) for i in range(1, n+1)]
nums.sort()

pos = nums.index(k)+1

print(pos)

А на третьем(ниже) пишет "Превышен лимит использования памяти"
Ввод:
1000000000
1000000000
Вывод:
10

Добавлено через 51 секунду
С вашим кодом работают только первые два примера

Добавлено через 2 минуты
avdivo, но все равно большое спасибо, что откликнулись

@idealist · 23.03.2022, 07:30

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
31
32
33
34
35
def add_prev( n_str, k_str ):
    #==========================================================================
    def count_added_strings( str_len, n_str, k_str ):
        num_beg = 10 ** (str_len - 1)
        num_end = int(k_str) * 10 ** ( str_len - len(k_str) ) - 1
        if str_len == len(n_str):
            num_end = min( num_end, int(n_str) )
        return num_end - num_beg + 1
    # =========================================================================
    res = 0
    for str_len in range( len(k_str)+1, len(n_str)+1 ):
        res += count_added_strings( str_len, n_str, k_str )
    return res
#==============================================================================
def remove_prev( k_str ):
    #==========================================================================
    def count_deleted_strings_with_k_dig( k_str ):
        res = 0
        for str_len in range( 2, len(k_str) ):
            res += ( int( k_str[0] ) + 1 ) * 10**(str_len-1) - 1 - int( k_str[:str_len] )
        return res
    # ==========================================================================
    def count_deleted_strings_with_digits_greater( k_str ):
        if len(k_str) == 1:
            return 0
        return ( 9 - int( k_str[0] ) ) * int( '1'* ( len(k_str)-1 ) )
    # ==========================================================================
    res = 0
    res += count_deleted_strings_with_k_dig( k_str )
    res += count_deleted_strings_with_digits_greater( k_str )
    return res
#==============================================================================
n_str = input('n = ')
k_str = input('k = ')
print( int(k_str) + add_prev( n_str, k_str ) - remove_prev( k_str ) )

Добавлено через 1 минуту
Результат работы:

Python
1
2
3
n = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
k = 444444444444444444444444444444444444444444444444444444
3827160493827160493827160493827160493827160493827160488888888888888888888888888888888888888888888919

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .

@VitaMinka 0 / 0 / 0 Регистрация: 05.06.2020 Сообщений: 10

	Задача "Магическая математика" 22.03.2022, 16:28. Показов 2350. Ответов 3 Метки python 3.7 (Все метки) В царстве фей все немного отличается от царства людей. Так, в начальной школе феи изучают магическую математику. Ее основное отличие от обычной математики в том, что числа в ней упорядочены не по возрастанию, а лексикографически, то есть как в словаре (сначала по первой цифре, затем, при равной первой цифре – по второй, и так далее). Кроме того, рассматривается не бесконечное множество натуральных чисел, а лишь первые n чисел. Так, например, если n=11, то числа в магической математике оказываются упорядоченными следующим образом: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9. Помогите ученикам в изучении этой науки – напишите программу, которая по заданному n находит место заданного числа k в порядке, определенном в странной математике. Например, если n=11 и k=2, программа должна выдать в качестве ответа 4. Формат ввода Первая строка входных данных содержит натуральное число n, 1 ≤ n ≤ 10¹⁰. Вторая строка входных данных содержит натуральное число k, 1 ≤ k ≤ n. Формат вывода Программа должна вывести единственное натуральное число – номер числа k среди первых n натуральных чисел в лексикографическом порядке. Пример 1: Ввод: 54 28 Вывод: 21 Пример 2: Ввод: 335454 45878 Вывод: 275321 0

@VitaMinka 0 / 0 / 0 Регистрация: 05.06.2020 Сообщений: 10
	23.03.2022, 02:14 [ТС]
	На первых двух примерах у меня работает код: n = int(input()) k = input() nums = [str(i) for i in range(1, n+1)] nums.sort() pos = nums.index(k)+1 print(pos) А на третьем(ниже) пишет "Превышен лимит использования памяти" Ввод: 1000000000 1000000000 Вывод: 10 Добавлено через 51 секунду С вашим кодом работают только первые два примера Добавлено через 2 минуты avdivo, но все равно большое спасибо, что откликнулись 0

Задача "Магическая математика"

Решение