Algorithm
Problem Name: beecrowd | 2846
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2846
Fibonot
By Francisco Elio Parente Arcos Filho, UEA 
Brazil
Timelimit: 1
The Fibonacci sequence is one of the most famous sequences in the world. The Fibonacci terms are always equal to the sum of the two terms preceding them in the sequence and the first two terms are 1. That is:
1 , 1, 2, 3, 5, 8, 13, 21, 34 ...
However, we are not interested in finding the terms of the Fibonacci sequence, but the terms of the Fibonot sequence!
The Fibonot sequence is composed of numbers that do not belong to the Fibonacci sequence. More specifically, non-zero positive integers. In ascending order!
Here are the first terms of Fibonot:
4, 6, 7, 9, 10, 11, 12, 14, 15 ...
Your task is to find the K-th Fibonot number.
Input
The entry consists of a single integer K (1 ≤ K ≤ 105) specifying the index of the element of the desired Fibonot sequence.
Output
A single integer representing the K-th term of the Fibonot sequence.
| Input Sample | Output Sample |
|
1 |
4 |
|
3 |
7 |
|
6 |
11 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define false 0
#define MAXSIZE 100100
long long fibo[MAXSIZE];
long long _fibonot[MAXSIZE];
void fib();
int main (void)
{
int n;
fib();
scanf("%d", &n);
printf("%lld\n", _fibonot[n]);
}
void fib()
{
int i, j, k;
fibo[0] = 0; fibo[1] = 1;
for (i = 2; i < = MAXSIZE; ++i)
fibo[i] = fibo[i - 1] + fibo[i - 2];
for (i = 1, j = 2, k = 1; i < = MAXSIZE; ++i)
if (fibo[j] != i)
_fibonot[k++] = i;
else
++j;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define ull unsigned long long
bool isperfect(ull int x)
{
ull int s=sqrt(x);
return s*s==x;
}
bool isfibonacci(ull int n)
{
return isperfect(5*n*n+4) || isperfect(5*n*n-4);
}
int main()
{
ull int k, n;
cin >> k;
vector < ull int>v;
for (int i = 0; i < 200000; ++i)
{
if (!isfibonacci(i+1))
v.push_back(i+1);
if (v.size()==k)
break;
}
cout << v[v.size()-1] << endl;
return 0;
}
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner leitor = new Scanner(System.in);
int cont = 0, res = 0;
int a = leitor.nextInt();
for (int i = 4; cont != a; i++) {
if (!isFib(i)) {
cont++;
res = i;
}
}
System.out.println(res);
}
private static boolean square(long x){
long s = (long) Math.sqrt(x);
return s * s == x;
}
private static boolean isFib(long c) {
return (square(5 * c * c + 4) || square(5 * c * c - 4)) ;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("node:fs")
const [input] = readFileSync("/dev/stdin", "utf8")
.split("\n", 1)
.map(value => Number.parseInt(value, 10))
function* fibonacci() {
let a = 0n
let b = 1n
while (true) {
[a, b] = [b, a + b]
yield a
}
}
function* fibonot(nth = 0) {
let res = 0n
let fib = fibonacci()
let min, max = fib.next().value
outer:
while (true) {
min = max
max = fib.next().value
// @ts-ignore
for (res = min + 1n; res < max; res++) {
yield res
if (--nth <= 0) break outer
}
}
fib.return()
return res
}
function main() {
const kthFibonot = [...fibonot(input)].pop().toString(10)
console.log(kthFibonot)
}
main()
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
def fibonot(n):
a = 1
b = 2
c = 3
while n > 0:
a = b
b = c
c = a + b
n -= (c - b - 1)
n += (c - b - 1)
return b + n
n = int(input())
print(fibonot(n))
Input
Output