아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Jar Game

면접 대비

시간 제한1초메모리 제한1024 MB

요약
세 항아리에 각각 a, b, c개의 구슬이 들어 있고, 두 사람이 번갈아 한 항아리에서 k번째 차례에 k개를 가져가며, 더 많이 가져간 사람이 이긴다. 최선의 플레이를 가정할 때 승자를 판정한다.
난이도

보통10점 중 6점

유형
게임 이론, 동적 계획법, 백트래킹
정답자
아직 제출이 없습니다

문제

Two players F(irst) and S(econd) play a game with three jars each containing aa, bb and cc pebbles. The game is played according to the following rules:

  • Two players take turns one at a time. For each turn, the player chooses a jar and takes some pebbles from the jar.
  • F starts first, then S next. These turns alternate till the game ends.
  • The number of pebbles that can be drawn at the kk-th turn is kk; the number of pebbles taken by F at the first turn is 11. So in the next turn, S takes 22 pebbles, then at the third turn, F takes 33 pebbles, and so on.
  • For each turn, the pebbles must be taken out of only one jar.
  • At the kk-th turn, if the number of pebbles remaining in the chosen jar is less than kk, the player should take all the remained pebbles in that jar. If the remained pebbles is greater than kk in the chosen jar, then the player is not allowed to take less than kk pebbles from the jar.
  • If there are no pebbles left in the three jars, then the game is over. The player with more pebbles wins the game when the game is over. So in some cases, a draw may be possible if the number of pebbles two players took is the same.
  • We assume that two players F and S do their best to win.
  • Two players always know the exact number of the pebbles remained in three jars. There is no hidden information in this jar game.

Given the number of pebbles in three jars, write a program to find who is the winner or if the draw is possible.

입력

Your program is to read from standard input. The input starts with a line containing three integers, aa, bb and cc (1≤a,b,c≤1001 ≤ a, b, c ≤ 100) denoting the number of pebbles in three jars at the beginning.

출력

Your program is to write to standard output. Print exactly one line. The line should contain a capital letter among {F, S, D}. {F, S} means the winner among two players and D denotes a draw when the game ends.

예제3

  1. 예제 1

    입력
    2 5 3
    
    예상 출력
    F
    
  2. 예제 2

    입력
    4 1 5
    
    예상 출력
    D
    
  3. 예제 3

    입력
    5 3 5
    
    예상 출력
    S