Two tokens move around a cycle, each jumping exactly D seats left or right per turn; find the fewest moves until a token lands on the other token's holder.
Medium5BFSGraphMathImplementationInterviewNo attempts yetTime limit1sMemory limit512 MBEunha likes drinks, games, and drinking games. Her favorite drinking game is the red ginseng game. N people sit in a circle around a table and play it by these rules.
After the contest the participants went to a nearby bar for the after party, and Eunha got everyone to play the red ginseng game. So many people had gathered that nobody could tell who was pointing at whom, so the game kept stopping. Eunseo, a friend of Eunha, could not watch this any longer and proposed the orderly red ginseng game, which changes the rules.
Thanks to Eunseo the participants could play the red ginseng game in an orderly way. Eunha kept running the game for hours, the participants wore out, and they started trying to end each game as fast as possible no matter whom Eunha points at and whatever pointing distances she sets. Rescue the after party from red ginseng hell.
The participants are numbered 1 to N counterclockwise. Participant i has participant i−1 immediately to the left and participant i+1 immediately to the right. As the exception, participant 1 has participant N immediately to the left, and participant N has participant 1 immediately to the right.
The first line contains the number of participants N (2≤N≤500), the number A of the person Eunha points at first and the number B of the person she points at second (1≤A,B≤N, A=B), and the integers DA and DB giving the pointing distance of each token (1≤DA,DB≤N−1), separated by spaces in that order.
Print, on the first line, the minimum number of pointings needed to end the given game as fast as possible. The opening move in which Eunha points at the two people does not count. If the game can never end, print Evil Galazy.
The game with N=6, A=5, B=1, DA=1, DB=2 ends in three pointings if it runs in this order.