RichThinker: 2009

2009年7月30日星期四

ACM Q10110

#include <iostream>
#include <math.h>
using namespace std;
int main(void){
        unsigned int N;
        while(true){
                cin>>N;
                if(N==0)
                        break;
                if((int)(sqrt(N))*(int)(sqrt(N))==N)
                        cout<<"yes"<<endl;
                else
                        cout<<"no"<<endl;
        }
        return 0;
}

下面是錯誤的code:

#include <iostream>
#include <math.h>
using namespace std;
int main(void){
        long long int N;
        while(true){
                cin>>N;
                if(N==0)
                        break;
                if((int)(sqrt(N))*(int)(sqrt(N))==N)
                        cout<<"yes"<<endl;
                else
                        cout<<"no"<<endl;
        }
        return 0;
}

2009年7月22日星期三

範本（Template）& 名稱空間（Namespace）(C++)

範本（Template）

提供被參數化的型態（Parameterized Types）功能

將數據跟操作分開

名稱空間 (Namespace)

則提供一個名稱管理容器，減低名稱衝突的機會發生

引用: http://caterpillar.onlyfun.net/Gossip/CppGossip/CppGossip.html

函數指標 (Function pointer) v.s. 指標函數(Pointer to function) (c++)

函數指標 (Function pointer)

例如: int (*p) (int, int)

指向函數地址的指標

指標函數(Pointer to function)

例如: float * q = function(num1, num2)

會return 指標的函數

指標陣列(Pointer Array) v.s. 陣列指標(Array Pointer) (c++)

指標陣列 (Pointer Array):

陣列內的元素都為指標

例如: int *a[10];

陣列指標(Array Pointer):

指向陣列的指標

例如: int *a = new int [100];

記得要使用 delete[] 否則會造成 memory leak

常數指標(pointer to constant object) v.s. 指標常數(constant pointer to object) (c++)

Pointer to constant object (const 放在 * 的左邊):

char const * p2;
const char *p3;

被指向的內容不得被修改

但可以做以下的操作

const char* node1 ="abc";
node1 = "xyz"; // node1 可以改指向xyz

Constant pointer to object (const 放在* 的右邊)

char*const p1;
本身不能被修改,但指向的內容可以修改

Class v.s. Struct (c++)

Class 和 Struct 的差別主要有兩個:

1. Struct 定義複雜數據類型, 不能用於OO上

2. class 默認的權限是private
Struct 默認為public

Typedef (c++)

主要功用是為型態取別名

細分為三種應用

1. 簡單型態的別名

typedef unsigned long DWORD;

2. 結構型態的別名

例:
typedef struct card{
int point, char suit;
}name1, *name2;

即可用 name1 obj1, name2 obj2 來建構結構

3. 函式型態的別名

typedef int (*fun)(int x, int y);

定義了函數指標的類型

malloc/free v.s. new/delete

在c中，malloc 只負責配置記憶體, free 只負責釋放記憶體

並不負責初始化與解構化

而當使用new/delete 時

編譯器在編譯到new 後

會自動呼叫 Constructor, 初始化類別

編譯到delete 時

會呼叫destructor, 解構化實體

this 指標 (c++)

每一個類別的函式成員(非靜態)都會隱含一個this指標

指向對象物件

當在函式中使用資料成員時

都會隱含的使用this指標指向對象地址

例如:
int data;
MyClass(int data){
this->data = data;
}

引用跟指標的差別

不同指標可以指向NULL

引用必須初始化

例如: int&rn = a; (a 引用 rn)

而且一但初始化後就不能改變引用的對象

因此比指標來的安全

物件導向

物件導向包含以下三個元素:

1. 封裝 (Encapsulation)

將資料屬性與操作方法放在一起
使程式碼易於理解

2. 繼承 (Inheritance)

子類別可以繼承父類別的屬性與方法
重複使用程式碼

3. 多型 (Polymorphism)

可以透過Overriding 和 Overloading 將使用同一方法卻產生不同行為
方便擴充與維護程式

Inline v.s. Macro

Inline 是在c++ 中加進來以改進c macro 的缺點

不同於macro, Inline 有透過 compiler 做編譯

因而擁有Compiler 所提供的型別確認(Type checcking)的好處

例如:

#define ABS(a) ((a>0)?(a):(-a))

inline int ABS(int a){
if(a>0)
return a;
else
return -a;
}

抽象類別 (Abstract classes)

當所使用的物件都繼承同一基礎類別時

但該類別方法卻不需被實現時

可以建立一個純虛擬函數

例: virtual int f() = 0

做為抽象類別

虛擬函數 (virtual functions)

虛擬函數主要是用來實現多型 (Polymorphism)

透過Overriding 的手法

可以覆寫掉base class 的方法

不用宣告類別為何

即可使用該類別方法

VIM 常用指令

PATTERN 代表符合的樣式

開新的分割視窗
:sp [filename]
- 切換游標所在視窗: ctrl+w 按兩次

所有列做排版:
gg=G

