Задания
Версия для печати и копирования в MS Word
Тип 26 № 40742
i

Во мно­гих ком­пью­тер­ных си­сте­мах те­ку­щее время хра­нит­ся в фор­ма­те «UNIX-время»  — ко­ли­че­стве се­кунд от на­ча­ла суток 1 ян­ва­ря 1970 года.

В одной ком­пью­тер­ной си­сте­ме про­во­ди­ли ис­сле­до­ва­ние за­гру­жен­но­сти. Для этого в те­че­ние ме­ся­ца с мо­мен­та UNIX-⁠вре­ме­ни 1633046400 фик­си­ро­ва­ли и за­но­си­ли в базу дан­ных мо­мен­ты стар­та и фи­ни­ша всех про­цес­сов, дей­ство­вав­ших в этой си­сте­ме.

Вам не­об­хо­ди­мо опре­де­лить, какое наи­боль­шее ко­ли­че­ство про­цес­сов вы­пол­ня­лось в си­сте­ме од­но­вре­мен­но на не­де­ле, на­чав­шей­ся в мо­мент UNIX-⁠вре­ме­ни 1633305600, и в те­че­ние ка­ко­го сум­мар­но­го вре­ме­ни (в се­кун­дах) вы­пол­ня­лось такое наи­боль­шее ко­ли­че­ство про­цес­сов.

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

За­да­ние 26

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство про­цес­сов за весь пе­ри­од на­блю­де­ния. Каж­дая из сле­ду­ю­щих N строк со­дер­жит 2 целых числа: время стар­та и время за­вер­ше­ния од­но­го про­цес­са в виде UNIX-⁠вре­ме­ни. Все дан­ные в стро­ках вход­но­го файла от­де­ле­ны одним про­бе­лом.

Если в ка­че­стве вре­ме­ни стар­та ука­зан ноль, это озна­ча­ет, что про­цесс был ак­ти­вен в мо­мент на­ча­ла ис­сле­до­ва­ния. Если в ка­че­стве вре­ме­ни за­вер­ше­ния ука­зан ноль, это озна­ча­ет, что про­цесс не за­вер­шил­ся к мо­мен­ту окон­ча­ния ис­сле­до­ва­ния.

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

В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла мак­си­маль­ное ко­ли­че­ство про­цес­сов, ко­то­рые вы­пол­ня­лись од­но­вре­мен­но на не­де­ле, на­чи­ная с мо­мен­та UNIX-⁠вре­ме­ни 1633305600, затем сум­мар­ное ко­ли­че­ство се­кунд, в те­че­ние ко­то­рых на этой не­де­ле вы­пол­ня­лось такое мак­си­маль­ное ко­ли­че­ство про­цес­сов.

 

Ответ:

Спрятать решение

Ре­ше­ние.

За­ме­тим, что не­де­ля в фор­ма­те UNIX-⁠вре­ме­ни  — это 604800 се­кунд. Со­зда­дим мас­сив time_process раз­ме­ром 604800 эле­мен­тов  — в нём будем отоб­ра­жать дан­ные о про­цес­сах, на­чав­ших­ся на не­де­ле, на­чав­шей­ся с мо­мен­та UNIX-⁠вре­ме­ни 1633305600. Объ­явим пе­ре­мен­ную max_process  — в ней будем хра­нить, какое наи­боль­шее ко­ли­че­ство про­цес­сов вы­пол­ня­лось в си­сте­ме од­но­вре­мен­но на не­де­ле. Объ­явим пе­ре­мен­ную sum_time  — в ней будем хра­нить сум­мар­ное ко­ли­че­ство се­кунд, в те­че­ние ко­то­рых на этой не­де­ле вы­пол­ня­лось мак­си­маль­ное ко­ли­че­ство про­цес­сов. Пе­ре­мен­ную count будем ис­поль­зо­вать для подсчёта те­ку­ще­го ко­ли­че­ство вы­пол­ня­е­мых про­цес­сов на не­де­ле в дан­ную се­кун­ду.

