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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

Два указателя. Сложно - C++

09.05.2013, 00:50. Просмотров 1370. Ответов 19

Вот есть задача, с которой я не могу справиться, мне не нужен ваш код, а будет вполне достаточно словесного описания алгоритма или сути его работы. Решается он через 2 указателя, может потребуется сортировка. Никак не могу додуматься до алгоритма. Help.
Учтите, задача не простая, посмотрите на ограничения.

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 262144 KB.

Дана последовательность целых чисел a1, a2,..., an. Требуется найти такую пару (index, length), чтобы сумма чисел [aindex, aindex+1,..., aindex+length-1] была положительной. При этом length должно быть наибольшим возможным. Если ответов несколько, выберите ответ с меньшим index.

В этой задаче последовательность ai будет задаваться в следующем виде: bi = (A · bi-1 + B) mod C, b0 = S, ai = X · bi + Y, где X, Y, A, B, C, S будут числами, заданными во входном файле.

mod — это оператор взятия остатка. Генерацию последовательности делайте в 64-битном типе.


Входные данные
В первой строке содержится число n (1 ≤ n ≤ 5000000). Во второй строке записаны числа X, Y, A, B, C и S, разделенные пробелами (|X| ≤ 1000, |Y| ≤ 10^9, 0 < C ≤ 10^6, 0 ≤ A, B, S ≤ 10^6).


Выходные данные
Выведите числа index и length через пробел. Гарантируется, что length > 0.

Ввод :
7
1 -2 3 4 5 6
Вывод :
3 5

Добавлено через 2 минуты
Хотя, я не брезгую, код тоже не помешает.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2013, 00:50     Два указателя. Сложно
Посмотрите здесь:

Выбор(будет ли сложно изучать два языка Си и СИ++) - C++
доброго дня. будет ли сложно изучать два языка (Си и СИ++). имею ввиду в том смысле, что в своем учебном заведении мне предстоит изучать...

в функцию передается два строковых указателя - C++
Добрый день! Функции передается два указателя на массив строк. Пользователь вводит строки, необходимо найти количество совпадений...

Как сравнить два указателя типа char? - C++
char *p1; p1 = new char; p1 = &quot;qwert&quot;; char *p2; p2 = new char; p2 = &quot;zz&quot;; if(*p1==*p2) cout &lt;&lt; &quot;Равны! &quot;&lt;&lt; endl; ...

Можно ли объявить два указателя на одну функцию? - C++
есть функция Send(uint type, char*data); но иногда второй аргумент const char*. можно ли сделать так чтобы на одну функцию Send указывали...

кому не сложно - C++
вот программа которая находит площадь пересечения прямоугольников #include &quot;stdafx.h&quot; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include...

C++ массив. Сложно - C++
Дан одномерный массив, состоящий из N вещественных элементов. 8.1. Заполнить массив случайными числами. 8.2. Найти минимальный...

Посмотрите если не сложно - C++
Уважаемые форумчане.Уже пол дня сижу, и не имею малейшего предпочтения как ее решить..... Если можно, то помогите хотя бы как то. :wall: ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 02:01     Два указателя. Сложно #2
Ternsip, думаю что генерацию последовательности ускорить нельзя. Хотя bi напоминает конгруэнтную последовательность, и если можно бы было узнать ее период >_> Самому мне думать лень, так что по теме раз фича, два фича. Надеюсь, что это тебе как-то поможет.
ssXXss
264 / 186 / 10
Регистрация: 15.01.2011
Сообщений: 668
09.05.2013, 02:34     Два указателя. Сложно #3
а тут точно так - bi = (A · bi-1 + B) mod C а не так bi = (A · b0-1 + B) mod C ?
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
09.05.2013, 06:08     Два указателя. Сложно #4
еще раз повторю общую просьбу: публикуйте ссылку на тестер.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 16:53  [ТС]     Два указателя. Сложно #5
ssXXss, да, там b0 опечатка
salam, http://acm.sgu.ru/univer/problem.php...=0&problem=436
http://acm.sgu.ru/univer/

Добавлено через 8 секунд
nonedark2008, спасибо

