Codechef 2019 Challenge java solutions

Chef and Modulo Game

https://www.codechef.com/problems/MGAME

Chef is playing a game with two of his friends. In this game, each player chooses an integer between 11 and PP inclusive. Let’s denote the integers chosen by Chef, friend 1 and friend 2 by ii, jj and kk respectively; then, Chef’s score is(((Nmodi)modj)modk)modN.(((Nmodi)modj)modk)modN.

Chef wants to obtain the maximum possible score. Let’s denote this maximum score by MM. Find the number of ways to choose the triple (i,j,k)(i,j,k) so that Chef’s score is equal to MM.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and PP.

Output

For each test case, print a single line containing one integer — the number of ways to obtain the maximum score.

Constraints

• 1≤T≤1061≤T≤106
• 1≤N≤P≤1061≤N≤P≤106

Subtasks

Subtask #1 (10 points):

• 1≤T≤1001≤T≤100
• 1≤N≤P≤1001≤N≤P≤100

Subtask #2 (90 points): original constraints

Example Input

2 4 4 3 4

Example Output

9 13

Explanation

Example case 1: Chef’s maximum possible score is M=1M=1. All possible values of (i,j,k)(i,j,k) such that the score is 11 are (3,2,2)(3,2,2), (3,2,3)(3,2,3), (3,2,4)(3,2,4), (3,3,2)(3,3,2), (3,3,3)(3,3,3), (3,3,4)(3,3,4), (3,4,2)(3,4,2), (3,4,3)(3,4,3), (3,4,4)(3,4,4).

Solution:

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

int t1 = Integer.parseInt(r.readLine());

while(t1– > 0)
{
String k = r.readLine();
String data[] = k.split(” “,2);
long n = Long.parseLong(data[0]);
long p = Long.parseLong(data[1]);

// System.out.println(n);
// System.out.println(p);

long m=0;
m= (n-1)/2;
// m= n%((n/2)+1);
long num_ways =0;
//System.out.println(m);
if(n <=2)
System.out.println(p*p*p);
else if(n ==p)
{
// one way to select i which gives max modulous
// j , k can be any value between m & P which will not change modulous

num_ways+= 1 *(p-m) * (p-m);

System.out.println(num_ways);

}
else
{
//case 1
// select i > n , j one way , k will be left with (p-m)
num_ways+= (p-n)*1 * (p-m);

// System.out.println(num_ways);
// case 2

// select i > n , j > n , k=1
num_ways+= (p-n)*(p-n)*1;

// System.out.println(num_ways);

// case 3
// select i=1 , j/k as (p-m)
num_ways += 1* (p-m)*(p-m);

System.out.println(num_ways);
}
}

}
}

Expression Processor :

import java.io.*;
import java.lang.reflect.Type;
import java.text.ParseException;
import java.util.*;
import com.google.gson.Gson;
import com.google.gson.reflect.TypeToken;
import org.json.JSONObject;

//[“AND”,
// {“var1” : “value1”},
// [“OR”,
// { “var2” : “value2” },
// { “var3” : “value3” }
// ]
// ]

public class ExP {
// The function can be extended for n number of oprtators
public static String performOp(String optr , String s1 , String s2)
{
if(optr.equals(“AND”))
{
Boolean b = Boolean.parseBoolean(s1) && Boolean.parseBoolean(s2);
return b.toString() ;
}
else{ //OR operator
Boolean b = Boolean.parseBoolean(s1) || Boolean.parseBoolean(s2);
return b.toString() ;

}
}

public static String transform( Map<String, Object> expMap)
{
Stack<String> orandS = new Stack<>();
for(String optr : expMap.keySet()) //oprator is always key
{
Object jA=expMap.get(optr);
for(int i=0 ; i <((ArrayList)jA).size();i++)
{
Object s= ((ArrayList)jA).get(i);
// Instead of boolean , conditions like x > y can be given,
// for that cdde can be modifed
if(s.toString().equals(“true”) || s.toString().equals(“false”))
{
if(orandS.size() > 0 ) {
String s1= orandS.peek();
orandS.pop();
orandS.push(performOp(optr,s.toString(),s1));
}
else
orandS.push(s.toString());
}
else
{
Gson gson = new Gson();
Type type = new TypeToken<Map<String, Object>>(){}.getType();
Map<String, Object> myMap = gson.fromJson(s.toString(), type);

orandS.push(transform(myMap));

}


}


}
return orandS.peek();
}

public static void pritnt(String jsonObject) throws IOException, ParseException {
// Parse a JsonObject into a JSON string
StringWriter stringWriter = new StringWriter();
String json = “”;
Reader inputString = new StringReader(jsonObject);
BufferedReader br = new BufferedReader(inputString);
String line;
StringBuilder builder=new StringBuilder();
while ((line = br.readLine()) != null) {
builder.append(line);

}
Gson gson = new Gson();
Type type = new TypeToken<Map<String, Object>>(){}.getType();
Map<String, Object> myMap = gson.fromJson(builder.toString(), type);

Map<String, Object> ob = (Map<String, Object> ) myMap.get(“e”);
// Parse a JSON string into a JsonNode
JSONObject js = new JSONObject(jsonObject);
Iterator<String> keys = js.keys();
Stack<String>oprS = new Stack<>();
Stack<String>orandS=new Stack<>();

while(keys.hasNext()) {
String key = keys.next();
Object jso= js.get(key);
Map<String, Object> expMap = gson.fromJson(jso.toString(), type);
System.out.println(transform(expMap));

}

}

public static void main (String[] args) throws ParseException,IOException
{

// Code can be modified to check x > 7 instead of sample boolean values
// String jo = “{\n” +
// “\t\”e\”: {\n” +
// “\t\t\”AND\”: [\”x > y\”,\n” +
// “\t\t\t\”y > 7 \”,\n” +
// “\t\t\t{\n” +
// “\t\t\t\t\”OR\”: [\”x > y\”,\n” +
// “\t\t\t\t\t\”y > 7 \”\n” +
// “\t\t\t\t]\n” +
// “\t\t\t}\n” +
// “\n” +
// “\t\t]\n” +
// “\n” +
// “\t}\n” +
// “}”;
// Can be mock tested for any level of nesting
String jo = “{\n” +
“\t\”e\”: {\n” +
“\t\t\”AND\”: [\”true\”, \”true\”,\n” +
“\t\t\t{\n” +
“\t\t\t\t\”OR\”: [\”false\”, \”false\”]\n” +
“\t\t\t}\n” +
“\t\t]\n” +
“\t}\n” +
“}”;
pritnt(jo);
}
}