ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1079. Maximum

Solution of the program
Posted by aybek 11 Dec 2013 00:44
I decided to write post my solution and comment it, may be it will
be useful for someone.
So, you have recursively defined sequence. Of course first idea is
to write recursive function. But, we need to find max element from
1 to n and if you will call function for every n in order to find
maximum element, such algorithm will cost O(n^2). Another way is to
store results gotten before in special array and compare gotten result
with max of them.
I hope I helped you at least as it.
And here is accepted solution in C++:
#include <iostream>

#define max(a, b) ((a) < (b) ? (b): (a))

int last = 1;
int mem[100000];
int max[100000];

int F(int n)
{
for (int i = last+1; i <= n; ++i) {
if (i%2)
mem[i] = mem[i/2]+mem[i/2+1];
else
mem[i] = mem[i/2];

max[i] = max(mem[i], max[i-1]);
}

return max[n];
}

int main()
{
mem[0] = 0; mem[1] = 1;
max[0] = 0; max[1] = 1;

int n;
while (1) {
std::cin >> n;

if (!n) break;

std::cout << F(n) << std::endl;
}

return 0;
}
Re: Solution of the program
Posted by Md. Shahedul Islam 7 Jun 2015 08:41
well done, bro.... :)
here's another way... >>
--------------------------------------------------------------------------------------
#include <iostream>
using namespace std;

int arr[100000];

int find_max(int n)
{
int maximum = 0;

for(int i = 0; i <= n; i++)
if(maximum < arr[i]) maximum = arr[i];

return maximum;
}

int main()
{
int n[11], i, idx;

arr[0] = 0;
arr[1] = 1;

for(idx = 2; idx < 100000; idx++) {
if(idx & 1) {       // when idx is odd.
i = (idx-1) / 2;
arr[idx] = arr[i] + arr[i+1];
}
else {              // when idx is even.
i = idx / 2;
arr[idx] = arr[i];
}
}

i = 0;
while(cin >> n[i], n[i++] != 0);

i--;
idx = i;

for(i = 0; i < idx; i++) {
cout << find_max(n[i]) << '\n';
}

return 0;
}
-------------------------------------------------------------------------------------

Edited by author 07.06.2015 08:42