Добавлено через 5 часов 21 минуту
nonedark2008, первая фича http://stackoverflow.com/questions/1...-or-equal-to-k Попытался по ней реализовать то, что там написано, вот что накатал, не работает, логика не ясна. arr у меня это массив частичных сумм
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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std; 
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    vector <int> arr;
    arr.push_back(0);
    arr.push_back(20);
    arr.push_back(-10);
    arr.push_back(20);
    arr.push_back(50);
    arr.push_back(50);
    arr.push_back(-40);
    vector < pair<int, int> > pr(arr.size());
    for(int i = 0; i < pr.size(); i++) {
        pr[i] = make_pair(arr[i], i);
    }
    sort(pr.begin(), pr.end());
    vector <int> lef(pr.size(), 0);
    for (int i = 1; i < pr.size(); i++) {
        if (pr[i].first == pr[i-1].first) 
            lef[i] = lef[i-1];
        else 
            lef[i] = i;
    }
    vector <int> maxid(pr.size(), pr[pr.size()-1].second);
    for (int i = maxid.size() - 2; i >= 0; i--) {
        maxid[i] = max(maxid[i+1], pr[i].second);
    }
    int idx = 0, len = 0;   
    for (int i = 0; i < maxid.size(); i++) {
        int ans = maxid[i] - lef[i];
        if (ans > len) {
            len = ans;
            idx = lef[i];
        }
    }
    cout << idx << " " << len;
    return 0;
}
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 18:24     Два указателя. Сложно #6
Ternsip, не сильно проверял, но вроде работает:
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
bool comp( const pair<int, int> &a, const pair<int, int> &b )
{
  if (a.second < b.second)
    return true;
  return false;
}
 
void main( void )
{
  vector<int> arr(6);
 
  arr[0] = -10, arr[1] = -2, arr[2] = 3, arr[3] = 3, arr[4] = 0, arr[5] = -4;
  
  for (int i = 0; i < 6; ++i)
    cout << arr[i] << ' ';
  cout << endl;
  int sum = 0;
  vector<pair<int, int>> pref(6 + 1);
  pref[0].first = pref[0].second = 0;
  for (int i = 1; i < 6 + 1; ++i)
  {
    sum += arr[i - 1];
    pref[i].first = i + 1;
    pref[i].second = sum;
  }
 
  std::sort(pref.begin(), pref.end(), comp);
  vector<int> maxInd(6 + 1);
 
  for(int i = 0; i < 6 + 1; ++i)
  {
    maxInd[i] = pref[i].first;
    for (int j = i + 1; j < 6 + 1; ++j)
    {
      if (pref[j].second >= pref[i].second && pref[j].first > maxInd[i])
        maxInd[i] = pref[j].first;
    }
  }
 
  int max = 0;
  for (int i = 1; i < 6 + 1; ++i)
  {
    if (maxInd[i] - pref[i].first > maxInd[max] - pref[max].first)
      max = i;
  }
 
  cout << pref[max].first << ' ' <<  maxInd[max] - pref[max].first << endl;
  system("pause");
}
В выводе нумерация элементов массива начинается с единицы.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 18:29  [ТС]     Два указателя. Сложно #7
nonedark2008, у вас сейчас квадратичный, медленный алгоритм, он не подходит, по времени не пройдёт
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 18:53     Два указателя. Сложно #8
Ternsip, ок, увидел. Все из-за двойного цикла. Я его писал без учета отсортированности массива. А так, подойдет та часть, что вы сами написал... Тогда удастся избежать двойного цикла, а значит и сложность будет nlogn.

Добавлено через 16 минут
А алгоритм достаточно понятен. Мы для каждого префикса в массиве находим префиксы больший либо равный текущему и берем тот, у которого индекс будет самым большим. Если идекс одного префикса больше индекса другого и второй префикс >= первому, то сумма элементов между индексов будет >= 0.
Выбирая префикс с самым большим индексом мы выбираем самую длинную цепочку.
А дальше, просто ижем максимум разности maxInd и ind - это будет длина самой длинной цеопчки, сумма которой больше нуля.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 19:11  [ТС]     Два указателя. Сложно #9
nonedark2008, вот переписал под свой лад
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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std; 
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, x, y, a, b, c, s;
    cin >> n >> x >> y >> a >> b >> c >> s;
    long long curb = s, cura, sum = 0;
    vector < pair<long long, int> > pref(n + 1);
    pref[0] = make_pair(0, 0); 
    for (int i = 1; i <= n; i++){
        curb = (a * curb + b) % c;
        cura = x * curb + y;
        sum += cura;
        pref[i] = make_pair(sum, i + 1); 
    }
    sort(pref.begin(), pref.end()); // пары сравниваются сначала по 1-ому, затем по второму эл-у
    vector <int> maxid(n + 1, pref[n].second);
    for (int i = n - 1; i >= 0; i--) {
        maxid[i] = max(maxid[i + 1], pref[i].second);
    }
    int max = 0;      
    for (int i = 1; i <= n; i++) {
        if (maxid[i] - pref[i].second > maxid[max] - pref[max].second) {
            max = i;
        }
    }
    cout << pref[max].second << " " << maxid[max] - pref[max].second;
    return 0;
}
Добавлено через 1 минуту
nonedark2008, щас затещу

