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

Найти в списке чисел заданный последовательный несортированный подсписок

08.11.2015, 01:39. Просмотров 1272. Ответов 16
Метки нет (Все метки)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
k = 0
with open('input.txt', 'r') as inp:
    file_list = [int(i) for i in inp.read().split()]
list_1 = file_list[1:file_list[0]+1]
list_2 = file_list[file_list[0]+2:file_list[0]+2+file_list[file_list[0]+1]]
list_1.sort()
if len(set(list_1)&set(list_2)) == len(set(list_1)):
    for i in range(len(list_2)-len(list_1)+1):
        if list_2[i] in list_1:
            proverka = list_2[i:i+file_list[0]]
            proverka.sort()
            if proverka == list_1:
                k = 1
                break
with open('output.txt', 'w') as out:
    if k == 1:
        out.write('YES\n'+str(list_2.index(list_1[0])))
    else: out.write('NO')
Условие

Условие:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Завтра у Дим Димыча день рождения, и Симка решила порадовать его подарком. Но под рукой ничего не оказалось, поэтому она решила подарить ему массив натуральных чисел. Чтобы Дим Димыч не обнаружил подарок раньше времени, Симка спрятала массив в системном блоке его компьютера. Однако как всегда прибежал Нолик и все испортил. Он перемешал все числа в массиве, и теперь он выглядит ужасно, на день рождения дарить его нельзя. К счастью, Нолик запомнил исходный массив и готов восстановить его, если Симка решит для него одну задачу. А именно, он хочет, чтобы она по данному набору чисел p нашла подотрезок q такой же длины в массиве-подарке, что p и q «практически совпадают». Два набора чисел практически совпадают, если в них можно переставить числа таким образом, чтобы они совпали точно. Например, наборы чисел [1, 2, 3] и [2, 3, 1] практически совпадают, а [1, 2, 3] и [2, 4, 3] — нет. Нолик написал на бумажке набор чисел p и теперь просит вас решить придуманную им задачу. Помогите Симке восстановить подарок Дим Димыча на день рождения!
Формат входных данных
В первой строке входного файла содержится единственное число n (1 ⩽ n ⩽ 100000) — количество чисел в наборе p. Во второй строке содержится n целых чисел pi (1 ⩽ pi ⩽ 100000) — набор чисел p. В третьей строке дано число m (n ⩽ m ⩽ 100000) — длина массива-подарка. В четвертой строке содержится m чисел ai (1 ⩽ ai ⩽ 100000) — числа из массива.
Формат выходных данных
В первой строке выходного файла выведите «YES», если в массиве-подарке существует подотрезок q, удовлетворящий условиям Нолика. В противном случае выведите «NO». В случае положительного ответа на второй строке также выведите позицию начала подотрезка. Если ответов несколько, можно вывести любой.
Примеры
input.txt
3
2 3 4
4
1 4 2 3

output.txt
YES
2


input.txt
3
1 2 3
4
2 3 4 5

output.txt
NO

Нужна помощь в ускорение работы обработчика (8-14)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.11.2015, 01:39
Ответы с готовыми решениями:

Написать функцию, которая находит в данном списке подсписок минимальной длины
Буду очень признателен!

Найти в одноуровневом числовом списке возрастающий подсписок максимальной длины
(Под влиянием предыдущей задачи). Мое решение (ищется первый список): ;; Дать длину...

Написать функцию, которая находит в данном списке подсписок минимальной длины. (HomeLisp) - Lisp
Буду очень признателен.

В нелинейном списке найти заданный элемент. Результат выдать в виде линейного списка
Здравствуйте. У меня есть задача: В нелинейном списке найти заданный элемент (м.б., не атом)....

16
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 11:13 2
Лучший ответ Сообщение было отмечено Cheshires как решение

Решение

Python
1
2
3
4
5
6
7
8
9
10
11
12
with open('input.txt', 'r') as inp,  open('output.txt', 'w') as out:
    lines = inp.readlines()
    p = lines[1].split()
    m = lines[3].split()
    res = 'NO'
 
    for x in range(len(m)-len(p)+1):
        if set(m[x:x+len(p)]) == set(p):
            res = 'YES\n'+str(x+1)
            break
 
    out.write(res)
Добавлено через 8 часов 49 минут
Python
1
2
3
4
5
6
7
8
9
def findme(p, m):
    for x in range(len(m)-len(p)+1):
        if set(m[x:x+len(p)]) == set(p):
            return 'YES\n'+str(x+1)
    return 'NO'
 
with open('input.txt', 'r') as inp,  open('output.txt', 'w') as out:
    lines = inp.readlines()
    out.write(findme(lines[1].split(), lines[3].split()))
1
Модератор
Эксперт NIX
2622 / 1969 / 663
Регистрация: 02.03.2015
Сообщений: 6,331
08.11.2015, 13:28 3
Лучший ответ Сообщение было отмечено Cheshires как решение

Решение

А почему Вы используете множество? Нигде в условии не сказано что числа не могут повторяться.
Python
3
4
5
    p = sorted(lines[1].split())
…
        if sorted(m[x:x+len(p)]) == p:
Добавлено через 3 минуты
Ну и так, к слову
Python
1
2
len(p) = int(lines[0])
len(m) = int(lines[2])
зачем их считать лишний раз?
1
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 13:30 4
Цитата Сообщение от Marinero Посмотреть сообщение
А почему Вы используете множество?
Ну и так, к слову
Абсолютно согласен, как всегда на шаг впереди
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
08.11.2015, 15:53  [ТС] 5
Тоже хотел сказать насчёт множеств, но что-то сильно сомневался.
По времени все ровно не укладываюсь.
Python
1
2
3
4
5
6
7
8
9
10
with open('input.txt', 'r') as inp,  open('output.txt', 'w') as out:
    lines = inp.readlines()
    p = sorted(lines[1].split())
    m = lines[3].split()
    res = 'NO'
    for x in range(int(lines[0])-int(lines[2])+1):
        if sorted(m[x:x+int(lines[0])]) == p:
            res = 'YES\n'+str(x+1)
            break
    out.write(res)
