Ho provato di fare l’esercizio di Algobadge CTF. Ho provato in vari modi:
- Con le Linked List - 30/100
- Con gli Array List - 30/100
- Con la formula trovata per induzione - 45/100
Non so cosa inventarmi, aiuto.
Allego il codice contenente la formula.
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Scanner;
import java.io.PrintWriter;
import java.lang.Math;
public class ctf
{
public static void main(String[] args) throws FileNotFoundException {
InputStream fin = new FileInputStream("input.txt");
OutputStream fout = new FileOutputStream("output.txt");
Scanner scan = new Scanner(fin);
PrintWriter prnt = new PrintWriter(fout);
int q = scan.nextInt();
for (int i = 0; i < q; i++)
{
int teamSize = scan.nextInt();
prnt.println((2 * (teamSize - (int)Math.pow(2,(int)(Math.log(teamSize) / Math.log(2))))+1));
}
prnt.close();
scan.close();
}
}
PS
Sono riuscito a farlo. La soluzione è la stessa, bisognava solo sostituire tutto con long.
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Scanner;
import java.io.PrintWriter;
public class ctf {
public static long e (long b , long n) {
if (n == 0)
{
return 1;
}
long r = e(b,n/2);
r = r * r;
if (n %2 == 1)
{
r = r * b ;
}
return r;
}
public static long log2(long N)
{
// calculate log2 N indirectly
// using log() method
long result = (long)(Math.log(N) / Math.log(2));
return result;
}
public static long solve(int teamSize)
{
long exp = log2(teamSize);
return (2*(teamSize-e(2,exp))+1);
}
public static void main(String[] args) throws FileNotFoundException {
InputStream fin = new FileInputStream("input.txt");
OutputStream fout = new FileOutputStream("output.txt");
Scanner scan = new Scanner(fin);
PrintWriter prnt = new PrintWriter(fout);
int q = scan.nextInt();
for (int i = 0; i < q; i++)
{
long teamSize = scan.nextLong();
long result = 2 * (teamSize - e(2, log2(teamSize))) + 1;
prnt.println(result);
}
// Close the resources
prnt.close();
scan.close();
}
}