可乐复制通过40%。当n=1000000000 超时！

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
long n=scanner.nextLong();
String string=  f(n);
System.out.println(string);
}


}
public static String  f(long n) {
Queue<String> q=new LinkedList<String>();
q.add("Alice");
q.add("Bob");
q.add("Cathy");
q.add("Dave");
long count=0;
String string=null;

while(!q.isEmpty()){

string  =q.poll();
count++;
q.add(string);
q.add(string);
if(count==n){break;}
}
return string;
}

}