Если про­цесс на­чал­ся до тре­бу­е­мой не­де­ли, а за­кон­чил­ся после на­ча­ла этой не­де­ли, будем сразу уве­ли­чи­вать зна­че­ние счётчика count. Если про­цесс на­чал­ся на тре­бу­е­мой не­де­ле, к эле­мен­ту мас­си­ва time_process, со­от­вет­ству­ю­ще­му се­кун­де на­ча­ла оче­ред­но­го про­цес­са на не­де­ле, будем при­бав­лять еди­ни­цу. Если про­цесс окон­чил­ся на тре­бу­е­мой не­де­ле, от эле­мен­та мас­си­ва time_process, со­от­вет­ству­ю­ще­му се­кун­де окон­ча­ния оче­ред­но­го про­цес­са на на­де­ле, будем от­ни­мать еди­ни­цу  — таким об­ра­зом учтём усло­вие, что если время стар­та од­но­го про­цес­са сов­па­да­ет с вре­ме­нем за­вер­ше­ния дру­го­го и дру­гих стар­тов и за­вер­ше­ний в этот мо­мент нет, то ко­ли­че­ство ак­тив­ных про­цес­сов в этот мо­мент не из­ме­ня­ет­ся. Учи­ты­вая усло­вия выше, счи­та­ем файл. После этого в цикле «for» пе­ре­берём эле­мен­ты мас­си­ва time_process, при­бав­ляя к счётчику count зна­че­ния эле­мен­тов этого мас­си­ва. Если зна­че­ние count ока­жет­ся боль­ше зна­че­ния пе­ре­мен­ной max_process  — будем об­нов­лять зна­че­ние этой пе­ре­мен­ной. В этом же цикле найдём сум­мар­ное ко­ли­че­ство се­кунд, в те­че­ние ко­то­ро­го вы­пол­ня­лось наи­боль­шее ко­ли­че­ство про­цес­сов  — к пе­ре­мен­ной sum_time будем до­бав­лять еди­ни­цу каж­дый раз, когда будет вы­пол­нят­ся усло­вие count  =  max_process. Если будет встре­че­на си­ту­а­ция, когда count > max_process  — будем об­ну­лять пе­ре­мен­ную sum_time.

 

При­ведём ре­ше­ние на языке Pascal.

var

n, count, sum_time, max_process, i: integer;

start_time, end_time, start_process, end_process: int64;

time_process: array[1..604800] of integer;

f: text;

begin

assign(f,'C:\26.txt');

reset(f);

readln(f, n);

start_time := 1633305600;

end_time := start_time + 604800;

count := 0;

while not eof(f) do begin

readln(f, start_process, end_process);

if (start_process < start_time) and ((end_process > start_time) or (end_process = 0)) then

count := count + 1;

if (start_process >= start_time) and (start_process <= end_time) then

time_process[start_process - start_time] := time_process[start_process - start_time] + 1;

if (end_process >= start_time) and (end_process <= end_time) then

time_process[end_process - start_time] := time_process[end_process - start_time] - 1;

end;

sum_time := 0;

max_process := 0;

for i := 1 to 604800 do begin

count := count + time_process[i];

if count > max_process then begin

max_process := count;

sum_time := 0;

end;

if count = max_process then sum_time := sum_time + 1;

end;

writeln(max_process, ' ', sum_time);

end.

 

В ре­зуль­та­те ра­бо­ты дан­но­го ал­го­рит­ма при вводе дан­ных из файла в усло­вии по­лу­ча­ем ответ  — 5000 46.

 

Ответ: 5000 46.

 

При­ме­ча­ние. Путь к файлу не­об­хо­ди­мо ука­зать со­глас­но рас­по­ло­же­нию файла на Вашем ком­пью­те­ре.

 

При­ведём дру­гое ре­ше­ние на языке Python.

f = open("26 (7).txt")

n = int(f.readline())

start_time = 1633305600

end_time = start_time + 604800

count = 0

time_process = [0 for i in range(0, 604801)]

for i in f:

start_process, end_process = i.split()

if (int(start_process) < start_time) and ((int(end_process) > start_time) or (int(end_process) == 0)):

count = count + 1

if (int(start_process) >= start_time) and (int(start_process) <= end_time):

time_process[int(start_process) - start_time] = time_process[int(start_process) - start_time] + 1

if (int(end_process) >= start_time) and (int(end_process) <= end_time):

time_process[int(end_process) - start_time] = time_process[int(end_process) - start_time] - 1

sum_time = 0

max_process = 0

for i in range(1, 604801):

count = count + time_process[i]

if count > max_process:

max_process = count

sum_time = 0

if count == max_process:

sum_time = sum_time + 1

print(max_process, sum_time)

 

При­ведём ре­ше­ние Мат­вея Кур­чен­ко на языке Python.

f = open('26.txt')

n = int(f.readline())

x0 = 1633046400

y0 = x0 + 31*24*60*60

pr = [0]*(y0-x0+1)

for i in range(n):

a, b = map(int, f.readline().split())

a = max(a, x0)

if b == 0:

pr[a-x0] += 1

else:

pr[a-x0] += 1

pr[b-x0] -= 1

for i in range(1, len(pr)):

pr[i] += pr[i-1]

x1 = 1633305600

y1 = x1 + 7*24*60*60

mx = t = 0

for i in range(x1-x0, y1-x0):

if pr[i] > mx:

mx = pr[i]

t = 0

if pr[i] == mx:

t += 1

print(mx, t)


Аналоги к заданию № 40742: 41001 Все

Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026