JOIN
Get Time

   Problem Statement  

 Problem Statement for ConvexPolygonGame

Problem Statement

    

Little Petya likes convex polygons a lot. Recently he has received a convex polygon as a gift from his mother. The only thing that Petya likes more than convex polygons is playing with little Masha. Petya invented the following game for two players that involves his polygon.



At the beginning of the game there is a convex polygon drawn on the plane. The coordinates of vertices of this polygon are given in int[] X and int[] Y. Petya and Masha take alternate turns, Masha plays first. On his or her turn the player draws a new convex polygon that has the following properties:

  • All vertices of the new polygon have integer coordinates.
  • Each new vertex is located either strictly inside the old polygon or on an edge of the old polygon.
  • No vertex of the new polygon coincides with any vertex of the old polygon.
  • No three vertices of the new polygon lie on the same line.
  • The new polygon has non-zero area.

Note that the new polygon and the old polygon are not required to have the same number of vertices.

After drawing a new polygon the player erases the old one. A player who can't make a move loses the game. Determine who will be the winner if both kids play optimally. If the winner is Masha, return the String "Masha" (without quotes), otherwise return "Petya".

 

Definition

    
Class:ConvexPolygonGame
Method:winner
Parameters:int[], int[]
Returns:String
Method signature:String winner(int[] X, int[] Y)
(be sure your method is public)
    
 

Constraints

-X will contain between 3 and 50 elements, inclusive.
-Y will contain between 3 and 50 elements, inclusive.
-X and Y will contain the same number of elements.
-Each element of X will be between -100 000 and 100 000, inclusive.
-Each element of Y will be between -100 000 and 100 000, inclusive.
-The polygon represented by X and Y will be convex, will have non-zero area and won't contain any 3 vertices that are located on the same line.
-Vertices of the polygon will be listed in counter-clockwise order.
 

Examples

0)
    
{0, 1, 0}
{0, 0, 1}
Returns: "Petya"
Masha has no valid moves, so she loses the game immediately.
1)
    
{0, 4, 2}
{0, 0, 2}
Returns: "Masha"
One of the possible Masha's moves is to select the triangle (1, 0), (3, 1), (1, 1). Regardless of her first move Petya will never be able to make the next move.
2)
    
{0, 100, 100, 0}
{0, 0, 100, 100}
Returns: "Masha"
3)
    
{0, 50, 100, 50}
{0, -1, 0, 1}
Returns: "Petya"
4)
    
{-100000, 100000, 100000, -100000}
{-1, -1, 1, 1}
Returns: "Masha"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 597 Round 1 - Division I, Level Two