Python

Помогите пожалуйста решить задачу по программированию наpython.

Одиндватри
Рассмотрим последовательность натуральных чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , …Перевернем в ней каждое число. Получим последовательность: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 01 , 11 , 21 , 31 , 41 , …Запишем полученную последовательность слитно в виде одной строки: 1234567890111213141... Напишите программу, которая выводит n-ую цифру полученной строки. Формат входных данных На вход программе подается натуральное число n, где 1 ⩽ n⩽ 10^50. Формат выходных данных Программа должна вывести n-ую цифру строки, представленной в условии задачи. Примечание. Тестовые данные доступны по ссылке.
Роман Рябуха
Роман Рябуха
104
Сейчас какой-нибудь очередной гений быдлокодинга тут напишет программу, которая крутит цикл от одного до 10⁵⁰, перебирая цифры. :-)

В общем, если это нормально решать, то нужно сформировать диапазоны цифр:
 #     1 - 9       1-значные, 9 шт

#    10 - 189     2-значные, 90 шт, 180 знаков

#   190 - 2889    3-значные, 900 шт, 2700 знаков

#  2890 - 38889   4-значные, 9000 шт, 36000 знаков

# 38890 - 488889  5-значные, 90000 шт, 450000 знаков
Каждый диапазон k-значных чисел содержит
 d(k) = k ∙ 9 ∙ 10ᵏ⁻¹ знаков
А позиции его начала и конца (p, q) можно рассчитать как
 p(k) = ∑(1; k-1) d(k) + 1

q(k) = p(k) + d(k) - 1

p(1) = 1

Учитывая, что d(k) > 10ᵏ , наша сумма дорастёт до 10⁵⁰ не более, чем на 50-значных числах.

Также учитываем, что индексация в Питоне делается с нуля, поэтому индексы подправляем, где надо.
 p(k) = ∑(1; k-1) d(k)

q(k) = p(k) + d(k) - 2

p(1) = 0

А как только мы оказались внутри диапазона k-значных чисел, нам нужно найти, какое именно это число (m), и какая по счёту цифра (f) в нём нам досталась.
 m = (n - 1 - p(k)) // k + 10ᵏ⁻¹

f = (n - 1 - p(k)) % k + 1
Значение цифры - это
 m // 10ᶠ⁻¹ % 10
(в обратной записи младшая цифра стоит на позиции 1, десятки - на позиции 2, последняя - на позиции k)

Вот таким кодом этого можно достичь:
 import bisect



K = 50 # максимальная допустимая разрядность



# Предварительно вычисляем величины для каждой разрядности

# индекс [0] соответствует разрядности 1

tens = [1]

d = [9]

p = [0]

q = [d[0] - 1]

for k in range(1, K + 1):

    tens.append(tens[k - 1] * 10)

    d.append((k + 1) * 9 * tens[k])

    p.append(q[k - 1] + 1)

    q.append(p[k] + d[k])



n = int(input())

if n > 1e50:

    print('Слишком большое число')

    exit(1)



# Находим порядок числа, т.е. кол-во цифр в нём

o = bisect.bisect_right(p, n)



# Находим само число и номер цифры в нём, извлекаем цифру

inside = n - p[o]

m = inside // o  + tens[o]

f = inside % o

print(m // tens[f] % 10)
Жангелди Усенов
Жангелди Усенов
54 053
Лучший ответ 
 n, e, i = int(input()) - 1, 1, 1

while n >= 9 * i * e:

  n -= 9 * i * e

  e *= 10

  i += 1

print(str(e + n // i)[-1 - n % i])
Для любого n > 0 - не только n ≤ 10⁵⁰

Да, идея та же самая, что и у Реципиента - разбиение на диапазоны по кол-ву цифр в числе. Но с последовательным перебором диапазонов и без формирования вспомогательных массивов: просто отнимаем длину каждого неподошедшего диапазона от n - пока n не окажется внутри очередного диапазона.
Андрей Буруяна
Андрей Буруяна
87 741
Владислав Новиков Ну, мне ж надо построить движок, чтоб эти числа миллионами молотил, иначе остаётся ощущение какой-то неполноты. :-)
А тогда - никаких str (98 делений для 50-значного числа, а достаточно 2-х), а раз нет str, то нужны степени 10 прекалькулированные. И bisect на заранее посчитанных границах 50 интервалов - всяко быстрее, чем интервалы перебирать линейно.
И для пущей быстроты можно было всё это ещё в 64-битный numpy забить. 
 s,i,n= "",1,int(input()) 

while len(s)
Алексей Попков
Алексей Попков
3 436
Андрей Буруяна А теперь попробуй в своей программе ввести число
100000000000000000000000000000000000000000000000000
которое - по условиям задачи - программа должна правильно обрабатывать.
Жангелди Усенов Я был прав в первой фразе своего ответа.

Похожие вопросы