//Author: Ujjal Suttra DHar [CSE’08,RUET]

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
int weight;
char value;
const node *child0;
const node *child1;

node( int c, int i ) {
value = c;
weight = i;
child0 = 0;
child1 = 0;
}

node( const node* c0, const node* c1 ) {
value = 0;
weight = c0->weight + c1->weight;
child0 = c0;
child1 = c1;
}

bool operator<( const node &a ) const {
if(weight ==a.weight)
return value>a.value;
else
return weight >a.weight;
}

void traverse(string code="") const{

if ( child0 ) {
child0->traverse( code + ‘0’ );
child1->traverse( code + ‘1’ );
} else {
cout <<" " <<value <<" ";
cout <<weight;
cout <<" " <<code <<endl;
}
}

};

/*
void count_chars( int *counts )
{
for ( int i = 0 ; i <256 ; i++ )
counts[ i ] = 0;

freopen("input.dat","r",stdin);

char c;
while((c=getchar())!=EOF)
counts[c]++;
}

*/

int main()
{

freopen("input.dat","r",stdin);

int counts[ 256 ];
char a[1000];

gets(a);

for ( int i = 0 ; i <256 ; i++ )
counts[ i ] = 0;

for(int i=0;i<strlen(a);i++)
counts[a[i]]++;

priority_queue < node > q;

for (int i = 0 ; i <256 ; i++ )
if ( counts[ i ] )
q.push( node( i, counts[ i ] ) );

//if you wanna show the queue
/*while(!q.empty()){
cout<<q.top().value<<endl;
q.pop();
}
*/

while ( q.size() >1 ) {
node *child0 = new node( q.top() );
q.pop();
node *child1 = new node( q.top() );
q.pop();
q.push( node( child0, child1 ) );
}

cout <<"CHAR FREQUENCY HOFFMAN-CODE" <<endl;
q.top().traverse();
return 0;
}

[/code]

Base-Class Access Control
When a class inherits another,the members of the base class become members of the derived class.
Class inherits uses the general form:
[code]
class derived-class:access base-class{
//body of class
};
[/code]

The access status of the base class’s members inside the derived class is determined by the access.
There are three types of access specifier.They are public,private and protected. If no access specifier is present, the access specifier is by default private.

When the access specifier for a base class is public, all public members of the base class become public members of the derived class and all protected members of the base become protected members of the derived class.

In all cases,the base’s private members remain private for the derived class and are not accessible by members of derived class.

When the access specifier for a base class is private, all public and protected members of the base class become private members of the derived class.

When the access specifier for a base class is protected, all public and protected members of the base class become protected members of the derived class.

See example from your text books for the better conception.

Then you have to download ContestAppletProd.jnlp to take part in the contests. To download this go to this page and click on “Launch Arena” on the leftside.

After completing download you are ready to start participating on contests. You have to register for any contest before 5 minutes of starting of the contest. You have to login on topcoder by this applet.

Before starting contest we must learn enough. Tutorials is the best tutorial I have seen.

To know about contest Rules HELP

Remarks:
1. You have not to submit your main(). you have to submit just the header files and the class part.

example:
[code]
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;

class ToastXRaspberry{

public:
int apply(int upper_limit, int layer_count){

if(upper_limit>=layer_count)
return 1;

int x=layer_count/upper_limit;

if(layer_count%upper_limit>0)
x+=1;

return (x);
}
};

[/code]
Class name and method name will be given in the problem description.

C ও C++ এর মধ্যে পার্থক্য হল C++ এ OOP(Object Oriented programming) এর সুবিধা রয়েছে যা JAVA তে পূর্ণতা পেয়েছে ।
Object Oriented programming আমাদের যে সুফলগুলো দিয়েছে সেগুলো হলঃ
01. Data Encapsulation
02. Data Hiding
03. Polymorphism
এই তিনটি সম্পর্কে পরবর্তীতে বিস্তারিত বলব।

প্রোগ্রামিং করার সময় আমরা যখন কোন Class এর Declaration দিব তখন ঐ Class এর বস্তু বা Object এর কি কি বৈশিষ্ট্য থাকবে তা নির্ধারণ করে দেব। দুই ধরণের বৈশিষ্ট্য থাকতে পারে, ১। Attribute ২। Member function

উদাহরন:
[code]
Class Car{ // Car is the user defined classname
//these three are attribue of the class Car
Char carname[20];
int wheel;
char color;

//these are the member functions
void getnameofcar(){
cin>>carname;
}
void getnumberofwheel(){
cin>>wheel;
}
}; //a semicolon must be placed after the declarationof that class
[/code]
তাহলে দেখা যাচ্ছে যে Car শ্রেণীর সকল Object এর তিনটি Attribute থাকবে যথাঃ carname,wheel এবং color । এবং ২ টি function আছে। এই বৈশিষ্ট্যগুলো তিন ধরনের হতে পারে যথাঃ public, private and protected.

An example :
[code]
#include<stdio.h>
#include <iostream>
using namespace std;

Class Car{ // Car is the user defined classname
//these three are attribue of the class Car
Char carname[20];
int wheel;
char color;

//these are the member functions
void getnameofcar(){
cin>>carname;
}
void getnumberofwheel(){
cin>>wheel;
}
}; //a semicolon must be placed after the declarationof that class

int main(){

Car obj1,obj2; // declaring of an object of Class Car

obj1.getnameofcar(); // calling the function for obj1
obj1.getnumberofwheel();

obj2.getnameofcar(); // calling the function for obj2
obj2.getnumberofwheel();

cout<<ob1.carname<<endl;
cout<<ob1.wheel<<endl;

cout<<ob2.carname<<endl;
cout<<ob2.wheel<<endl;

return 0;
}[/code]
/////////////////////////////////////////

Definitions:
A class is a template for multiple objects with similar features. Classes embody all the
features of a particular set of objects.

An instance of a class is another word for an actual object. If classes are an abstract
representation of an object, an instance is its concrete representation.

Object is the more general term, but both instances and objects are the concrete representation of a class.
In fact, the terms instance and object are often used interchangeably in OOP language. An instance of a Car and a Car object are both the same thing.


// next_permutation
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

return 0;
}


Frequently used container classes of STL :
1. vector
2. queue
3. string
4. stack
5. map
6. list
7. set
8. pair

Vector class:
A vector models a dynamic array. Thus, it is an abstraction that manages its elements with a dynamic array.However, note that the standard does not specify that the implementation use a dynamic array. Rather, it follows from the constraints and specification of the complexity of its operation.

To use a vector we must include
[code]
#include <vector>
Using namespace std;[/code]

Declaration :
[code]Vector<datatype> c;[/code]
//Elem refers to all kind of data types like int,float,char,double,string,struct,class,pair etc.

All functions of vector class :
*vector c // Creates an empty vector without any elements
*vector c1(c2) // Creates a copy of another vector of the same type (all elements are copied)
*vector c(n) // Creates a vector with n elements that are created by the default constructor
*vector c(n,elem) //Creates a vector initialized with n copies of element elem
*vector c(beg,end) //Creates a vector initialized with the elements of the range [beg,end)
*c.~vector() //Destroys all elements and frees the memory
*c.size() //Returns the actual number of elements
*c.max_size() //Returns the maximum number of elements possible
*capacity() //Returns the maximum possible number of elements without reallocation
*reserve() //Enlarges capacity, if not enough yet
*c1 == c2 //Returns whether c1 is equal to c2
*c1 = c2 //Assigns all elements of c2 to c1
*c.assign(beg,end) //Assigns the elements of the range [beg,end)
*c1.swap(c2) //Swaps the data of c1 and c2
*swap(c1,c2) // Same (as global function)
*c.at(idx) //Returns the element with index idx (throws range error exception if idx is out of range)
*c[idx] //Returns the element with index idx (no range checking)
*c.front() //Returns the first element (no check whether a first element exists)
*c.back() //Returns the last element (no check whether a last element exists)
*c.insert(pos,elem) /*Inserts at iterator position pos a copy of elem and returns the position of the new element*/
*c.insert(pos,n,elem) //Inserts at iterator position pos n copies of elem (returns nothing)
*c.insert(pos,beg,end) /*Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)*/
*c.insert(pos,beg,end) /*Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)*/
*c.push_back(elem) //Appends a copy of elem at the end
*c.pop_back() //Removes the last element (does not return it)
*c.resize(num) /*Changes the number of elements to num (if size() grows, new elements are created by their default constructor)*/
*c.resize(num,elem) // Changes the number of elements to num (if size() grows, new elements are copies of elem)
*c.clear() //Removes all elements (makes the container empty)

An example:
[code]
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{

//create empty vector for strings
vector<string> sentence;

//reserve memory for five elements to avoid reallocation
sentence.reserve(5);

//append some elements
sentence.push_back("Hello,");
sentence.push_back("how");
sentence.push_back("are");
sentence.push_back("you");
sentence.push_back("?");

//print elements separated with spaces
copy (sentence.begin(), sentence.end(),
ostream_iterator<string>(cout," "));
cout << endl;

//print ”technical data”
cout << " max_size(): " << sentence.max_size() << endl;
cout << " size(): " << sentence.size() << endl;
cout << " capacity(): " << sentence.capacity() << endl;

//swap second and fourth element
swap (sentence[1], sentence [3]);

//insert element "always" before element "?"
sentence.insert (find(sentence.begin(),sentence.end(),"?"),
"always");

//assign "!" to the last element
sentence.back() = "!";

//print elements separated with spaces
copy (sentence.begin(), sentence.end(),
ostream_iterator<string>(cout," "));
cout << endl;

//print "technical data" again
cout << " max_size(): " << sentence.max_size() << endl;
cout << " size(): " << sentence.size() << endl;
cout << " capacity(): " << sentence.capacity() << endl;

}
/*The output of the program might look like this:
Hello, how are you ?
max_size(): 268435455
size(): 5
capacity(): 5
Hello, you are how always !
max_size(): 268435455
size(): 6
capacity(): 10
*/[/code]

queue Class :
queue is one of the data structures that is also called First-in-First-out [FIFO]. In STL there are also some built in functions for implementing queue.

To use queue we must include
[code]#include<queue>
using namespace std;[/code]

Declaration
[code]queue<datatype>name;[/code]

Frequently used functions:
push(value);
front();
pop();
empty();

[The functions defined in Vector class can be used in queue also,check for further]

An example of queue and dequeUva 10935
[code]
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<deque>
using namespace std;

int main(){

int a,b,n,i,k,c;

while(scanf("%d",&n)&&n){
if(n==1){
cout<<"Discarded cards:"<<endl;
cout<<"Remaining card: 1"<<endl;
continue;
}

deque<int>q;
queue<int>q2;

for(i=1;i<=n;i++){
q.push_front(i);
}

do{
k=q.back();
q2.push(k);
q.pop_back();

q.push_front(q.back());
q.pop_back();
}
while(q.size()>1);

c=0;
cout<<"Discarded cards:";
while(!q2.empty()){
cout<<" "<<q2.front();
if(c<n-2)
cout<<",";
c++;
q2.pop();
}

cout<<endl<<"Remaining card:";
while(!q.empty()){
cout<<" "<<q.front()<<endl;
q.pop_front();
}
}
return 0;
}
[/code]

stack Class :
stack is one of the data structures that is also called Last-in-First-out [LIFO]. In STL

To use stack we must include
[code]#include<stack>
using namespace std;[/code]

Declaration
[code]stack<datatype>name;[/code]

Frequently used functions:
push(value);
top();
pop();
empty();
[The functions defined in Vector class can be used in stack also,check for further]
UVA 10420