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();
}

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;
}

找因數 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;
}

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次

切開之後變成超省時

ACM-369 Combinations with C++

/********************************/
/* This program is used to      */   
/*    calculate C(N,R)          */
/*                              */
/*                              */
/* First input is N ,           */
/*  and second 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("%d things taken %d at a time is %0.Lf exactly.\n",N,R,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
 {
  for(int i=1 ; i<=r ; i++)
  {
   tempres = (tempres * (n-r+i) / i) ;
  }
  return tempres;
 }
}

本來我用遞迴做

馬上就被賞了個TLE

還是乖乖的邊乘邊除

ACM-160 Factors and Factorials with C++

#include<iostream>
#include<stdio.h>
#include<cstdio>

using namespace std;

void funct(int a , int b);

int array[25]={ 2, 3, 5, 7,11,13,
  17,19,23,29,31,37,
  41,43,47,53,59,61,
  67,71,73,79,83,89,97};
  
  
int buffer;
int step;

int main(int argc, char* argv[])
{
 int a;
 int b;
 
 while(cin != NULL)
 {
  cin>>a;
  //store the input
  if(a != 0)
  {
   printf("%3d! =",a);
   b = 0;
   step = 0;
   buffer = 0;
   while(a >= array[b])
   {
    funct(a,b);
    b++;
    if(b == 25)
    break;
   }
  }else
  {
   break;
  }
  printf("\n");
 }
 return 0;
}


void funct(int a , int b)
{
 if(a >= array[b])
 {
  buffer += a/array[b];
  a = a/array[b];
  funct(a,b);
 }else
 {
  step++;
  if(step == 16)
  {
   printf("\n      ");
   step = 1;
  }
  printf("%3d",buffer);
  buffer = 0;
 }
}

ACM-113 Power of Cryptography with C

#include <stdio.h>
#include <math.h>


int main(int argc, char* argv[])
{
 double n,p;
 double k;
 
 while (scanf("%lf %lf", &n, &p) == 2) 
 {
  k = exp(log(p)/n);
  printf("%.0lf\n", k);
 }
 
 return 0;
}

ACM-102 Ecological Bin Packing with C++

#include<iostream>
#include<stdio.h>
#include<cstdio>

using namespace std;
string funct(int c1 , int c2 , int c3 , string s_temp , int temp , int temp_max);

 /********************************/
 /* glass[a][b]                  */
 /* a is bucket number           */
 /* b is glass color             */
 /* b = 1 Brown                  */
 /* b = 2 Green                  */
 /* b = 3 Clean                  */
 /********************************/
   


int main(int argc, char* argv[])
{
 unsigned int Bucket[3][3];
 int can_1, can_2, can_3;
 
 while (scanf("%d %d %d %d %d %d %d %d %d", &Bucket[0][0], &Bucket[0][1],
                                            &Bucket[0][2], &Bucket[1][0],
                                            &Bucket[1][1], &Bucket[1][2],
                                            &Bucket[2][0], &Bucket[2][1],
                                            &Bucket[2][2]) != EOF)
 {
  /* initiate */
  unsigned int max = 0 , move = 0;
  int init = 0, total = 0, temp_total = 0;
  string s_goal = "XXX";
  for(int i=0 ; i<3 ; i++)
  {
   for(int j=0 ; j<3 ; j++)
   {
    total = total + Bucket[i][j];
   }
  }
  
  for(can_1=0 ; can_1<3 ; can_1++)
  {
   init = Bucket[0][can_1];
   temp_total =  Bucket[0][can_1];
   for(can_2=0 ; can_2<3 ; can_2++)
   {
    if(can_1 != can_2)
    {
     temp_total = temp_total + Bucket[1][can_2];
     for(can_3=0 ; can_3<3 ; can_3++)
     {
      if( (can_3 != can_2) && (can_3 != can_1) )
      {
       temp_total = temp_total + Bucket[2][can_3];
       if(temp_total >= max)
       {
        s_goal = funct(can_1 , can_2 , can_3 , s_goal , temp_total , max);
        max = temp_total;
       }
       temp_total = init;
      }
     }
    }
   }
         
  }
  
  move = total - max;
  cout<< s_goal << " " << move <<endl;
 }
 
 return 0;
}


string funct(int c1 , int c2 , int c3 , string s_temp , int temp , int temp_max)
{
 string str="";
 int size = 0;

 if(c1==0){  
  str=str+"B";  
 }else if(c1==1){  
  str=str+"G";  
 }else 
  str=str+"C";  
     
 if(c2==0){  
  str=str+"B";  
 }else if(c2==1){  
  str=str+"G";  
 }else 
  str=str+"C";     
      
 if(c3==0){  
  str=str+"B";  
 }else if(c3==1){  
  str=str+"G";  
 }else 
  str=str+"C";
  
 if(temp == temp_max)
 {
  while(size < 2)
  {
   if(str[size] < s_temp[size])
    return str;
   else if(str[size] > s_temp[size])
    break;
   else
    size++;
  }  
  return s_temp;
 }   
 
 return str;
}

ACM-101 The Blocks Problem with C++

經過了3天的激戰

順利的擊敗了ACM-101

執行時間0.020 排名2901

神人好多阿

#include <sstream>
#include <iostream>
#include <stdio.h>
#include <ctype.h>
#include <cstdio>
#include <list>

using namespace std;

list <int> block[25];  // 25 stack
int pos[25];  // if block 1 is in the stack and the base block is 5 then pos[1] = 5;


void initiate();
void printresult(int x);
void moveonto(int a , int b);
void moveover(int a , int b);
void pileonto(int a , int b);
void pileover(int a , int b);
bool checkblock(int a , int b);


int main(int argc, char* argv[])
{
 int block_1, block_2;
 int final;


 string str1, str2;
 string quit = "quit";
 string move = "move";
 string pile = "pile"; 
 string onto = "onto"; 
 string over = "over"; 
 
 while( cin>>str1 )
 {
  if(str1 == quit)//print the final result
  {
   printresult(final);                  
  }else if(str1 == move || str1 == pile) // move and pile action
  {
   cin >> block_1 >> str2 >> block_2;
   if(block_1 != block_2 && checkblock(block_1 , block_2))
   {
    if(str1 == move)
    {
     if(str2 == onto)
     {
      moveonto(block_1 , block_2);
     }else
     {
      moveover(block_1 , block_2);
     }
    }else
    {
     if(str2 == onto)
     {
      pileonto(block_1 , block_2);
     }else
     {
      pileover(block_1 , block_2);
     }
    }           
   }else
   {
    //cout<<"Are you kidding"<<endl;
   }               
  }else  // how many blocks are used in the process
  {
   istringstream stream1;
   stream1.str(str1);
   stream1 >> final;
   initiate();
  }
 }
 return 0;
}


void initiate()
{
 for(int i=0 ; i<25 ; i++)
 {
  if(block[i].empty())
  {
   block[i].push_back(i);
   pos[i] = i;
  }else
  {
   block[i].clear();
   block[i].push_back(i);
   pos[i] = i;
  }
 }
}


void printresult(int x)
{
 list<int>::iterator iter2;
 for(int y=0 ; y<x ; y++)
 {
  iter2 = block[y].begin();
  cout << y <<":";
  while( iter2 != block[y].end() ) 
  {
   cout <<" "<<*iter2;
   ++iter2;
  } 
  cout<<endl;
 }
}


bool checkblock(int a , int b)
{
 if(pos[a] != pos[b])
 return true;
 else
 return false;     
}



void moveonto(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos1, bpos2;                  
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 while(bpos1 != a)  //put the last block back 
 {
  block[bpos1].push_back(bpos1);
  pos[bpos1] = bpos1;
  block[temp_pos1].pop_back();
  bpos1 = block[temp_pos1].back();
 }
 
 while(bpos2 != b)  //put the last block back
 {
  block[bpos2].push_back(bpos2);
  pos[bpos2] = bpos2;
  block[temp_pos2].pop_back();
  bpos2 = block[temp_pos2].back();
 }
 
 /*** move the first block onto the second block ***/          
 block[temp_pos1].pop_back();     
 block[temp_pos2].push_back(a);
 pos[a] = temp_pos2;
}

void moveover(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos1;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
      
 while(bpos1 != a)  //put the last block back 
 {
  block[bpos1].push_back(bpos1);
  pos[bpos1] = bpos1;
  block[temp_pos1].pop_back();
  bpos1 = block[temp_pos1].back();
 }
 
 /*** move the first block onto the second block ***/          
 block[temp_pos1].pop_back();     
 block[temp_pos2].push_back(a);
 pos[a] = temp_pos2;
}

void pileonto(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos2;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 list<int> mylist;
 list<int>::iterator it;
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 //bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 for(it=block[temp_pos1].begin() ; it!=block[temp_pos1].end() ; it++)
 {
  if(*it == a)
  {
   mylist.splice ( mylist.begin(), block[temp_pos1], it, block[temp_pos1].end());
   break;
  }
 }
 
 
 while(bpos2 != b)  //put the last block back
 {
  block[bpos2].push_back(bpos2);
  pos[bpos2] = bpos2;
  block[temp_pos2].pop_back();
  bpos2 = block[temp_pos2].back();
  //cout<<"*";
 }
 
 
 block[temp_pos2].splice(block[temp_pos2].end(),mylist);
 for(it=block[temp_pos2].begin() ; it!=block[temp_pos2].end() ; it++)
      {
  pos[*it] = temp_pos2;
 }
 pos[a] = temp_pos2;
}

void pileover(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 //int bpos1, bpos2;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 list<int> mylist;
 list<int>::iterator it;
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 //bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 //bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 for(it=block[temp_pos1].begin() ; it!=block[temp_pos1].end() ; it++)
 {
  if(*it == a)
  {
   mylist.splice ( mylist.begin(), block[temp_pos1], it, block[temp_pos1].end());
   break;
  }
 }
 
 block[temp_pos2].splice(block[temp_pos2].end(),mylist);
 for(it=block[temp_pos2].begin() ; it!=block[temp_pos2].end() ; it++)
 {
  pos[*it] = temp_pos2;
 }
 pos[a] = temp_pos2;
}

ACM-100 The 3n + 1 problem with C++

#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
 int a,b;
 int start,end;
 int temp,count;
 int max;

 while(cin >> a >> b)
 {
  //cout << a << b << endl;
  if(a > b)
  {
   start = b;
   end = a;
  }else
  {
   start = a;
   end = b;
  }

  max = 0;

  for(int k = start; k <= end ; k++)
  {
   temp = k;
   count = 1;
   while(temp!=1)
   {
    ++count;
    if(temp%2 ==1)
    {
     temp = 3 * temp + 1;
    }else
    {
     temp = temp / 2;
    }
   }

   if(max < count)
   {
    max = count;
   }
  }
  cout >> a >> " " >> b >> " " >> max >> endl;
 }

 return 0;
}

TEST

 public class HelloWorld{  
     public static void main(String args[]){  
          System.out.println("Hello World!");  
     }  
 }