取代指令: s
- 將文件中所有strinA的字串換成stringB: %s/stringA/stringB/g (g表示整行有符合的都換掉, 不加g只取代一行的第一個符合字串)
- 區域取代: 選取一段文字後按s之後接/stringA/stringB/g
- 從游標所在行數開始到最後一行做取代: .,$s/stringA/stringB/g (.表示目前所在行, $表示最後一行)
- 在2~300行之間取代: 2,300s/stringA/stringB/g

將所有符合PATTERN樣式的行做刪除
:g/PATTERN/d

自訂一個strcat (c++)

#include <iostream>
using namespace std;

char *strcat2(char *dest, const char*src);
int main(void){

        char* dest = (char *)malloc(256);
        *dest='\0';
        cout<<strcat2(dest,"concat string")<<endl;

        return 0;
}

char *strcat2(char *dest, const char*src){
        char *ret;
        ret = dest;
        while(*dest++);
        dest--;
        while(*dest++= *src++);

        return ret;
}

Extern (c++)

Extern可以聲明變數會在其它的位置被定義，這個位置可能是在同一份文件之中，或是在其它文件之中．

2009年7月21日星期二

Static 的作用 (c++)

Static 主要有三種功能:

1. 修飾檔案中的全域變數或函式保護檔案中的全域變數或函式只限於該檔案使用,不受其他檔案存取

2. 修飾函式中的區域變數，使區域變數具有全域變數的效果，受到static 修飾的變數只會初始一次．

例：
#include
using namespace std;

void func(void){
static int i=0;
i++;
printf("%d", i);
}
int main(void){
for(int j=0; j<10; j++)
func();

return 0;
}

印出：１２３４５６７８９１０

3. 修飾類別中的資料或函式成員
static 成員可以用類別名稱:: 直接使用

參考資料: http://shukaiyang.myweb.hinet.net/courses/cpp/static.zhtw.htm

Palindrome (c++)


#include <iostream>
#include <string>
using namespace std;

int main(void){
        string s = "abcdef";
        string::iterator pos;
        reverse(s.begin(), s.end());

        string tmp ="";
        for(int i=0; i< s.length(); i++){
                tmp += s[s.length()-i-1];
        }

        for(pos = s.begin(); pos != s.end(); ++pos)
                cout<<*pos;
        cout<<endl;

        cout<<s<<endl;
        cout<<tmp<<endl;
        return 0;
}

String & int conversion (c++)


#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main(void){

string s= "12345678";

/*string to int:: c_str() version*/
cout<<atoi(s.c_str())+123<<endl;

/*string to int :: stringstream version*/
int tmp;
stringstream ss1(s);
ss1 >> tmp;
cout<< tmp+4<<endl;

int ints = 123;
/*int to string :: sprintf version*/
char str_2[10];
sprintf(str_2,"%d",ints);
cout<<str_2[2]<<endl;
/*int to string :: stringstream version*/
stringstream ss;
ss <<ints;
string str = ss.str();
cout<<str<<endl;
cout<<str[2]<<endl;

return 0;
}

Character Array Shift (c++)


#include <iostream>
using namespace std;

int main(void){
        char input[] ="12345678";
        int length =(sizeof(input)-1);
        int shift;
        cin>>shift;
        shift = shift % length;
        char *tmp = new char[length];
        for(int i=0; i< length; i++)
                tmp[i]= input[(i+shift)%length];
        cout<< tmp <<endl;
        return 0;
}

MAX, MIN ,AVG (c++)


#include <iostream>
using namespace std;

int main(void){
        int loop;
        cin>>loop;
        int *ary = new int[loop];

        for(int i=0; i<loop; i++){
                int tmp;
                cin>>tmp;
                ary[i] = tmp;
        }

        int min=ary[0];
        int max =ary[0];
        float sum =0;
        for(int j=1; j< loop ; j++){
        if(ary[j]<min)
                min = ary[j];
        if(ary[j]>max)
                max = ary[j];
        sum += ary[j];
        }
        cout<<"Min = "<<min<<endl;
        cout<<"Max= "<<max<<endl;
        printf("Avg= %.2f\n",(sum/loop));

}

Leap Year (c++)


#include <iostream>
using namespace std;

int main(void){
        int year;
        cin>> year;
        if(year%4==0 && year%100!=0||year%400==0)
                cout<<year<<" is Leap Year"<<endl;
        else
                cout<<year<<" is not Leap Year"<<endl;

        return 0;
}

Card Shuffle (c++)


#include <iostream>
#include <time.h>
using namespace std;
struct card{
        char color;
        int point;

};

        void shuffle (struct card *deck, int n){
                srand((unsigned) time (NULL));
                        struct card tmp;
                for(int i=0; i< n; i++){
                        int j = rand()%52;
                        tmp = deck[i];
                        deck[i] = deck[j];
                        deck[j] = tmp;

                }

        }
int main(void){
        struct card deck[52];
        for(int i=0; i< 52; i++){
                if(i%4==0){
                        deck[i].color = 's';
                        deck[i].point = (i/4)+1;
                }else if(i%4==1){
                        deck[i].color = 'd';
                        deck[i].point = ((i-1)/4)+1;
                }else if(i%4==2){
                        deck[i].color = 'c';
                        deck[i].point = ((i-2)/4)+1;
                }else{
                        deck[i].color = 'h';
                        deck[i].point = ((i-3)/4)+1;
                }
        }
        shuffle(deck, 52);
        return 0;
}