Теперь половину тестов не проходит!
0
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 15:54 6
а какая система проверки?
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
08.11.2015, 15:57  [ТС] 7
Есть тесты и ответы к ним(2 txt файла с входными и выходными данными). Я написал цикл, который бы проверял.
Но так же я вручную сверял.
0
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 16:03 8
а можно тесты посмотреть-подебажить?
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
08.11.2015, 16:09  [ТС] 9
Все тесты к этой задачи. Те что с припиской ".a" - ответы.
tests.rar
0
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 16:35 10
Цитата Сообщение от Cheshires Посмотреть сообщение
Теперь половину тестов не проходит!
в ответах есть пустая строка в конце файла, добавьте её к ответу

первых 47 тестов прошло удачно, потом подвисло по времени

Добавлено через 2 минуты
представляю, что будет на 49-50 тестах, где по полтора мега входных данных))
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
08.11.2015, 16:53  [ТС] 11
Большое спасибо за помощь! Видимо, это та задача, которая на питоне не решается за опред. время. Пошёл листать учебник по паскалю!)
0
Эксперт по компьютерным сетям
3835 / 2638 / 822
Регистрация: 03.11.2009
Сообщений: 8,307
Записей в блоге: 3
08.11.2015, 17:30 12

Не по теме:

всегда пожалуйста! ...вангую двух оптимизаторов в этой ветке :)



если они придут, я остановился на вот таком варианте (с проверкой тестов)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findme(lp, p, lm, m):
    for x in range(lm-lp+1):
        if sorted(m[x:x+lp]) == p:
            return 'YES\n'+str(x+1)
    return 'NO'
 
for x in range(1, 11): #test numbers
    fi = './tsts/'+str(x).zfill(2)
    fo = fi+'.a'
 
    with open(fi, 'r') as inp, open(fo, 'r') as out:
        lines = inp.readlines()
        result = findme(int(lines[0]), sorted(lines[1].split()), int(lines[2]), lines[3].split())+"\n"
        print('test #', str(x).zfill(2), 'passed :', result == out.read())
Добавлено через 27 минут
99% всего времени занимает сортировка листа...

Код
Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     6                                           @profile
     7                                           def findme(lp, p, lm, m):
     8         1            7      7.0      0.0      if p == m:
     9                                                   return 'YES\n1'
    10      2099         2718      1.3      0.1      for x in range(lm-lp+1):
    11      2099      3364038   1602.7     99.9          if sorted(m[x:x+lp]) == p:
    12         1            5      5.0      0.0              return 'YES\n'+str(x+1)
    13                                               return 'NO'
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
08.11.2015, 17:46  [ТС] 13
А если нам начинать проверку не с 0 элемента, а с (lm/2) и идти в обе стороны, к lm и к 0. Тогда, у нас кол-во проверок будет равно не (lm-lp+1), а (lm-lp*2+1), но тогда нам придётся делать 1-у проверку вне цикла for, эта идея может сработать?
0
Модератор
Эксперт NIX
2622 / 1969 / 663
Регистрация: 02.03.2015
Сообщений: 6,331
08.11.2015, 23:37 14
Можно и без сортировки
Python
7
8
9
10
11
12
13
14
15
16
17
18
19
20
testp = p[:]
idx = 0
for x in range(lm - lp + 1):
    try:
        testp.remove(m[x])
    except ValueError:
        testp = p[:]
        idx = x
        continue
    if not testp:
        result = 'YES\n' + str(idx + 2)
        break
else:
    result = 'NO'
И р можно тоже не сортировать.
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
09.11.2015, 17:15  [ТС] 15
Вы уверены, что код правильный? Я уже как не изворачивался, но некоторые тесты не проходит!
0
Модератор
Эксперт NIX
2622 / 1969 / 663
Регистрация: 02.03.2015
Сообщений: 6,331
10.11.2015, 12:20 16
Cheshires, Странно что хоть какие-то прошёл… (условие было наоборот)+ Вы же обратили внимание что это только часть кода(без ввода данных и вывода результата)?
0
1 / 1 / 0
Регистрация: 20.10.2015
Сообщений: 28
10.11.2015, 15:19  [ТС] 17
Marinero, Да, заметил! Даже так я пробовал (правда уже сам), и у меня все ровно некоторые тесты не проходили. И скорость на некоторых примерах оставляла желать лучшего

У меня только отсутствовал:
Python
1
2
3
else:
    result = 'NO
'
Вместо него я присвоил значение в самом начале: 'NO'
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.11.2015, 15:19

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Организовать поиск заданного числа с заменой его на заданный в односвязном списке "очередь" из случайных целых чисел
1. Создать в динамической памяти односвязный список типа «очередь» из случайных целых чисел ....

Найти количество чисел, попадающих в заданный диапазон в массиве 16-разрядных чисел со знаком
помогите выполнить. Найти количество чисел, попадающих в заданный диапазон в массиве 16-разрядных...

В линейном списке целых чисел найти среднее арифметическое нечётных чисел, делящихся на 5
Требуется создать линейный список целых чисел, элементами которого являются случайные целые числа и...

Найти сумму чисел в списке
Всем доброго времени суток! Нужно найти сумму чисел в списке. Атомы списка состоят из чисел и...


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

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

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