Codechef programming set #24
 |
| COOKMACH |
#40
Cooking Machine
Chef is on a vacation these days, so his friend Chefza is trying to solve Chef's everyday tasks.
Today's task is to make a sweet roll. Rolls are made by a newly invented cooking machine. The machine is pretty universal - it can make lots of dishes and Chefza is thrilled about this.
To make a roll, Chefza has to set all the settings to specified integer values. There are lots of settings, each of them set to some initial value. The machine is pretty complex and there is a lot of cooking to be done today, so Chefza has decided to use only two quick ways to change the settings. In a unit of time, he can pick one setting (let's say its current value is v) and change it in one of the following ways.
- If v is even, change this setting to v/2. If v is odd, change it to (v − 1)/2.
- Change setting to 2 × v
The receipt is given as a list of integer values the settings should be set to. It is guaranteed that each destination setting can be represented as an integer power of 2.
Since Chefza has just changed his profession, he has a lot of other things to do. Please help him find the minimum number of operations needed to set up a particular setting of the machine. You can prove that it can be done in finite time.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains two integers A and B denoting the initial and desired values of the setting, respectively.
Output
For each test case, output a single line containing minimum number of operations Chefza has to perform in order to set up the machine.
Constraints
- 1 ≤ T ≤ 200
- 1 ≤ A ≤ 107
- 1 ≤ B ≤ 107, and B is an integer power of 2
Subtasks
- Subtask #1 [40 points]: A ≤ 100 and B ≤ 100
- Subtask #2 [60 points]: No additional constraints
Example
Input: 6 1 1 2 4 3 8 4 16 4 1 1 4 Output: 0 1 4 2 2 2
Explanation
- In the first test case, you don't need to do anything.
- In the second test case, you need to multiply 2 by 2 and get 4. This is done in 1 operation.
- In the third test case, you need to obtain 1 from 3 and then multiply it by 2 three times to obtain 8. A total of 4 operations.
- In the fourth test case, multiply 4 by 2 twice.
- In the fifth test case, divide 4 by 2 twice.
- In the sixth test case, multiply 1 by 2 twice.
MY SOLUTION :
import java.util.Scanner;
class cookmatch {
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int b=in.nextInt();
while(b-->0)
{
long q=in.nextInt();
long w=in.nextInt();
int count = 0;
while(q!=w){
if(q<w)
{
w=w/2;
count++;
}
else if(q>w)
{
q=q/2;
count++;
}
}
System.out.println(count);
}
}
}
#41
Chef and Subarrays
Chef likes problems involving arrays. Unfortunately, the last one he tried to solve didn't quite get solved.
Chef has an array A of N positive numbers. He wants to find the number of subarrays for which the sum and product of elements are equal.
Please help Chef find this number.
Input
The first line of input contains an integer T denoting the number of test cases. T test cases follow. The first line of each test contains the integer N. The next line contains N integers — A1, A2, ..., AN — denoting the array.Output
For each test case, output a single line with the answer for the instance.Constraints
- 1 ≤ T ≤ 50
- 1 ≤ n ≤ 50
- 1 ≤ Ai ≤ 109
- A1 * A2 * ... * An ≤ 109
Example
Input: 3 3 1 3 2 4 4 1 2 1 6 1 2 2 2 2 1 Output: 4 5 9
Explanation:
Example case 1. There are 4 such subarrays: A[1..1], A[2..2], A[3..3], A[1..3]. Consider A[1..3], sum = 1 + 3 + 2 = 6, product = 1 * 3 * 2 = 6.
My Solution:
import java.util.Scanner;
class chefandsubarray {
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int b=in.nextInt();
while(b-->0)
{
int count=0;
int n=in.nextInt();
int arr[]=new int [n];
for(int i=0;i<n;i++)
{
arr[i]=in.nextInt();
}
for(int j=0;j<n;j++){
int sum=0;
int product =1;
for(int i=j;i>=0;i--)
{
sum+=arr[i] ;
product*=arr[i];
if (sum==product) count++;
}
}
System.out.println(count);
}
}
}
#42
Brackets
A valid parentheses sequence is a non-empty string where each character is either '(' or ')', which satisfies the following constraint:
You can find a way to repeat erasing adjacent pairs of parentheses '()' until it becomes empty.
For example, '(())' and '()((()()))' are valid parentheses sequences, but ')()(' and '(()' are not.
Mike has a valid parentheses sequence. He really likes everything about his sequence, except the fact that it is quite long. So Mike has recently decided that he will replace his parentheses sequence with a new one in the near future. But not every valid parentheses sequence will satisfy him. To help you understand his requirements we'll introduce the pseudocode of function F(S):
FUNCTION F( S - a valid parentheses sequence )
BEGIN
balance = 0
max_balance = 0
FOR index FROM 1 TO LENGTH(S)
BEGIN
if S[index] == '(' then balance = balance + 1
if S[index] == ')' then balance = balance - 1
max_balance = max( max_balance, balance )
END
RETURN max_balance
END
In other words, F(S) is equal to the maximal balance over all prefixes of S.
Let's denote A as Mike's current parentheses sequence, and B as a candidate for a new one. Mike is willing to replace A with B if F(A) is equal to F(B). He would also like to choose B with the minimal possible length amongst ones satisfying the previous condition. If there are several such strings with the minimal possible length, then Mike will choose the least one lexicographically, considering '(' to be less than ')'.
Help Mike!
Input
The first line of the input contains one integer T denoting the number of testcases to process.
The only line of each testcase contains one string A denoting Mike's parentheses sequence. It is guaranteed that A only consists of the characters '(' and ')'. It is also guaranteed that A is a valid parentheses sequence.
Output
The output should contain exactly T lines, one line per each testcase in the order of their appearance. The only line of each testcase should contain one string B denoting the valid parentheses sequence that should be chosen by Mike to replace A.
Constraints
1 ≤ T ≤ 5;
1 ≤ |A| ≤ 100000(105).
Example
Input: 1 ()((()())) Output: ((()))
My Solution:
import java.util.Scanner;
class bracket {
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int b=in.nextInt();
while(b-->0)
{
String s=in.next();
int balance=0;
int max_balance=0;
String S[]=s.split("");
for(int i=0;i<S.length;i++)
{
if(S[i] .equals('('+"")) balance = balance + 1;
if(S[i] .equals(')'+"")) balance = balance - 1;
max_balance = Math.max( max_balance, balance );
}
System.out.println();
for(int i=0;i<max_balance;i++) System.out.print("(");
for(int i=0;i<max_balance;i++) System.out.print(")");
}
}
}
Posted by lol ik
Comments
Post a Comment