3331 - Bob and Solitary Kings

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3331 - Bob and Solitary Kings

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
isaac
Posts: 83
Joined: 4 years ago
Gender: None specified

Re: 3331 - Bob and Solitary Kings

Post by isaac » 4 years ago

Si analizamos la entrada, nos damos cuenta que existe la misma solucion para un tablero de n x m que para uno de m x n, asi que hacemos un pequeño detalle, si n > m, los intercambiamos, asegurandonos que siempre n <= m. Analizamos el caso particular cuando n == 1 y la idea es:

1- Contar la cantidad de esquinas del tablero.
2- Contar la cantidad de casillas tal que si el rey estuviera en una de esas casillas, el otro rey pueda ser colocado en estas sin que se ataquen.

3- Contar la candidad de casillas que estan en el borde pero que no son esquinas.
4- Hacer lo mismo para estas casillas que con 2-.

5- Contar la cantidad de casillas que no son del borde.
6- Contar lo mismo para estas que en 4- y en 2 (por supuesto, relativamente).

Finalmente, debemos imprimir la suma de (1) * (2) + (3) * (4) + (5) * (6).

Post Reply

Return to “Problem set”