首页 > 专题系列 > Java解POJ > POJ 3024 The Gossiping System [解题报告] Java
2013
11-12

POJ 3024 The Gossiping System [解题报告] Java

The Gossiping System

问题描述 :

A common amusement in almost any society, though certainly not the most glamorous one, is for its inhabitants to spread rumours about each other. In the town of Knoxville, this is definitely known to be the case. In order to establish some sort of order without completely ruin the pleasure of gossiping, they have agreed on a system for everyday life activities, in which rumours spread in a controlled fashion. The inhabitants meet in certain groups in their work, as well as in their spare time, on a daily basis. The following three criteria are met for their system:
  • Each group must have the same non-zero number of members m.
  • Each person must belong to the same number of groups r, as any other person.
  • Each pair of different groups has exactly one member in common.

We say that a (n,g,m,r)-gossiping system is such a system consisting of n persons divided into g groups, with m and r as above. The beauty of these systems lies in their uniformity. The construction seems fair to everyone, and still all meetings are held in small groups. Since any two groups have a member in common, information about the activities and people in one group is swiftly transferred to all the other groups. Furthermore, it is easy for a messenger to lie if he or she would like to, since the truth is hard to validate due to the fact that no two persons share more than one group. Unfortunately, there are several combinations of n, g, and m for which these systems do not exist!

As a mathematician living in Knoxville, you are interested in studying the existence conditions for these systems for large values of n. However, you soon realise the complexity of these combinatorial objects, and choose to study only their simplest non-trivial class, the (n,g,m,2)-gossiping systems.

输入:

On the first line of input, is a single positive integer t. Thereafter t test cases follow. Each test case consists of one positive number n, 1 <= n <= 1050, given in the standard base 10 representation, where n specifies the number of persons.

输出:

For each test case in the input, output the text ‘Yes.’ on a line of its own, if there exists a (n,g,m,2)-gossiping system for any positive integers g>1 and m>0 for the value of n in the test case, otherwise output the text ‘No.’

样例输入:

5
3
4
5
6
678678658335615

样例输出:

Yes.
No.
No.
Yes.
Yes.

解题代码:

//* @author: 
import java.util.*;
import java.io.*;
import java.math.*;
class Main
{
 public static void main(String args[]) throws Exception
 {
  Scanner cin = new Scanner(System.in);
  String s;
  BigInteger bi;
  int T;
  boolean res;
  T = cin.nextInt();
  cin.nextLine();
  while (T-- > 0)
  {
    s = cin.nextLine();
    bi = new BigInteger(s);
    res = check(bi);
    if (res) System.out.println("Yes.");
    else System.out.println("No.");
   }
  }
	
 static boolean check(BigInteger bi)
 {
   bi = bi.add(bi);
   BigInteger min, max, mid, tmp;
   BigInteger Two = BigInteger.ONE.add(BigInteger.ONE);
   BigInteger One = BigInteger.ONE;
   BigInteger nOne = BigInteger.valueOf(-1);
   min = BigInteger.ZERO;
   max = bi;
   while (min.compareTo(max) <= 0)
   {
    mid = min.add(max).divide(Two);
    tmp = mid.add(One).multiply(mid);
    if (tmp.equals(bi)) return true;
    if (tmp.compareTo(bi) < 0) min = mid.add(One);
    else max = mid.add(nOne);
    }
	return false;
   }
}

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }