Welcome to ZOJ
86 - ZOJ Monthly, January 2010 - A
Apple or Doughnut

Time Limit: 1 Second      Memory Limit: 32768 KB

Give a computer doughnut and an apple,would the computer know the difference? Actually, that depends on the inner workings of the computer, whether it has been programmed to be able to do so by a talented programmer as you!

Now, to differentiate two objects involves many aspects, colors, textures, size,shape, and so on. But an intelligent program should be able to differentiate the most essential aspect, structure. Note that a doughnut has a hole through it while an apple doesn't. To simplify, the followings hold:

  • The description of the given objects are formed with 1*1*1 cubes, and in each description there is only one object.
  • The object is contiguous, thats is to say each 1*1*1 cube of the object has a face stuck to another cube in the object.
  • The object does not have inner cavity, that is to say it can be an apple but not a balloon because a ballon is empty inside.
  • The hole can turn many times, it's not just restricted to the form: comes in from the top and directly comes out at the bottom, it can turn many times inside the object.
  • There will be at most one hole to worry about, and all cubes are either completely separate or connected, there are no cubes that are "connected" by an edge.

This all seems confusing, a simple description would be:

A doughnut object could have a loop drawn on it's surface that does not separate it into two parts, while an apple object does not.

Now given the description an object, you are to determine if it's a doughnut object or an apple object.


There are many test cases,each are of the form:

First there are three integers representing the dimensions of the input: A(1 <= A <= 5),B(1 <= B <= 5),C(1 <= C <= 5).

Then follows A matrices each with B rows and C columns. 0 stands for not part of the object and 1 stands for part of the object. The object will not be of zero volume.


For each test case, if the object is an apple object, output "APPLE". If it's a doughnut object output "DOUGHNUT".

Sample Input

1 1 1
1 3 3
1 1 1
1 0 1
1 1 1

Sample Output



Euler's theorem:

Let P be a polyhedron which satisfies:

(a)Any two vertices of P can be connected by a chian of edges.

(b)Any loop on P which is made up of straight line segments(not necessarily edges) separates P into two pieces.

Then Vertex Number - Edge Number + Face Number = 2 for P.

Author: SONG, Yu
Source: ZOJ Monthly, January 2010
Submit    Status