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

Рассмотрим пример. Пусть t=100t=100, d=20d=20 и задано 3 промежутка недоступности связи: (5;25), (27;40), (75;90)(5;25),(27;40),(75;90). Тогда потребуется восемь сеансов связи, которые можно провести в моменты времени 0, 5, 25,45, 65, 75,90,1000,5,25,45,65,75,90,100. Конкретное расписание может быть другим, но в любом случае количество сеансов не может быть меньше восьми.

Ваша программа должна по имеющейся информации найти минимальное возможное количество сеансов связи.

Формат входных данных
В первой строке через пробел записаны три натуральных числа nn, dd и tt — количество интервалов недоступности связи, максимальный интервал между между сеансами и время, на которое составляется расписание. n\leq 200000n≤200000, d,t\leq 10^{9}d,t≤10
9
. Далее в nn строках заданы по два целых неотрицательных числа a_ia
i

и b_ib
i

— начало и конец каждого интервала недоступности связи. b_i-a_i\leq db
i

−a
i

≤d. Интервалы недоступности связи не пересекаются, каждый следующий интервал начинается строго после окончания предыдущего. 0\leq a_1 1

1

2

2

<… n

n

≤t.

Формат выходных данных
Вывести одно число — количество сеансов связи в графике.

Методика проверки
Программа проверяется на 25 тестах. Прохождение каждого теста оценивается в 0. Тест из условия задачи при проверке не используется.

В первых десяти тестах t\leq 1000t≤1000. В следующих 10 тестах t\leq 10^6t≤10
6
.

Sample Input:
3 20 100
5 25
27 40
75 90

Sample Output:
8

👇

Увидеть ответ

Ответ:

gsgshhshsbababa

24.06.2020

n, d, t = map(int, input().split())

p =[list(map(int, input().split())) for i in range(n)]

c = 0

i = 0

r = 1

while c < t:

r += 1

c += d

for j in range(i, n):

if p[j][0] < c < p[j][1]:

c = p[j][0]

i = j

break

print(r)

Объяснение:

4,8(93 оценок)

Открыть все ответы

Ответ:

MrDackes

24.06.2020

1. Вот так это пишется с функцией

// PascalABC.NET 3.1, сборка 1200 от 13.03.2016
function IsPrime(n:integer):boolean;
begin
if n<4 then Result:=True
else begin
    var found:= (n mod 2 = 0);
    var p:=3;
    while (not found) and (sqr(p)<=n) do
      begin
      found:=(n mod p = 0);
      p+=2
      end;
    Result:=not found
    end
end;

begin
Writeln('k=',ArrRandom(ReadInteger('n='),1,999).Println.
    Where(x->IsPrime(x)).Count)
end.

Тестовое решение:
n= 10
401 828 780 444 694 965 23 341 673 875
k=3

2. А вот так это пишется с процедурой

// PascalABC.NET 3.1, сборка 1200 от 13.03.2016
procedure IsPrime(n:integer; var res:boolean);
begin
if n<4 then res:=True
else begin
    var found:= (n mod 2 = 0);
    var p:=3;
    while (not found) and (sqr(p)<=n) do
      begin
      found:=(n mod p = 0);
      p+=2
      end;
    res:=not found
    end
end;

begin
var a:=ArrRandom(ReadInteger('n='),1,999); a.Println;
var k:=0;
var prime:boolean;
foreach var e in a do begin
    IsPrime(e,prime);
    if Prime then Inc(k)
    end;
Writeln('k=',k)
end.

Тестовое решение:
n= 12
199 43 71 365 417 904 170 212 694 103 161 689
k=4

4,8(69 оценок)

Ответ: