Kuku Question

QUESTION

Kuku recently learnt about triangular numbers. Ani thinks Kuku has not learnt it properly and start asking questions. But, As we all know kuku is one of the most intelligent on this planet. He answered each and every question correctly. This annoyed Ani and he geared up his question’s level and started asking even harder questions. Kuku can’t answer such big questions manually. So , He decided to write a computer program which can answer Ani’s questions .\n\nKuku is good at mathematics but not at programming ( Dont Doubt His Intelligence ) . So,he hired you ( A World Class Programmer ) to write a computer program which can answer Ani’s Questions with in time.\n\nIn Each question, Ani has given a range [L,R] and asked kuku to calculate numbers of such triplets [A,B,K] which follows A+B=K\n\nwhere \nA,B are any two triangular numbers and K must be in an integers that belongs to given range [L, R] both inclusive.\n\nNote :\n\nTwo triplets are considered to be different if they contain at least one different elements [A,B,K].\n\nINPUT:\n\nFirst line of input contains a single integer Q denoting the number of Ani’s questions.\nNext Q lines of input contains two space separated integers \nL R each describing one question.\n\nOUTPUT:\n\nOutput consists of \nQ lines each containing answer to the corresponding question.

“TESTCASE_1”: “2\n1 5\n16 16\n###—###SEPERATOR—###—\n2\n2”, “TESTCASE_2”: “3\n4 5\n6 32\n9 20\n###—###SEPERATOR—###—\n1\n19\n8”, “TESTCASE_3”: “5\n40 51\n6 32\n9 45\n1 8\n7 90\n###—###SEPERATOR—###—\n9\n19\n25\n4\n59”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

import java.io.*;
import java.util.*;
 
class TestClass {
    
    final static int len = 1414213;
    
    public static int lowerBound(long[] a, int l, int r, long k)
    {
        
        int mid = 0, o = r;
        while (l<=r)
        {
            mid = (l+r)/2;
            if (mid == o) return mid;
            if (a[mid] >= k) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
    
    public static int upperBound(long[] a,int l, int r, long k)
    {
        
        int mid = 0, o = r;
        while (l<=r)
        {
            mid = (l+r)/2;
            if (mid == o) return mid;
            if (a[mid] > k) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
    
    
                   
    public static void main(String args[] ) throws Exception {
        
        PrintWriter out = new PrintWriter(System.out);
        Reader reader = new Reader(System.in);
        
        int t = reader.nextInt();
        long a[] = new long[len];
        for (int i=1; i<=len; i++)
            a[i-1] = (long) i*(i+1)/2;
        
        for (int t_i=0; t_i<t; t_i++)
        {
            long l = reader.nextLong();
            long r = reader.nextLong();
            long count = 0;
            for (int i=0; i<len; i++)
            {
                if (a[i]<=r)
                {
                    count += upperBound(a,0,i,r-a[i])-lowerBound(a,0,i,l-a[i]);
                    count += (2*a[i]<=r && 2*a[i]>=l)?1:0;
                }
            }
            out.println(count);
                           
        }
        out.close();
    }
    static class Reader {
 
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private Reader.SpaceCharFilter filter;
 
        public Reader(InputStream stream) {
            this.stream = stream;
        }
 
        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }
 
        public String readString() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.