Tuesday, February 7, 2012

ACM 10062 -- Tell me the frequencies!


#include <iostream>

using namespace std;
void checkunique(string str);
bool first;

int main()
{
    string input;
    first = true;
    //while(cin>>input)
    while(getline(cin, input)){
        if(first == false)
            cout<<endl;
        checkunique(input);
        first = false;
    }
    return 0;
}


void checkunique(string str){
    int char_set[256] = {0};
    for(int i = 0 ; i < str.length() ; i ++){
        int val = str[i];
  char_set[val]++;

    }

    for(int i = 1 ; i <= str.length() ; i ++){
        for(int j = 256 ; j >= 0 ; j--){
            if(char_set[j] == i){
                cout<<j<<" "<<i<<endl;
            }
        }
    }
}

Friday, November 19, 2010

ACM-392 Polynomial Showdown with C++


#include <iostream>
#include <sstream>
#include <list>


using namespace std;
string showExponentSP(int temp, int item); //用來處理輸入裡面最先出現的項次
string showExponent(int temp, int item);   //用來處理剩下的項次
//item 表示"項次"
//temp 表示"輸入的值"


int main()
{
    string str = "";
    list<int> l;

    int input;
    int counter = 0;
    int level = 8;

    cin>>input;

    while( cin )
    {
        l.push_back(input);
        counter++;

        if(counter == 9)
        {
            list<int>::iterator iter = l.begin();
            while( iter != l.end() ) {
                if(str.empty())
                {
                    str.append(showExponentSP(*iter,level));
                }
                else
                {
                    str.append(showExponent(*iter,level));
                }
                ++iter;
                level--;
            }

            cout<<str<<endl;
            str.clear();
            l.clear();
            counter = 0;
            level = 8;
        }
        cin>>input;
    }
    return 0;

}



string showExponentSP(int temp, int item)
{
    string s="";
    stringstream ss(s);

    if(item == 0)
    {
        ss<<temp;
    }
    else if(item == 1)
    {
        if (temp == 0)
        {
            ss<<"";
        }
        else
        {
            if(temp == -1)
            ss<<"-x";
            else if(temp == 1)
            ss<<"x";
            else
            ss<<temp<<"x";
        }
    }
    else
    {
        if (temp == 0)
        {
            ss<<"";
        }
        else
        {
            if(temp == -1)
            ss<<"-x^"<<item;
            else if(temp == 1)
            ss<<"x^"<<item;
            else
            ss<<temp<<"x^"<<item;
        }
    }
    return ss.str();
}


string showExponent(int temp, int item)
{
    string s="";
    stringstream ss(s);
    if(item>1)
    {
        if(temp == -1)
        ss<<" - "<<"x^"<<item;
        else if(temp == 1)
        ss<<" + "<<"x^"<<item;
        else if(temp<0)
        ss<<" - "<<(-temp)<<"x^"<<item;
        else if(temp>0)
        ss<<" + "<<temp<<"x^"<<item;
        else
        ss<<"";
    }
    else if(item == 0)
    {
        if(temp<0)
        ss<<" - "<<(-temp);
        else if(temp>0)
        ss<<" + "<<temp;
        else
        ss<<"";
    }else
    {
        if(temp == -1)
        ss<<" - "<<"x";
        else if(temp == 1)
        ss<<" + "<<"x";
        else if(temp<-1)
        ss<<" - "<<(-temp)<<"x";
        else if(temp>1)
        ss<<" + "<<temp<<"x";
        else
        ss<<"";
    }
    //cout<<item<<"  ";
    return ss.str();
}



Sunday, November 7, 2010

ACM-382 Perfection with C++


#include <iostream>
#include <iomanip>
#include <list>

using namespace std;

int sqrts(int test);
void compare(int val, int com);

int main()
{
    int input;
    int result;

    list<int> l;

    cin>>input;
    while(input != 0)
    {
        l.push_back(input);
        cin>>input;
    }

    cout<<"PERFECTION OUTPUT"<<endl;

    list<int>::iterator iter = l.begin();
    while( iter != l.end() ) {
        result = sqrts(*iter);
        compare(*iter, result);
        ++iter;
    }

    cout<<"END OF OUTPUT"<<endl;
    return 0;
}

int sqrts(int test)
{
    int temp = 0;

    for(int i = 1 ; i < test ; i++)
    {
        if(test%i == 0)
        {
            temp = temp + i;
        }
    }
    return temp;
}

void compare(int val, int sum)
{
    if(val > sum)
    cout<<setw(5)<<val<<"  DEFICIENT"<<endl;
    else if(val == sum)
    cout<<setw(5)<<val<<"  PERFECT"<<endl;
    else
    cout<<setw(5)<<val<<"  ABUNDANT"<<endl;
}

Wednesday, September 29, 2010

找因數 with C++


#include <iostream>
#include <sstream>
#include "math.h"
#include <stack>
#include <windows.h>


using namespace std;
void brute(int test);
void sqrts(int test);

int main()
{
    int input;


    cout << "Input a integer" << endl;

    cin>>input;


 LARGE_INTEGER m_liPerfFreq={0};
 QueryPerformanceFrequency(&m_liPerfFreq);
 LARGE_INTEGER m_liPerfStart={0};
 QueryPerformanceCounter(&m_liPerfStart);

    brute(input);

 LARGE_INTEGER liPerfNow={0};
 QueryPerformanceCounter(&liPerfNow);
 long decodeDulation=( ((liPerfNow.QuadPart - m_liPerfStart.QuadPart) * 1000000)/m_liPerfFreq.QuadPart);



 LARGE_INTEGER m_liPerfFreq2={0};
 QueryPerformanceFrequency(&m_liPerfFreq2);
 LARGE_INTEGER m_liPerfStart2={0};
 QueryPerformanceCounter(&m_liPerfStart2);

    sqrts(input);

 LARGE_INTEGER liPerfNow2={0};
 QueryPerformanceCounter(&liPerfNow2);
 long decodeDulation2=( ((liPerfNow2.QuadPart - m_liPerfStart2.QuadPart) * 1000000)/m_liPerfFreq2.QuadPart);



 cout.setf(ios::showpoint, ios::fixed);
 cout.precision (10);

    cout<<decodeDulation<<"  "<<decodeDulation2<<endl;

    return 0;
}


void brute(int test)
{
    string str = "";
    stringstream ss(str);
    for(int i = 1 ; i <= test ; i++)
    {
        if(test%i == 0)
        {
            ss<<i<<"|";
        }
    }
    cout<<ss.str()<<endl;
}



void sqrts(int test)
{
    string str = "";
    stringstream ss(str);
    stack<int> first;

    int temp;
    double sq;

    sq = (int) sqrt(test);

    for(int i = 1 ; i <= sq ; i++)
    {
        if(test%i == 0)
        {
            ss<<i<<"|";
            if(test/i != i)
            {
                first.push(test/i);
            }

        }
    }

    while(!first.empty())
    {
        temp = first.top();
        first.pop();
        ss<<temp<<"|";
    }

    cout<<ss.str()<<endl;
}

Thursday, July 29, 2010

ACM-488 Triangle Wave with C++



#include <iostream>

using namespace std;
void printres(int a);

int main(int argc, char* argv[])
{
int A[100],F[100];
int group;
int temp;

while(cin>>group)
{
for(int i=0 ; i<group ;i++)
{
cin>>A[i]>>F[i];
}

for(int l=0 ; l<group ;l++)
{
for(int n=0; n<F[l] ;n++)
{
temp = A[l];
printres(temp);
if(n<(F[group-1]-1))
cout<<endl;
}
}
}
return 0;
}


void printres(int a)
{
for(int k=1; k<=a ;k++)
{
for(int j=0; j<k ;j++)
{
cout<<k;
}
cout<<endl;
}
for(int m=1 ; m<a ;m++)
{
for(int j=0; j<(a-m) ;j++)
{
cout<<(a-m);
}
cout<<endl;
}
}





難度僅次於ACM100 的3n+1

本題很適合用來練習迴圈(for while)

但是我都用for

本題最難的地方是..................排版 = =a

我也很偷懶

所以直接宣告A[100] F[100]

超級偷懶的 囧

ACM-530 Binomial Showdown with C++


/********************************/
/* This program is used to      */
/*    calculate C(N,R)          */
/*                              */
/*                              */
/* First input is N ,and second */
/* one is R                     */
/* Output is the result of      */
/* C(N,R)                       */
/********************************/

#include <iostream>

using namespace std;
long double calculate(int n , int r);

int main(int argc, char* argv[])
{
 int N,R,temp;
 long double res;
 
 
 while(cin>>N>>R)
 {
  //the situation that stop the program
  if(N==0 && R==0)
  {
   break;
  }
  
  /****************************/
  /*  check                   */
  /*  if N!=R and R > N/2     */
  /*  then C(N,R) = C(N,N-R)  */
  /****************************/
  
  if(N != R && R > (N/2))
  {
   temp = N - R;
  }else
  {
   temp = R;
  }
  
  /* start to caiculate C(N,R) */
  res = calculate(N ,temp);
  printf("%0.Lf\n",res);
 }
 return 0;
}


long double calculate( int n , int r)
{
 long double tempres = 1.0;
 
 if(n == r)
 {
  return 1;
 }
 else if(r == 1)
 {
  return n;
 }
 else if(r ==0)
 {
  return 1;
 }
 else
 {
  for(int i=1 ; i<=r ; i++)
  {
   tempres = (tempres * (n-r+i) / i) ;
  }
  return tempres;
 }
}




幾乎和369是一樣的題目

除了一部分的條件不同

根本是寫一題賺兩題 = =a

ACM-374 Big Mod with C++



/********************************/
/* This program is used to */
/* calculate */
/* R = B^P mod M */
/********************************/


#include <iostream>
#include <ctype.h>
#include <cstdio>
#include <math.h>

using namespace std;
long long M;
long long ans_power(long long a ,long long b);


int main(int argc, char* argv[])
{
long long B,P;
long long res;

while(cin>>B>>P>>M)
{
if(M == 1)
{
res = 0;
}
else if(B == 0 && P == 0) //0^0 = 1
{
res = 1;
}
else if(B == 0 && P != 0) //0^n = 0
{
res = 0;
}
else if(B != 0 && P == 0) //n^0 = 1
{
res = 1;
}
else
{
res = ans_power(B,P) % M;
}
cout<<res<<endl;
}
return 0;
}


long long ans_power(long long a ,long long b)
{
if (b == 0)
{
return 1;
}
else if ((b % 2) == 1)
{
long long foo = ans_power(a, (b/2));
return ((foo * foo * a) % M);
}
else
{
long long foo = ans_power(a, (b/2));
return ((foo * foo) % M);
}
}



本來用for迴圈做

也是吃了TLE

決定切開來mod這樣比較快

不然本來2的300次方

迴圈跑300次

切開之後變成超省時