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

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

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

Гроб настоящий! - C++

08.04.2013, 15:05. Просмотров 618. Ответов 11
Метки нет (Все метки)

Всем привет!
Помогите пожалуйста, напишите код решения этой задачи или объясните хотя бы идею...

{
Ограничение по времени, сек 2
Ограничение по памяти, мегабайт 64


Мальчику Пете очень нравится математика. Недавно он выписал открыл новую последовательность чисел и, назвав её в свою честь, тут же записал её на длинной ленте, чтобы не забыть. Всё бы хорошо, но у Пети есть младший брат Гена. Гене не очень нравится математика - он мечтает стать дизайнером. Вот и сейчас, увидев новую красивую ленточку, он решил вырезать её часть и украсить ей свою комнату. А чтобы украшению порадовался и Петя, Гена решил вырезать такую часть, чтобы сумма всех чисел на ней была бы как можно больше.

Входные данные

В первой строке входного файла записано число n (1 ≤ n ≤ 100000) - длина последовательности Пети. Во второй строке записаны числа a1, ..., an - сама последовательность( - 109 ≤ ai ≤ 109).

Выходные данные

Выходной файл должен содержать два числа - максимальную сумму, которую может получить Гена, и количество вариантов получить данную сумму.

Примеры тестов

Входные данные

5
2 3 0 -5 5

Выходные данные

5 4
}

Вот блин....сколько не пытался, ничего кроме O(N*N) не придумал
То что длинка, так это однозначно....но ещё и при N(квадрат) тут вообще...уууу...помогите с решением на 100.
Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
08.04.2013, 15:07     Гроб настоящий! #2
А задача то где? Телепат живёт на форуме игроделов.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
08.04.2013, 18:20     Гроб настоящий! #3
интересно... киньте ссылку на задачу, пожалуйста.

Добавлено через 55 минут
вроде норм решается. жду ссылку на тест.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
08.04.2013, 18:59  [ТС]     Гроб настоящий! #4
Цитата Сообщение от salam Посмотреть сообщение
интересно... киньте ссылку на задачу, пожалуйста.

Добавлено через 55 минут
вроде норм решается. жду ссылку на тест.
http://informatics.mccme.ru/moodle/m...ew.php?id=6444
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
08.04.2013, 19:53     Гроб настоящий! #5
с тестером бред какой-то... там только один тест...) притом - из условия...)
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
08.04.2013, 19:56  [ТС]     Гроб настоящий! #6
Цитата Сообщение от salam Посмотреть сообщение
с тестером бред какой-то... там только один тест...) притом - из условия...)
ну а вообще расскажите идею решения или код скиньте...пожалуйста, очень нужно и интересно....Московская олимпиада все таки))
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
08.04.2013, 19:59     Гроб настоящий! #7
я не могу дать вам свой код, поскольку не уверен, что в нем нет бага.
почитайте вот это http://e-maxx.ru/algo/maximum_average_segment
если интересна московская олимпиада, могу скинуть вам мои решения нескольких задач с нее.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
08.04.2013, 20:00  [ТС]     Гроб настоящий! #8
Цитата Сообщение от salam Посмотреть сообщение
с тестером бред какой-то... там только один тест...) притом - из условия...)
вам надо зарегистрироваться на сайте, потом отправить свое решение, выбрав Я/П и вам скажет что да как
Все банально просто
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
08.04.2013, 20:01     Гроб настоящий! #9
я умею обращаться с тестерами, друг мой, поверьте...)
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
08.04.2013, 20:02  [ТС]     Гроб настоящий! #10
Цитата Сообщение от salam Посмотреть сообщение
я не могу дать вам свой код, поскольку не уверен, что в нем нет бага.
почитайте вот это http://e-maxx.ru/algo/maximum_average_segment
если интересна московская олимпиада, могу скинуть вам мои решения нескольких задач с нее.
да, было бы не плохо, ещё и условия тоже)
ну все же...есть там баг или нет....хотя какую-то идею хочется посмотреть)
я разберусь в коде)))
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
08.04.2013, 20:13     Гроб настоящий! #11
пожалуйста...

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/* All the code in this file belongs to the Govnocoding Inc. USA. California. 2013 */
 
/* C header files */
#include <cmath> 
#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib> 
 
/* C++ header files */
#include <map> 
#include <set> 
#include <deque> 
#include <limits> 
#include <string> 
#include <vector>  
#include <utility>
#include <algorithm>
 
/* C++ input / output */
#include <fstream> 
#include <iomanip>
#include <iostream>
 
using namespace std;
 
/* C++ types */
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
 
/* Pairs */
#define ft first
#define sc second
#define mp(a, b) make_pair((a), (b))
typedef pair <ll, ll> pll;
typedef pair <int, int> pi;
typedef pair <double, double> pd;
 
/* Single vectors */
#define pop() pop_back()
#define push(s) push_back(s)
typedef vector <pi> vec_pi;
typedef vector <int> vec_i;
typedef vector <bool> vec_b;
typedef vector <char> vec_c;
typedef vector <double> vec_d;
typedef vector <long long> vec_ll; 
 
/* Macroses */
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define len(s) s.length()
#define maxV(type) numeric_limits<type>::max()
#define minV(type) numeric_limits<type>::min()
#define sf(a, b, i) for(size_t (i)=(a); (i) < (b); (i)++)
 