自訂一個strcmp (c++)


#include <iostream>
using namespace std;
int strcmp2(const char *dest, const char *ori);
int main(void){
        cout<<strcmp2("aello","a")<<endl;
        return 0;
}
int strcmp2(const char *dest, const char *ori){
        assert(ori !=NULL && dest!=NULL);
        int tmp =0;
        while(!(tmp = *(unsigned char*)dest - *(unsigned char*)ori)&&*ori){
                ++dest;
                ++ori;
        }
        if(tmp <0){
                tmp= -1;
        }else if(tmp >0){
                tmp=1;
        }
        return tmp;
}

自訂一個strlen(c++)


#include <iostream>
using namespace std;
int strlen2(const char *ori);
int main(void){
        cout<<strlen2("hello world")<<endl;
        return 0;
}
int strlen2(const char *ori){
        assert(ori !=NULL);
        int len =0;
        while(*ori++ !='\0'){
                len++;
        }
        return len;
}

memcpy v.s. strcpy

從strcpy 跟 memcpy 的實做中可以發現

strcpy 限定複製字串內容

而memcpy 並未限定複製內容,可以複製任何類型的內容

strcpy 遇到 '\0' 時停止複製

memcpy 可以指定要複製多少"內容" (int size)

自訂一個memcpy (c++)


#include <iostream>
using namespace std;
void *memcpy2(void *dest, const void *ori, int size);
int main(void){
        char tmp[] = "adfadfaf";
        memcpy2(tmp, "hello world",4);
        tmp[4]='\0';
        cout<<tmp;
        return 0;
}
void *memcpy2(void *dest, const void *ori, int size){
        assert(dest!=NULL && ori !=NULL);
        char *dest2= (char *) dest;
        char *ori2= (char *) ori;
        for(int i=0; i< size; i++){
                *dest2++ = *ori2++;
        }
        return dest2;
}

自訂一個strcpy (c++)


#include <iostream>
using namespace std;

char *strcpy2(char *dest, const char *ori);
int main(void){
        char tmp[] = "adfadfaf";
        strcpy2(tmp, "hello world");
        cout<<tmp;
        return 0;
}
char *strcpy2(char *dest, const char *ori){
        assert(dest!=NULL && ori !=NULL);
        char *addr= dest;
        while((*dest++ = *ori++)!='\0');
        return addr;
}

2009年6月25日星期四

ACM Q11462


#include <iostream>

using namespace std;

int main(){
    int ints[100];
  while(true){
    int count =0;
    int count2 =0;
    for(int i=0; i< 100; i++){
      ints[i]=0;
    }
    int items;
    cin >>  items;
    if(items==0)
      break;
    for(int i=0; i< items; i++){
      int tmp;
      cin >> tmp;
      if(ints[tmp-1]==0)
        count++;
      ints[tmp-1]++;
    }

    for(int i=0; i< 100; i++){
      if(ints[i]>0)
        count2++;
      for(int j=0; j< ints[i]; j++){
        if(count2==count && j==ints[i]-1)
        cout<<(i+1)<<endl;
        else
        cout<<(i+1)<<" ";
      }
    }
  }
  return 0;
}

ACM Q11428


import java.util.Scanner;
import java.lang.Math.*;
public class Q11428 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while(true){
      double N = cin.nextDouble();
      boolean flag = false;
      int tmpx=99999, tmpy=99999;
      if(N==0)
        break;
      double base = (double) 1/3;
      for(int x = (int)Math.ceil(Math.pow(N,base)); x <= Math.sqrt(N) ; x++){
        if (((int)(((Math.pow((Math.pow(x,3)-N),base)+1e-7)*100000)%100000)==0)&&(Math.pow((Math.pow(x,3)-N),base)!=0)){
          flag = true;
          if((int)(Math.pow((Math.pow(x,3)-N),base)+1e-7)< tmpy){
            tmpx = x;
            tmpy = (int)(Math.pow((Math.pow(x,3)-N),base)+1e-7);
          }
        }
      }
      if(flag==false){
        System.out.println("No solution");
      }else{
        System.out.println(tmpx+" "+tmpy);
      }
    }
  }
}

2009年6月24日星期三

ACM Q11369


import java.util.Scanner;
import java.util.Arrays;

public class Q11369 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int loop = Integer.parseInt(cin.nextLine());
    for(int i=0; i< loop ; i++){
      int count =0;
      int items = Integer.parseInt(cin.nextLine());
      String str = cin.nextLine();
      String[] tokens = str.split(" ");

      int[] ints = new int [items] ;
      for(int k = 0 ; k < items ; k++){
        ints[k] = Integer.parseInt(tokens[k] ) ;
      }

      Arrays.sort(ints);
      for(int k = items-1; k>=0; k--){
        if((items-k-1)%3==2){
        count += ints[k];
        }
      }
      System.out.println(count);

    }
  }
}

