Tuesday, 31 July 2012

UVa 465 - Overflow Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

main()
{
    char s1[1000],s2[1000];
    long double a,b;
    char c;
    while(cin>>s1>>c>>s2)
    {

       a=atof(s1);
       b=atof(s2);

        cout<<s1<<" "<<c<<" "<<s2<<endl;
        //cout<<a+b<<endl<<a*b<<endl;

        if(a>2147483647)
            cout<<"first number too big"<<endl;
        if(b>2147483647)
            cout<<"second number too big"<<endl;
        if(c=='+' && (a+b)>2147483647)
            cout<<"result too big"<<endl;
        if(c=='*' && (a*b)>2147483647)
            cout<<"result too big"<<endl;
    }
}
at No comments:
Labels:

UVa 10066 - The Twin Towers Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

int x[110],y[110],c[110][110];

int LCS(int m,int n)
{
    for(int i=0;i<=m;i++)
        c[i][0]=0;
    for(int i=0;i<=n;i++)
        c[0][i]=0;

    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(x[i]==y[j])
                c[i][j]=c[i-1][j-1]+1;
            else
                c[i][j]=max(c[i-1][j],c[i][j-1]);
    return c[m][n];

}

main()
{
    int n1,n2,kk=1;
    while(cin>>n1>>n2)
    {
        if(n1==0 && n2==0)
        break;

        for(int i=1;i<=n1;i++)
            cin>>x[i];

        for(int i=1;i<=n2;i++)
            cin>>y[i];

        int res=LCS(n1,n2);
        cout<<"Twin Towers #"<<kk++<<endl<<"Number of Tiles : ";
        cout<<res<<endl<<endl;
    }
}
at No comments:
Labels:

Monday, 30 July 2012

UVa 490 - Rotating Sentences Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


int main()
{
    char sentence[110][110];
    int mx_sentence=0,mx_length=0;

    for(int i=0;i<110;i++)
        for(int j=0;j<110;j++)
            sentence[i][j]=' ';

    while(gets(sentence[mx_sentence]))
    {
        //mx_length=max(mx_length, strlen(sentence[mx_sentence]));//.length());
        int length=strlen(sentence[mx_sentence]);
        sentence[mx_sentence][length]=' ';
        mx_length=max(mx_length,length);
        mx_sentence++;
    }
    //cout<<mx_length<<endl;
    for(int i=0;i<mx_length;i++)
        {
            for(int j=mx_sentence-1;j>=0;j--)
                cout<<sentence[j][i];
            cout<<endl;
        }
return 0;
}
at No comments:
Labels:

UVa 10276 - Hanoi Tower Troubles Again! Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007




int main()
{
    int n,t,i,j,sqrt_sum;
    bool used;
    cin>>t;
    while(t--)
    {
        cin>>n;
        stack<int>peg[55];
        for(i=1;;i++)
            {
                used=false;
                for(j=0;j<n;j++)
                    if(!peg[j].empty())
                    {
                        sqrt_sum=sqrt(peg[j].top()+i);
                        if((peg[j].top()+i)==(sqrt_sum*sqrt_sum))
                            {
                                peg[j].push(i);
                                used=true;
                                break;
                            }
                    }

                    else
                    {
                        peg[j].push(i);
                        used=true;
                        break;
                    }
                if(!used)
                    break;

            }
            cout<<i-1<<endl;
    }
return 0;
}
at No comments:
Labels:

Sunday, 29 July 2012

UVa 12471 - Association of Strings Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100010
#define MOD 1000000007

int failur[MX],length;
char pattern[MX];

void FailureFunction(int i,int j)
{
    while(i<length)
    {
        if(pattern[i]==pattern[j])
        {
            j++;
            failur[i]=j;
            i++;
        }
        else if(j>0)
            j=failur[j-1];
        else
        {
            failur[i]=0;
            i++;
        }
    }
}


int main()
{
    int t,kk=1,n,arr[MX];
    bool found,chk;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>arr[i];

        if(arr[0]!=0)
            {
                cout<<"Case "<<kk++<<": -1"<<endl;
                continue;
            }
        chk=true;
        failur[0]=0;
        length=1;
        pattern[0]='a';
        for(int i=1;i<n;i++)
        {
            length=i+1;
            found=false;
            for(int j=0;j<16;j++)
            {
                pattern[i]=j+'a';
                FailureFunction(i, failur[i-1]);
                if(failur[i]==arr[i])
                    {
                        found=true;
                        break;
                    }
            }
            if(!found)
                {
                    chk=false;
                    break;
                }
        }

        if(!chk)
            cout<<"Case "<<kk++<<": -1"<<endl;
        else
            {
                cout<<"Case "<<kk++<<": ";
                for(int i=0;i<n;i++)
                    cout<<pattern[i];
                cout<<endl;
            }

    }
return 0;
}
at No comments:
Labels:

Saturday, 28 July 2012

UVa 11753 - Creating Palindrome Solution 

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 10010
#define MOD 1000000007

LL arr[MX],k;
//LL memo[MX][MX][MX];

int func(int i,int j, int cnt)
{
    if(cnt>k)   return cnt;
    if(i>j)
        return cnt;
    if(arr[i]==arr[j])
        return func(i+1,j-1,cnt);
    else
        return min(func(i+1,j,cnt+1),func(i,j-1,cnt+1));
}

main()
{
    LL t,kk=1,n,i,j,cnt;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(i=0;i<n;i++)
            cin>>arr[i];

        i=0;
        j=n-1;
        //cnt=0;

        cnt=func(i,j,0);

        /*while(i<j)
        {
            if(arr[i]==arr[j])
            {
                i++;
                j--;
            }
            else
            {
                if(arr[i+1]==arr[j])
                {
                    cnt++;
                    j--;
                    i+=2;
                }
                else if(arr[i]==arr[j-1])
                {
                    cnt++;
                    i++;
                    j-=2;
                }
                else
                {
                    cnt+=2;
                    i++;
                    j--;
                }
            }
        }*/


    cout<<"Case "<<kk++<<": ";
    if(cnt>k)
        cout<<"Too difficult";
    else if(cnt==0)
        cout<<"Too easy";
    else
        cout<<cnt;
    cout<<endl;
    }
}
at No comments:
Labels:

Thursday, 26 July 2012

UVa 11475 - Extend to Palindrome Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 1000010
#define MOD 1000000007

char text[MX],pattern[MX];
int failur[MX],length,cnt;

void FailureFunction()
{
    int i=1,j=0;
    failur[0]=0;
    while(i<length)
    {
        if(pattern[i]==pattern[j])
        {
            j++;
            failur[i]=j;
            i++;
        }
        else if(j>0)
            j=failur[j-1];
        else
        {
            failur[i]=0;
            i++;
        }
    }
}

void KMPmatch()
{
    FailureFunction();
    int i=0,j=0;

    while(i<length)
    {
        if(text[i]==pattern[j])
        {
            i++;
            j++;
            //if(j>cnt)           //maximum palindrom
                cnt=j;
        }
        else if(j>0)
            j=failur[j-1];
        else
            i++;

    }
}

int main()
{
    while(cin>>text)
    {
        int i,j;
        CLR(failur);
        length=strlen(text);
        for(i=0,j=length-1;j>=0;i++,j--)    //pattern is the revese string of text
        pattern[i]=text[j];

        cnt=0;
        KMPmatch();

        cout<<text;
        for(i=cnt;i<length;i++)             //extra character needed
            cout<<pattern[i];
        cout<<endl;
    }
return 0;
}
at No comments:
Labels:

Wednesday, 25 July 2012

UVa 10298 - Power Strings Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


main()
{
    string s;
    while(cin>>s && s!=".")
    {
        int max=1;
        int s_length=s.length();
        for(int i=1;i<s_length;i++)
            while(s[i]!=s[i%max])
                max++;
        if(s_length%max!=0)
            cout<<"1"<<endl;
        else
            cout<<s_length/max<<endl;
    }
}
at 1 comment:
Labels:

Tuesday, 24 July 2012

UVa 750 - 8 Queens Chess Problem Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


vector<string>result;
int tmp[10];
string s;
int lft[20],rgt[20],row[10],max_sol;    //bottom left diagonal and bottom right diagonal, it can be -8 to +8

void solutions(int n) //all solutions return with string vector result
{
    if(n==8)
    {
        s="";
        for(int j=0;j<8;j++)
        {
            s+=  (tmp[j]+'0');
        }
        result.PB(s);
        return;
    }

    for(int i=1;i<=8;i++)
        if(!row[i] && !lft[n+i] && !rgt[n-i+8])//if not visited
        {
            row[i]=lft[n+i]=rgt[n-i+8]=1;//set visit
            tmp[n]=i;
            solutions(n+1);
            row[i]=lft[n+i]=rgt[n-i+8]=0;
        }
}

int main()
{
    solutions(0);
    //cout<<result[0]<<endl;
    int len=result.size();
    int t,x,y;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>x>>y;
        if(i!=1)
        cout<<endl;
        int kk=1;
        cout << "SOLN       COLUMN" << endl;
        cout << " #      1 2 3 4 5 6 7 8" << endl<<endl;
        for(int j=0;j<len;j++)
            if(result[j][y-1]== x+'0')
            {
                cout<<setw(2)<<kk++<<"     ";
                for(int k=0;k<8;k++)
                    cout<<" "<<result[j][k];
                cout<<endl;
            }
    }

return 0;
}
at No comments:
Labels:

Sunday, 22 July 2012

UVa 10252 - Common Permutation Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


main()
{
    char s1[1010],s2[1010];
    map<char, int>freq;
    while(gets(s1))
    {
        gets(s2);
        int l1=strlen(s1);
        sort(s1,s1+l1);
        int l2=strlen(s2);
        sort(s2,s2+l2);

        freq.clear();

        for(int i=0;i<l1;i++)
            freq[s1[i]]++;
        for(int i=0;i<l2;i++)
            if(freq[s2[i]])
            {
                cout<<s2[i];
                freq[s2[i]]--;
            }
        cout<<endl;
    }
}
at 1 comment:
Labels:

UVa 10336 - Rank the Languages Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

char grid[1010][1010];
map<pair<int,int>,int>visit;
map<char,int>frequency;

void mark(int x,int y,char c)
{
    visit[MP(x,y)]=1;
    if(grid[x][y+1]==c && !visit[MP(x,y+1)])
        mark(x,y+1,c);
    if(grid[x][y-1]==c && !visit[MP(x,y-1)])
        mark(x,y-1,c);
    if(grid[x+1][y]==c && !visit[MP(x+1,y)])
        mark(x+1,y,c);
    if(grid[x-1][y]==c && !visit[MP(x-1,y)])
        mark(x-1,y,c);
}

main()
{
    int t,kk=1,n,m,i,j;
    char c;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        CLR(grid);
        visit.clear();
        frequency.clear();
        int max_freq=0;

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                cin>>grid[i][j];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                if(!visit[MP(i,j)])
                {
                    frequency[grid[i][j]]++;
                    mark(i,j,grid[i][j]);
                    if(frequency[grid[i][j]]>max_freq)
                    max_freq=frequency[grid[i][j]];
                }

        cout<<"World #"<<kk++<<endl;
        for(i=max_freq;i>0;i--)
            for(j=97;j<=122;j++)
                {
                    c=j;
                    if(frequency[c]==i)
                    cout<<c<<": "<<i<<endl;
                }


    }
}
at No comments:
Labels:

UVa 11384 - Help is needed for Dexter Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

main()
{
    LL n;
    while(cin>>n)
    {
        for(int i=0;;i++)
            if(pow(2,i)>n)
            {
                cout<<i<<endl;
                break;
            }
    }
}
at No comments:
Labels:

UVa 10102 - The path in the colored field Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

char grid[1000][1000];
int m;

int min_dist(int x,int y)
{
    int mn=1000;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            if(grid[i][j]=='3')
            {
                int tmp=abs(x-i)+abs(y-j);
                mn=min(mn,tmp);
            }
    return mn;
}

main()
{
    while(cin>>m)
    {
        CLR(grid);
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                cin>>grid[i][j];

        int mx=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                if(grid[i][j]=='1')
                {
                int tmp=min_dist(i,j);
                mx=max(mx,tmp);
                }
    cout<<mx<<endl;
    }
}
at No comments:
Labels:

UVa 576 - Haiku Review Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

bool isVowel(char c)
{
    if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u' || c=='y')
    return true;
    return false;
}

main()
{
    string line;
    int cnt1,cnt2,cnt3,i;
    while(getline(cin,line))
    {
        if(line=="e/o/i")   break;

        cnt1=cnt2=cnt3=0;

        if(isVowel(line[0]))
        cnt1++;
        for(i=1;;i++)
        {
            if(line[i]=='/')    break;
            if(isVowel(line[i]) && !isVowel(line[i-1]))
            cnt1++;
        }

        if(isVowel(line[i+1]))
        cnt2++;
        for(i=i+2;;i++)
        {
            if(line[i]=='/')    break;
            if(isVowel(line[i]) && !isVowel(line[i-1]))
            cnt2++;
        }


        if(isVowel(line[i+1]))
        cnt3++;
        for(i=i+2;i<line.length();i++)
        {
            //if(line[i]=='/')    break;
            if(isVowel(line[i]) && !isVowel(line[i-1]))
            cnt3++;
        }

        //cout<<cnt1<<" "<<cnt2<<" "<<cnt3<<endl;
        if(cnt1!=5)
        cout<<"1";
        else if(cnt2!=7)
        cout<<"2";
        else if(cnt3!=5)
        cout<<"3";
        else
        cout<<"Y";
        cout<<endl;


    }
}
at No comments:
Labels:

UVa 572 - Oil Deposits Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

char grid[110][110];
map < pair < int,int >, int > visit;
int n,m;
int adjx[]={1,1,1,0,-1,-1,-1,0};
int adjy[]={-1,0,1,1,1,0,-1,-1};

void dfs(int a,int b)
{
    int x,y;
    visit[MP(a,b)]=1;
    for(int i=0;i<8;i++)
        {
            x= a+adjx[i];
            y= b+adjy[i];
            //cout<<x<<" "<<y<<endl;
          if(grid[x][y]=='@' && !visit[MP(x,y)])
          dfs(x,y);
        }
}

int main()
{
    while(cin>>n>>m)
    {
        if(n==0 && m==0)    break;

        CLR(grid);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>grid[i][j];

        visit.clear();
        int cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(grid[i][j]=='@' && !visit[MP(i,j)])
                {
                    cnt++;
                    //cout<<"ok";
                    dfs(i,j);
                }
        cout<<cnt<<endl;
    }
}

at No comments:
Labels:

Saturday, 21 July 2012

UVa 516 - Prime Land Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

bool stats[33000+10];
vector<LL>prime;
LL N,n,primeSize,cnt;
map<LL, LL>factor;
map<LL, LL>freq;

void PrimeGenerate()
{
    LL i,j,sqrtN;

    for(i=4;i<=33000;i+=2)
        stats[i]=true;

    sqrtN=sqrt(33000);

    for(i=3;i<=sqrtN;i+=2)
    {
        if(!stats[i])
            for(j=i*i;j<=33000;j+=i+i)
                stats[j]=true;
    }

    for(i=2;i<=33000;i++)
        if(!stats[i])
            prime.PB(i);

    primeSize=prime.size();
}


void PrimeFactorize()
{
    LL i;
    cnt=0;

    for(i=0;i<primeSize;i++)
    {
        if(n%prime[i]==0)
        {
            factor[cnt]=prime[i];
            cnt++;

            while(n%prime[i]==0)
                {
                    freq[cnt-1]++;
                    n/=prime[i];
                }
        }

        if(n==1)    break;
    }
}


int main()
{
   LL multy,base,exp;
   string line;
   PrimeGenerate();
   while(getline(cin,line))
   {
       if(line=="0") break;
       multy=1;
       istringstream ss(line);
       while(ss>>base)
       {
           ss>>exp;
           multy*=pow(base,exp);
       }
       n=multy-1;
       N=n;
       factor.clear();
       freq.clear();
       PrimeFactorize();
       for(LL i=cnt-1;i>0;i--)
            cout<<factor[i]<<" "<<freq[i]<<" ";
        cout<<factor[0]<<" "<<freq[0]<<endl;
   }
return 0;
}
at No comments:
Labels:

Thursday, 19 July 2012

UVa 10954 - Add All Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 10010
#define MOD 1000000007


int main ()
{
    long n, num, i, sum;

    while (cin>>n &&n) {
        priority_queue< int, vector<int>, greater<int> >mypq;

        for (i = 0; i < n; i++)
        {
            cin>>num;
            mypq.push(num);
        }
        if(n==1)
        {
            cout<<num<<endl;
            continue;
        }

        sum=0;
        while(mypq.size()>1)
        {
            num=mypq.top();
            mypq.pop();
            num+=mypq.top();
            mypq.pop();
            sum+=num;
            mypq.push(num);
            //cout<<mypq.size()<<endl;
        }

        cout<<sum<<endl;
    }

    return 0;
}


at No comments:
Labels:

UVa 11137 - Ingenuous Cubrency Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 10010
#define MOD 1000000007

LL ways[MX]
void precal()
{
    int coin[] = {9261, 8000, 6859, 5832, 4913, 4096, 3375, 2744, 2197, 1728, 1331, 1000, 729, 512, 343, 216, 125, 64, 27, 8, 1};
    ways[0]=1;
    for(int i=0;i<21;i++)
        for(int j=coin[i];j<MX;j++)
            ways+=ways[j-coin[i]];
}


int main()
{
    precal();
    int n;
    while(cin>>n)
        cout<<ways[n]<<endl;
return 0;
}
at No comments:
Labels:

Tuesday, 17 July 2012

UVa 12043 - Divisors Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100010
#define MOD 1000000007

int main()
{
    LL s[MX],d[MX],a,b,k,g,h,t,sqt;

    d[1]=1;
    s[1]=1;
    for(LL i=2;i<MX;i++)
    {
        d[i]=2;
        s[i]=1+i;
        sqt=sqrt(i);
        for(LL j=2;j<=sqt;j++)
            if(i%j==0)
            {
                d[i]+=2;
                s[i]+=j+i/j;
            }
        if(sqt*sqt==i)
            {
                d[i]--;
                s[i]-=sqt;
            }
    }

    cin>>t;
    while(t--)
    {
       cin>>a>>b>>k;
       LL div=a/k;
       if(div*k!=a)
       a=(div+1)*k;

       g=0;
       h=0;

       while(a<=b)
       {
           g+=d[a];
           h+=s[a];
           a+=k;
       }
       cout<<g<<" "<<h<<endl;
    }

return 0;
}
at No comments:
Labels:

UVa 12049 - Just Prune The List Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

int main()
{
    int t,m,n,marr[10000+10],narr[10000+10];
    cin>>t;
    while(t--)
    {
        cin>>m>>n;

        for(int i=0;i<m;i++)
            cin>>marr[i];
        sort(marr,marr+m);

        for(int i=0;i<n;i++)
            cin>>narr[i];
        sort(narr,narr+n);

        int cnt1=0,cnt2=0;
        int same=0;

        while(cnt1<m && cnt2<n)
        {
            if(marr[cnt1]==narr[cnt2])
            {
                same++;
                cnt1++;
                cnt2++;
            }
            else if(marr[cnt1]>narr[cnt2])
                cnt2++;
            else
                cnt1++;
        }

        cout<<m+n-2*same<<endl;
    }
return 0;
}
at No comments:
Labels:

UVa 10664 - Luggage Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

int arr[25],total,sum;
int memo[2000+10][25];

int func(int psum, int cnt)
{
    if(cnt>total)
        return 0;
    if(psum==sum/2)
        return 1;
    if(memo[psum][cnt]!=-1) return memo[psum][cnt];
    int ret=0;
    ret=ret | func(psum+arr[cnt],cnt+1);
    ret=ret | func(psum,cnt+1);

    return memo[psum][cnt]=ret;
}
int main()
{
    string line;
    int t,num;
    cin>>t;
    getchar();
    while(t--)
    {
        getline(cin,line);
        istringstream ss(line);
        int cnt=0;
        sum=0;
        SET(memo);
        while(ss>>num)
        {
            arr[cnt++]=num;
            sum+=num;
        }
        total=cnt-1;

        if(sum%2==0)
        {
            if(func(0,0))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
            cout<<"NO"<<endl;
    }
return 0;
}
at No comments:
Labels:

UVa 389 - Basically Speaking Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007

long long to_decimal(string s,int base)
{
    int cnt=0;
    long long res=0;
    for(int i=s.length()-1;i>=0;i--)
    {
        if ( s[i] > 47 && s[i] < 58 )
        res+= (pow(base,cnt)*(s[i]-'0'));
        else
        res+= (pow(base,cnt)*(s[i]-55));
        cnt++;
    }
    return res;
}

string dec_to(long long num, int base)
{
    string s="";
    while(num)
    {
        int tmp=num%base;
        if(tmp<10)
            s+=tmp+'0';
        else
            s+= char (tmp+55);
        num/=base;
    }
    if(s=="")
    return "0";
    return s;
}

int main()
{
   string s,sr,res;
   int from, to;
   while(cin>>s>>from>>to)
   {
       long long buf;
       buf=to_decimal(s,from);
       sr=dec_to(buf,to);
       res="";
       for(int i=sr.length()-1;i>=0;i--)
            res+=sr[i];
       if(res.length()>7)
            cout<<"  ERROR"<<endl;
       else
            cout<<setw(7)<<res<<endl;
       //cout<<setw(7)<<dec_to(buf,to)<<endl;
   }
return 0;
}
at No comments:
Labels:

UVa 305 - Joseph Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


int main()
{
    map<int,int>mp;
    int k,p,m,dead,newp;
    while ((cin>>k)&&k)
    {
        if(mp[k])
        {
            cout<<mp[k]<<endl;
            continue;
        }
        p = k*2;
        for(m=k; ;m++)
            {
                newp=p;
                dead=(m-1)%newp;
                while (dead>=k && newp>=k)
                {
                    newp--;
                    dead = (dead-1+m)%newp;
                }
                if (newp==k)
                    {
                        mp[k]=m;
                        break;
                    }
            }
            cout << m << endl;
        }
    }
at No comments:
Labels:

Monday, 16 July 2012

UVa 486 - English-Number Translator Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007




int main()
{
    string line,s;

    string word[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
    int number[] =  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40, 50, 60, 70, 80, 90 };
    while(getline(cin,line))
    {
        istringstream ss(line);
        //ss>>s;

        long long million=0,thousand=0,hundred=0,tmp=0;
        while(ss>>s)
        {
            for(int i=0;i<28;i++)
                if(s==word[i])
                {
                    tmp+=number[i];
                    break;
                }
                else if(s=="negative")
                {
                    cout<<"-";
                    break;
                }
                else if(s=="million")
                {
                    million=tmp*1000000;
                    tmp=0;
                    break;
                }
                else if(s=="thousand")
                {
                    thousand=tmp*1000;
                    tmp=0;
                    break;
                }
                else if(s=="hundred")
                {
                    tmp=tmp*100;
                    break;
                }
        }
        cout<<million+thousand+tmp<<endl;
    }
return 0;
}
at No comments:
Labels:

UVa 10699 - Count the factors Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 1000005
#define MOD 1000000007


bool stats[MX+10];
vector<long>prime;
long N,n,primeSize,cnt;
//map<long, long>factor;

void PrimeGenerate()
{
    long i,j,sqrtN;

    for(i=4;i<=MX;i+=2)
        stats[i]=true;

    sqrtN=sqrt(MX);

    for(i=3;i<=sqrtN;i+=2)
    {
        if(!stats[i])
            for(j=i*i;j<=MX;j+=i+i)
                stats[j]=true;
    }

    for(i=2;i<=MX;i++)
        if(!stats[i])
            prime.PB(i);

    primeSize=prime.size();
}


void PrimeFactorize()
{
    long i;
    cnt=0;

    for(i=0;i<primeSize;i++)
    {
        if(n%prime[i]==0)
        {
            //factor[cnt]=prime[i];
            cnt++;

            while(n%prime[i]==0)
                n/=prime[i];
        }

        if(n==1)    break;
    }
}


int main()
{
   //long result;
   PrimeGenerate();
   while(cin>>n)
   {
       if(n==0) break;
       if(n==1)
       {
           cout<<"0"<<endl;
           continue;
       }
       N=n;
       PrimeFactorize();
       cout<<N<<" : "<<cnt<<endl;
   }
return 0;
}
at No comments:
Labels:
Subscribe to: Posts (Atom)