Определить минимальное и максимальное количество дней, которое прошло от сообщения

@NebraskKrasnod · Регистрация: 16.04.2022

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

Известны дни, когда геймеры писали сообщения на форумах (не более одного сообщения в день), а так же дни, когда разработчики отвечали (так же не более одного сообщения в день).

Ваша задача — определить минимальное и максимальное количество дней, которое прошло от сообщения какого-либо геймера до ближайшего к нему ответа разработчиков (известно, что разработчики в итоге написали ответы на все вопросы геймеров, некоторые ответы могли быть сразу на несколько вопросов).

Замечание. Разработчики отвечают утром, а геймеры пишут свои вопросы вечером, поэтому, если геймер задал вопрос в день
d, то ответ он получит как минимум в день d+1.

Входные данные
В первой строке содержатся целые числа n и m

(1≤n≤105,1≤m≤10000) — количество ответов разработчиков и количество вопросов геймеров.

Во второй строке содержится n целых чисел s1,s2,…,sn

(1≤s1<s2<…<sn≤1000000000) — номера дней, когда разработчики давали ответ.

В третьей строке содержится целых чисел p1,p2,…,pm

(1≤p1<p2<…<pm<sn) — номера дней, в которые геймеры писали вопросы на форуме.

Выходные данные
Выведите два целых числа — минимальное и максимальное количество дней, которое прошло от сообщения какого-либо геймера до ближайшего к нему ответа разработчиков. Разделяйте числа пробелом или переводом строки.

Примеры
входные данные
7 10
1 5 13 23 25 30 31
2 4 5 12 15 22 24 25 28 30
выходные данные
1
8
------------------------------------------
входные данные
3 2
1 5 100
8 64
выходные данные
36
92
------------------------------------------
Примечание:
В первом примере на вопросы в день 2 и 4 будет получен ответ от разработчиков в день 5 (надо будет подождать 3 дня и 1 день, соответственно).

Вопросы в дни 5 и 12 будут отвечены в день 13 (ожидание 8 дней и 1 день).

Вопрос в день 5 не может быть отвечен в день 5, так как был задан вечером (все вопросы задаются вечером), а разработчики отвечают утром (все ответы разработчики пишут с утра после чашечки хорошего кофе с печеньем любятово, которое доставляется ООО "Я из Села").

На вопросы, поступившие в дни 15 и 22, будет получен ответ в день 23 (ожидание 8 дней и 1 день).

На вопрос в день 24 будет получен ответ в день 25 (1 день ожидания).

Вопросы в дни 25 и 28 будут отвечены в день 30 (ожидание 5 дней и 2 дня, соответственно).

Вопрос в день 30 - ответ в день 31 (1 день ждать).

Во втором примере оба вопроса будут отвечены в день 100 (ожидание 92 дня и 36 дней, соответственно).

@eaa · 14.05.2022, 12:58

NebraskKrasnod, что конкретно не получается?

@NebraskKrasnod · 14.05.2022, 13:36 **[ТС]**

3адачу решить

@Ivan_bebrovich · 14.05.2022, 13:36

ну это чисто на дп сделай там через шашку и готово

@anton78spb · 14.05.2022, 20:23

NebraskKrasnod, Написал за 5 мин. Скорее всего можно было сделать как-то более эстетично. Но данные тесты проходит.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, m = 7, 10
s = [1, 5, 13, 23, 25, 30, 31]
p = [2, 4, 5, 12, 15, 22, 24, 25, 28, 30]
# n, m = 3, 2
# s = [1, 5, 100]
# p = [8, 64]
 
pos = 0
ans = []
for current_p in p:
    for i, current_s in enumerate(s[pos:]):
        if current_s > current_p:
            pos = i
            ans.append(current_s - current_p)
            break
print(min(ans))
print(max(ans))

@eaa · 14.05.2022, 20:33

не уверен что это во времени зайдет

@anton78spb · 14.05.2022, 21:44

eaa, Почему? Там сложность O(n), где n = len(s) + len(p). Конструкция из вложенных циклов хоть и выглядит страшно как O(n^2), но реально по каждому пробегаются всего один раз.
Просто очень лень было думать, как это красиво оформить при помощи while.

Добавлено через 12 минут
eaa, Там единственная проблема, что во внутреннем цикле, каждый раз создается срез, что требует определенного времени. Хотя я не знаю, как это устроено внутри Python. Создает ли он его физически (делает копию), или там работает что-то типа генератора, который просто берет значения из текущего списка с определенной позиции.

@Gdez · 14.05.2022, 21:52

anton78spb,цикл по "p" с бинпоиском по "s" быстрее будет...

@anton78spb · 14.05.2022, 22:59

Gdez, Вот такой вариант еще в голову пришел. Просто последовательный проход по двум спискам.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, m = 7, 10
s = [1, 5, 13, 23, 25, 30, 31]
p = [2, 4, 5, 12, 15, 22, 24, 25, 28, 30]
# n, m = 3, 2
# s = [1, 5, 100]
# p = [8, 64]
 
pos_s, pos_p = 0, 0
res = []
while pos_s < n and pos_p < m:
    if s[pos_s] > p[pos_p]:
        res.append(s[pos_s] - p[pos_p])
        pos_p += 1
    else:
        pos_s += 1
print(min(res))
print(max(res))

Добавлено через 43 минуты
eaa, Gdez, Сравнил быстродействие обоих вариантов. Сгенерировал последовательности длинной 50К. Похоже Python действительно генерирует новый список, когда создает срез. Скорость увеличилась на несколько порядков.
Первый вариант: 142.984 sec.
Второй вариант (через while): 0.051 sec.

@Gdez · 14.05.2022, 23:50

