Category Archives: Code Solve

Code if you can solve #codeifyoucansolve

Sereja and Votes

Posted on by
Reply

Sereja conducted a voting about N of his opinions. Ai percent of people voted for opinion number i.
This statistics is called valid if sum of all Ai is equal to 100.

Now let us define rounding up of a statistics A.

If Ai is not an integer, it will be rounded up to next integer.
Otherwise it will be left as it is.

e.g. 4.1 became 5, 4.9 became 5 but 6 will still be 6.

Now let us consider a statistics B of size N in which each of Bi is an integer. Now he wants to know whether there exists some valid statistic A of size N (may contain real numbers) such that after rounding it up, it becomes same as B?
Input

First line of input contain integer T – number of test cases.
For each test, case first line contains integer N – number of opinions.
Next line contains N integers B1, B2, …, BN as defined in the problem.

Output

For each test case, output YES or NO denoting the answer of the problem, i.e. if there exists some statistics A which could be rounded to make it B, print YES otherwise NO.
Constraints

1 ≤ T ≤ 50
1 ≤ N ≤ 10000
0 ≤ Bi ≤ 1000

Sub tasks

Subtask #1: N ≤ 100 (50 points)
Subtask #2: original (50 points)

Example

Input:
3
3
30 30 30
4
25 25 25 25
2
50 51
Output:
NO
YES
YES

Explanation

In test case 1, There can not be any A which could be rounded up to get B. Hence answer is NO.
In test case 2, In this case A = {25, 25, 25, 25}. After rounding we get {25, 25, 25, 25} which is equal to B. Hence answer is YES.
In test case 3, A = {49.5, 50.5}. After rounding up we get {50, 51} which is equal to B. Hence answer is YES.

#include
inline int get_input()
{
int num=0,sign=1;
char d = getchar_unlocked();
if(d == ‘-‘)
sign = -1;
while((d’9′) && d!=EOF&&d!=’-‘)
d = getchar_unlocked();
if(d == ‘-‘)
sign = -1, d=getchar_unlocked();
while(d>=’0’ && d<='9')
{
num=(num<<3)+(num<100)
flag = 0;
}
if(flag == 0)
printf(“NO\n”);
else
{
if(sum=1)
printf(“NO\n”);
else
printf(“YES\n”);
}
}
}
return 0;
}

http://www.codechef.com/viewplaintext/5736441
http://www.codechef.com/JAN15/status/SEAVOTE,vikasmcajnu

Chef and Stones

Posted on by
Reply

Chef is playing a game. Currently in the game, he is at a field full of stones. There are total N kinds of
stones. There is unlimited supply of each kind of stone.

Chef knows that one stone of kind i needs Ai minutes to pick it from the ground and it will give Chef a profit of
Bi Rs.

Chef has K minutes of free time. During this free time, Chef want to pick stones so as to maximize his profit.
But he can not pick stones of different kinds, he has to pick stones of a single kind.

Please help Chef to find the maximal possible profit.
Input

First line contains single integer T denoting the number of test cases.
First line of each test case contains two integers N and K.
Next line contains N integers Ai denoting the time needed to pick one stone of kind i.
Next line contains N integers Bi denoting the profit due to picking ithth stone.

Output

For each test case, print a single line containing maximal possible profit.

Constraints

1 ≤ T ≤ 5
1 ≤ N ≤ 105
1 ≤ K ≤ 109
1 ≤ Ai, Bi ≤ 109

Subtasks

Subtask N ≤ 5, T ≤ 2 Points: 30
Subtask N ≤ 105, T ≤ 5 Points: 70

Example

Input:
1
3 10
3 4 5
4 4 5

Output:
12

Explanation

If Chef picks stones of first kind he can pick 3 stones, he will get a profit of 3*4 = 12 Rs.
If Chef picks stones of second kind he can pick 2 stones, he will get a profit of 2*4 = 8 Rs.
If Chef picks stones of third kind he can pick 2 stones, he will get a profit of 2*5 = 10 Rs.

