焦作赛区网络预赛J题 – Participate in E-sports

ACM-ICPC 2018 焦作赛区网络预赛的大水题,链接

其实就是判断n和n(n-1)/2是不是都是完全平方数,当然,n很大。
大整数,自然是Java了。牛顿迭代法,配合%3%4还有末位的常数瞎几把优化。
嗯好的,全国第九个过的,吹逼一年。

import java.math.BigInteger;
import java.math.BigDecimal;
import java.util.Scanner;



public class Main {

    public static boolean calculateSquareRoot(BigInteger number) { 

        BigInteger number_mod_3=number.mod(BigInteger.valueOf(3));
        BigInteger number_mod_4=number.mod(BigInteger.valueOf(4));
        if( ( (BigInteger.ONE).equals(number_mod_3) || (BigInteger.ZERO).equals(number_mod_3) ) && ( (BigInteger.ONE).equals(number_mod_4) || (BigInteger.ZERO).equals(number_mod_4) ) )
        {
            ;
        }
        else
        {
            return false;
        }
        BigInteger last_digit_1=number.mod(BigInteger.valueOf(10));
        BigInteger last_digit_2=number.mod(BigInteger.valueOf(100));
        if( (BigInteger.ONE).equals(last_digit_1) || (BigInteger.valueOf(4)).equals(last_digit_1) || (BigInteger.valueOf(6)).equals(last_digit_1) || (BigInteger.valueOf(9)).equals(last_digit_1) || (BigInteger.ZERO).equals(last_digit_1) || (BigInteger.valueOf(25)).equals(last_digit_2)  )
        {
            ;
        }
        else
        {
            return false;
        }        
        if(number.equals(BigInteger.ZERO))return true;
        BigInteger squareRootResult = determineClosestWholeNumberSquareRoot(number);
        if( squareRootResult.pow(2).equals(number)) {
            return true;
        }
        return false;
    }

    private static BigInteger determineClosestWholeNumberSquareRoot(BigInteger number) {

        BigInteger result = null;

        if(number.equals(BigInteger.ONE)) {
            return BigInteger.ONE;
        } else if( number.equals(BigInteger.valueOf(2)) ) {
            return BigInteger.ONE;
        } else if( number.equals(BigInteger.valueOf(3)) ) {
            return BigInteger.ONE;
        } else if( number.equals(BigInteger.valueOf(4)) ) {
            return BigInteger.valueOf(2);
        }

        BigInteger tempBaseLow = BigInteger.valueOf(2);
        BigInteger tempBaseHigh = number.shiftRight(1); // divide by 2

        int loopCount = 11;

        while(true) {

            if( tempBaseHigh.subtract(tempBaseLow).compareTo(BigInteger.valueOf(loopCount)) == -1 ) { // for lower numbers use for-loop
                //System.out.println("Breaking out of while-loop.."); // uncomment-for-debugging
                break;
            }

            BigInteger tempBaseMid = tempBaseHigh.subtract(tempBaseLow).shiftRight(1).add(tempBaseLow); // effectively mid = [(high-low)/2]+low
            BigInteger tempBaseMidSquared = tempBaseMid.pow(2);
            int comparisonResultTemp = tempBaseMidSquared.compareTo(number);


            if(comparisonResultTemp == -1) { // move mid towards higher number
                tempBaseLow = tempBaseMid;
            } else if( comparisonResultTemp == 0 ) { // number is a square ! return the same !
                    return tempBaseMid;
            } else { // move mid towards lower number
                tempBaseHigh = tempBaseMid;
            }

        }

        BigInteger tempBasePrevious = tempBaseLow;
        BigInteger tempBaseCurrent = tempBaseLow;
        for(int i=0;i<(loopCount+1);i++) {
            BigInteger tempBaseSquared = tempBaseCurrent.pow(2);
            //System.out.println("Squared :"+tempBaseSquared); // uncomment-for-debugging
            int comparisonResultTempTwo = tempBaseSquared.compareTo(number);

            if( comparisonResultTempTwo == -1 ) { // move current to previous and increment current...
                tempBasePrevious = tempBaseCurrent;
                tempBaseCurrent = tempBaseCurrent.add(BigInteger.ONE);
            } else if( comparisonResultTempTwo == 0 ) { // is an exact match!
                tempBasePrevious = tempBaseCurrent;
                break;
            } else { // we've identified the point of deviation.. break..
                //System.out.println("breaking out of for-loop for square root..."); // uncomment-for-debugging
                break;
            }
        }

        result = tempBasePrevious;

        //System.out.println("Returning :"+result); // uncomment-for-debugging
        return result;

    }

    
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        BigInteger N,M;
        boolean N_sqrt,M_sqrt;
        int T=in.nextInt();
        for(int i=1;i<=T;i++)
        {
            N=in.nextBigInteger();
            M=(N.multiply(N.subtract(BigInteger.valueOf(1)))).divide(BigInteger.valueOf(2));
            N_sqrt=calculateSquareRoot(N);
            M_sqrt=calculateSquareRoot(M);
            if(N_sqrt && M_sqrt) System.out.println("Arena of Valor");    
            else if(N_sqrt && !M_sqrt) System.out.println("Hearth Stone");
            else if(!N_sqrt && M_sqrt) System.out.println("Clash Royale");
            else System.out.println("League of Legends");
        }
    }
    
}

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注