Форум программистов, компьютерный форум CyberForum.ru

определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка - C++

Восстановить пароль Регистрация
 
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
05.06.2013, 00:42     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #1
вообщем нам даны числа m и n
m-длина луча на котором буду отрезки
далее идет n*3 чисел
в каждой строке по 3 числа
x y z
x-откуда начинается
y-где кончается
z-какая минимальная цифра написана на этом отрезке
нужно определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка
например
100 4
1 10 5
7 7 5
1 6 2
2 3 4
ответ 4
т.к. сначала на участке с 1 по 10 мин=5
дальше поиск сузился и мы получили что только на 7 клетке стоит 5
дальше со 2ой до 6 стоит 2-верно
а потом говорят что со 2ой до 3ей 4 но на самом деле 2!
ответ 4.
p.s. вроде дерево...но как его тут пристроить....О_о

Добавлено через 2 минуты
n<=20000
m<=1000000000
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2013, 00:42     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка
Посмотрите здесь:

C++ Даны координаты точки на плоскости. Определить и вывести на экран номер квадранта, в который попадает точка
Определить длину отрезка в случае, если он лежит в первом квадранте C++
Правильно ли и в каком случае может быть ошибка? C++
C++ В каком случае проверка условия выполняется быстрее?
Вводится номер семестра N <= 10. Вывести фразу «Я проучился N семестров », согласовав слово« семестр »с числом N. Определить номер курса C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:46     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #2
yutr777, хотел предложить дерево отрезков или дерево фенвика, но при таких ограничениях на m не пойдет новерное
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
05.06.2013, 00:49  [ТС]     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #3
Цитата Сообщение от aram_gyumri Посмотреть сообщение
yutr777, хотел предложить дерево отрезков или дерево фенвика, но при таких ограничениях на m не пойдет новерное
тут м не причем....тут все дело в кол-ве запросов.
напишите хоть перебор какой-нибудь
очень надо,,,спасибо заранее!
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:51     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #4
кажись придумал решение, создаем массив туда кидаем тройки {начало отрезка,конец отрезка,минимум}, при каждом запросе находим отрезки с которыми пересекается данный и если заданный минимум больше или ровно каждому минимуму то это не фальшивый запрос

Добавлено через 55 секунд
Цитата Сообщение от yutr777 Посмотреть сообщение
тут м не причем
при дереве отрезков причем там нужно 4*м памяти а это где-то 4ГБ будет
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
05.06.2013, 00:54  [ТС]     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #5
Цитата Сообщение от aram_gyumri Посмотреть сообщение
кажись придумал решение, создаем массив туда кидаем тройки {начало отрезка,конец отрезка,минимум}, при каждом запросе находим отрезки с которыми пересекается данный и если заданный минимум больше или ровно каждому минимуму то это не фальшивый запрос

Добавлено через 55 секунд

при дереве отрезков причем там нужно 4*м памяти а это где-то 4ГБ будет
но ведь тут надо сокращать отрезки
и ведь может быть так что один отрезок накроет целых пять...что тогда?
можете закодить сам алгоритм поиска?
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:57     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #6
Цитата Сообщение от yutr777 Посмотреть сообщение
и ведь может быть так что один отрезок накроет целых пять...что тогда?
наверное непонятно написал алго работает и если покрывает n отрезков
если нынешний минимум>=max{мин_1,мин_2,...,мин_n} то все нормально если нет то лживый запрос
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
05.06.2013, 06:16     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #7
можно "официальный" вариант условия?
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
05.06.2013, 20:07  [ТС]     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #8
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
#include <iostream>
 
using namespace std;
 
struct otrezki
{
       int x,y,z;
};
 
int main()
{
int n,m;
int ans=0;
cin >> m >> n;
otrezki a[40003];
bool b[40003]={false};
for (int o=1;o<=n;o++)
{
    cin >> a[o].x >> a[o].y >> a[o].z;
    if (ans!=0){continue;}
    bool f=false,check=false;
      for (int i=1;i<o;i++)
      {
          if (b[i]==true){continue;}
          if (a[o].x<=a[i].x && a[o].y>=a[i].x && a[o].x>=a[i].x && a[o].z==a[i].z)
             {
              a[o].x=a[i].x;
              b[i]=true;
              f=true;
              break;
             }
          if (a[o].x<=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z)
             {
              a[o].x=a[i].x;
              a[o].y=a[i].y;
              b[i]=true;
              f=true;
              break;
             }
           if (a[o].x>=a[i].x && a[o].y<=a[i].y && a[i].z==a[o].z)
             {
              b[i]=true;
              f=true;
              break;
             }
           if (a[o].x>=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z)
              {
               f=true;
               b[i]=true;
               a[o].y=a[i].y;
               break;
              }
           if ((a[o].x<=a[i].x && a[o].y>=a[i].x && a[o].x>=a[i].x && a[o].z!=a[i].z)||(a[o].x<=a[i].x && a[o].y>=a[i].y && a[i].z!=a[o].z)||(a[o].x>=a[i].x && a[o].y<=a[i].y && a[i].z!=a[o].z)||(a[o].x>=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z))
           {
                               check=true;
                               break;
           }
      }
      if (check==true){ans=o;continue;}
}
cout << ans;
system("PAUSE >> void");
return 0;
}
вот что я написал
вроде как бы работает)
гляньте, мош какой косяк есть

Добавлено через 9 минут
Цитата Сообщение от yutr777 Посмотреть сообщение
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
#include <iostream>
 
using namespace std;
 
struct otrezki
{
       int x,y,z;
};
 
int main()
{
int n,m;
int ans=0;
cin >> m >> n;
otrezki a[40003];
bool b[40003]={false};
for (int o=1;o<=n;o++)
{
    cin >> a[o].x >> a[o].y >> a[o].z;
    if (ans!=0){continue;}
    bool f=false,check=false;
      for (int i=1;i<o;i++)
      {
          if (b[i]==true){continue;}
          if (a[o].x<=a[i].x && a[o].y>=a[i].x && a[o].x>=a[i].x && a[o].z==a[i].z)
             {
              a[o].x=a[i].x;
              b[i]=true;
              f=true;
              break;
             }
          if (a[o].x<=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z)
             {
              a[o].x=a[i].x;
              a[o].y=a[i].y;
              b[i]=true;
              f=true;
              break;
             }
           if (a[o].x>=a[i].x && a[o].y<=a[i].y && a[i].z==a[o].z)
             {
              b[i]=true;
              f=true;
              break;
             }
           if (a[o].x>=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z)
              {
               f=true;
               b[i]=true;
               a[o].y=a[i].y;
               break;
              }
           if ((a[o].x<=a[i].x && a[o].y>=a[i].x && a[o].x>=a[i].x && a[o].z!=a[i].z)||(a[o].x<=a[i].x && a[o].y>=a[i].y && a[i].z!=a[o].z)||(a[o].x>=a[i].x && a[o].y<=a[i].y && a[i].z!=a[o].z)||(a[o].x>=a[i].x && a[o].y>=a[i].y && a[i].z==a[o].z))
           {
                               check=true;
                               break;
           }
      }
      if (check==true){ans=o;continue;}
}
cout << ans;
system("PAUSE >> void");
return 0;
}
вот что я написал
вроде как бы работает)
гляньте, мош какой косяк есть
нашел ошибку в одном ифе...исправил...в первом ифе лажа)
и в конце лажа)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 20:21     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка
Еще ссылки по теме:

Дан номер единицы длины и длина отрезка L в этих единицах. Вывести длину данного отрезка в метрах C++
C++ В каком случае данная программа выведет слово “Yes” ?
В каком случае данная программа выведет слово ДА C++

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

Или воспользуйтесь поиском по форуму:
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 20:21     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #9
yutr777, прочитайте сначала весь инпут а потом уж проверяйте
Yandex
Объявления
05.06.2013, 20:21     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка
Ответ Создать тему
Опции темы

Текущее время: 02:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru