Code-Bin #1112

untitled C++ Code
Posted by: SRM 370 Div 2 1000 | February 12, 2011 @ 11:01am

C++ Code

/*************FORHAD-SUST-BD*****************/

#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <set>
#include <cmath>
#include <cstring>

#include <stdio.h>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <vector>
#include <iomanip>

using namespace std;

#ifdef __GNUC__
typedef long long ll;typedef unsigned long long ull;
#else
typedef __int64 ll;  typedef unsigned __int64 ull;
#endif

#define INF 1<<28
#define SIZE 100
#define ERR 1e-7
#define PI 2*acos(0)
#define REP(i,n) for (i=0;i<n;i++)
#define REPE(i,n) for (i=0;i<=n;i++)
#define REV(i,n) for (i=n;i>=0;i--)
#define FOR(i,p,k) for (i=p; i<k;i++)
#define FORE(i,a,b) for (int i=a; i<=b; i++)
#define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)

#define bug(x)    cout<< "->" <<#x<<": "<<x<<endl
#define Sort(x) sort(x.begin(),x.end())
#define Reverse(x) reverse(x.begin(),x.end())
#define MP(a,b) make_pair(a,b)
#define Clear(x,with) memset(x,with,sizeof(x))
#define Copy(c,r)   memcpy(c,r,sizeof(r))
#define SZ(x) (int)x.size()
#define length(x) (int)x.length()
#define All(x) x.begin(),x.end()
#define pb push_back
#define popcount(i) __builtin_popcount(i)
#define gcd(a,b)    __gcd(a,b)
#define fs first
#define sc second
#define two(X) (1<<(X))
#define twoL(X) (((ll)(1))<<(X))
#define setBit(mask,i) (mask|two(i))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
#define maximum(v) *max_element(All(v))
#define minimum(v) *min_element(All(v))
#define CS c_str()
#define findx(a,x) (find(All(a),x)-a.begin())
#define Unique(v) sort((v).begin(),(v).end()),v.erase(unique(v.begin(),v.end()),v.end())

typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<double>vd;
typedef vector<ll>vll;
typedef vector<string> vs;
typedef vector<vi>vvi;
typedef vector<vll>vvll;
typedef vector<vd>vvd;
typedef vector<pii>vpii;
typedef map<string,int> msi;
typedef map<int,int>mii;
typedef map<pii,int>mpi;

template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> T Abs(T x) {return x > 0 ? x : -x;}
template<class T> inline T sqr(T x){return x*x;}
template<class T> inline bool isPrime(T n){if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
template<class T> inline T Mod(T n,T m) {return (n%m+m)%m;} //For Positive Negative No.
//For debugging
template<class T> void debug(const T& e){cout<<e<<endl;}
template<class T1,class T2> void debug(const T1& e1,const T2& e2){cout<<e1<<"\t"<<e2<<endl;}
template<class T1,class T2,class T3> void debug(const T1& e1,const T2& e2,const T3& e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
template<class T1,class T2,class T3,class T4> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
template<class T1,class T2,class T3,class T4,class T5> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4,const T5& e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
template<class T> void debug(vector<T>& e){int i;REP(i,SZ(e)) cout<<e[i]<<" ";cout<<endl;}
template<class T> void debug(vector< basic_string<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j];cout<<endl;} cout<<endl;}
template<class T> void debug(vector< vector<T> >& e,int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<"\t";cout<<endl;} cout<<endl;}
template<class T> void debug(T e[SIZE][SIZE],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
template<class T> void debug(T e[],int row){int i;REP(i,row) cout<<e[i]<<" ";cout<<endl;}

//Important Functions

//int,double is converted to string
template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
//string is converted to int
int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
//string is converted to Long long
ll toLl(string s){ll r=0;istringstream sin(s); sin>>r; return r;}
//check character is vowel
bool IsVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}
//compute b^p
ll Pow(ll B,ll P){	ll R=1;	while(P>0)	{if(P%2==1)	R=(R*B);P/=2;B=(B*B);}return R;}
//compute b^p%m
int BigMod(ll B,ll P,ll M){	ll R=1;	while(P>0)	{if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;}	return (int)R;}
/*calculates (a*b)%c taking into account that a*b might overflow */
ll mulmod(ll a,ll b,ll c){ ll x = 0,y=a%c; while(b>0){ if(b%2 == 1){x=(x+y)%c;} y=(y*2)%c;b/= 2;}return x%c;}
//print a number in binary format with n length
void binprint(ll mask,ll n){ll i;string s="";do{s+=(mask%2+'0');mask/=2;}while(mask);Reverse(s);s=string(max(n-SZ(s),0LL),'0')+s;for(i=SZ(s)-n;i<SZ(s);i++) printf("%c",s[i]);printf("\n");}
//ASCII Chart
void ASCII_Chart(){int i,j,k;printf("ASCII Chart:(30-129)\n");FOR(i,30,50){REP(j,5){k=i+j*20;printf("%3d---> '%c'   ",k,k);}printf("\n");}}
//SubstringGenerate
vector<string> SubstringGenerate(string str){int i,j,len;vs store;len=SZ(str);REP(i,len) FOR(j,i,len)store.pb(str.substr(i,j-i+1));return store;}

//struct pq{    int cost,node;bool operator<(const pq &b)const{return cost>b.cost;}};// Min Priority Queue
//bool comp(pq a,pq b){    return a.cost < b.cost;}   //Asc Sort by cost

//int month[]={31,28,31,30,31,30,31,31,30,31,30,31};  //Not Leap Year

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction

#include<conio.h> //for using getch();

vector<string>dict;
int N;

int T9[]={
            2,2,2,
            3,3,3,
            4,4,4,
            5,5,5,
            6,6,6,
            7,7,7,7,
            8,8,8,
            9,9,9,9
         };

int count(string word)
{
    string pattern,temp;
    int i,j,cost;

REP(i,SZ(word))
    {
        pattern+=T9[word[i]-'a']+'a';
    }
    cost=0;
    REP(i,N)
    {
        if(SZ(dict[i])<SZ(word)) continue;
        if(dict[i].substr(0,SZ(word))==word) return cost;
        temp="";
        REP(j,SZ(word))
        {
            temp+=T9[dict[i][j]-'a']+'a';
        }
        if(temp==pattern) cost++;   //For Next in dictionary
    }
    return INF;
}

int dp[SIZE],len;
string msg;

int rec(int i)
{
    int &ret=dp[i],j;
    string word;

if(ret!=-1) return ret;

if(i==len) return ret=-1;

ret=INF;

word="";
    FOR(j,i,len)
    {
        word+=msg[j];
        ret=min(ret,rec(j+1)+(j-i+1)+count(word)+1);
    }
    return ret;
}

class JohnnysPhone
{
public:
	int minimizePushes(vector <string> dictionary, string message)
	{
	    int i,n,res,space;
	    string str;

n=SZ(dictionary);
	    dict.clear();
	    REP(i,n)
	    {
	        istringstream iss(dictionary[i]);
	        while(iss>>str)
	        {
                dict.pb(str);
	        }
	    }
	    N=SZ(dict);
	    istringstream iss(message);
	    res=0;
	    space=0;
	    REP(i,SZ(message))
            if(message[i]==' ')
                space++;
	    while(iss>>str)
	    {
	        msg=str;
            len=SZ(msg);
            Clear(dp,-1);
	        res+=rec(0);
	        if(res>=INF) return -1;
	    }
	    return res+space;
	}
};

template<typename T> void print( T a ) {
    cerr << a;
}

void print( long long a ) {
    cerr << a << "L";
}

void print( string a ) {
    cerr << '"' << a << '"';
}

template<typename T> void print( vector<T> a ) {
    cerr << "{";
    for ( int i = 0 ; i != a.size() ; i++ ) {
        if ( i != 0 ) cerr << ", ";
        print( a[i] );
    }
    cerr << "}" << endl;
}

template<typename T> void assert_eq( int n, T have, T need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}

template<typename T> void assert_eq( int n, vector<T> have, vector<T> need ) {
    if( have.size() != need.size() ) {
        cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
        print( have );
        print( need );
        return;
    }
    for( int i= 0; i < have.size(); i++ ) {
        if( have[i] != need[i] ) {
            cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
            print( have );
            print( need );
            return;
        }
    }
    cerr << "Case " << n << " passed." << endl;
}
void assert_eq( int n, string have, string need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}

int main( int argc, char* argv[] )
{

JohnnysPhone objectJohnnysPhone;

//test case0
	vector <string> param00;
	param00.push_back("age messagd messagd message");
	string param01 = "message";
	int ret0 = objectJohnnysPhone.minimizePushes(param00,param01);
	int need0 = 8;
	assert_eq(0,ret0,need0);

//test case1
	vector <string> param10;
	param10.push_back("b a c d");
	string param11 = "abcd  dcba ";
	int ret1 = objectJohnnysPhone.minimizePushes(param10,param11);
	int need1 = 23;
	assert_eq(1,ret1,need1);

//test case2
	vector <string> param20;
	param20.push_back("a b c");
	string param21 = "d";
	int ret2 = objectJohnnysPhone.minimizePushes(param20,param21);
	int need2 = -1;
	assert_eq(2,ret2,need2);

//test case3
	vector <string> param30;
	param30.push_back("gajdkwifpcks iclfabc");
	string param31 = "gajf";
	int ret3 = objectJohnnysPhone.minimizePushes(param30,param31);
	int need3 = -1;
	assert_eq(3,ret3,need3);

//test case4
	vector <string> param40;
	param40.push_back("a ");
	param40.push_back("aa ");
	param40.push_back("aaa ");
	param40.push_back("aaaa ");
	param40.push_back("ab");
	string param41 = "ab";
	int ret4 = objectJohnnysPhone.minimizePushes(param40,param41);
	int need4 = 5;
	assert_eq(4,ret4,need4);

//test case5
	vector <string> param50;
	param50.push_back("aaa ");
	param50.push_back("bbb ");
	param50.push_back("ccc");
	string param51 = "ccc";
	int ret5 = objectJohnnysPhone.minimizePushes(param50,param51);
	int need5 = 5;
	assert_eq(5,ret5,need5);

}

Syntax Highlighting

[Open in new window]

Author Comments

none

Rating

4.40 / 8
55 Votes