http://mendo.mk/jforum/posts/list/7.page JForum - http://www.jforum.net #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>arr;
void leftRotatebyOne()
{
int temp = arr[0], i;
for (i = 0; i < arr.size() - 1; i++)
arr[i] = arr[i + 1];

arr[i] = temp;

return;
}
void count_positive_rotations()
{
int good_rotations=0;
for(int j=0;j<arr.size();j++)
{
int sum=arr[0];
bool good_rotation=true;
if(sum<0)
good_rotation=false;
else
{
for(int i=1;i<arr.size();i++)
{
if(sum+arr[i]>=0)
sum+=arr[i];
else{
good_rotation=false;
break;
}
}
}
if(good_rotation)
good_rotations++;

leftRotatebyOne();
}


cout<<good_rotations<<endl;
return;
}
int main()
{
int N;
cin>>N;
for(int i=0;i<N;i++)
{
int a;
cin>>a;
arr.push_back(a);
}
count_positive_rotations();

return 0;
}[/code]
????? ?? ?????? ?? ?????? 8 ????????, ?? ?????????? ?? ???? ?? ?????, ???? ?? ?? ???????]]> http://mendo.mk/jforum/posts/preList/707/3834.page http://mendo.mk/jforum/posts/preList/707/3834.page GMT Твојот алгоритам има преголема сложеност. Оваа задача може да се реши во линеарно време O(N). Така да, не може секогаш да се "убрза" некој почнат код, и треба да се внимава да направиме анализа на алгоритамот пред да почнеме да решаваме (за да не изгубиме време на пишување на решение кое нема да освои онолку поени колку што очекуваме, па да почнеме од почеток со куцање на нешто друго).

Е сега, во однос на задачата. Размисли дали можеме да пресметаме неколку работи однапред, за да не ги правиме при секоја ротација. Еве еден начин како може да се реши задачава со тој пристап:
    Нека имаме низа frontSum[i] која што ни го памети збирот на првите i броеви - т.е. A[1] + A[2] + A[3] + ... + A[i].
    Нека имаме низа backSum[i] која што ни го памети збирот на сите броеви од i-тиот до N-тиот - т.е. A[i] + A[i+1] + ... + A[N]
    Нека имаме низа frontMin[i] која што го памети најмалиот збир од последователни броеви завршувајќи со i - т.е. min(A[1], A[1]+A[2], ... A[1] + A[2] + ... + A[i])
    Нека имаме низа backMin[i] која што го памети најмалиот збир од последователни броеви почнувајќи со i - т.е. min(A[i], A[i]+A[i+1], A[i]+A[i+1]+A[i+2], ...)


Со овие низи, проверките се доста едноставни за секоја ротација. На пример, ако решиме да ја разгледуваме i-тата ротација (онаа која почнува со i-тиот број), треба само да провериме дали се исполнети овие два услови:
    1) backMin[i] >= 0 (со ова го проверуваме потребниот услов за сите броеви од i-тиот до N-тиот, т.е. дали A[i] >= 0, дали A[i] + A[i+1] >= 0, итн)
    2) backSum[i] + frontMin[i-1] >= 0 (ако ротацијата почнува од i-тиот елемент, тогаш таа по броевите A[i], A[i+1], ... A[N] ќе заврши со броевите A[1], A[2], А[i-1], па со овој чекор го проверуваме условот за тие следни броеви. Види како истиот е сличен на првиот, но додаваме backSum[i]).

За првата ротација не мора да го проверуваме вториот услов, бидејќи таму нема прелевање (т.е. броевите се A[1], A[2], ... A[N]). Еве и код ако уште не е јасно:

[code]#include <bits/stdc++.h>
using namespace std;

int main() {

int N;
cin >> N;

vector<long long> A(N + 1);
for (int i=1; i<=N; i++) {
cin >> A[i];
}


long long frontSum[N+1], frontMin[N+1];
frontSum[0] = 0; frontMin[0] = 1000000000000000LL;

for (int i=1; i<=N; i++) {
frontSum[i] = frontSum[i-1] + A[i];
frontMin[i] = min(frontMin[i-1], frontSum[i]);
}

long long backSum[N+1], backMin[N+1];
backSum[N] = A[N]; backMin[N] = A[N];

for (int i=N-1; i>=1; i--) {
backSum[i] = A[i] + backSum[i+1];
backMin[i] = min(A[i], A[i] + backMin[i+1]);
}


int counter = 0;
if (backMin[1] >= 0) {
counter++;
}

for (int i=2; i<=N; i++) {
if ((backMin[i] >= 0) && (backSum[i] + frontMin[i-1] >= 0)) {
counter++;
}
}

cout << counter << endl;
return 0;
}[/code]]]> http://mendo.mk/jforum/posts/preList/707/3835.page http://mendo.mk/jforum/posts/preList/707/3835.page GMT