歡迎來到 T.H.K.: ACM

Showing posts with label ACM. Show all posts

Tuesday, July 31, 2012

ACM105 -- The Skyline Problem

#include <iostream>

using namespace std;

int main()
{
    int L,H,R;
    int counter = 0;
    int temp_pre,temp_curr;
    int min = 20000,max = 0;
    int building[10001] = {0};


    while(cin>>L>>H>>R)
    {
        if(min>L)
        min = L;

        if(max<R)
        max = R;

        for(int i = L ; i < R ; i++)
        {
            if(building[i] < H)
            building[i] = H;
        }
        counter++;
    }



    bool check = true;
    temp_pre = building[min];
    cout<<min<<" "<<temp_pre<<" ";

    for(int j = min+1 ; j <= max ; j++)
    {
        temp_curr = building[j];
        if(check) //check == true
        {
            if(temp_curr == 0)
            {
                check = false;
                cout<<j<<" "<<temp_curr;
            }else
            {
                if(temp_curr != temp_pre)
                {
                    cout<<j<<" "<<temp_curr<<" ";
                    temp_pre = temp_curr;
                }
            }
        }
        else
        {
            if(temp_curr == 0)
            {
                //do nothing
            }else
            {
                check = true;
                temp_pre = temp_curr;
                cout<<" "<<j<<" "<<temp_curr<<" ";
            }
        }
    }

    cout<<endl;
    return 0;
}

ACM 10035 -- Primary Arithmetic

#include <iostream>

using namespace std;


int main(int argc, char* argv[]){
    unsigned long long n1;
    unsigned long long n2;
    int carry = 0;
    int sum = 0;
    int count = 0;

    while(cin >> n1 >> n2) {
        if(n1 == 0 & n2 == 0)
            break;

        carry = 0;
        count = 0;
        sum = 0;

        while ((n1 > 0) || (n2 > 0)) {

            sum = carry + (n1 % 10) + (n2 % 10);

            if (sum >= 10) {
                count++;
            }

            carry = sum / 10;

            n1 /= 10;
            n2 /= 10;
        }

        if (count == 0) {
            cout << "No carry operation." << endl;
        } else if (count == 1) {
            cout << "1 carry operation." << endl;
        } else {
            cout << count << " carry operations." << endl;
        }
    }
 return 0;
}

ACM 494 -- Kindergarten Counting Game

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    int counter = 0;
    int isWord = 0;
    while((temp = getchar()) != EOF){
        if(temp == '\n'){
            printf("%d\n", counter);
            counter = 0;
            isWord = 0;
        }else{
            if((temp >= 65 && temp <= 90)||(temp >= 97 && temp <= 122)){
                if(isWord == 0){
                    isWord = 1;
                    counter++;
                }
            }else{
                if(isWord == 1){
                    isWord = 0;
                }
            }
        }
    }
    return 0;
}

ACM 10038 -- Jolly Jumpers

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


int main(int argc, char* argv[])
{
    int counter;
    int num[3000];
    int flag[3000];

    while( scanf("%d", &counter) == 1 ){
        int i;
 for(i = 0 ; i < counter ; i++){
            scanf("%d", &num[i]);
            flag[i] = 0;
        }

        int res = 0;
        for(i = 1 ; i < counter ; i++){
            int diff;
            if(num[i] > num[i-1]){
                diff = num[i] - num[i-1];
            }else{
                diff = num[i-1] - num[i];
            }

            if(0 < diff && diff < counter){
                if(flag[diff] == 0){
                    flag[diff] = 1;
                }else{
                    res = 1;
                    break;
                }
            }else{
                res = 1;
                break;
            }

        }

        if( res == 1 ){
            printf("Not jolly\n");
        }
        else{
            printf("Jolly\n");
        }
    }
 return 0;
}

ACM 458 -- The Decoder

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    while((temp=getchar())!=EOF)
    {
        (temp == '\n') ? putchar(temp) : putchar(temp-7);
    }
    return 0;
}

ACM 272 -- TEX Quotes

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    int pair = 0;
    while((temp=getchar())!=EOF){
        if(temp == '"'){
            if(pair == 0){
                pair++;
                printf("``");
            }else{
                pair = 0;
                printf("''");
            }
        }else{
            putchar(temp);
        }
    }
    return 0;
}

ACM 10071 -- Back to High School Physics

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int v, t;
    while (scanf("%d %d",&v, &t)!= EOF){
        printf("%d\n", 2*v*t);
    }
    return 0;
}

ACM 10055 -- Hashmat the Brave Warrior

#include <stdio.h>


int main()
{
    long long int hash, oppen;
    while (scanf("%lld %lld",&hash, &oppen)!= EOF){
        if(hash > oppen)
            printf("%lld\n", (hash - oppen));
        else
            printf("%lld\n", (oppen - hash));
    }
    return 0;
}

ACM 10110 -- Light, more light

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

using namespace std;

bool willLight(double num){
    long long int test = (int) sqrt(num) ;

    if(test*test == num)
        return true;


    return false;
}


int main()
{
    double input;

    while(scanf("%lf", &input)){
        if(input == 0.0)
            break;

        if( willLight(input) )
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }

    return 0;
}

ACM 492 -- Pig-Latin

#include <stdio.h>
#include <ctype.h>
int test(char ch);

int main()
{
    int i;
    char ch;
    char root;
    int s;

    while(1){
        i = 0;
        while(1){
            ch = getchar();
            if(ch == EOF)
                return 0;
            if(isalpha(ch)){
                if(!i){
                    s = test(ch);

                    if(s)
                        printf("%c", ch);
                    else
                        root = ch;
                    i++;
    }else{
                    printf("%c", ch);
                }
            }else{
                if(!i){
                    printf("%c", ch);
                    break;
                }
                if(s){
                    printf("ay%c", ch);
                }else{
                    printf("%cay%c", root, ch);
                }
                break;
            }
        }
    }
    return 0;
}

int test(char ch){
 if(ch == 'A' || ch == 'a')
  return 1;
 if(ch == 'E' || ch == 'e')
  return 1;
 if(ch == 'I' || ch == 'i')
  return 1;
 if(ch == 'O' || ch == 'o')
  return 1;
 if(ch == 'U' || ch == 'u')
  return 1;

 return 0;
}

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

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次

切開之後變成超省時

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

Wednesday, July 21, 2010

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

歡迎來到 T.H.K.