Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.97/29: Рейтинг темы: голосов - 29, средняя оценка - 4.97
8 / 1 / 0
Регистрация: 20.02.2019
Сообщений: 35

Гости

23.03.2019, 12:56. Показов 5953. Ответов 9
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ребят, помогите, пожалуйста, решить задачу... Идей пока вообще нет, даже не знаю как подступиться...
Буду очень благодарен за любую помощь!


Гости
Вася переехал из своего родного города и очень скучает по старым друзьям. К сожалению, Вася снимает маленькую квартиру и одновременно в гости к нему может приехать только один друг.

Каждый друг сказал Васе два числа A и B - с какого по какой день он может приехать в гости. Каждый друг приезжает и уезжает в полдень. Каждый друг может приехать к Васе только один раз и остаться у него на несколько дней. Вася хотел бы, чтобы суммарное количество дней, когда у него в гостях есть кто-нибудь из друзей, было максимальным. Помогите ему определить даты приезда для каждого из друзей так, чтобы они не пересекались (допустима ситуация, что в один день один из друзей приезжает, а другой - уезжает) и суммарное время, когда у Васи в гостях есть кто-то из друзей, было максимальным.

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи.

В следующих N строках записано по два целых числа Ai и Bi (оба числа от 1 до 109) - возможное время приезда i-го друга.

Формат результата
Выведите N пар чисел Li и Ri - номера дней, в которые приедет и уедет i-й друг соответственно (Ai ≤ Li ≤ Ri ≤ Bi). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.

Примеры
Входные данные
3
1 2
2 4
3 5
Результат работы
1 2
2 3
3 5
Входные данные
3
2 3
1 4
3 5
Результат работы
-1 -1
1 4
4 5
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
23.03.2019, 12:56
Ответы с готовыми решениями:

Гости у Васи
Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти:...

Гости
Добрый день. Подскажите, как решить данную задачу, используя стандартные процедуры и функции, как можно проще. Вася переехал из...

Загулявшие гости
N гостей засиделись на даче и боятся опоздать на последнюю электричку. У хозяина дачи, который остается на ночь, есть автомобиль, но в него...

9
 Аватар для m0nte-cr1st0
1043 / 578 / 242
Регистрация: 15.01.2019
Сообщений: 2,178
Записей в блоге: 1
23.03.2019, 13:02
А где Ваш код?
0
8 / 1 / 0
Регистрация: 20.02.2019
Сообщений: 35
23.03.2019, 13:04  [ТС]
Я же говорю, я не знаю как подступиться к этой задаче...

У меня нет идей, как обработать эти данные...
Вот я и прошу дать любую подсказку для направления мысли...
0
 Аватар для m0nte-cr1st0
1043 / 578 / 242
Регистрация: 15.01.2019
Сообщений: 2,178
Записей в блоге: 1
23.03.2019, 13:11
Для начала алгоритм распиши, как ты видишь решение, а код написать - то такое..

Не по теме:

Цитата Сообщение от vakru Посмотреть сообщение
Я же говорю, я не знаю как подступиться к этой задаче...
если не знаешь как приступиться, может, рано пока такие задачи решать?

0
8 / 1 / 0
Регистрация: 20.02.2019
Сообщений: 35
23.03.2019, 13:13  [ТС]
Впринципе, даже со стороны математики не помешала бы помощь, как сделать расселения более рациональным...
0
 Аватар для m0nte-cr1st0
1043 / 578 / 242
Регистрация: 15.01.2019
Сообщений: 2,178
Записей в блоге: 1
23.03.2019, 13:14
Цитата Сообщение от m0nte-cr1st0 Посмотреть сообщение
Для начала алгоритм распиши, как ты видишь решение
...
0
8 / 1 / 0
Регистрация: 20.02.2019
Сообщений: 35
23.03.2019, 13:24  [ТС]
Не, у меня есть небольшие наработки и основ кода, но они не работают...