ACM Q11461


import java.util.Scanner;
import java.lang.Math.*;
public class Q11461 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while(cin.hasNextInt()){
      int M = cin.nextInt();
      int N = cin.nextInt();
      if((M==0)&&(N==0))
        break;
      int L = (int) Math.ceil(Math.sqrt(Math.min(M,N)));
      int U = (int) Math.floor(Math.sqrt(Math.max(M,N)));
      System.out.println(U-L+1);
    }
  }
}

ACM Q11586


import java.util.Scanner;
public class Q11586 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int loop = Integer.parseInt(cin.nextLine());
    boolean flag;
    for(int i=0; i< loop ; i++){
      flag =true;
      int FF=0, FM=0, RF=0, RM=0;
      String str = cin.nextLine();
      if(str.isEmpty()){
        System.out.println("LOOP");
        continue;
      }
      String[] tokens = str.split(" ");
      if(tokens.length>1){
        for(int j = 0; j< tokens.length; j++){
          if(tokens[j].charAt(0)=='M'){
            FM++;
          }
          else if(tokens[j].charAt(0)=='F'){
            FF++;
          }
          if(tokens[j].charAt(1)=='F'){
            RF++;
          }
          else if(tokens[j].charAt(1)=='M'){
            RM++;
          }
        }
      }else{
        System.out.println("NO LOOP");
        continue;
      }

      if((FM==RF) && (FF==RM)){
        System.out.println("LOOP");
      }else{
        System.out.println("NO LOOP");
      }
    }
  }
}

2009年6月11日星期四

ACM Q11530


import java.util.Scanner;
public class Main {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int T = cin.nextInt();
    cin.nextLine();
    for(int i=0; i< T; i++){
      int count =0;
      String line = cin.nextLine();
      char[] lineAry = line.toCharArray();
      for(int j=0; j<lineAry.length; j++){
        int tmp = lineAry[j];
        if(tmp<112&& tmp>= 97){
          count += ((int)lineAry[j]-1)%3+1;
        }else if(lineAry[j]=='p'||lineAry[j]=='t'||lineAry[j]=='w'||lineAry[j]==' '){
          count +=1;
        }else if (lineAry[j]=='q'||lineAry[j]=='u'||lineAry[j]=='x'){
          count +=2;
        }else if (lineAry[j]=='r'||lineAry[j]=='v'||lineAry[j]=='y'){
          count +=3;
        }else if (lineAry[j]=='s'||lineAry[j]=='z'){
          count +=4;
        }
      }
        System.out.println("Case #"+(i+1)+": "+count);
    }
  }
}

ACM Q10079


import java.util.Scanner;
public class Q10079 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while(cin.hasNextLong()){
    long n = cin.nextLong();
    if(n<0)
      break;
      System.out.println(n*(n+1)/2+1);
    }
  }
}

ACM Q686


import java.util.Scanner;
import java.util.HashSet;
import java.util.ArrayList;
import java.lang.Math.*;
public class Main {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    numbers.add(2);
    numbers.add(3);
    for(int i=3; i< 32768; i+=2){
      boolean flag = false;
      for(int j=0; j< numbers.size(); j++){
        if(numbers.get(j)>Math.sqrt(i)){
          break;
        }else if((i%numbers.get(j))==0){
          flag=false;
          break;
        }else{
          flag=true;
        }

      }
      if(flag==true)
        numbers.add(i);
    }
    HashSet<Integer> numberSet = new HashSet<Integer>(numbers);
    while(cin.hasNextInt()){
      int n = cin.nextInt();
      int count=0;
      if(n==0)
        break;
      for(int i=0; numbers.get(i)<=(n/2); i++){
        if(numberSet.contains(n-numbers.get(i))){
          count ++;
        }
      }
      System.out.println(count);
    }
  }
}

2009年6月6日星期六

ACM Q482


import java.util.Scanner;
import java.util.Iterator;
import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;

public class Q482 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int set =  Integer.parseInt(cin.nextLine());
    for(int i=0; i<set; i++){
      HashMap<Integer, String> numbers = new HashMap<Integer, String>();
      String empty = cin.nextLine();
      String index = cin.nextLine();
      String[] indexToken = index.split(" ");
      String content = cin.nextLine();
      String[] contentToken = content.split(" ");
      for(int j=0; j< indexToken.length; j++){
        numbers.put(Integer.parseInt(indexToken[j]),contentToken[j]);
      }
      ArrayList<Integer> as = new ArrayList<Integer>(numbers.keySet());
      Collections.sort(as);
      Iterator<Integer> itr = as.iterator();
      while(itr.hasNext()){
        int s = itr.next();
        System.out.println(numbers.get(s));
      }
      if(i!=set-1)
      System.out.println();
    }
  }
}

2009年6月5日星期五

ACM Q530


import java.util.Scanner;
public class Main {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while(cin.hasNextDouble() ){
      double n = cin.nextDouble();
      double m = cin.nextDouble();
      double fac_n=1, fac_m=1;
      double count;
      if(n<1&&m==0&&m-n<=0){
      break;
      }
      if(m==0){
      System.out.println(1);
      continue;
      }
      if(n-m < m){
      count = n-m;
      }else{
      count =m;
      }
      for(double i=0; i<count; i++){
        fac_n *= (n-i);
      }
      for(double j=1; j<=count; j++){
        fac_m *= j;
      }
      System.out.println((int) (fac_n / fac_m));
    }
  }
}

2009年6月3日星期三

ACM Q591


import java.util.Scanner;
public class Q591 {
  public static void main(String args[]) {
    int count =0;
    Scanner cin = new Scanner(System.in);
    while(cin.hasNextLine() ){
      String inputLine = cin.nextLine();
      int size = Integer.parseInt(inputLine);
      if (size==0){
        break;
      }
      count++;
      System.out.println("Set #"+count);
      String tokenLine = cin.nextLine();
      String[] tokens = tokenLine.split(" ");
      int total =0;
      int move =0;
      for(int i=0; i< size;i++ ){
        total += Integer.parseInt(tokens[i]);
      }
      for(int j=0; j< size;j++ ){
        if( Integer.parseInt(tokens[j])> total/size){
          move +=  Integer.parseInt(tokens[j]) - total/size;
        }
      }
      System.out.println("The minimum number of moves is "+move+".\n");
    }
  }
}

2009年6月2日星期二

ACM Q579


import java.util.Scanner;
public class Q579 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while(cin.hasNextLine() ){
      String  inputLine = cin.nextLine();
      String[] tokens = inputLine.split(":");
      float h = Float.parseFloat(tokens[0]);
      float m = Float.parseFloat(tokens[1]);
      if(h==0 && m==0){
      break;
      }
      float angle = (float) Math.abs(h * 30 + m /2 - m * 6);
      if( angle > 180){
      System.out.printf("%.3f\n",360-angle);
      }else{
      System.out.printf("%.3f\n",angle);
      }
    }

  }
}

ACM Q11296


import java.util.Scanner;
public class Q11296 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    long  n;
    while(cin.hasNextInt() ){
      n = cin.nextInt();
      if(n > 1000001){
        continue;
      }
      long count=0;
        count = (n/2+1)*(n/2+2)/2;
      System.out.println(count);
    }

  }
}

利用公式解!!!


import java.util.Scanner;
public class Q11296 {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int  n;
    while(cin.hasNextInt() ){
      n = cin.nextInt();
      if(n > 1000001){
        continue;
      }
      long count=0;
      for(int x=n%2; x<=n ;x=x+2){
        count += (n-x)/2+1;
      }
      System.out.println(count);
    }

  }
}

不用公式解!!!

How to format source code for blogger

Please visit this site for further information

http://www.manoli.net/csharpformat/

http://formatmysourcecode.blogspot.com/

It may re-decorate your source code into HTML format

Software Company Interview Question


