ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

University academic school olympiad in informatics 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. He is not a knight for you

Time limit: 1.0 second
Memory limit: 256 MB
It turns out, chess knights don’t really like to visit each other. Usually, the road goes roundabout ways. Coming with present is also not an option, because there is nowhere to get a present from. And if guests finally come, they occupy all the space, and the host has to leave the house until the guests quit.
Not so long ago knight Ostap started to consider an option of moving to another chessboard of size N × N. He doesn’t want to move alone. Instead, he wants to invite as many other knights as possible to join him. The only reason for moving is the fact that right now he has guests all the time. In order to not repeat his mistake, he wants to know the maximum number of knights he can invite with him, such that they will all fit in the new chessboard and no one will be able to visit anyone else.
The house of every knight is located in some cell of a chessboard. A knight can visit another knight, if there is a path between their houses, consisting of knight moves. It is known that knights only move in the following way: at first B cells forward, then A cells sideward.
This is how all the possible moves of a knight look like for A = 1, B = 2:
Problem illustration


The first line contains the size of the chessboard N (1 ≤ N ≤ 109). The second and the third lines contain the parameters of the knight move  — A and B (0 ≤ AB ≤ 3).


In a single line you should output the maximum number of knights that can move to a new chessboard. Ostap should be included in this number.


Problem Author: Kirill Deviatkin
Problem Source: University academic school olympiad in informatics 2019
To submit the solution for this problem go to the Problem set: 2116. He is not a knight for you