Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/25: Рейтинг темы: голосов - 25, средняя оценка - 5.00
7 / 7 / 7
Регистрация: 20.06.2016
Сообщений: 72
1

Создание массива на 10**18 элементов (cannot fit 'int' into an index-sized integer)

26.10.2017, 22:54. Показов 5147. Ответов 12
Метки нет (Все метки)

Приветствую. Решаю олимпиадную задачу, где вводятся числа 1 <= K <= N <= 10**18. Проблема в том, что мне нужно как-то создать список на 10**18 значений, заполненный нулями. Если ввести число, больше стандартного int вылетает ошибка. Что можно сделать в данном случае? Крашится на третьей строчке.
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
36
37
38
39
40
41
42
43
44
45
46
n = int(input())
k = int(input())
a = [0] * n
maximum = 0
end_ind = 0
current = 0
last_ind = 0
left = 0
right = 0
for i in range(k):
    maximum = 0
    end_ind = 0
    current = 0
    for j in range(n):
        if a[j] == 1:
            if current >= maximum:
                maximum = current
                end_ind = j - 1
            current = 0    
        elif j == n - 1:
            if current + 1 >= maximum:
                maximum = current + 1
                end_ind = j
        else:
            current += 1
 
    last_ind = end_ind - maximum // 2
    a[last_ind] = 1
    
left = last_ind - 1
right = last_ind + 1
while a[right] != 1 and right != n - 1:
    right += 1
    
while a[left] !=1 and left != 0:
    left -= 1
 
if left == 0:
    left = last_ind - left
else:
    left = last_ind - left - 1
if right == n - 1:
    right -= last_ind
else:
    right = right - last_ind - 1
print(min(left, right), max(left, right))
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2017, 22:54
Ответы с готовыми решениями:

Последний index массива int[]
Привет всем! Помогите пожалуйста, есть массив int array = { }; нужно узнать index последнего...

Перезапись данных из одно fit файла в другой fit файл
Помогите пожалуйста составить программу, которая брала бы имеющийся файл in.fit и переписовала бы...

Преобразование int[] в Integer[]
Возможно ли преобразовать int в Integer без итерации массивов?

Создание int массива, используя строку string
Хочу создать int массив, используя строку string типа: 1, 4, 7, 5, 56, 68 итд. По сути нужно только...

12
433 / 425 / 159
Регистрация: 21.05.2016
Сообщений: 1,338
26.10.2017, 23:07 2
Вы представляете себе что такое 10**18 байт?
0
7 / 7 / 7
Регистрация: 20.06.2016
Сообщений: 72
26.10.2017, 23:19  [ТС] 3
Может, есть какой-нибудь другой способ решения, но мне тяжело представить, как решить данную задачу без массивов.
ТЗ: Есть ряд кинотеатра длинной N. Изначально пуст. Заходят по очереди K человек. Каждый выбирает себе место как можно дальше от других. А именно, посетитель находит самый длинный свободный участок и садится на его середину. Если его длина четная, садится на любое из двух мест. Надо определить и вывести количество свободных мест, которое останется слева и справа от последнего посетителя.
0
18 / 17 / 16
Регистрация: 20.10.2017
Сообщений: 39
27.10.2017, 12:38 4
Лучший ответ Сообщение было отмечено Anikin как решение

Решение

Спасибо за интересную задачу! Мне очень понравилось её решать.
Я только начинаю учить Питон, я насколько смог протестировал решение, прошу прощения, если какие-то ошибки остались.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
k = int(input())
worklist = list()
worklist.append(n)
while k > 0:
    if worklist[0] % 2 == 1:
        tmp = int((worklist[0] - 1) / 2)
        del worklist[0]
        worklist.append(tmp)
        worklist.append(tmp)
    else:
        tmp = int(worklist[0] / 2)
        del worklist[0]
        worklist.append(tmp)
        worklist.append(tmp-1)
    k = k-1
print(worklist[len(worklist)-2], worklist[len(worklist)-1])
Основная идея: я храню в списке длины свободных отрезков, отсортированных по убыванию. При пустом зале список имеет вид [n]. Первый зритель разобьет этот отрезок пополам: [(n-1)/2, (n-1)/2] в случае, если n нечетное; и [(n-1)/2; (n-2)/2], если n было четным. Аналогично, каждый следующий зритель будет "разбивать" самый длинный пустой отрезок. Результат "разбиения" от последнего зрителя и есть ответ на задачу.

Буду очень благодарен за указания, как сделать код лучше/быстрее.
1
Эксперт Python
4531 / 1959 / 351
Регистрация: 17.03.2012
Сообщений: 9,862
Записей в блоге: 5
27.10.2017, 13:51 5
10**18 байт ~ 10**9 Gb. То есть вам нужен миллиард гигабайт памяти.
0
7 / 7 / 7
Регистрация: 20.06.2016
Сообщений: 72
27.10.2017, 18:55  [ТС] 6
Спасибо за ваше решение! Оно мне очень помогло! У меня были некоторые мысли, насчет данного решения, но реализация оказалась слишком сложной. Ваш код очень прост и эффективен. Несколько микромоментов в коде. Мы можем сразу объявить список с элементом n.
Python
1
worklist = [n]
Так же в конце, когда нам нужно вывести последний элемент. Можно воспользоваться конструкцией:
Python
1
print(worklist[-2], worklist[-1])
"-" перед числом сообщит об отсчете с конца.

Добавлено через 43 минуты
Сделал ваш код немного компактнее, смысл абсолютно такой же.
Python
1
2
3
4
5
6
7
8
9
n = int(input())
k = int(input())
worklist = [n]
while k > 0:
    temp = worklist.pop(0)
    worklist.append((temp - temp % 2) // 2)
    worklist.append((temp - temp % 2) // 2 - (1 - temp % 2))
    k -= 1
print(worklist[-1], worklist[-2])
0
433 / 425 / 159
Регистрация: 21.05.2016
Сообщений: 1,338
27.10.2017, 23:38 7
Т.е. вас снова не смутил тот факт, что при k=10**18 вам потребуются миллиарды гигабайт памяти?
0
0 / 0 / 0
Регистрация: 21.09.2017
Сообщений: 5
28.10.2017, 00:32 8
Цитата Сообщение от oldnewyear Посмотреть сообщение
Т.е. вас снова не смутил тот факт, что при k=10**18 вам потребуются миллиарды гигабайт памяти?
Неа. Эта переменная будет весить 32 байта. Всё на "Снимок.PNG"
0
Миниатюры
Создание массива на 10**18 элементов (cannot fit 'int' into an index-sized integer)  
433 / 425 / 159
Регистрация: 21.05.2016
Сообщений: 1,338
28.10.2017, 03:50 9
Цитата Сообщение от _the_ Посмотреть сообщение
Неа. Эта переменная будет весить 32 байта. Всё на "Снимок.PNG"
Причем здесь k? Я говорю про список worklist
0
0 / 0 / 0
Регистрация: 21.09.2017
Сообщений: 5
28.10.2017, 12:19 10
Цитата Сообщение от oldnewyear Посмотреть сообщение
Причем здесь k? Я говорю про список worklist
Ну не знаю. Решение уже написали выше и за него поблагодарили.
0
433 / 425 / 159
Регистрация: 21.05.2016
Сообщений: 1,338
28.10.2017, 19:24 11
А, ну раз так, то это все меняет. Как я не заметил
0
18 / 17 / 16
Регистрация: 20.10.2017
Сообщений: 39
30.10.2017, 08:26 12
Да, я в курсе, что worklist - это список с k+1 элементами, так что от проблемы создания списка с 10**18 элементов мы не ушли. Есть другое решение задачи, более громоздкое, некрасивое и медленное, но в нем проблема со списком решена.
Можно хранить данные в списке формата {<длина свободного отрезка>:<количество подобных отрезков>}. Количество записей в таком словаре будет ~O(log2(k)), то есть для k = 10 ** 18, записей в словаре будет ~ 60.

Код аналогичен предыдущей версии, но более громоздок из-за работы со словарем

Вот код:
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
36
37
def maxkeyindict(x):
    # Максимальное значение ключа в словаре
    a = [i for i in x.keys()]
    if max(a) > 0:
        return max(a)
    else:
        return 0
 
def createnewkeyorinc(x, y):
    # Если ключ имеется в словаре, то его значение уменьшается на один
    # Если ключа нет - то создается пара (ключ:1)
    if y in x.keys():
        x[y] += 1
    else:
        x[y] = 1
 
n = int(input())
k = int(input())
workdict = {n:1}
maxkeys = n
while k > 0:
    temp = maxkeys
    if workdict[maxkeys] > 1:
        workdict[maxkeys] -= 1
    else:
        workdict.pop(maxkeys)
    createnewkeyorinc(workdict, (temp - temp % 2) // 2)
    createnewkeyorinc(workdict, (temp - temp % 2) // 2 - (1 - temp % 2))
    k -= 1
    maxkeys = maxkeyindict(workdict)
# Вывод ответа
a = [i for i in workdict.keys()]
a.sort()
if workdict[a[0]] >= 2:
    print(a[0], a[0])
else:
    print(a[1], a[0])
0
433 / 425 / 159
Регистрация: 21.05.2016
Сообщений: 1,338
30.10.2017, 16:34 13
Цитата Сообщение от distance Посмотреть сообщение
Python
1
2
3
4
5
6
7
8
9
10
import math
 
n = 100
k = 3
level = int(math.log2(k)) 
z = (n-k)/(2**level)
left = int(z//2)
right = int(z - left)
print('Left: ', left)
print('Right: ', right)
Добавлено через 4 минуты
Сильно не тестировал, но вроде работает
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.10.2017, 16:34

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Дано описание массива, у которого индексы имеют ограниченный тип над integer, а тип элемента – integer или real
Дано описание массива, у которого индексы имеют ограниченный тип над integer, а тип элемента –...

Какая из этих функций int Q(int w) int W(int y,int u,int i) сработает быстрее?
Если есть 2 функции(простые или перегруженные) к примеру Q(int w) int W(int y,int u,int i)или int...

Перевод элементов массива char в int
Задача о золотом песке. Во входном файле 6 чисел, первые три стоимость за килограмм каждого вида...

Нельзя преобразовать тип function(a: integer;b: integer):integer к real
unit matr1; interface type matr2=array of real; matr3=array of real; procedure sum...

Создать два класса: целые (Integer) и вестор (int*). Определить конструкторы.
Sm1le_fun, ПравилаИзначальное название темы: &quot;Помогите с классами!!!&quot;. Дана задача такого вида :...

Максимальный количество элементов массива в long int
Подкажите пожулуйста скольок максимум элементов может выдержать массив long int mas


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.