using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace ApplicantTestin
{
    /// The DataObject class stored with a key
    class DataObject
    {
        // Populate
        private string keyStr;
        private long keyValue;
        private bool keyStatus;
       
 
        
        public DataObject(string inputKey)
        {      
                keyStr = inputKey;                
        }

        public string Str
        {
            get { return keyStr; }          
        }
        public long Val
        {
            get { return keyValue; }
            set { keyValue = value; }
        }
        public bool Status
        {
            get { return keyStatus; }
            set { keyStatus = value; }
        }


        public void Decrease()
        {
            keyValue--;
        }
        public void Increase()
        {
            keyValue++;
        }

      
    }

  
    class Program
    {
       static Hashtable Data = new Hashtable();
       
        static string[] StaticData = new string[] { "X-ray","Echo","Alpha", "Yankee","Bravo", "Charlie", 
            "Delta",    "Hotel", "India", "Juliet", "Foxtrot","Sierra",
            "Mike","Kilo", "Lima",  "November", "Oscar", "Papa", "Qubec", 
            "Romeo",  "Tango","Golf", "Uniform", "Victor", "Whisky",  
             "Zulu"};

        static void Main(string[] args)
        {
            for (int i = 0; i < StaticData.Length; i++)
                Data.Add(StaticData[i].ToLower(), new DataObject(StaticData[i]));         
            while (true)
            {
                PrintSortedData();
                Console.WriteLine();
                Console.Write("> ");
                string str = Console.ReadLine();
                string[] strs = str.Split(' ');

                if (strs[0] == "q")
                    break;
                else if (strs[0] == "printv")
                    PrintSortedDataByValue();
                else if (strs[0] == "print")
                    PrintSortedData();
                else if (strs[0] == "inc")
                    Increase(strs[1]);
                else if (strs[0] == "dec")
                    Decrease(strs[1]);
                else if (strs[0] == "swap")
                    Swap(strs[1], strs[2]);
                else if (strs[0] == "ref")
                    Ref(strs[1], strs[2]);
                else if (strs[0] == "unref")
                    UnRef(strs[1]);
            }
        }

        /// <summary>
        /// Create a reference from one data object to another.
        /// </summary>
        /// <param name="key1">The object to create the reference on</param>
        /// <param name="key2">The reference object</param>
        static void Ref(string key1, string key2)
        {
            try
            {
                if (Data.ContainsKey(key1) && Data.ContainsKey(key2))
                {
                    Data[key1.ToLower()] = Data[key2.ToLower()];                   
                    Console.WriteLine(key1 + " -> <" + ((DataObject)Data[key1.ToLower()]).Str + ">");
                    Console.WriteLine(key2 + " -> <" + ((DataObject)Data[key2.ToLower()]).Str + ">");
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }               
        }

        /// <summary>
        /// Removes an object reference on the object specified.
        /// </summary>
        /// <param name="key">The object to remove the reference from</param>
        static void UnRef(string key)
        {
            try
            {
                if (Data.ContainsKey(key))
                {
                    string tmpstr = key.Substring(0, 1).ToUpper() + key.Substring(1, key.Length - 1);
                    Data[key.ToLower()] = new DataObject(tmpstr);                                                
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }

        }

        /// <summary>
        /// Swap the data objects stored in the keys specified
        /// </summary>
        static void Swap(string key1, string key2)
        {
            // Populate
            try
            {
                if (Data.ContainsKey(key1) && Data.ContainsKey(key2))
                {
                    DataObject obj = (DataObject)Data[key1.ToLower()];
                    Data[key1.ToLower()] = Data[key2.ToLower()];
                    Data[key2.ToLower()] = obj;
                    Console.WriteLine(key1+ " <-> " + key2);
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }
        }

        /// <summary>
        /// Decrease the Value field by 1 of the 
        /// data object stored with the key specified
        /// </summary>
        static void Decrease(string key)
        {
            try
            {
                if (Data.ContainsKey(key))
                {

                    ((DataObject)Data[key.ToLower()]).Decrease();                    
                    Console.WriteLine("Decrement: " + ((DataObject)Data[key.ToLower()]).Val);

                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }
        }

        /// <summary>
        /// Increase the Value field by 1 of the 
        /// data object stored with the key specified
        /// </summary>
        static void Increase(string key)
        {
            try
            {
                if (Data.ContainsKey(key))
                {
                    ((DataObject)Data[key.ToLower()]).Increase();                    
                    Console.WriteLine("Increment: "+ ((DataObject)Data[key.ToLower()]).Val);
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }

        }


        /// <summary>
        /// Prints the information in the Data hashtable to the console.
        /// Output should be sorted by key 
        /// References should be printed between '<' and '>'
        /// The output should look like the following : 
        /// 
        /// 
        /// Alpha...... -3
        /// Bravo...... 2
        /// Charlie.... <Zulu>
        /// Delta...... 1
        /// Echo....... <Alpha>
        /// --etc---
        /// 
        /// </summary>
        static void PrintSortedData()
        {
            ArrayList sortList = new ArrayList();
            sortList.AddRange(Data.Keys);
            sortList.Sort();
            foreach (string s in sortList)
            {
                DataObject obj = (DataObject)Data[s];
                string tmpstr = s.Substring(0,1).ToUpper()+s.Substring(1,s.Length-1);

                if(obj.Str == tmpstr){
                Console.WriteLine(tmpstr + " " + obj.Val);
                }else{
                  Console.WriteLine(tmpstr + " <" + obj.Str+">");
                }
            }  
        }


        /// <summary>
        /// Prints the information in the Data hashtable to the console.
        /// Output should be sorted by stored value
        /// References should be printed between '<' and '>'
        /// Sorting order start from max to min, larger value takes priority.
        /// The output should look like the following : 
        /// 
        /// 
        /// Bravo...... 100
        /// Echo...... 99
        /// Zulu...... 98
        /// Charlie.... <Zulu>
        /// Delta...... 34
        /// Echo....... 33
        /// Alpha...... <Echo>
        /// --etc---
        /// 
        /// </summary>
        static void PrintSortedDataByValue()
        {
            ArrayList sortlistValue = new ArrayList();
            sortlistValue.AddRange(Data.Keys);
            for (int i = sortlistValue.Count-1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                     if (((DataObject)Data[sortlistValue[j+1]]).Val > ((DataObject)Data[sortlistValue[j]]).Val){
                         string tmp = sortlistValue[j].ToString();
                         sortlistValue[j] = sortlistValue[j+1];
                         sortlistValue[j+1] = tmp;
                     }
                }

            }

            Console.WriteLine("Sorted by value\n====================");
       
            foreach (string s in sortlistValue)
            {
                DataObject obj = (DataObject)Data[s];
                string tmpstr = s.Substring(0, 1).ToUpper() + s.Substring(1, s.Length - 1);

                if (obj.Str == tmpstr)
                {
                    Console.WriteLine(tmpstr + " " + obj.Val);
                }
                else
                {
                    Console.WriteLine(tmpstr + " <" + obj.Str + ">");
                }
            }
            Console.WriteLine("====================");
        }
    }
}

2009年6月1日星期一

ACM Q101 - C#


using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace test
{
    class test
    {
  
        static void Main(){

         int stack_n = int.Parse(Console.ReadLine());
         Stack<int>[] intStack = new Stack<int>[stack_n];
         int[] Block = new int[stack_n];

         for (int i = 0; i < stack_n; i++)
         {
             Block[i] = i;
            intStack[i] = new Stack<int>();
            intStack[i].Push(Block[i]);
         }

             while (true)
             {
         
                 string rl = Console.ReadLine();                
                 string[] parts = rl.Split(' ');

                 if (parts.Length == 4)
                 {
                     int a = int.Parse(parts[1]);
                     int b = int.Parse(parts[3]);

                     if (parts[0] == "move" && parts[2] == "onto")
                     {

                         while (intStack[Block[a]].Peek() != a)
                         {
                             int tmp = intStack[Block[a]].Pop();
                             intStack[tmp].Push(tmp);
                             Block[tmp] = tmp;
                         }
                         while (intStack[Block[b]].Peek() != b)
                         {
                             int tmp = intStack[Block[b]].Pop();
                             intStack[tmp].Push(tmp);
                             Block[tmp] = tmp;
                         }
                         int tmp2 = intStack[Block[a]].Pop();
                         intStack[Block[b]].Push(tmp2);
                         Block[tmp2] = Block[b];
                     }
                     else if (parts[0] == "move" && parts[2] == "over")
                     {
                         while (intStack[Block[a]].Peek() != a)
                         {
                             int tmp = intStack[Block[a]].Pop();
                             intStack[tmp].Push(tmp);
                             Block[tmp] = Block[b];
                         }
                         int tmp2 = intStack[Block[a]].Pop();
                         intStack[Block[b]].Push(tmp2);
                         Console.WriteLine("moveover " + tmp2+" "+a +" "+b);
                         Block[tmp2] = Block[b];
                     }
                     else if (parts[0] == "pile" && parts[2] == "onto")
                     {
                         Stack<int> tmpstack = new Stack<int>();
                         while (intStack[Block[a]].Peek() != a)
                         {
                             int tmp = intStack[Block[a]].Pop();
                             tmpstack.Push(tmp);
                         }
                         tmpstack.Push(intStack[Block[a]].Pop());
                         while (intStack[Block[b]].Peek() != b)
                         {
                             int tmp = intStack[Block[b]].Pop();
                             intStack[tmp].Push(tmp);
                             Block[tmp] = tmp;
                         }
                         while (tmpstack.Count > 0)
                         {
                             int tmp = tmpstack.Pop();
                             intStack[Block[b]].Push(tmp);
                             Block[tmp] = Block[b];
                         }
                     }
                     else if (parts[0] == "pile" && parts[2] == "over")
                     {
                         Stack<int> tmpstack = new Stack<int>();
                         while (intStack[Block[a]].Peek() != a)
                         {
                             int tmp = intStack[Block[a]].Pop();                     
                             tmpstack.Push(tmp);
                         }
                         tmpstack.Push(intStack[Block[a]].Pop());
                         while (tmpstack.Count > 0)
                         {
                             int tmp = tmpstack.Pop();
                             intStack[Block[b]].Push(tmp);
                             Block[tmp] = Block[b];
                         }
                     }
                 }

                 if(parts[0]=="quit")
                 {
                     break;
                 }
              
             }
             for (int i = 0; i < stack_n; i++)
             {
                 Console.Write(i + " :");
                 foreach (int j in intStack[i])
                 {
                     Console.Write(j);
                 }
                 Console.WriteLine();
             }            
        }
 

    }
}

2009年5月27日星期三

ACM Q11417

import java.util.Scanner;
public class Q11417 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int count=0;
while(cin.hasNextInt()){
int N = cin.nextInt();
if(N==0){
break;
}
count++;
int G=0;
for(int i=1;i< N;i++)
for(int j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
System.out.println(G);
}
}
public static int GCD(int x, int y) {
int tmp;
while (x % y != 0) {
tmp = y;
y = x % y;
x = tmp;
}
return y;
}
}

2009年5月26日星期二

ACM Q10696

import java.util.Scanner;
public class Q10696 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int count=0;
while(cin.hasNextInt()){
int N = cin.nextInt();
count++;
if(N==0 || count >=250000){
break;
}else{
if(N>=101 ){
int tmp = N-10;
System.out.println("f91("+N+") = "+tmp);
}else{
System.out.println("f91("+N+") = 91");
}
}
}
}
}

ACM Q11577

import java.util.Scanner;
public class Q11577 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int[] arrayd = new int[26];
int loop = Integer.parseInt(cin.nextLine().toString());

for(int j=1; j<=loop; j++)
{
int max=0;
for(int p =0; p<26; p++){
arrayd[p]=0;
}
String line = cin.nextLine();
char[] ca = line.toCharArray();

for(int i=0; i< ca.length; i++){
if(ca[i]<= 90 && ca[i]>=65){
int tmpval = (int)ca[i]-65;
arrayd[tmpval]++;
if(arrayd[tmpval] > max){
max = arrayd[tmpval];
}
}else if (ca[i]<= 122 && ca[i]>=97){
int tmpval = (int)ca[i]-97;
arrayd[tmpval]++;
if(arrayd[tmpval] > max){
max = arrayd[tmpval];
}
}
}

for(int p =0; p<26; p++){
if(arrayd[p]==max){
System.out.print((char)(p+97));
}
}

System.out.println();
}
}
}

