Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

09.05.2013, 00:50. Просмотров 1567. Ответов 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 минуты
Хотя, я не брезгую, код тоже не помешает.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2013, 00:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Два указателя. Сложно (C++):

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

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

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

Как сравнить два указателя типа 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; ...

Почему увеличение указателя на sizeof(тип) не тождественно инкременту этого же указателя? - C++
Всем доброго дня.:) Можете обьяснить ,почему при инкриментировании указателя,его значение(адресс) увеличивается на 4 (размер int в...

Как сделать функцию от указателя на класс и указателя на метод? - C++
Не получается сделать функцию, параметрами которой являются указатель на класс и на метод. Обращаться к классу нужно именно по указателю,...

19
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
09.05.2013, 02:01 #2
Ternsip, думаю что генерацию последовательности ускорить нельзя. Хотя bi напоминает конгруэнтную последовательность, и если можно бы было узнать ее период >_> Самому мне думать лень, так что по теме раз фича, два фича. Надеюсь, что это тебе как-то поможет.
1
ssXXss
266 / 188 / 10
Регистрация: 15.01.2011
Сообщений: 681
09.05.2013, 02:34 #3
а тут точно так - bi = (A · bi-1 + B) mod C а не так bi = (A · b0-1 + B) mod C ?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
09.05.2013, 06:08 #4
еще раз повторю общую просьбу: публикуйте ссылку на тестер.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 16:53  [ТС] #5
ssXXss, да, там b0 опечатка
salam, http://acm.sgu.ru/univer/problem.php?contest=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;
}
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
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");
}
В выводе нумерация элементов массива начинается с единицы.
1
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 18:29  [ТС] #7
nonedark2008, у вас сейчас квадратичный, медленный алгоритм, он не подходит, по времени не пройдёт
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
09.05.2013, 18:53 #8
Ternsip, ок, увидел. Все из-за двойного цикла. Я его писал без учета отсортированности массива. А так, подойдет та часть, что вы сами написал... Тогда удастся избежать двойного цикла, а значит и сложность будет nlogn.

Добавлено через 16 минут
А алгоритм достаточно понятен. Мы для каждого префикса в массиве находим префиксы больший либо равный текущему и берем тот, у которого индекс будет самым большим. Если идекс одного префикса больше индекса другого и второй префикс >= первому, то сумма элементов между индексов будет >= 0.
Выбирая префикс с самым большим индексом мы выбираем самую длинную цепочку.
А дальше, просто ижем максимум разности maxInd и ind - это будет длина самой длинной цеопчки, сумма которой больше нуля.
0
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 секунды проходить
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
09.05.2013, 19:12 #10
Цитата Сообщение от Ternsip Посмотреть сообщение
curb = (a * curb + b) % c; cura = x * curb + y;
Проверь, мне кажется что строчки перепутаны местами.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 19:20  [ТС] #11
nonedark2008, нет, тут всё ок
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 19:20 #12
Цитата Сообщение от Ternsip Посмотреть сообщение
может из-за make_pair() так медленно ? по идее N Log N должно за 0.5 секунды проходить
может быть, попробуй написать свой pair
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
09.05.2013, 19:34 #13
Ternsip, в вашем решении больше всего жрет сортировка - как и должно быть. Чаще всего вызывается оператор сравнения в сортировке, что плохо, т.к. для сравнения двух чисел вызывается отдельный метод.
Так что лучше написать свой алгоритм сортировки, отказаться от использования векторов в пользу массивов, отказаться от использования потокового ввода/вывода в пользу printf/scanf.
Чтобы самому проверять что жрет больше всего - нужно использовать анализатор производительности, например он встроен в VS, а также он есть в утилитах от Intel.

Добавлено через 5 минут
Ternsip, кстати, ты вроде забыл про условие, что если встретятся одинаковые ответы, то нужно выбрать с наименьшим индексом. Так что в последнем цыкле еще нужно проверять на >=, а внутри выбирать с наименьшим индексом.
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
09.05.2013, 20:00 #14
Цитата Сообщение от Ternsip Посмотреть сообщение
по идее N Log N должно за 0.5 секунды проходить
не должно. тут довольно простая линия.
0
nonedark2008
931 / 670 / 147
Регистрация: 28.07.2012
Сообщений: 1,828
09.05.2013, 20:05 #15
Цитата Сообщение от salam Посмотреть сообщение
не должно. тут довольно простая линия.
Ну хоть по оценке сложности судить о точном времени, но на моем ноуте при максимальном размере n программа выполняется примерно за 0.57 секунды, так что после оптимизации будет самое то!
0
09.05.2013, 20:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 20:05
Привет! Вот еще темы с ответами:

Преобразование кода без указателя в код с использованием указателя - C++
Правильно ли выполнил? Исходный код без указателя #include &lt;iostream&gt; #include &lt;cstdlib&gt; #include &lt;fstream&gt; using namespace...

В чём отличие константного указателя и указателя на константу? - C++
int *const p1 и int const* p2 Объясните мне в чём тут отличие.

Написать обработчик исключений ситуации при преобразовании указателя на класс B до указателя на абстрактный класс А ... - C++
Написать обработчик исключений ситуации при преобразовании указателя на класс B до указателя на абстрактный класс А ... как сделать...

Перезаписать память начиная с указателя Bitmap[1] элементами начиная с указателя Bitmap[0] - C++
Задан массив из 3 указателей Bitmap, по адресу Bitmap необходимо записать 480*640 элементов из массива Bitmap. В последнем цикле for выдает...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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