anton78spb, У меня так:

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
47
import timeit
from random import randint
from bisect import bisect_left
def wrapper(func, *args, **kwargs):                                                                   
    def wrapper():                                                                                    
        return func(*args, **kwargs)                                                                  
    return wrapper 
 
 
def fun_1():
    n, m = 105, 10000
    i = bisect_left(s, p[0])
    pos = 0
    tmin = 1e10
    tmax = 0
    for elem in s[i:]:
        ind = pos
        pos = bisect_left(p, elem, lo=ind, hi=m-1)
        tmin = min(elem - p[pos-1], tmin)
        tmax = max(elem - p[ind], tmax)
        
    return tmin, tmax
 
 
def fun_2():
    n, m = 105, 10000
 
    pos_s, pos_p = 0, 0
    res = []
    while pos_s < n and pos_p < m:
        if s[pos_s] > p[pos_p]:
            res.append(s[pos_s] - p[pos_p])
            pos_p += 1
        else:
            pos_s += 1
    return min(res), max(res)
    
    
s = sorted([randint(1, int(1e9)) for _ in range(105)])
p = sorted([randint(1, int(1e9)) for _ in range(10000)])
wrapped = wrapper(fun_1)                                                                  
print(timeit.timeit(wrapped, number=100))
wrapped = wrapper(fun_2)                                                                  
print(timeit.timeit(wrapped, number=100))
 
print(fun_1())
print(fun_2())

@eaa · 15.05.2022, 07:24

anton78spb, да тут merge через два указателя.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

Определить минимальное и максимальное количество дней, которое прошло от сообщения

Решение

Решение

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139

	Определить минимальное и максимальное количество дней, которое прошло от сообщения 14.05.2022, 10:59. Показов 2796. Ответов 10 Метки нет (Все метки) Известны дни, когда геймеры писали сообщения на форумах (не более одного сообщения в день), а так же дни, когда разработчики отвечали (так же не более одного сообщения в день). Ваша задача — определить минимальное и максимальное количество дней, которое прошло от сообщения какого-либо геймера до ближайшего к нему ответа разработчиков (известно, что разработчики в итоге написали ответы на все вопросы геймеров, некоторые ответы могли быть сразу на несколько вопросов). Замечание. Разработчики отвечают утром, а геймеры пишут свои вопросы вечером, поэтому, если геймер задал вопрос в день d, то ответ он получит как минимум в день d+1. Входные данные В первой строке содержатся целые числа n и m (1≤n≤105,1≤m≤10000) — количество ответов разработчиков и количество вопросов геймеров. Во второй строке содержится n целых чисел s1,s2,…,sn (1≤s1<s2<…<sn≤1000000000) — номера дней, когда разработчики давали ответ. В третьей строке содержится целых чисел p1,p2,…,pm (1≤p1<p2<…<pm<sn) — номера дней, в которые геймеры писали вопросы на форуме. Выходные данные Выведите два целых числа — минимальное и максимальное количество дней, которое прошло от сообщения какого-либо геймера до ближайшего к нему ответа разработчиков. Разделяйте числа пробелом или переводом строки. Примеры входные данные 7 10 1 5 13 23 25 30 31 2 4 5 12 15 22 24 25 28 30 выходные данные 1 8 ------------------------------------------ входные данные 3 2 1 5 100 8 64 выходные данные 36 92 ------------------------------------------ Примечание: В первом примере на вопросы в день 2 и 4 будет получен ответ от разработчиков в день 5 (надо будет подождать 3 дня и 1 день, соответственно). Вопросы в дни 5 и 12 будут отвечены в день 13 (ожидание 8 дней и 1 день). Вопрос в день 5 не может быть отвечен в день 5, так как был задан вечером (все вопросы задаются вечером), а разработчики отвечают утром (все ответы разработчики пишут с утра после чашечки хорошего кофе с печеньем любятово, которое доставляется ООО "Я из Села"). На вопросы, поступившие в дни 15 и 22, будет получен ответ в день 23 (ожидание 8 дней и 1 день). На вопрос в день 24 будет получен ответ в день 25 (1 день ожидания). Вопросы в дни 25 и 28 будут отвечены в день 30 (ожидание 5 дней и 2 дня, соответственно). Вопрос в день 30 - ответ в день 31 (1 день ждать). Во втором примере оба вопроса будут отвечены в день 100 (ожидание 92 дня и 36 дней, соответственно). 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 12:58
	NebraskKrasnod, что конкретно не получается? 2

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	14.05.2022, 13:36 [ТС]
	3адачу решить 1

@Ivan_bebrovich 7 / 6 / 1 Регистрация: 18.02.2022 Сообщений: 30
	14.05.2022, 13:36
	Сообщение было отмечено NebraskKrasnod как решение Решение ну это чисто на дп сделай там через шашку и готово 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 20:33
	не уверен что это во времени зайдет 1

@anton78spb 1956 / 874 / 352 Регистрация: 05.09.2021 Сообщений: 1,387
	14.05.2022, 21:44
	eaa, Почему? Там сложность O(n), где n = len(s) + len(p). Конструкция из вложенных циклов хоть и выглядит страшно как O(n^2), но реально по каждому пробегаются всего один раз. Просто очень лень было думать, как это красиво оформить при помощи while. Добавлено через 12 минут eaa, Там единственная проблема, что во внутреннем цикле, каждый раз создается срез, что требует определенного времени. Хотя я не знаю, как это устроено внутри Python. Создает ли он его физически (делает копию), или там работает что-то типа генератора, который просто берет значения из текущего списка с определенной позиции. 1

@Gdez 8850 / 4501 / 1864 Регистрация: 27.03.2020 Сообщений: 7,316
	14.05.2022, 21:52
	anton78spb,цикл по "p" с бинпоиском по "s" быстрее будет... 1

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