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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
#1

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

05.06.2013, 00:42. Просмотров 382. Ответов 8
Метки нет (Все метки)

вообщем нам даны числа 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++
Дан отрезок с координатами точек А (X1 , Y1) и В ( X2, Y21 ) .Написать программу, определяющую его длину в случае, если этот отрезок лежит...

Вводится номер семестра N <= 10. Вывести фразу «Я проучился N семестров », согласовав слово« семестр »с числом N. Определить номер курса - C++
начало кода есть , но он не показывает что нужно , там надо наверное через if-else !! но не получается:ireful: #include &lt;stdio.h&gt; ...

Вывести данные о багаже пассажиров, упорядочить их по весу вещей, а в случае равенства - по количеству вещей - C++
Подскажите в чем проблема! При запуске программы вылетает Вывести данные о багаже пассажиров, упорядочить их по весу вещей, а в случае...

Правильно ли и в каком случае может быть ошибка? - C++
Определить произведение элементов массива, расположенных между максимальным и «центральным» элементами массива (предполагается, что число...

В каком случае данная программа выведет слово “Yes” ? - C++
В каком случае данная программа выведет слово “Yes” ? int main() { int fl = 0; int f , i; for ( i = 0; i &lt; 20; i++ ) ...

В каком случае данная программа выведет слово ДА - C++
int main() { int fl = 0; int f , i; for (i = 0; i &lt; 20; i++) scanf ( &quot;%d&quot;, &amp;f ); for (i = 0; i &lt; 19; i++) if ( f ==...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:46     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #2
yutr777, хотел предложить дерево отрезков или дерево фенвика, но при таких ограничениях на m не пойдет новерное
yutr777
5 / 5 / 0
Регистрация: 07.04.2013
Сообщений: 85
05.06.2013, 00:49  [ТС]     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #3
Цитата Сообщение от aram_gyumri Посмотреть сообщение
yutr777, хотел предложить дерево отрезков или дерево фенвика, но при таких ограничениях на m не пойдет новерное
тут м не причем....тут все дело в кол-ве запросов.
напишите хоть перебор какой-нибудь
очень надо,,,спасибо заранее!
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:51     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #4
кажись придумал решение, создаем массив туда кидаем тройки {начало отрезка,конец отрезка,минимум}, при каждом запросе находим отрезки с которыми пересекается данный и если заданный минимум больше или ровно каждому минимуму то это не фальшивый запрос

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

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

при дереве отрезков причем там нужно 4*м памяти а это где-то 4ГБ будет
но ведь тут надо сокращать отрезки
и ведь может быть так что один отрезок накроет целых пять...что тогда?
можете закодить сам алгоритм поиска?
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 00:57     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #6
Цитата Сообщение от yutr777 Посмотреть сообщение
и ведь может быть так что один отрезок накроет целых пять...что тогда?
наверное непонятно написал алго работает и если покрывает n отрезков
если нынешний минимум>=max{мин_1,мин_2,...,мин_n} то все нормально если нет то лживый запрос
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
05.06.2013, 06:16     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка #7
можно "официальный" вариант условия?
yutr777
5 / 5 / 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     определить, в каком случае данные обманчивы.И вывести номер обманчивого отрезка
Еще ссылки по теме:

В каком случае проверка условия выполняется быстрее? - C++
В каком случае проверка условия выполняется быстрее? while(1); или while(true); Ведь в одном из этих случаев должно происходить...

В каком случае может понадобиться эксклюзивный доступ. Shared mutex - C++
Допустим у меня есть некоторый вектор с классами. Есть пул тредов которые могут как читать, так и писать. Читаю из вектора я обычным...

Есть булева функция. В каком случае будет выведено в лог сообщение “Hello”? - C++
Есть фрагмент кода. вроде на С++. если нет, то на каком скажите пожалуйста. Есть булева функция (приведена ниже). В каком случае будет...

Определить столбец с максимальным по модулю значением этой суммы и вывести его номер на экран - C++
В квадратной матрице размером Т*Т, имеющей имя MKA , содержаться целые числа, Т-число строк и столбцов Ввести элементы матрецы с...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru