Своя версия игры 2048

@cjsfkmse · 06.07.2021, 09:26. **Показов** 3436. **Ответов** 9

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

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

Игра состоит из одной вертикальной полоски бесконечной длины, на которую сверху последовательно падают n кубиков. На каждом из этих кубиков написано число 2 или 4. Когда кубик падает на другой кубик с точно таким же числом x, они объединяются в один кубик с числом 2x и этот процесс продолжается.

Помогите Вите и напишите бота, который запустит эту игру и выведет конечную конфигурацию кубиков.

Входные данные
В первой строке входного файла дано одно положительное целое число n (1≤n≤105).

Во второй строке входного файла даны n целых чисел a1, ..., an — числа, записанные на кубиках, которые будут последовательно падать сверху. (ai=2 или ai=4)

Выходные данные
В первой строке выведите одно положительное целое число k — количество кубиков в конечной конфигурации.

Затем, во второй строке выведите ровно k целых чисел b1, ..., bk. bi должно обозначать число, написанное на i-м кубике сверху.

@Gdez · 06.07.2021, 10:38

cjsfkmse, можно так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
a = list(map(int, input().split()))
res = [a[0]]
for num in a[1:]:
    res.append(num)
    while len(res) > 1:
        tmp = res.pop()
        if tmp == res[-1]:
            res[-1] *= 2
            n -= 1
        else:
            res.append(tmp)
            break
print(n)

Добавлено через 8 минут
Можно "убрать" циклическое определение len():

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
a = list(map(int, input().split()))
res = [a[0]]
k = 1
for num in a[1:]:
        res.append(num)
        k += 1
        while k > 1:
            tmp = res.pop()
            if tmp == res[-1]:
                res[-1] *= 2
                n -= 1
                k -= 1
            else:
                res.append(tmp)
                break
print(n)

@avdivo · 06.07.2021, 14:39

chelovek333,

Python
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
cubes = input().split()[:n]
 
line = []
for one in cubes:
    line.insert(0, int(one))
    while len(line) > 1 and line[0] == line[1]:
        line[0] = line.pop(1) * 2
 
print (len(line))
print (*line)

@unfindable_404 · 06.07.2021, 16:00

avdivo, немного поправил ваш код. Вставка в начало списка очень затратная операция. Намного эффективнее добавлять элемент в конец списка.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
input()
cubes = input().split()
 
line = []
for one in cubes:
    tmp = int(one)
    while line and line[-1] == tmp:
        line.pop()
        tmp *=  2
    line.append(tmp)
 
print(len(line))
print(*reversed(line))

@Catstail · 06.07.2021, 21:00

Сообщение от unfindable_404

Вставка в начало списка очень затратная операция. Намного эффективнее добавлять элемент в конец списка.

- странно... Почему? Особенность Питона?

@unfindable_404 · 06.07.2021, 22:31

Сообщение от Catstail

Почему? Особенность Питона?

Насколько мне известно, это особенность любых "массивоподобных" объектов.
Добавление в конец имеет сложность O(1), а вставка в начало O(n).

@Arsegg · 07.07.2021, 00:35

Сообщение от Catstail

- странно... Почему? Особенность Питона?

Не только: в любом ЯП добавление в начало массива предполагает собой сдвиг всех имеющихся элементов вправо, разумеется удостоверившись, что позволяет capacity.

@Catstail · 07.07.2021, 05:21

Сообщение от Arsegg

в любом ЯП добавление в начало массива предполагает собой сдвиг всех имеющихся элементов вправо, разумеется удостоверившись, что позволяет capacity.

- массива - да, но не списка!

Сообщение от unfindable_404

особенность любых "массивоподобных" объектов. Добавление в конец имеет сложность O(1), а вставка в начало O(n).

- но мы-то работаем не с массивоподобными объектами, а со списками! Список (связный список) - это не массив! И, если на то пошло, то при разумной организации списка (если хранить ссылку на начало и на конец), то добавление в начало и в конец будут иметь сложность O(1). Добавление в середину - O(n) (за счет поиска места вставки, т.к. в настоящих списках сдвига элементов не происходит никогда).

В языках с "простыми" списками добавление в начало - простая операция, добавление в конец - затратная. Именно так и обстоят дела в Лиспе и Хаскелле:

Lisp
1
2
3
4
5
6
7
;; вставка в начало списка
 
   (cons 'a  '(b c d))  => (a b c d)  ;; один вызов встроенной функции cons
 
;; вставка  в конец
 
   (append '(a b c) '(d)) => (a b c d) ;; append - рекурсивная функция сложноcти O(n) - проход по первому арг. до конца

Haskell
1
2
3
4
5
6
7
-- вставка в начало списка
 
   1:[2,3,4] => [1,2,3,4] - встроенная (быстрая) операция (:) - однократный вызов
 
-- вставка в конец
 
   [1,2,3]++[4] => [1,2,3,4] - проход по первому аргументу до конца

Понятно, что в Лиспе и Хаскелле списки - элементарные структуры. А в Питоне список "наворочен". Но в этом-то и дело! Если связный список (как объект) имеет ссылку на начало и на конец, то добавить элемент что в конец, что в начало - это O(1).

@Arsegg · 07.07.2021, 10:53

Сообщение от Catstail

А в Питоне список "наворочен".

Насколько я помню, списки (list) в Python'е реализованы на динамическом массиве. Понимаю, если бы была Scala с ее односвязными списками (там добавление в начало как раз таки O(1)).
Вот в collections.deque добавление в начало и в конец дека будет O(1), т. к. это двусвязный список в своем представлении со всеми вытекающими: индексация O(N) и т. п.

@Catstail · 07.07.2021, 11:02

Сообщение от Arsegg

списки (list) в Python'е реализованы на динамическом массиве.

- если так, то понятно.

Новые блоги и статьи Все статьи Все блоги /
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .

@cjsfkmse Заблокирован

	Своя версия игры 2048 06.07.2021, 09:26. Показов 3436. Ответов 9 Метки нет (Все метки) Витя решил создать свою версию игры 2048. Оригинальная игра на таблице оказалась слишком сложной, поэтому Витя решил начать с простого. Игра состоит из одной вертикальной полоски бесконечной длины, на которую сверху последовательно падают n кубиков. На каждом из этих кубиков написано число 2 или 4. Когда кубик падает на другой кубик с точно таким же числом x, они объединяются в один кубик с числом 2x и этот процесс продолжается. Помогите Вите и напишите бота, который запустит эту игру и выведет конечную конфигурацию кубиков. Входные данные В первой строке входного файла дано одно положительное целое число n (1≤n≤105). Во второй строке входного файла даны n целых чисел a1, ..., an — числа, записанные на кубиках, которые будут последовательно падать сверху. (ai=2 или ai=4) Выходные данные В первой строке выведите одно положительное целое число k — количество кубиков в конечной конфигурации. Затем, во второй строке выведите ровно k целых чисел b1, ..., bk. bi должно обозначать число, написанное на i-м кубике сверху. 0