Добавлено через 2 минуты
nonedark2008, 2/90 видимо сдесь какой то архикосяк, сейчас попробую понять вашу идею, пока сам не допёр ещё

Добавлено через 36 секунд
nonedark2008, кстати, TL очень много за NlogN не проходит решение

Добавлено через 1 минуту
nonedark2008, может из-за make_pair() так медленно ? по идее N Log N должно за 0.5 секунды проходить
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 19:12     Два указателя. Сложно #10
Цитата Сообщение от Ternsip Посмотреть сообщение
curb = (a * curb + b) % c; cura = x * curb + y;
Проверь, мне кажется что строчки перепутаны местами.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 19:20  [ТС]     Два указателя. Сложно #11
nonedark2008, нет, тут всё ок
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 19:20     Два указателя. Сложно #12
Цитата Сообщение от Ternsip Посмотреть сообщение
может из-за make_pair() так медленно ? по идее N Log N должно за 0.5 секунды проходить
может быть, попробуй написать свой pair
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 19:34     Два указателя. Сложно #13
Ternsip, в вашем решении больше всего жрет сортировка - как и должно быть. Чаще всего вызывается оператор сравнения в сортировке, что плохо, т.к. для сравнения двух чисел вызывается отдельный метод.
Так что лучше написать свой алгоритм сортировки, отказаться от использования векторов в пользу массивов, отказаться от использования потокового ввода/вывода в пользу printf/scanf.
Чтобы самому проверять что жрет больше всего - нужно использовать анализатор производительности, например он встроен в VS, а также он есть в утилитах от Intel.

Добавлено через 5 минут
Ternsip, кстати, ты вроде забыл про условие, что если встретятся одинаковые ответы, то нужно выбрать с наименьшим индексом. Так что в последнем цыкле еще нужно проверять на >=, а внутри выбирать с наименьшим индексом.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
09.05.2013, 20:00     Два указателя. Сложно #14
Цитата Сообщение от Ternsip Посмотреть сообщение
по идее N Log N должно за 0.5 секунды проходить
не должно. тут довольно простая линия.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 20:05     Два указателя. Сложно
Еще ссылки по теме:

Зделайте на С++ пж если не сложно - C++
Даний одномірний масив А, що складається з N елементів. Перенести в початок масиву всі парні елементи, а в кінець масиву - усі непарні.

Исправьте кому не сложно - C++
Здравствуйте, поправьте пожалуйста код кому не сложно компилятор dev c++ 4.9.9.2 #include &quot;iostream&quot; #include &lt;string.h&gt; using...

Подправьте код кому не сложно - C++
#include &quot;iostream&quot; #include &lt;stdio.h&gt; using namespace std; class Rastenie { /*îïèñàíèå ýëåìåíòîâ êëàññà Ðàñòåíèé*/ ...

Сложно найти ошибку отладчиком - C++
Здравствуйте, столкнулся с такой проблемой, в курсовой вылетает иногда ошибка list iterator not dereferencable Понятно, что это...

Нахождение чисел в матрице. Очень сложно - C++
#include &quot;stdafx.h&quot; #include &quot;iostream&quot; #include &quot;conio.h&quot; #include &quot;math.h&quot; #include &quot;time.h&quot; using namespace std; #define...


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

Или воспользуйтесь поиском по форуму:
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
09.05.2013, 20:05     Два указателя. Сложно #15
Цитата Сообщение от salam Посмотреть сообщение
не должно. тут довольно простая линия.
Ну хоть по оценке сложности судить о точном времени, но на моем ноуте при максимальном размере n программа выполняется примерно за 0.57 секунды, так что после оптимизации будет самое то!
Yandex
Объявления
09.05.2013, 20:05     Два указателя. Сложно
Ответ Создать тему
Опции темы

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