_________________________________________________________________________
It’s always Christmas in Christmasville, and there are many laws about the christmas decoration that can be used there. Mr. Grinch Claus, mayor of Christmasville has defined that the christmas lights have to blink in a special way, where:
- In a set of christmas lights, all light bulbs are sequentially connected by a power cable, where each one has a numerated, in sequence, starting from 0
- No neighbor lights can be turned on at the same time
- When pluged to the power, all lamps must be off, and after one second, only the first lamp (lamp #0) turns on
- After that, at every second the light(s) that were on, go off and their neighbors turn on, like this:
- Instant 0 – All lights are off
- Instant 1 – Light #0 turns on
- Instant 2 – Light #0 turns off and light #1 turns on
- Instant 3 – Light #1 turns off and lights #0 and #2 turn on
- Instant 4 – Lights #0 and #2 turn off and lights #1 and #3 turn on
- Instant 5 – Lights #1 and #3 turn off and lights #0, #2 and #4 turn on
- …
To make sure every factory is following these restrictions, Mr. Grinch Claus asked you to write a software to validate this behavior, and given the number of lights in the set and the instant of time, your software must tell which lamps should be ON at that moment.
Input
- N – number of test cases, the number of inputs you need to validate
- For every N test case, the input has:
- l – the number of lights in the set
- t – the time, in seconds from the moment the set was turn on, that you want to verify
Output
For each N test cases, one line with the list of lights that are turned on (in order) or All lights are off :( if there’s no light turned on
Limits
- 1 ≤ N ≤ 100
- 1 ≤ l ≤ 64
- 1 ≤ t ≤ 109
Example
Sample input
4 5 3 8 6 1 2 2 3
Sample output
0 2 1 3 5 All lights are off :( 0
TEST
453861223
_________________________________________________________________________
SuperHardSum Class:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Clase encargada de mantener el bucle de ejecución del programa hasta el fin de linea.
* @author Javier de Pedro López
*/
public class UserInterface {
/**
* Permite mantener el bucle de lecutra.
*/
public void run() throws IOException{
String line;
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//Bucle que realiza las lecturas hasta que lo recibido sea EOF (null)
line = reader.readLine();
int numCases = Integer.valueOf(line.trim());
do{
int numLights = Integer.valueOf(reader.readLine());
int time = Integer.valueOf(reader.readLine());
ChristmasLights christmas = new ChristmasLights(numLights,time);
System.out.println(christmas.getOnLights());
numCases--;
} while(numCases > 0);
}
}
Christmas Lights Class:
/**
* Clase que realiza los cálculos necesarios para conocer el numero de luces encendidas tras un tiempo segun el enunciado dado.
* @author Javier de Pedro López
*/
public class ChristmasLights {
//ATRIBUTOS//
private boolean[] _lights;
private int _even;
private int _odd;
//CONSTRUCTOR//
/**
* Instancia la clase para que sea capaz de contar las luces en función del tiempo.
* @param numLights numero de luces que se van a tratar.
* @param time tiempo en el que se encenderan o apagaran.
*/
public ChristmasLights(int numLights, long time){
_lights = new boolean[numLights];
//Apagamos todas las luces
allLightsOff();
//Para optimizar trataremos de ver el caso por el que se pasa y se alternan las luces
if (time > numLights){
//Se encienden las pares
if (time % 2 == 1){
//El numero de luces pares vendra asignado en funcion del numero de luces totales.
if (_lights.length % 2 == 0){
_even = _lights.length/2;
}else{
_even = _lights.length/2 + 1;
}
turnOnEven();
//Se encienden las impares
}else{
_odd = _lights.length/2;
turnOnOdd();
}
//Si no nos pasamos del tiempo
}else{
for (int i = 0; i < time; i++){
//Si el tiempo es par se encienden las pares
if (i % 2 == 0){
_even++;
turnOffOdd();
turnOnEven();
//Si es impar se encienden las impares
}else{
_odd++;
turnOffEven();
turnOnOdd();
}
}
}
}
//METODOS//
/**
* Permite obtener un String con las luces que se encuentran encendidas.
* @return el String con las luces encendidas.
*/
public String getOnLights(){
String lights = "";
for (int i = 0; i < _lights.length; i++){
if (_lights[i] == true){
lights += i + " ";
}
}
if (lights.equals("")){
lights = "All lights are off :(";
}
return lights.trim();
}
/**
* Inicializa las luces a apagado.
*/
private void allLightsOff(){
_even = 0;
_odd = 0;
for (int i = 0; i < _lights.length; i++){
_lights[i] = false;
}
}
/**
* Apaga las luces impares que estén encendidas.
*/
private void turnOffOdd(){
for (int i = 0; i < _odd; i++){
//Se toma i*2+1 para tomar solo los valores impares
_lights[i * 2 + 1] = false;
}
}
/**
* Enciende las luces impares que deban ser encendidas.
*/
private void turnOnOdd(){
for (int i = 0; i < _odd; i++){
_lights[i * 2 + 1] = true;
}
}
/**
* Apaga las luces pares que esten encendidas.
*/
private void turnOffEven(){
for (int i = 0; i < _even; i++){
//Se toma i*2 para tomar solo los valores pares
_lights[i * 2] = false;
}
}
/**
* Enciende las luces pares que deban ser encendidas.
*/
private void turnOnEven(){
for (int i = 0; i < _even; i++){
_lights[i * 2] = true;
}
}
}
