首页 > 专题系列 > Java解POJ > POJ 3372 Candy Distribution [解题报告] Java
2013
11-12

POJ 3372 Candy Distribution [解题报告] Java

Candy Distribution

问题描述 :

N children standing in circle who are numbered 1 through N clockwise are waiting their candies. Their teacher distributes the candies by in the following way:

First the teacher gives child No.1 and No.2 a candy each. Then he walks clockwise along the circle, skipping one child (child No.3) and giving the next one (child No.4) a candy. And then he goes on his walk, skipping two children (child No.5 and No.6) and giving the next one (child No.7) a candy. And so on.

Now you have to tell the teacher whether all the children will get at least one candy?

输入:

The input consists of several data sets, each containing a positive integer N (2 ≤ N ≤ 1,000,000,000).

输出:

For each data set the output should be either "YES" or "NO".

样例输入:

2
3 
4

样例输出:

YES
NO
YES

解题代码:

//* @author: [email protected]
/*题目大意:有n个同学坐成一个圆,一老师发糖果,依次发给第1、2、4、7...个同学,问是否每个同学都能得到至少一个糖。 *分析:写个朴素的程序,输出1~100的情况后不难发现,只有当n=2^k(k为整数)时,输出YES。 */ import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); while(in.hasNext()) { int a=in.nextInt(); while(a%2==0) a=a/2; if(a==1) System.out.println("YES"); else System.out.println("NO"); } } }

  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