2009年5月24日星期日

ACM Q10038

import java.util.Scanner;
import java.lang.Math;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class Q10038 {

public static void main(String args[]){
Scanner cin = new Scanner(System.in);
String inputLine;
while (cin.hasNextLine()){
int count =0;
int max =0;
ArrayList as = new ArrayList();

boolean flag = true;
inputLine = cin.nextLine();
String[] tokens = inputLine.split(" ");
count = Integer.parseInt(tokens[0]);
for (int i=1 ;i < tokens.length; i++) {
if(Integer.parseInt(tokens[i])> max){
max = Integer.parseInt(tokens[i]);
}

}
for (int i=1 ;i < tokens.length-1; i++) {
as.add(Math.abs(Integer.parseInt(tokens[i])-Integer.parseInt(tokens[i+1])));
}
Collections.sort(as);

for (int i=0 ;i < as.size(); i++) {
if(as.get(i)!=i+1){
System.out.println("Not jolly");
flag =false;
break;
}
}
if(flag ==true){
System.out.println("Jolly");
}

}

}
}

ACM Q494

import java.util.Scanner;

public class Q494 {

public static void main(String args[]){
Scanner cin = new Scanner(System.in);
String regex = "^[A-Za-z]+.*";
String delims = " [^A-Za-z]";
String inputLine;
while (cin.hasNextLine()){
int count =0;
inputLine = cin.nextLine();
String[] tokens = inputLine.split("[^A-Za-z]");

for (String s : tokens) {
if(s.matches(regex)){
count++;
}

}
System.out.println(count);
}

}

}

ACM Q10035

import java.util.Scanner;
public class Q10035 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while(cin.hasNextInt()){
String x = cin.next();
String k = cin.next();
if(x.charAt(0)=='0' && k.charAt(0)=='0'){
break;
}
int Match_length=Math.max(x.length(), k.length());
char [] x1 = new char[Match_length];
char [] k1 = new char[Match_length];
int carry=0, count =0;
char[] x2 = x.toCharArray();
char[] k2 = k.toCharArray();
for(int i=0; i< x1.length; i++){
if(i< Match_length- x2.length){
x1[i] ='0';
}else{
x1[i] = x2[i+x2.length-Match_length];
}
}
for(int j=0; j< k1.length; j++){
if(j< Match_length- k2.length){
k1[j] ='0';
}else{
k1[j] = k2[j+k2.length-Match_length];
}
}
for(int p=Match_length-1; p>= 0; p--){
if(Integer.parseInt(Character.toString(x1[p]))+Integer.parseInt(Character.toString(k1[p]))+carry>=10){
carry = 1;
count ++;
}else{
carry =0;
}
}
if(count ==0){
System.out.println("No carry operation.");
}else if(count ==1){
System.out.println("1 carry operation.");
}else{
System.out.println(count+" carry operations.");
}
}

}
}

ACM Q10107

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;

public class Q10107 {
public static void main(String args[]) {

Scanner cin = new Scanner(System.in);
LinkedList al=new LinkedList();
int count=0;
int flag = 0;
while (cin.hasNext()) {
count++;
Iterator itr = al.iterator();
int tmp = cin.nextInt();
int insert_pos=0;
while(itr.hasNext())
{
if(tmp > (Integer) itr.next()){
insert_pos ++;
}else{
break;
}
}
al.add(insert_pos,tmp);

if(count%2==1){
System.out.println(al.get(flag));
}else{
System.out.println((al.get(flag) + al.get(flag+1))/2);
flag++;
}

}
}
}

ACM Q10062

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.Iterator;

import java.util.Scanner;

public class Q10062 {

public static void main(String args[]){

Scanner cin = new Scanner(System.in);

String inputLine;

while (cin.hasNextLine()){

inputLine = cin.nextLine();

Scanner tokenize = new Scanner(inputLine).useDelimiter("");

final HashMap numbers = new HashMap();

while(tokenize.hasNext()) {

String tmp = tokenize.next();

if(!numbers.containsKey(tmp)){

numbers.put(tmp,1);

}else{

int value = numbers.get(tmp)+1;

numbers.put(tmp,value);

}

ArrayList as = new ArrayList(numbers.keySet());

Collections.sort(as, Collections.reverseOrder());

Collections.sort( as , new Comparator

2009年7月30日 星期四

2009年7月22日 星期三

2009年7月21日 星期二

2009年6月25日 星期四

2009年6月24日 星期三

2009年6月11日 星期四

2009年6月6日 星期六

2009年6月5日 星期五

2009年6月3日 星期三

2009年6月2日 星期二

2009年6月1日 星期一

2009年5月27日 星期三

2009年5月26日 星期二

2009年5月24日 星期日

2009年3月9日 星期一

2009年2月12日 星期四

2009年1月22日 星期四

2009年1月2日 星期五