SPOJ.com - Problem FUSC

FUSC - Obfuscated Property

no tags

Consider the sequence:

    0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4...

This sequence is defined recursively by the formula:

f(2n) = f(n)
f(2n+1) = f(n) + f(n+1)

with the initial values f(0) = 0 and f(1) = 1

In 1982, Dijkstra called this sequence fusc because it possesses a curious obfuscated property: if the sum of two indices, n and m, is a power of 2, then f(n) and f(m) are coprime.

The sequence of the ratios of two consecutive elements u_n = f(n) / f(n+1) runs through all non-negative rational numbers (in reduced form) just once!

    0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4 ...

Moreover, if the terms are written as an array:

    1
    1, 2
    1, 3, 2, 3
    1, 4, 3, 5, 2, 5, 3, 4
    1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5
    1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6

then the sum of the k-th row is 3^k-1, each column is an arithmetic progression, and the steps are nothing but the original sequence!

In this problem, given n, you have to find max{f(i); 0 <= i <= n)}

Input

One single line contains n (0 <= n <= 10¹⁵).

Output

One single line contains max{f(i); 0 <= i <= n)}.

Example

Input:
10

Output:
4

Submit solution!

hide comments

< Previous 1 2 Next >

	mr_parallel: 2024-10-17 18:56:53 I took the challenge to write a solution to the problem in PHP. I was naive. A regular loop of 109 iterations with a minimum of arithmetic takes me 14 seconds. I will rewrite my solution in C later. Edit: Found a solution that can be implemented even in PHP. My result: 0.17 seconds; 26M memory If someone is still trying to find a speed-optimised solution, you will need a mathematical analysis of the fusc sequence: ‘Record-Setters in the Stern Sequence’ Last edit: 2024-11-11 19:16:12**
	prashanth6484: 2024-06-26 10:22:31 It seems like you're describing an algorithmic approach to finding a maximum value within a specific range derived from the number \( n \). If you're encountering TLE (Time Limit Exceeded) errors, it typically means that your solution is taking too long to execute, often due to inefficient looping or excessive computations. To optimize your approach, consider the following: 1. Efficient Range Calculation: Ensure that your calculations for 'n_start', 'n_end', and 'n_end2' are correct and efficiently computed using bitwise operations ('pow(2, k)' can be efficiently replaced by '1 << k'). 2. Loop Optimization: Instead of looping through all potential values from 'n_start' to 'n_end2' or 'n_end', consider using binary search or a more refined algorithm that reduces the number of iterations needed to find the maximum value. This can significantly reduce the computational load. 3. Edge Cases: Handle edge cases such as when 'n' is very close to 'n_start', 'n_end', or within small ranges differently to avoid unnecessary computations. 4. Algorithm Complexity: Analyze the complexity of your algorithm. If it's O(n) or worse, it might be necessary to refactor it to O(log n) or better to handle larger inputs efficiently. Without the specific implementation details of your code, it's challenging to give precise optimization advice. However, focusing on reducing unnecessary computations and ensuring efficient handling of the range calculations should help in avoiding TLE issues. [Simes]: your comment would carry more weight if you'd solved this problem. Or any problem. Last edit: 2024-06-26 17:17:47
	h3r37ic_m46607: 2024-06-13 17:10:13 Time limit 1s and they allow script languages Python?! That's sadistic.
	bomba420: 2024-04-04 14:11:23 bruh who the fck is creating these questions
	Dawid Chmura: 2023-06-07 11:56:08 Please a more test case.
	chienstar: 2022-10-14 12:19:57 the first thing if you see the terms you could see max always in the last 2 rows and each row if element 1 is omitted, it is always symmetric so from the given number n i calculate the log 2 of n .after that i use the floor function to calculate the integer nearest log2(n) so let call the variable floor_n = floor(log2(n)), n_start = pow(2, floor_n) - 1 is 2^m - 1, n_end = pow(2, floor_n+1) -1 is 2^(m+1) - 1 and n_end2 = n_start + (2^(m+1)-2^m)/2. So i check if n_end- n <= n -n_start i find max by looping from n_start to n_end2 else i find max by looping from n_start to n. For Example The given number n = 50 => log2(n) = 5,6 => m = floor(n) = 5 , 2^m-1 = 31 < n=50 < 2^(m+1)-1=63 => n_start = 31, n_end = 63, n_end2 = 47 => n - start = 19, n_end - n = 13 so i will find max of f(i) with i from 31 to 47 ( 5, 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9) is 13 but i still get the TLE (=.=). Can anyone publish some other idea.
	chienstar: 2022-10-13 20:06:56 did anyone find max(f(i)) by not using loop ? my code always reach the TLE in test case 5
	fjkexgnffhwihp: 2022-07-01 17:00:58 a clearer definition of this sequence: f(0) = 0 f(1) = 1 f(n) = f(n/2) if n is even f(n) = f((n-1)/2) + f((n+1)/2) if n is odd Last edit: 2022-07-02 11:18:58
	louis_22: 2022-06-30 00:01:35 I have no idea what I’m doing
	louis_22: 2022-06-30 00:00:31 I need help

Submit solution!

Added by:	Jimmy
Date:	2006-12-28
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET