Saturday 17 March 2012

TopCoder SRM 537 Match

TopCoder SRM 537 Match

250 PROBLEM

King Dengklek is the perfect king of Kingdom of Ducks, where slimes and ducks live together in peace and harmony.

After several years of waiting, King Dengklek and the queen finally had a baby. Now he is looking for a name for the newborn baby. According to the private rule of Kingdom of Ducks, the name of each member of the royal family must be such that:

It must consist of exactly eight letters. All letters must be lowercase ('a'-'z').
It must have exactly two vowels and six consonants. (Vowels are the letters 'a', 'e', 'i', 'o', and 'u'; the rest are consonants.)
The two vowels must be equal.

SO I HAVE WRITTEN A SIMPLE CODE FOR THIS

#include<iostream>

#include<vector>

#include<stdio.h>

#include<stdlib.h>

#include<queue>

#include<list>

#define show(x) copy(x.begin(),x.end(),output)

#include<iterator>

#define sort(x) sort(x.begin(),x.end())

#include<string>

#define vs vector<string>

#define vi vector<int>

#define pb push_back

#include<map>

#include<algorithm>

#include<sstream>

#include<stack>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<cctype>

using namespace std;

class KingXNewBaby

{

public:

string isValid (string name)

{

int v = 0;

if(name.size() != 8 )

{

return "NO";

}

for(int i = 0 ; i < name.size() ; i++)

{

if( (name[i] == 'a') || (name[i] == 'e') || (name[i] == 'i') || (name[i] == 'o') || (name[i] == 'u') || (name[i] == 'e' ))

{

v++;

}

if( v == 2)

{

return "YES";

}

else

{

return "NO";

}

return 0;

}

};

For example, "dengklek" is a valid name because it consists of exactly eight letters: six consonants and two identical vowels, 'e'.

You are given a String name. Please help the kingdom determine whether name is valid. Return "YES" if it is a valid name for King Dengklek's newborn baby, or "NO" otherwise.

Sunday 26 February 2012

Codeforces Round #109 (Div. 2)

B. Combination
Ilya plays a card game by the following rules.

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number ai, and the bottom contains number bi, then when the player is playing the card, he gets ai points and also gets the opportunity to play additional bi cards. After the playing the card is discarded.

More formally: let's say that there is a counter of the cards that can be played. At the beginning of the round the counter equals one. When a card is played, the counter decreases by one for the played card and increases by the number bi, which is written at the bottom of the card. Then the played card is discarded. If after that the counter is not equal to zero, the player gets the opportunity to play another card from the remaining cards. The round ends when the counter reaches zero or the player runs out of cards.

Of course, Ilya wants to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of cards Ilya has.

Each of the next n lines contains two non-negative space-separated integers — ai and bi (0 ≤ ai, bi ≤ 104) — the numbers, written at the top and the bottom of the i-th card correspondingly.

SO I HAVE WRITTEN A SIMPLE CODE FOR THIS

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<cctype>
using namespace std;
int main()
{
multimap<int , int , less<int> > m;
multimap<int,int>::iterator it ;
multimap<int,int>::iterator iter;
int n = 0;
int a = 0;
int b = 0;
int i = 0 ;
int score = 0;
int count = 1;
cin>>n;
for(i = 0 ; i < n ; i ++)
{
cin>>a;
cin>>b;
m.insert(pair<int,int>(b,a));

}
while(count > 0)
{
count--;
if(count >= 0)
{
it = m.end();

iter = ++it; // as iterator is invalidated
score =+ (iter->second);
count = count + (iter->first);
m.erase(iter);
}
}
cout<<score<<endl;
return 0;
}
BY : SAURABH BHATIA (GNDU , RC , JAL)

Codeforces Round #109 (Div. 2)

A. I_love_%username%
Vasya adores sport programming. He can't write programs but he loves to watch the contests' progress. Vasya even has a favorite coder and Vasya pays special attention to him.

One day Vasya decided to collect the results of all contests where his favorite coder participated and track the progress of his coolness. For each contest where this coder participated, he wrote out a single non-negative number — the number of points his favorite coder earned in the contest. Vasya wrote out the points for the contest in the order, in which the contests run (naturally, no two contests ran simultaneously).

Vasya considers a coder's performance in a contest amazing in two situations: he can break either his best or his worst performance record. First, it is amazing if during the contest the coder earns strictly more points that he earned on each past contest. Second, it is amazing if during the contest the coder earns strictly less points that he earned on each past contest. A coder's first contest isn't considered amazing. Now he wants to count the number of amazing performances the coder had throughout his whole history of participating in contests. But the list of earned points turned out long and Vasya can't code... That's why he asks you to help him.

Input
The first line contains the single integer n (1 ≤ n ≤ 1000) — the number of contests where the coder participated.

The next line contains n space-separated non-negative integer numbers — they are the points which the coder has earned. The points are given in the chronological order. All points do not exceed 10000.

Output
Print the single number — the number of amazing performances the coder has had during his whole history of participating in the contests.

#include<iostream>
#include<vector>
using namespace std;
int main()
{

int n = 0;
int a = 0;
int count = 0;
int small = 0;
int large = 0;
int i = 0;
cin>>n;
vector<int>code(n,0);
for(i = 0 ; i < n ; i++)
{
cin>>a;
code[i] = a;
}
for(i = 1 ; i < n ; i ++)
{
large = 0;
small = 0;
for(int j = 0 ; j < i ; j++)
{
if(code[i] > code[j])
{
large++;
}
else if(code[i] < code[j])
{
small++;
}
}
if(small == i || large == i)
{
count++;
}
}
cout<<count<<endl;
return 0;
}

BY : SAURABH BHATIA (GNDU , RC , JAL)

Friday 17 February 2012

Codeforces Round #106 (Div. 2)

A. BUSINESS TRIP

What joy! Petya's parents went on a business trip for the whole year and the playful kid is left all by himself. Petya got absolutely happy. He jumped on the bed and threw pillows all day long, until...

Today Petya opened the cupboard and found a scary note there. His parents had left him with duties: he should water their favourite flower all year, each day, in the morning, in the afternoon and in the evening. "Wait a second!" — thought Petya. He know for a fact that if he fulfills the parents' task in the i-th (1 ≤ i ≤ 12) month of the year, then the flower will grow by a_i centimeters, and if he doesn't water the flower in the i-th month, then the flower won't grow this month. Petya also knows that try as he might, his parents won't believe that he has been watering the flower if it grows strictly less than by k centimeters.

Help Petya choose the minimum number of months when he will water the flower, given that the flower should grow no less than by kcentimeters.

Input

The first line contains exactly one integer k (0 ≤ k ≤ 100). The next line contains twelve space-separated integers: the i-th (1 ≤ i ≤ 12) number in the line represents a_i (0 ≤ a_i ≤ 100).

Output

Print the only integer — the minimum number of months when Petya has to water the flower so that the flower grows no less than by kcentimeters. If the flower can't grow by k centimeters in a year, print -1.

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<cctype>
using namespace std;

int main()
{
int K = 0;
int ret = 0;
int sum = 0;
int a1 = 0;
vector<int>a;
cin>>K;

for(int i = 0 ; i < 12 ; i++)
{
cin>>a1;
a.pb(a1);
}
sort(a.begin(),a.end());
for(int j = a.size() - 1 ; j >= 0 ; j--)
{
sum = sum + a[j];
ret++;
if( sum >= K)
{
break;
}
}
if( K == 0)
{
ret = 0;
cout<<ret;
return 0;
}
if(sum < K )
{
ret = -1;
cout<<ret;
return 0;
}
cout<<ret<<endl;
cin.get();
return 0;
}

BY: SAURABH BHATIA(GNDU , RC JAL)

Saturday 11 February 2012

Codeforces Round #104 (Div. 1)

A. Lucky Conversion

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has two strings a and b of the same length n. The strings consist only of lucky digits. Petya can perform operationsof two types:

replace any one digit from string a by its opposite (i.e., replace 4 by 7 and 7 by 4);
swap any pair of digits in string a.

Petya is interested in the minimum number of operations that are needed to make string a equal to string b. Help him with the task.

solution:

As i have solve this problem in a very easy way...just check it out....

BY: SAURABH BHATIA(GNDU , RC JAL)

Thursday 9 February 2012

TopCoder SRM PROBLEM

Installation programs often run several tasks, one after another. Each task is assigned an integer, the expected execution time of this task. During the installation, a progress bar shows the user what percentage of the installation time has elapsed. In this problem, the bar will be represented by a string containing exactly 20 characters. If X% of the installation has been completed, then the leftmost X% of these characters should be a '#', while the remaining characters should be '.'. If necessary, round down the number of '#' characters to the nearest integer less than or equal to the actual value (see example 0). The bar starts at 0% and is only updated each time a task finishes execution.
Create a class ProgressBar containing the method showProgress which takes a vector <int> taskTimes, the expected execution time for each task in the order they are run, and an int tasksCompleted, the number of these tasks that have been completed. The method should return a string containing exactly 20 characters showing the progress bar according to the descriptions above.

I HAVE SOLVE THIS QUESTION IN A VERY SIMPLE WAY...:)

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<cctype>
using namespace std;

class ProgressBar
{
public:
string showProgress (vi taskTimes , int tasksCompleted)
{
string ret;
int ctotal = 0;
double per = 0;
int total = 0;
for(int i = 0 ; i <taskTimes.size() ; i++)
{
total = total + taskTimes[i];
if( i == tasksCompleted - 1)
{
ctotal = total;
}
}
per = double(ctotal / (total * 1.000));
total = int(20 * per);
for(int j = 0 ; j < 20 ; j++)
{
if( j < total)
{
ret = ret + "#";
}
else
{
ret = ret + ".";
}
}
return ret;
}
};
int main()
{
ProgressBar p;
vi a;
a.pb(19);
a.pb(20);
a.pb(25);
a.pb(35);
a.pb(39);
int c = 3;
string d = p.showProgress(a,c);
cout<<d<<endl;
cin.get();
return 0;
}

BY SAURABH BHATIA ( GNDU , RC , JAL)

Saturday 4 February 2012

SPOJ (ONLINE JUDGE) CODING CONTEST PROBLEM

SPOJ CONTEST PROBLEM

Half of a Set

Problem code: HS11PART

You are given X, a set of n < 20 positive integers: x₁, x₂, ... x_n, where x_i < 20. Let S=x₁ +x₂ + ... + x_n be the sum of all x_i. Please, check if there exists a subset of X whose sum of elements is equal to S/2.

Input

First t < 500, the nuber of sets. Next, for each test case, two lines follow. The first contains n, while the second the n set elements, separated by spaces.

Output

For each test case output one word in a separate line: YES if it is possible to achieve S/2 and NO if it is impossible.

SO I HAVE WRITTEN THIS SIMPLE CODE FOR YOU....

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
using namespace std;
int main()
{
int S = 0;
int t = 0 ; cin>>t;
int j = 0;
int X[20];
int flag = 0;
for(int i = 0 ; i < t ; i ++)
{
int n ; cin>>n;
for(j = 0 ; j < n ; j++)
{
scanf("%d",&X[j]);

}
S = 0;
for(j = 0 ; j < n ; j++)
{
S = S + X[j];
}
flag = 0;
for(j = 0 ; j < n-1 ; j++)
{
for(int k = j+1; k < n ; k++)
{

if( (X[j] + X[k]) == S/2 )
{
flag++;
break;
}
if( flag != 0)
{
break;
}
}
}
if( flag != 0 )
{
printf("YES\n");

}
else
{
printf("NO\n");
}
}

return 0;
}


BY : SAURABH BHATIA (GNDU , RC , JAL)

Thursday 2 February 2012

SPOJ (ONLINE JUDGE) CODING CONTEST PROBLEM

SPOJ PROBLEM

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a dictionary approach you decide to explore something more along the lines of Markov-chain text generation. Since you are generating character names rather than paragraphs, you treat each character as a state, and in order to simplify matters you make the assumption that each letter is independent of all of the letters coming before it except for its immediate predecessor.

The input consists of two lines. The first character of the first line is the character to be considered. The rest of the line will consist of an arbitrary number of characters, this is the sample of text to be considered. Ignore the content of the second line. You are to output a single character, the one which occurs most frequently after the given character in the sample.

The number of characters is small enough that you need not worry about exceeding the limits of int. The character string will consist of only uppercase or lowercase alphabets, you will not encounter any other characters.

Example

Input

aabcdefghijklmnopqrstuvwxyza

Output

SO I HAVE WRITTEN A SIMPLE CODE FOR THIS.....AGAIN ENJOY PROGRAMMING....:)

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<cctype>
using namespace std;
class saurabh
{
public:
char find( string s)
{
int count = 0;
int temp = 0;
int index = 0;
int position = 0;
char f = s[0];
stringstream ss;
ss<<f;
char ret;
position = s.find(ss.str());
index = count + position;
while(position != string ::npos)
{
count = 0;
for(int i = position ; i < s.size() ; i++)
{
if(s[i] == f)
{
count++;
}
else
{
break;
}
}
if( temp < count)
{
temp = count;
index = count + position ;
}
position = s.find(f,position+1);
}
ret = s[index];
return ret;
}
};
int main()
{
string s = "aabcdefghijklmnoaaaapqrstuvwxyza";
saurabh p;
char c = p.find(s);
cout<<c<<endl;
cin.get();
return 0;
}

BY: SAURABH BHATIA (GNDU , RC , JAL)

CODE CHEF FEBRUARY CHALLENGE (2 - 11) FEB

MAX COUNT PROBLEM

Given an array A of length N, your task is to find the element which repeats in A maximum number of times as well as the corresponding count. In case of ties, choose the smaller element first.

Input

First line of input contains an integer T, denoting the number of test cases. Then follows description of T cases. Each case begins with a single integer N, the length of A. Then follow N space separated integers in next line. Assume that 1 <= T <= 100, 1 <= N <= 100 and for all i in [1..N] : 1 <= A[i] <= 10000

Output

For each test case, output two space separated integers V & C. V is the value which occurs maximum number of times and C is its count.

Example

Input:
2
5
1 2 3 2 5
6
1 2 2 1 1 2

Output:
2 2
1 3

Description:
In first case 2 occurs twice whereas all other elements occur only once. 
In second case, both 1 and 2 occur 3 times but 1 is smaller than 2.

SO I HAVE WRITTEN THE SIMPLE CODE FOR THIS......JUST ENJOY...PROGRAMMING...

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
    int T = 0;
    int A[100];
    int N = 0 , index = 0 , V = 0;
    int C = 0 ,count = 0;
    scanf("%d",&T);
    cout<<""<<endl;
    for(int i = 0 ; i < T ; i++)
    {
            scanf("%d",&N);
            cout<<""<<endl;
            for(int j = 0 ; j < N ; j++)
            {
                    cin>>A[j];
                    
            }
            for(int k = 0 ; k < N ; k++)
            {
                    count = 0;
                    if(A[k] != 0)
                    for(int o = 0 ; o < N ; o++)
                    {
                            if(A[k] == A[o])
                            {
                                    count++;
                                   
                            }      
                    }
                    if(V < count)
                    {
                            C = count;
                            index = k;
                            V = A[k];
                    }
                    else if(C == count)
                    {
                         if(A[index] > A[k])
                         {
                                     index = k;
                                     V = A[k];
                         }
                    }
            }
            cout<<V<<" "<<C<<endl;
    }

    return 0;
}

BY:   SAURABH BHATIA (GNDU RC JAL)

Thursday 26 January 2012

GOOGLE NIM GAME

THEY HAVE ASKED TO MAKE A NIM GAME AND PRESENT IT IN A GOOD WAY SO IN THIS QUES PRESENTATION ALSO HAS ITS OWN MARKS SO I HAVE WRITTEN THE SIMPLE CODE FOR THIS...

#include<iostream.h>

#include<conio.h>

#include<process.h>

#include<iomanip.h>

#include<dos.h>

void selection();

void display();

void moving();

void ending();

void rules();

int *a;

char x='A';

char p1[20] , p2[20];

int turn = 0;

void main()

{

clrscr();

gotoxy(24,10);

cout<<"WELCOME TO THE NIM GAME MADE BY SAURABH "<<endl;

gotoxy(24,11);

cout<<"________________________________________"<<endl;

cin.get();

clrscr();

rules();

selection();

getch();

}

void rules()

{

cout<<" THIS GAME WILL HAVE 2 PLAYERS "<<endl;

cout<<" " <<endl;

cout<<" FIRST OF ALL PLZ ON YOUR CAPSLOCK KEY " <<endl;

cout<<" "<<endl;

cout<<" IN THIS YOU HAVE TO TAKE OBJECTS FROM THE HEAP (A , B , C , D) TURN WISE "<<endl;

cout<<" "<<endl;

cout<<" THE PLAYER WHO TAKE OUT THE LAST OBJECT WILL BE THE WINNER OF THE GAME "<<endl;

cout<<" " <<endl;

cout<<" FOR THIS YOU HAVE TO FIRST INPUT THE NAME OF HEAP AND THAN NUMBER OF "<<endl;

cout<<" ELEMENTS YOU WANT TO TAKE FROM THAT HEAP "<<endl;

cout<<" " << endl;

cout<<" ONE HEAP CAN TAKE MAXIMUM OF 9 OBJECTS SO INPUT THE NUMBER OF OBJECTS CAREFULLY"<<endl;

cout<<" BEFORE STARTING THE GAME "<<endl;

cout<< " "<<endl;

cout<<" YOU CAN PRESS 'E' FOR EXIT AT ANY TIME BETWEEN THE GAME " <<endl;

cout<<" "<<endl;

cout<<" PRESS ENTER TO PROCEED FURTHER "<<endl;

cin.get();

clrscr();

}

void selection()

{

int obj;

char y;

cout<<"ENTER THE NAME OF PLAYER 1 "<<endl;

cin.get(p1,15);

cout<<"ENTER THE NAME OF PLAYER 2 "<<endl;

cin>>p2;

a = new int[3];

cout<<"MAXIMUM NUMBER OF OBJECTS A HEAP CAN HAVE IS 9 "<<endl;

cout<<" "<<endl;

for(int i=0;i<3;i++)

{

y = x+i;

cout<<"ENTER THE OBJECTS IN HEAP "<<y<<endl;

cin>>obj;

a[i] = obj;

}

cin.get();

clrscr();

gotoxy(24,10);

cout<<p1<<" WILL START THE GAME "<<endl;

cout<<""<<endl;

gotoxy(24,11);

cout<<"BEST OF LUCK"<<endl;

cout<<""<<endl;

gotoxy(24,12);

cout<<"PRESS ENTER TO START THE GAME "<<endl;

cin.get();

clrscr();

display();

}

void display()

{

cout<<"SIZES OF HEAP"<<setw(30)<<"MOVES" <<endl;

cout<<" "<<endl;

cout<<"A"<<setw(5)<<"B"<<setw(5)<<"C";

cout<<endl;

cout<<a[0]<<setw(5)<<a[1]<<setw(5)<<a[2];

moving();

}

void moving()

{

int elements;

char ch;

char c = getch();

switch(c)

{

case 'A':

ch = 'A';

if(a[0] == 0)

{

moving();

}

else

{

elements = getch();

elements = elements - 48;

a[0] = a[0] - elements;

}

break;

case 'B':

ch = 'B';

if(a[1] == 0)

{

moving();

}

else

{

elements = getch();

elements = elements - 48;

a[1] = a[1] - elements;

}

break;

case 'C':

ch = 'C';

if(a[2] == 0)

{

moving();

}

else

{

elements = getch();

elements = elements - 48;

a[2] = a[2] - elements;

}

break;

case 'E':

exit(0);

break;

default:

moving();

}

turn++;

if(turn % 2 == 0)

{

cout<<setw(21)<<p2<<" HAS MOVED "<<elements<<" FROM " << ch <<endl;

}

else

{

cout<<setw(21)<<p1<<" HAS MOVED "<<elements<<" FROM "<< ch<<endl;

}

cout<<a[0]<<setw(5)<<a[1]<<setw(5)<<a[2];

if((a[0] == 0) && (a[1] == 0) && (a[2] == 0) )

{

sleep(1);

ending();

}

else

{

moving();

}

void ending()

{

clrscr();

if( turn % 2 ==0)

{

gotoxy(24,10);

cout<<p2<< " HAS WON THE GAME "<<endl;

}

else

{

gotoxy(24,10);

cout<<p1<<" HAS WON THE GAME "<<endl;

}

gotoxy(24,11);

cout<<"THANKS FOR PLAYING NIM GAME "<<endl;

gotoxy(24,12);

cout<<"REGARDS : SAURABH BHATIA CSE (2010 - 2014) "<< endl;

}

BY: SAURABH BHATIA (GNDU , RC JAL)

HONE YOUR CODING SKILLS

Pages

Saturday 17 March 2012

TopCoder SRM 537 Match

Sunday 26 February 2012

Codeforces Round #109 (Div. 2)

Codeforces Round #109 (Div. 2)

Friday 17 February 2012

Codeforces Round #106 (Div. 2)

Saturday 11 February 2012

Codeforces Round #104 (Div. 1)

Thursday 9 February 2012

Saturday 4 February 2012

SPOJ (ONLINE JUDGE) CODING CONTEST PROBLEM

SPOJ CONTEST PROBLEM

Half of a Set

Problem code: HS11PART

Input

Output

Thursday 2 February 2012

SPOJ (ONLINE JUDGE) CODING CONTEST PROBLEM

CODE CHEF FEBRUARY CHALLENGE (2 - 11) FEB

Input

Output

Example

Thursday 26 January 2012

GOOGLE NIM GAME

About Me

Blog Archive