Игра в числа

@matrenkino · Регистрация: 20.12.2019

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

Игра в числа ведётся на одномерном массиве целых положительных чисел. Перед началом, жеребьёвкой определяется, кто будет ходить первым (первый игрок), а кто – вторым (второй игрок). Процесс игры состоит в том, что игроки по очереди (сначала первый игрок, затем второй, следом опять первый и так далее) вычёркивают числа из массива. Вычеркнуть можно только число, находящееся в конце или начале оставшегося массива. При этом всегда вычёркивается максимальное число из этих двух. Если первое и последнее числа массива равны, то вычёркивается первое. Игра продолжается до того момента, пока не будут вычеркнуты все числа. Каждое вычеркнутое число идёт в актив тому игроку, который его вычеркнул. После окончания игры каждый игрок суммирует вычеркнутые им числа. Победителем объявляется тот, кто наберет больше очков.

Некоторые игроки поняли, что результат не зависит от стратегии игры, и решили попросить Вас написать программу для получения результата.

Входные данные

В первой строке находится одно целое число N – количество чисел в массиве (1 ≤ N ≤ 104). Во второй строке находятся N целых положительных чисел из диапазона [1, 32000], разделённых пробелом.

Выходные данные

Выведите два числа, разделенные двоеточием. Первое число – количество очков, набираемых первым игроком при игре на этом массиве, второе число – для второго.

INPUT.TXT

5
4 4 1 5 4

OUTPUT.TXT

9:9

@udeep · 21.12.2019, 10:42

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
a = list(map (int, input().split()))
 
x = y = 0
for k in range(n):
    i = a[0]
    j = a[-1]
    if j > i:
        z = j
        del a[-1]
    else:
        z = i
        del a[0]
    if k & 1:
        y += z
    else:
        x += z
    
print(f'{x}:{y}')

@matrenkino · 21.12.2019, 10:55 **[ТС]**

Большое спасибо

поняла что к чему

@eaa · 21.12.2019, 10:56

udeep, Шеф, два счетчика

@udeep · 21.12.2019, 15:10

eaa,
Так понятнее и отражает суть игры

@eaa · 21.12.2019, 15:21

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

Так понятнее и отражает суть игры

По времени может не пройти.

@udeep · 22.12.2019, 23:42

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

По времени может не пройти.

Пробел знаний (не нашел в google). Как удаление из списка реализуется в Python? IMHO, должно быть всего две операции - смена указателя на следующий элемент и отметка в менеджере памяти(?)

@eaa · 22.12.2019, 23:52

Удаление O(n) по времени вроде как. Значит будет сдвиг хвоста или начала. Точно не могу сказать.

@udeep · 23.12.2019, 00:55

eaa,
Пока загадка. - И если список в Рython не подобен TList, ...

@tooru · 23.12.2019, 01:22

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

Пробел знаний (не нашел в google). Как удаление из списка реализуется в Python? IMHO, должно быть всего две операции - смена указателя на следующий элемент и отметка в менеджере памяти(?)

Можно в исходниках посмотреть

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;
 
    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

в общем, там новый список создается без удаляемого элемента

@udeep · 23.12.2019, 09:54

Python
1
2
3
4
5
6
add_last   - time: 0.0166955330 seconds
del_first  - time: 2.0168308220 seconds
add_first  - time: 3.1527889180 seconds
del_last   - time: 0.0103985540 seconds
pop_first  - time: 1.9149358810 seconds
pop_last   - time: 0.0113944010 seconds

Кликните здесь для просмотра всего текста

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
from timeit import default_timer as timer
 
 
n = 100000 
 
def add_last(a):
    for i in range(n):
        a.append(i)
 
def add_first(a):
    for i in range(n):
        a.insert(0, i)
        
def del_first(a):
    while a:
        del a[0]
 
def del_last(a):
    while a:
        del a[-1]
        
 
def pop_first(a):
    while a:
        a.pop(0)
 
def pop_last(a):
    while a:
        a.pop()
 
def run_time(function, a):
    t = timer()
    function(a)
    time = timer() - t
    print(f"{function.__name__:10} - time: {time:.10f} seconds")
 
 
a = []
run_time(add_last, a)
run_time(del_first, a)
run_time(add_first, a)
run_time(del_last, a)
add_last(a)
run_time(pop_first, a)
add_last(a)
run_time(pop_last, a)

@eaa · 23.12.2019, 10:07

что и требовалось доказать.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@matrenkino 0 / 0 / 0 Регистрация: 20.12.2019 Сообщений: 19

	Игра в числа 20.12.2019, 23:18. Показов 6934. Ответов 11 Метки python (Все метки) Игра в числа ведётся на одномерном массиве целых положительных чисел. Перед началом, жеребьёвкой определяется, кто будет ходить первым (первый игрок), а кто – вторым (второй игрок). Процесс игры состоит в том, что игроки по очереди (сначала первый игрок, затем второй, следом опять первый и так далее) вычёркивают числа из массива. Вычеркнуть можно только число, находящееся в конце или начале оставшегося массива. При этом всегда вычёркивается максимальное число из этих двух. Если первое и последнее числа массива равны, то вычёркивается первое. Игра продолжается до того момента, пока не будут вычеркнуты все числа. Каждое вычеркнутое число идёт в актив тому игроку, который его вычеркнул. После окончания игры каждый игрок суммирует вычеркнутые им числа. Победителем объявляется тот, кто наберет больше очков. Некоторые игроки поняли, что результат не зависит от стратегии игры, и решили попросить Вас написать программу для получения результата. Входные данные В первой строке находится одно целое число N – количество чисел в массиве (1 ≤ N ≤ 104). Во второй строке находятся N целых положительных чисел из диапазона [1, 32000], разделённых пробелом. Выходные данные Выведите два числа, разделенные двоеточием. Первое число – количество очков, набираемых первым игроком при игре на этом массиве, второе число – для второго. INPUT.TXT 5 4 4 1 5 4 OUTPUT.TXT 9:9 0

@matrenkino 0 / 0 / 0 Регистрация: 20.12.2019 Сообщений: 19
	21.12.2019, 10:55 [ТС]
	Большое спасибо поняла что к чему 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	21.12.2019, 10:56
	udeep, Шеф, два счетчика 0

@udeep 55 / 40 / 18 Регистрация: 16.12.2019 Сообщений: 149
	21.12.2019, 15:10
	eaa, Так понятнее и отражает суть игры 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	22.12.2019, 23:52
	Удаление O(n) по времени вроде как. Значит будет сдвиг хвоста или начала. Точно не могу сказать. 0

@udeep 55 / 40 / 18 Регистрация: 16.12.2019 Сообщений: 149
	23.12.2019, 00:55
	eaa, Пока загадка. - И если список в Рython не подобен TList, ... 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	23.12.2019, 10:07
	что и требовалось доказать. 0

Игра в числа

Решение