Tuesday, March 20, 2012

Grid Walk

Challenge Description
There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

InputThere is no input for this program.

Output
Print out the how many points can the monkey access. (The number should be printed as an integer whole number eg.
if the answer is 10 (its not !!), print out 10, not 10.0 or 10.00 etc)

exist = []
point = {}

#make sure the sum of digit is less or equal than 19
def belowUpper(x, y):
    if x<0 or y<0:
        return False
    abs_x = str(abs(x))
    abs_y = str(abs(y))
    sum_x = 0
    sum_y = 0
    for c in abs_x:
        sum_x = sum_x + int(c)
    for c in abs_y:
        sum_y = sum_y + int(c)

    if sum_x + sum_y <= 19:
        return True



#check the point is valid or not
def addToList(x, y):
    if belowUpper(x+1, y):
        tmp = str(x+1) + " " + str(y)
        try:
            point[tmp]
        except:
            point[tmp] = 1
            exist.append([x+1, y])
        
        
    if belowUpper(x, y+1):
        tmp = str(x) + " " + str(y+1)
        try:
            point[tmp]
        except:
            point[tmp] = 1
            exist.append([x, y+1])




#remove overlap part when x = 0 or y = 0
def removeOverlap(x, y):
    total = 0
    xx = x
    yy = y
    while True:
        if belowUpper(xx, yy):
           total += 1
           xx += 1
        else:
            break

    return total
    

#main function
exist.append([0,0])

start = 0

while True:
    addToList(exist[start][0],exist[start][1])
    start+=1
    if start >= len(exist):
        break

over = removeOverlap(0, 0)

print (len(exist) - (over)) * 4 + 1

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