int main()
{
   //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
   cin.tie(0);
   ios_base::sync_with_stdio(0);
    
   int n;
   int cmax = 0;
   ll mmax = minV(ll);
   int l = 0;
   int a[100000];
   ll  d[100000];
   ll sum[100000];
   cin >> n;
   for(int i=0; i < n; i++)
      cin >> a[i];
   d[0] = a[0];
   sum[0] = a[0];
   for(int i=1; i < n; i++)
      sum[i] = sum[i-1] + a[i];
   for(int i=1; i < n; i++) {
      if(d[i-1] < 0)
         l = i;
      d[i] = sum[i] - (l ? sum[l-1] : 0);
      if(d[i] > mmax) {
         mmax = d[i];
         cmax = 1;
      }
      else {
         if(d[i] == mmax)
            cmax++;
         if(a[i] == mmax)
            cmax++;
      }
   }
   cout << mmax << " " << cmax << endl;
   
   //system("pause");
   return 0;
}
Добавлено через 3 минуты
если что-то будет непонятно, напишите лс, я постараюсь объяснить.

Добавлено через 12 секунд
там мало интересного, на самом деле... посмотрите лучше задачи в этой группе http://www.facebook.com/groups/311783538877524/
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.04.2013, 21:50     Гроб настоящий!
Еще ссылки по теме:

Настоящий ли это Intel i7 4790k
Найти дату, с которой по настоящий день прошло n месяцев C++
Последний гвоздь в гроб ООП ( на примере ММОРПГ сервера )
Проверка на настоящий IP PHP
Настоящий мужчина

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

Или воспользуйтесь поиском по форуму:
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
08.04.2013, 21:50  [ТС]     Гроб настоящий! #12
Цитата Сообщение от salam Посмотреть сообщение
пожалуйста...

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/* All the code in this file belongs to the Govnocoding Inc. USA. California. 2013 */
 
/* C header files */
#include <cmath> 
#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib> 
 
/* C++ header files */
#include <map> 
#include <set> 
#include <deque> 
#include <limits> 
#include <string> 
#include <vector>  
#include <utility>
#include <algorithm>
 
/* C++ input / output */
#include <fstream> 
#include <iomanip>
#include <iostream>
 
using namespace std;
 
/* C++ types */
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
 
/* Pairs */
#define ft first
#define sc second
#define mp(a, b) make_pair((a), (b))
typedef pair <ll, ll> pll;
typedef pair <int, int> pi;
typedef pair <double, double> pd;
 
/* Single vectors */
#define pop() pop_back()
#define push(s) push_back(s)
typedef vector <pi> vec_pi;
typedef vector <int> vec_i;
typedef vector <bool> vec_b;
typedef vector <char> vec_c;
typedef vector <double> vec_d;
typedef vector <long long> vec_ll; 
 
/* Macroses */
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define len(s) s.length()
#define maxV(type) numeric_limits<type>::max()
#define minV(type) numeric_limits<type>::min()
#define sf(a, b, i) for(size_t (i)=(a); (i) < (b); (i)++)
 
int main()
{
   //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
   cin.tie(0);
   ios_base::sync_with_stdio(0);
    
   int n;
   int cmax = 0;
   ll mmax = minV(ll);
   int l = 0;
   int a[100000];
   ll  d[100000];
   ll sum[100000];
   cin >> n;
   for(int i=0; i < n; i++)
      cin >> a[i];
   d[0] = a[0];
   sum[0] = a[0];
   for(int i=1; i < n; i++)
      sum[i] = sum[i-1] + a[i];
   for(int i=1; i < n; i++) {
      if(d[i-1] < 0)
         l = i;
      d[i] = sum[i] - (l ? sum[l-1] : 0);
      if(d[i] > mmax) {
         mmax = d[i];
         cmax = 1;
      }
      else {
         if(d[i] == mmax)
            cmax++;
         if(a[i] == mmax)
            cmax++;
      }
   }
   cout << mmax << " " << cmax << endl;
   
   //system("pause");
   return 0;
}
Добавлено через 3 минуты
если что-то будет непонятно, напишите лс, я постараюсь объяснить.

Добавлено через 12 секунд
там мало интересного, на самом деле... посмотрите лучше задачи в этой группе http://www.facebook.com/groups/311783538877524/
я вот написал сам гляньте-ка,зашло на 100 правда там 1 тест((((
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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
int n;
cin >> n;
int a[100010]={0};
for (int i=0;i<n;i++)
{
    cin >> a[i];
}
int ans = a[0],
    sum = 0;
for (int r=0; r<n; ++r) {
    sum += a[r];
    ans = max (ans, sum);
    sum = max (sum, 0);
}
int g1=0;
int kol=0;
int b[100010]={0};
while (true)
{
      fill_n(b,n,0);
      b[g1]=a[g1];
      for (int i=g1+1;i<n;i++)
      {
          b[i]=a[i]+b[i-1];
          if (b[i]==ans){kol++;}
      }
      if (g1==n-1){break;}
      g1++;
}
if (a[n-1]==ans){kol++;}
cout << ans << " " << kol;
system("PAUSE >> void");
return 0;
}
Yandex
Объявления
08.04.2013, 21:50     Гроб настоящий!
Ответ Создать тему
Опции темы

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