Вот:
C++
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream> 
using namespace std; 
int main(){ 
int N; 
cin » N; 
int data[N][2]; 
int result[N][2]; 
int min=110, meetme=0; 
int a; 
int number[N]; 
int startday[N]; 
int finishday[N]; 
int gift=0; 
int fri[N]; 
for(int i=0; i<N; i++){ 
for(int j=0; j<2; j++){ 
cin » a; 
data[i][j]=a; 
result[i][j]=a; 
} 
number[i]=i; 
} 
min=data[0][0]; 
startday[0]=data[0][0]; 
finishday[0]=data[0][1]; 
 
//???? ???????? 
int k=0; 
setlocale(LC_ALL, "Russian"); 
while(k<N){ 
cout « 1; 
gift=0; 
if(k==0){ // K==0 
for(int i=0; i<N; i++){ //????? ??? 
if(data[i][0]<min){ 
min=data[i][0]; 
startday[k]=data[i][0]; 
finishday[k]=data[i][1]; 
number[k]=i; 
} 
} 
cout « endl « "min=" « min « endl; 
fri[number[k]]=1; 
gift++; 
meetme=1; 
} 
cout « endl « "gift=" « gift « endl; 
for(int i=0; i<N; i++){ 
cout « endl « "ß âîøåë â öèêë äëÿ i" « endl; 
if(data[i][0]==min and fri[i]==0){ 
cout « endl « "ß âîøåë â öèêë äëÿ i è â if ïðè íåì" « endl; 
if(data[i][1]>data[number[k+gift-1]][1]){ 
cout « endl « "ß âîøåë â if â if ïðè öèêëå ñ i" « endl; 
startday[k+gift]=finishday[k+gift-1]; 
finishday[k+gift]=data[i][1]; 
number[k+gift]=i; 
result[i][0]=startday[k+gift]; 
result[i][1]=finishday[k+gift]; 
} 
else{ 
cout « endl « "ß âîøåë â else â if ïðè öèêëå ñ i" « endl; 
result[i][0]=-1; 
result[i][1]=-1; 
number[k+gift]=-1; 
} 
fri[i]=1; 
gift++; 
} 
} 
min=finishday[k+gift-1]; 
/*if(meetme==0){ 
min++; 
k=k-gift; 
} 
else{ 
min++; 
k=k+gift; 
}*/ 
cout « endl « gift « endl; 
k++; 
} 
cout « endl; 
for(int y=0; y<N; y++){ 
for(int u=0; u<2; u++){ 
if(u==0) cout « result[y][u] « " "; 
else cout « result[y][u] « endl; 
} 
} 
return 0; 
}
Добавлено через 4 минуты
Но этот код на с++...
И писать я собираюсь на с++. Впринципе, мне подойдет любой код. Надеюсь, я смогу его переделать.

Добавлено через 3 минуты
Мы создаем одномерный массив и сортируем, пока все друзья не встанут в правильном порядке приездов. А дальше выводим в изначальном порядке с нужными цифрами...
0
 Аватар для m0nte-cr1st0
1043 / 578 / 242
Регистрация: 15.01.2019
Сообщений: 2,178
Записей в блоге: 1
23.03.2019, 13:32
Цитата Сообщение от vakru Посмотреть сообщение
Но этот код на с++...
И писать я собираюсь на с++. Впринципе, мне подойдет любой код. Надеюсь, я смогу его переделать.
Вы ошиблись адресом тогда.
0
8 / 1 / 0
Регистрация: 20.02.2019
Сообщений: 35
23.03.2019, 13:34  [ТС]
Я знаю, но мне нужна идея для размышления дальше хотя бы на словах...
0
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 1
05.05.2021, 05:09
Я написал код, но не прохоит на 4 тесте.
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
48
49
50
51
52
53
54
55
n = int(input())
possible_days = []
ranges = []
mas_print = []
 
for i in range(n):
    a, b = input().split()
    ranges_mini = []
 
    for j in range(int(a), int(b) + 1):
        possible_days.append(j)
        ranges_mini.append(j)
 
    ranges.append(ranges_mini)
 
possible_days = sorted(set(possible_days))
 
ranges_origin = ranges
ranges = sorted(ranges)
index = []
for i in ranges:
    k = ranges_origin.index(i)
    index.append(k)
 
#print(possible_days, 'possible_days')
#print(ranges, 'ranges')
#print(index)
 
for i in ranges:
    if len(possible_days) == 0:
        break
 
    w = len(i)
    mas_print_mini = []
    for j in i:
        if j in possible_days:
            c = possible_days.index(j)
            mas_print_mini.append(possible_days[c])
            del possible_days[c]
    mas_print.append(mas_print_mini)
 
for i in index:
 
    if len(mas_print[i]) == 1:
        f = mas_print[i]
        print(f[0], f[0])
        #print(f)
    elif len(mas_print[i]) == 0:
        print(-1, -1)
 
    elif len(mas_print[i]) > 2:
        f = mas_print[i]
        print(f[0], f[-1])
    else:
        print(*mas_print[i])
если кто сможет подправить, то вот....
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
05.05.2021, 05:09
Помогаю со студенческими работами здесь

Гости и Зарегистрированные
Друзья ваш помощь снова нужен мне. Скажем так у меня ест чат и файли для загрузки. Какой код мне добавить чтобы регистрированные...

Гости в контакте и ФБ
собсно весь вопрос.. можно ли их отслеживать..

Гости онлайн
Добрый день знатоки php! Помогите мне с одной маленькой проблемой если не трудно) Хочу сделать вывод гостей (всего онлайн), есть база и...

Что за гости на сайте?
Здравствуйте. Есть сайт, всего 1,5 мес. vutvoryushka.ru. Искусственная посещалка отключена. Еще до индексации его уже посещали посторонние:...

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
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. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru