Промежутки

@max_besheniy · Регистрация: 21.11.2013

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

Есть задача:
Поликарп очень любит учиться в школе и всегда добросовестно выполняет домашнее задание. У Поликарпа никогда не было проблем с естественно-научными дисциплинами, поскольку прапрапрадедом Поликарпа был великий физик Зейнштейн. Но вот с историей у Поликарпа всегда были проблемы.

Всем известно, что в мировой истории произошло ровно N событий: i-ое событие продолжалось с a[i] по b[i] годы включительно (a[i] < b[i]). Поликарпу не составило никакого труда выучить даты начала и конца каждого из n событий истории (ему от прапрапрадеда генетически передалась также великолепная память). Но учитель дал задание не просто выучить даты начала и конца всех событий, а также выяснить для каждого события существует ли другое событие, включающее его. По мнению учителя Поликарпа событие j включает в себя событие i, если a[j] < a[i] и b[i] < b[j]. Ваша же задача проще: найдите количество событий, которые включены в какое-либо другое событие.
Входные данные:
Во входном потоке в первой строке дано целое число N ( N < 10000 )
В следующих N строках через пробел даны по 2 целых числа a[i] и b[i] - промежуток события.

Выходные данные:
Вывести единственное целое число.

Пример входного файла (input.txt):
5
1 10
2 9
3 8
4 7
5 6
Пример выходного файла (output.txt):
4

Код мой вот

Pascal
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
var a,b:array[1..100000] of longint;
pr:array[1..100000] of boolean;
n,i,j,m,s,k:longint;
begin
readln(n);
fillchar(pr,sizeof(pr),false);
for i:=1 to n do
read(a[i],b[i]);
s:=0;
for j:=1 to n-1 do
for i:=j+1 to n do
if (a[j]<a[i])and(b[i]<b[j])and(pr[j]=false) then 
begin
inc(s);
pr[j]:=true;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]<a[j])and(b[j]<b[i])and(pr[i]=false) then 
begin
inc(s);
pr[i]:=true;
end;
writeln(s);
end.

Вроде бы задача простая, но не проходит половина тестов. Может я неправильно решал. Помогите

valeriikozlov · 22.12.2013, 01:35

первое:
эти два куска кода:

Сообщение от max_besheniy

Pascal
1
2
3
4
5
6
7
for j:=1 to n-1 do
for i:=j+1 to n do
if (a[j]<a[i])and(b[i]<b[j])and(pr[j]=false) then 
begin
inc(s);
pr[j]:=true;
end;

Сообщение от max_besheniy

Pascal
1
2
3
4
5
6
7
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]<a[j])and(b[j]<b[i])and(pr[i]=false) then 
begin
inc(s);
pr[i]:=true;
end;

выполняют одно и тоже.

второе.
рассмотрим любой из них:

Сообщение от max_besheniy

Pascal
1
2
3
4
5
6
7
for j:=1 to n-1 do
for i:=j+1 to n do
if (a[j]<a[i])and(b[i]<b[j])and(pr[j]=false) then 
begin
inc(s);
pr[j]:=true;
end;

здесь идет поиск когда событие j включает в себя событие i. И в этом коде (например при j равном 4) не рассматриваются варианты: включает в себя или нет событие j события с 1 по 3.
Поэтому правильнее будет вместо двух циклов написать один, например так:

Pascal
1
2
3
4
5
6
7
for j:=1 to n do
for i:=1 to n do
if (a[j]<a[i])and(b[i]<b[j])and(pr[j]=false) then 
begin
inc(s);
pr[j]:=true;
end;

@max_besheniy · 22.12.2013, 11:32 **[ТС]**

Все равно часть тестов не проходит что с вашим, что с моим решением

valeriikozlov · 22.12.2013, 12:47

Сообщение от max_besheniy

Все равно часть тестов не проходит что с вашим, что с моим решением

я немного недосмотрел: в цикле в обоих случаях замените pr[j] на pr[i]

@max_besheniy · 22.12.2013, 12:52 **[ТС]**

Так работает. Спасибо что помогли

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@max_besheniy 25 / 25 / 5 Регистрация: 21.11.2013 Сообщений: 208
	22.12.2013, 11:32 [ТС]
	Все равно часть тестов не проходит что с вашим, что с моим решением 0

@max_besheniy 25 / 25 / 5 Регистрация: 21.11.2013 Сообщений: 208
	22.12.2013, 12:52 [ТС]
	Так работает. Спасибо что помогли 0