So the maximum possible profit is 12.

#include
#define MODS 1000000007
inline long long get_input()
{
long long num=0,sign=1;
char d = getchar_unlocked();
if(d == ‘-‘)
sign = -1;
while((d’9′) && d!=EOF&&d!=’-‘)
d = getchar_unlocked();
if(d == ‘-‘)
sign = -1, d=getchar_unlocked();
while(d>=’0’ && d<='9')
{
num=(num<<3)+(num<<1)+(d-'0');
d=getchar_unlocked();
}
return sign*num;
}
int main(void) {
int T;
unsigned long long int N,K,A[100000],B[100000],i,j;
double max,t1,t2;
T = (int)get_input();
while(T–)
{
N = get_input();
K = get_input();
i = 0;
max = 0;
while(i<N)
{
A[i] = get_input();
i++;
}
i = 0;
while(i<N)
{
B[i] = get_input();
i++;
}
i = 0;
j = 0;
while(imax)
{
max = t1*t2;
j = i;
}
i++;
}

printf(“%llu\n”,(K/A[j])*B[j]);
}
return 0;
}

http://www.codechef.com/viewplaintext/5694690

One Dimensional Kingdoms

Posted on by
Reply

N one dimensional kingdoms are represented as intervals of the form [ai , bi] on the real line.
A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L ≤ x ≤ R.

Your task is to determine minimum number of bombs required to destroy all the one dimensional kingdoms.
Input

First line of the input contains T denoting number of test cases.
For each test case, first line contains N denoting the number of one dimensional kingdoms.
For each next N lines, each line contains two space separated integers ai and bi.

Output

For each test case , output an integer denoting the minimum number of bombs required.
Constraints

Subtask 1 (20 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 100 , 0 ≤ ai ≤ bi ≤500

Subtask 2 (30 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 1000 , 0 ≤ ai ≤ bi ≤ 1000

Subtask 3 (50 points) : 1 ≤ T ≤ 20 , 1 ≤ N ≤ 105, 0 ≤ ai ≤ bi ≤ 2000
Example

Input:
1
3
1 3
2 5
6 9

Output:
2

Explanation

There are three kingdoms [1,3] ,[2,5] and [6,9]. You will need at least 2 bombs
to destroy the kingdoms. In one of the possible solutions, you can place two bombs at x = 2 and x = 6 .
#include

inline long get_input()
{
long num=0,sign=1;
char d = getchar_unlocked();
if(d == ‘-‘)
sign = -1;
while((d’9′) && d!=EOF && d!=’-‘)
d = getchar_unlocked();
if(d == ‘-‘)
sign = -1, d=getchar_unlocked();
while(d>=’0′ && d<=’9’)
{
num = (num<<3)+(num<<1)+(d-‘0’);
d = getchar_unlocked();
}
return sign*num;
}
int main(void) {
int a[2][100000],x1,x2,L,R;
long N,t,bmb,T,count;
T = get_input();
while(T–)
{
N = get_input();
t = 1;
L = get_input();
R = get_input();
count = 0;
bmb = 1;
while(t<N)
{
x1 = get_input();
x2 = get_input();
if(x1=R)
{
L = L;
R = R;
}
else if(x1>=L&&x1=R)
{
L = x1;
}
else if(x1>=L&&x2<=R)
{
L = x1;
R = x2;
}
else if(x1<=L&&x2=L)
{
R = x2;
}
else
{
a[0][count] = x1;
a[1][count] = x2;
count++;
}
t++;
}
N = count;
while(N>0)
{
t = 1;
count = 0;
L = a[0][0];
R = a[1][0];
while(t<N)
{
x1 = a[0][t];
x2 = a[1][t];
if(x1=R)
{
L = L;
R = R;
}
else if(x1>=L&&x1=R)
{
L = x1;
}
else if(x1>=L&&x2<=R)
{
L = x1;
R = x2;
}
else if(x1<=L&&x2=L)
{
R = x2;
}
else
{
a[0][count] = x1;
a[1][count] = x2;
count++;
}
t++;
}
bmb++;
N = count;
}
printf(“%ld\n”,bmb);
}
return 0;
}

http://ideone.com/6k3hVn

Linked List representation through JAVA.

Posted on by
Reply

class Element
{
Element next;
int num;
public Element(int val)
{
next = null;
num = val;
}
}
class LinkList
{
private Element head = null;
public void append(int val)
{
Element lastElement = null;
//code for retrive last node
if(head == null)
lastElement = null;
else
{
Element tmp = head;
while(tmp.next != null)
{
tmp = tmp.next;
}
lastElement = tmp;
}
//add next element
if(lastElement == null)
head = new Element(val);
else
lastElement.next = new Element(val);

}
public void printList()
{
System.out.println(“”);
if(head != null)
{
Element tmpElement = head;
while(tmpElement.next != null)
{
System.out.print(tmpElement.num+”->”);
tmpElement = tmpElement.next;
}

}

}
public static void main(String[] args)
{
LinkList ll = new LinkList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(5);
ll.append(6);
ll.append(7);
ll.append(8);
ll.append(9);
ll.append(10);
ll.printList();
}
}

Link to compiled source

http://ideone.com/eV4TUO

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation).

Posted on by
Reply

#codeifyoucansolve
Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,…,z. Assume that there is only one RPN form (no expressions like a*b*c).
Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.
Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

//sollution

#include <stdio.h>
#include<string.h>
int main(void) {
 char q[400],stack[400],str[400],ch;
 int n,top,i,front;
 scanf("%d",&n);
 while(n--)
 {
 front  = 0;
 top = 0;
 scanf("%s ",str);
 for(i=0;i<strlen(str);i++)
 {
           if(str[i]!='+'&&str[i]!='-'&&str[i]!='*'&&str[i]!='/'&&str[i]!='^'&&str[i]!='('&&str[i]!=')')
           {
              q[front++] = str[i];
           }
           else
           {
               if(str[i]=='+')
               {
                  while(top>0)
                  {
                   ch = stack[top-1];
                   if(ch != '(')
                   {
                      q[front++] = ch;
                      top--;
                   }
                   else
                     break;
                  }
               }
               else if(str[i]=='-')
               {
                  while(top>0)
                  {
                   ch = stack[top-1];
                   if(ch != '+'&&ch != '(')
                   {
                       q[front++] = ch;
                       top--;
                   }
                   else
                      break;
                  }
               }
               else if(str[i]=='*')
               {
                  while(top>0)
                  {
                   ch = stack[top-1];
                   if(ch != '+'&&ch != '-'&&ch != '(')
                   {
                       q[front++] = ch;
                       top--;
                   }
                   else
                     break;
                  }
               }
               else if(str[i]=='/')
               {
                  while(top>0)
                  {
                   ch = stack[top-1];
                   if(ch != '+'&&ch != '-'&&ch != '*'&&ch != '(')
                   {
                       q[front++] = ch;
                       top--;
                   }
                   else
                     break;
                  }
               }
               else if(str[i]=='^')
               {
                  while(top>0)
                  {
                   ch = stack[top-1];
                   if(ch != '+'&&ch != '-'&&ch != '*'&&ch != '/'&&ch != '(')
                   {
                       q[front++] = ch;
                       top--;
                   }
                    else
                      break;
                  }
               }
               else if(str[i]==')')
               {
                  while(stack[top-1]!='(')
                  {
                   ch = stack[top-1];
                   q[front++] = ch;
                   top = top -1;
                  }
                  top = top - 1;
               }
               if(str[i] !=')')
                  stack[top++] = str[i];
           }
 }
 while(top>0)
 {
    q[front++] =  stack[top-1] ;
    top = top-1;
 }
 q[front] = '';
 printf("%s\n",q);
 }
 return 0;
}

http://ideone.com/FXfx0t

Given two binary strings, A and B, output 1 if B is a substring of A and 0 otherwise.

Posted on by
Reply

#codeifyoucansolve
Given two binary strings, A (of length 10) and B (of length 5), output 1 if B is a substring of A and 0 otherwise.

Please note, that the solution may only be submitted in the following languages: Brainf**k, Whitespace and Intercal.
Input

24 lines consisting of pairs of binary strings A and B separated by a single space.
Output

The logical value of: ‘B is a substring of A’.
Example

First two lines of input:

1010110010 10110
1110111011 10011

First two lines of output:
1
0

//sollution
#include <stdio.h>

int main()
{
 int T = 24,SI,MSI,two,flag,i,j;
 char str[25],sub[6];
 while(T--)
 {
 two = 1;
 SI = 0;
 MSI = 0;
 flag = 0;
 scanf("%s ",str);
 scanf("%s ",sub);
 for(i=4;i>=0;i--)
 {
 if(sub[i]=='0')
   two*=2;
  else
    {
       SI+=two;
       two*=2;
    }
 }
 for(i=23;i>=4;i--)
 {
 for(j=i;j>=(i-4);j--)
 {
 if(str[j]=='0')
    two*=2;
   else
     {
       MSI+=two;
       two*=2;
 } 
 }
 if(MSI%SI==0)
 {
   flag = 1;
   break;
 }
 
 }
 if(flag)
 printf("1\n");
 else
   printf("0\n");
 
 }
}

http://ideone.com/tSR5ET

Drawing competition for K kids, but with K human-sized pencils.

Posted on by
Reply

#codeifyoucansolve
Liliputs are holding a drawing competition for K kids, but with K human-sized pencils stolen from humans. In order to make life easier for the kids, the organizers want to give a pencil to each kid in a way such that the sum of the absolute differences of the height of a kid and the length of the pencil assigned to him/her is minimized. What is the minimum sum of absolute differences that can be achieved?
Input

The first line contains the number of test cases N (0 < N ≤ 3).

For each test case, the first line contains the number of kids and pencils K (0 < K ≤ 100). The second line contains K positive integers, each containing the height in millimeter of a kid. The third line contains K positive integers, each containing the length in millimeter of a pencil.
Output

For each test case, print the case number, followed by a colon, followed by a single space, followed by a single integer indicating the minimum sum of absolute differences achieved (in millimeter).
Sample Input

2
5
51 60 51 72 70
65 60 88 72 88
4
123 234 188 175
219 334 122 233

Sample Output

Case 1: 69
Case 2: 190
///sollution 

#include <stdio.h>
#include<limits.h>
#include<stdlib.h>
inline int get_input()
{
int num=0,sign=1;
char d=getchar_unlocked();
if(d=='-')
sign=-1;
while((d<'0'||d>'9')&&d!=EOF&&d!='-')
d=getchar_unlocked();
if(d=='-')
sign=-1, d=getchar_unlocked();
while(d>='0'&&d<='9')
{
num=(num<< 3)+(num<<1)+(d-'0');
d=getchar_unlocked();
}
return sign*num;
}

//randomized Quicksort
  /*int i,temp,x,j;
  srand(time(0));
  i= rand() % (l - f) + f;*/
int partition(long long unsigned A[100],int f,int l)
{
 //Renodm Number
 unsigned long  num_bins = (unsigned long )(l+1) ,
                       num_rand = (unsigned long )(RAND_MAX+1) ,
                       bin_size = num_rand/num_bins ,
                       defect = num_rand%num_bins;
  int i,temp,x,j;
  while (num_rand - defect <= (unsigned long)(i = random()));
  i  =  (  i / bin_size  )  %  (  l  -  f  ) + f;
  ///////////
  temp = A[l];
  A[l] = A[i];
  A[i] = temp;
  i = f-1;
  x = A[l];
  for(j=f;j<l;j++)
  {
   if(A[j]<=x)
   {
   i = i+1;
     temp = A[i];
   A[i] = A[j];
   A[j] = temp;
   }
  }
      temp = A[i+1];
   A[i+1] = A[l];
   A[l] = temp; 
  return i+1;
}
void quicksort(long long unsigned A[100],int first,int last)
{
 int q;
 if(first<last)
 {
 q=partition(A,first,last);
 quicksort(A,first,q-1);
 quicksort(A,q+1,last);
 }
}
///////////////////
int main(void) {
 long long unsigned Kid[100],pencil[100];
 int t,i,cs=1,N,K,minsum;
 N=get_input();
 while(N--)
 {
 K=get_input();
 t=K;i=0;
 while(t--)
 Kid[i++] = get_input();
 t=K;i=0;
 while(t--)
 pencil[i++] = get_input();
 quicksort(Kid,0,K-1);
     quicksort(pencil,0,K-1);
     minsum = 0;
    for(i=0;i<K;i++)
       minsum+=abs(pencil[i]-Kid[i]);
    printf("Case %d: %d\n",cs,minsum);
    cs++;
 }
 return 0;
}

http://ideone.com/LeeuX7

getchar_unlocked()

Posted on by
Reply

#codeifyoucansolve
C programming :
getchar_unlocked();
: This reads a charchater from stdin.
when there is no thread safety required but speed is.
Program :

#include<stdio.h>

int main()
{
  char ch;
  ch     =       getchar_unlocked();
  printf("%c\n",ch);
  return 0;
}

http://ideone.com/zABJQ0

How much water would be collected between the buildings?

Posted on by
Reply

#codeifyoucansolve
Andrew has recently moved to Wengaluru. He finds this city amazing as all the buildings of the city are of same shape. There are N buildings in a row with no space in between. Buildings may have different heights while width in other two dimensions is always 1 unit.

Rain occurs very frequently in Wengaluru so Andrew being the curious boy thought that if the entire city is flooded with water then How much water would be collected between the buildings? Water would be collected between the buildings if a small sized building occurs between 2 big sized building i.e. if a building with small height occurs between buildings of relatively larger height.

Input
The first line contains T, the number of test cases.
Each test case consist of 2 lines. First line of each test case Would contain N- total no. of buildings in the city. Second line contains N integers, the height of N buildings.

Output
For each test case output the answer to the above query. As the total water collected between the buildings could be a huge number so output your answer by taking Modulus with 10^9+7(1000000007).

Constraints
1<=T<= 10
1<=N<=10^5
1<=A[i]<=10^7

Sample Input (Plaintext Link)
2
5
3 2 1 4 5
5
1 2 3 4 5
Sample Output (Plaintext Link)
3
0
Explanation
In the 1st testcase height of the buildings are 3,2,1,4 and 5.So for 2nd building it could collect 1 unit of water,3rd building could collect 2 units,which sums up to 3.
In the 2nd testcase as we can see no water could be collected between any 2 buildings.So total water collected would be 0 units.
Time Limit: 1 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Scoring: Score is assigned in case any testcase passes.

#include <stdio.h>
#define MAXA 10000000LL
#define MAXN 100000L
int main(void) {
 int T,flag=0;
 unsigned long N,index,i,j;
 unsigned long long A[MAXN],max1,max2,max,w;
 scanf("%d",&T);
 if(T<1||T>10)
 return 0;
 for(;T>0;T--)
 {
 w=0;flag=0;
 scanf("%ld",&N);
 if(N<1||N>MAXN)
  break;
 for(i=0;i<N;i++)
   scanf("%lld",&A[i]);
     for(i=0;i<N;)
     {
      if(A[i]<1||A[i]>MAXA)
        break;
      max1=A[i];
      max2=A[i+1];
      index=i+1;
      for(j=i+1;j<N;j++)
      {
      if(A[j]>max2)
       {
        max2=A[j];
        index=j;
        flag=1;
       }
       if(A[j]<max2&&flag)
         break;
      }
      if(j>N&&(flag==0))
        break;
      if(max1>max2)
        max=max2;
      else
        max=max1;
      for(j=i+1;j<index;j++)
      {
      if(A[j]<max)
        w=w+(max-A[j]);
      }
      flag=0;
      i=index;
     }
     printf("%ld\n",w);
 }
 return 0;
}

http://ideone.com/fork/2BnwrC

palindrome

Posted on by
Reply

#codeifyoucansolve
MODIFIED PLOINDROME :::::::: 🙂

Do you know that The Chef has a special interest in palindromes? Yes he does! Almost all of the dishes in his restaurant is named by a palindrome strings. The problem is that a name of a dish should not be too long, so The Chef has only limited choices when naming a new dish.

For the given positive integer N, your task is to calculate the number of palindrome strings of length not exceeding N, that contain only lowercase letters of English alphabet (letters from ‘a’ to ‘z’, inclusive). Recall that a palindrome is a string that reads the same left to right as right to left (as in “radar”).

For example:

For N = 1, we have 26 different palindromes of length not exceeding N:
“a”, “b”, …, “z”.
For N = 2 we have 52 different palindromes of length not exceeding N:
“a”, “b”, …, “z”,
“aa”, “bb”, …, “zz”.
For N = 3 we have 728 different palindromes of length not exceeding N:
“a”, “b”, …, “z”,
“aa”, “bb”, …, “zz”,
“aaa”, “aba”, …, “aza”,
“bab”, “bbb”, …, “bzb”,
…,
“zaz”, “zbz”, …, “zzz”.

Since the answer can be quite large you should output it modulo 1000000007 (109 + 7). Yes, we know, most of you already hate this modulo, but there is nothing we can do with it
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 a single integer N.
Output

For each test case, output a single line containing the answer for the corresponding test case.
Constrains

1 ≤ T ≤ 1000
1 ≤ N ≤ 109

Example

Input:
5
1
2
3
4
100

Output:
26
52
728
1404
508533804

After Modification ..

sollution :

#include<stdio.h>
#include<math.h>
#define MAX 1000000000LL
#define MODS 1000000007LL
#define ULL unsigned long long

int main()
{
   int T;
   ULL N,i,mods1,mods2,sum=0LL,p=0LL,e,mod;
   scanf("%d",&T);
   if(T>1000||T<1)
     return 0;
   for(;T>0;T--)
   {
      scanf("%llu",&N);
      if(N>MAX||N<1)
        break;
      if(N%2==0L)
      {
        p=0LL;
        sum=0LL;
         for(i=0;i<(N/2);)
         {
             mod =1;e=0;
             while(e<p)
             {
              e++;
              mod=(26*mod)%MODS;
             }
             sum=(sum+2*((mod*26)%MODS))%MODS;
            //mods1=(26*(((ULL)(pow(26,i)))%MODS))%MODS;
            //mods2=(26*(((ULL)(pow(26,i)))%MODS))%MODS;
            //sum=((sum%MODS)+((mods1+mods2)%MODS))%MODS;
            //sum=sum%MODS;
            p++;
            i=i+1;
         }
      }
      else
      {
       p=0LL;
       sum=0LL;
        for(i=0;i<(N/2);)
         {
             mod =1;e=0;
             while(e<p)
             {
              e++;
              mod=(26*mod)%MODS;
             }
             sum=(sum+2*((mod*26)%MODS))%MODS;
            //mods1=(26*(((ULL)(pow(26,p)))%MODS))%MODS;
            //mods2=(26*(((ULL)(pow(26,p)))%MODS))%MODS;
            //sum=sum+(mods1+mods2);
            //sum=((sum%MODS)+((mods1+mods2)%MODS))%MODS;
            //sum=sum%MODS;
            p++;
            i=i+1;
         }   
           mod =1;e=0;
             while(e<p)
             {
              e++;
              mod=(26*mod)%MODS;
             }
             sum=(sum+(mod*26)%MODS)%MODS;
      }
      printf("%llu\n",sum);
   }
   return 0;
}

//compiled
http://ideone.com/ZUEXuq