Blank's Program Language: 2012

2012年12月26日星期三

研究所

台大：

1.英文(A)：成績不計入考試總分計算，惟成績未達該科本校到考生前80%者，不予錄取。
2.數學(含線性代數、離散數學)
3.計算機系統(含計算機結構、作業系統)
4.軟體設計(含資料結構、演算法)

台大資工:
線代:投資報酬率低，簡單的很簡單難的很難，
算子(黃子嘉第八章)和求反矩陣的方法要熟一點
離散:要廣，幾乎都不能放棄，代數簡單的要會，
圖論證明要記，其他的證明能記就記

計組:往年滿正常的，今年很奇怪，建議之後算盤本第0張要看一下...
台大教授上課投影片能拿則拿考題能拿則拿

OS :分散式系統考很多...(要特別準備台大OS，這個最好不要放棄)
台大教授上課投影片能拿則拿考題能拿則拿
(聽說今年OS是非題，滿多上課投影片有)

ALGO & DS: 97年考一堆ALGO，今年考滿多DS，建議明年是不要賭，
有時間的話，ALGO重要的地方都要會

2012年12月24日星期一

ITSA20

 
#include<stdio.h>
int main(){
    int n,i,j,cas=1;
    while(scanf("%d",&n)!=EOF){
        long long s[20],max=0,tmp;
        for(i=0;i<n;i++) scanf("%lld",&s[i]);
        for(i=0;i<n;i++){
            tmp=1;
            //max=(max<tmp)? tmp:max;
            for(j=i;j<n;j++){
                tmp*=s[j];
                max=(max<tmp)? tmp:max;
            }
        }
        printf( "Case #%d: The maximum product is %lld.\n\n", cas++, max );
    }
return 0;
}

ITSA19

 
#include<stdio.h>
int main(){
    long long x,fun[200000];
    char str[200000];
    while(~scanf("%lld",&x)){
        int top=0,num=0,i,j,op=1;
        getchar();
        gets(str);
        for(i=0;str[i];i++){
            if(str[i]!=' '){
            if(str[i]=='-') op=-1,i++;
                num*=10;
                num+=str[i]-'0';
            }
            else{
                fun[top++]=num*op;

                num=0;
                op=1;
            }
        }
        fun[top++]=num*op;
        long long sum=0,r=1;
        for(i=top-2,j=1;i>=0;j++,i--){
            sum+=j*fun[i]*r;
            r*=x;
        }
        printf("%lld\n",sum);
    }
return 0;
}

ITSA18

 
#include<stdio.h>
int main(){
int n,a=0,b=1,c=1,fib[20000],top=0;
while(c<=100000000){
fib[top++]=c;
c=a+b;
a=b;
b=c;
}
scanf("%d",&n);
while(n--){
    int num,i;
    scanf("%d",&num);
    printf("%d = ",num);
    for(i=top-1;fib[i]>num;i--);
    while(i>0){
        if(num-fib[i]>=0){
                printf("1");
                num-=fib[i];
        }
        else
        printf("0");
        i--;
    }
    printf(" (fib)\n");
}
return 0;
}

ITSA17

 
#include<stdio.h>
int main(){

int n;
    while(scanf("%d", &n)&&n){

    int i;
    int count=0;
    printf("%d : ",n);
    for(i=2;i<=n;i=i+1)
    {
      if(n%i==0)
      {
        while(n%i==0)
        {
          n=n/i;

        }
        count=count+1;
      }
    }

     printf("%d\n", count);
    }
return 0;
}

ITSA16

 
#include <stdio.h>
#include <string.h>

void solve(int o[], int base) {
    int a[500] = {};
    int i, j, k, len;
    int cnt = 0;
    len = 299;
    while(o[len] == 0)  len--;
    do {
        for(i = 0, j = len; i < j; i++, j--)
            if(o[i] != o[j])
                break;
        if(i >= j)
            break;
        cnt++;
        for(i = 0; i <= len; i++)
            a[i] = o[i]+o[len-i];
        for(i = 0; i <= len+10; i++) {
            if(a[i] >= base) {
                a[i+1] += a[i]/base;
                a[i] %= base;
            }
            o[i] = a[i];
        }
        len += 10;
        while(o[len] == 0)  len--;
    } while(1);
    printf("%d", cnt);
}
int main() {
    char s[105];
    while(scanf("%s", &s) == 1) {
        int i, j, k, len = strlen(s), base = 0;
        for(i = 0; i < len; i++) {
            if(s[i] <= '9')
                s[i] -= '0';
            else
                s[i] -= 'A'-10;
            if(s[i] > base)
                base = s[i];
        }
        if(base == 0)   base = 1;
        for(i = 15; i > base; i--) {
            if(i != 15) printf(" ");
            int o[500] = {};
            for(j = len-1, k = 0; j >= 0; j--, k++)
                o[k] = s[j];
            solve(o, i);
        }
        for(i = base; i >= 2; i--) {
            if(i != 15) printf(" ");
            printf("?");
        }
        puts("");
    }
    return 0;
}

ITSA15

 
#include <stdio.h>
int main()
{
    int T, m, n, q, x, y, i;
    char map[101][101];
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &m, &n, &q);
        for(i = 0; i < m; i++)
            scanf("%s", map[i]);
        printf("%d %d %d\n", m, n, q);
        while(q--){
            scanf("%d%d", &x, &y);
            for(i = 1; ; i++){
                int xx = x-i, yy = y-i, dx = x+i, dy = y+i, judge = 0;
                if(xx < 0 || yy < 0 || dx >= m || dy >= n)    {printf("%d\n", 2*i-1); break;}
                for(int a = xx; a < xx+i*2+1 && !judge; a++)
                    for(int b = yy; b < yy+i*2+1 && !judge; b++)
                        if(map[a][b] != map[x][y])   judge = 1;
                if(judge)   {printf("%d\n", 2*i-1); break;}
            }
        }
    }
    return 0;
}

ITSA14

 
#include<stdio.h>
int main(){
int ch[200],ans[200],top=0,i,j;
char c;
for(i=0;i<200;i++) ch[i]=0;
while((c=getchar())!=EOF){
    if(c=='\n'){
        for(i=0;i<200;i++)
            if(ch[i]!=0)
                ans[top++]=i;;
        for(i=0;i<top;i++)
            for(j=i;j<top;j++)
                if(ch[ans[i]]>=ch[ans[j]]){
                    int t;
                    t=ans[i],ans[i]=ans[j],ans[j]=t;
                }
        for(i=0;i<top;i++)
            printf("%X %d\n",ans[i],ch[ans[i]]);
        puts("");
        for(i=0;i<200;i++) ch[i]=0;
        top=0;
    }
    else{
        ch[c]++;
    }
}

return 0;
}


//21 - 7f = 5E =94

ITSA13

 
#include<stdio.h>
int main(){
int n,m,i,x1,y1,x2,y2,cas=0;
int lx,ly,rx,ry;
scanf("%d",&n);
while(n--){
    scanf("%d",&m);

    scanf("%d %d %d %d",&lx,&ly,&rx,&ry);
    for(i=1;i<m;i++){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        if(x1>lx) lx=x1;
        if(y1>ly) ly=y1;
        if(x2<rx) rx=x2;
        if(y2<ry) ry=y2;
    }
    if((rx-lx)<0||(ry-ly)<0)
    printf("Case %d: 0\n",++cas);
    else
    printf("Case %d: %d\n",++cas,(rx-lx)*(ry-ly));
}
return 0;
}

ITSA12

 
#include<stdio.h>
int main(){
int i,j,k,n,d;
scanf("%d",&n);
while(n--){
    scanf("%d",&d);
    int judge=1;
    for(i=0;i*i<=d;i++)
        for(j=i;j*j<=d;j++)
            for(k=j;k*k<=d;k++)
                if((i*i+j*j+k*k)==d&&judge==1){
                    printf("%d %d %d\n",i,j,k);
                    judge=0;
                }
if(judge)
 printf("-1\n");
}
return 0;
}

ITSA11

#include<stdio.h>
#include<stdlib.h>
int main(){
int n;
while(scanf("%d",&n)==1){
    if(n==0) break;
    while(n>=10){
        int sum=0;
        while(n!=0){
            sum+=n%10;
            n/=10;
        }
        n=sum;
    }
    printf("%d\n",n);
}
return 0;
}

ITSA10

 
 #include<stdio.h>
int main(){
char c;
while((c=getchar())!=EOF){

    if(c=='<') {
        while(c!='>') c=getchar();
    }
    else if(c==' '||c=='\t'||c=='\n')
        ;
    else{
        printf("[");
        while(c!='<'){
        putchar(c);
        c=getchar();
        }
        printf("]\n");
        while(c!='>') c=getchar();
    }
}
return 0;
}

老師解法(有去尾部空白)

 
#include<stdio.h>
#include <stdlib.h>
main()
{
 char line[1024];
 int idx;
 int state;
 int c;
 state=0;
 while((c=getchar())!=EOF){
  if(state==0){
   if(c=='<'){
    state=1;
   }
   else{
    if(c!=' '&&c!='\n'&&c!='\t'){
     state=2;
     idx=0;
     line[idx++]=c;
    }
   }
  }
  else if(state==1){
   if(c=='>'){
    state=0;
   }
  }
  else if(state==2){
   if(c=='<'){
    for(idx--;line[idx]==' '||line[idx]=='\n'||line[idx]=='\t';idx--);
    line[idx+1]='\0';
    printf("[%s]\n", line);
    state=1;
   }else line[idx++]=c;
  }
 }
}

ITSA 9

 
#include <stdio.h>
#include <string.h>

int main(){
    char c;
    while((c=getchar())!=EOF){
        if(c<0||c>127){
            printf("%%%X",c+256);
        }
        else
            putchar(c);
    }
return 0;
}

ITSA8

註解部分為原本答案預設一解圍三重跟。
許沁憲表示判斷此根3次方和c相同則為重跟，不同則為無解。

#include <stdio.h>

int main(){
int a,b,c,i,j;

while(scanf("%d %d %d",&a,&b,&c)==3){

int ans[3],nc=0;
ans[0]=ans[1]=ans[2]=0;

for (i=-1000;i<=1000;i++){
    if ((i*i*i+a*i*i+b*i+c)==0)
        ans[nc++]=-i;
}
/*
if(nc==1){
    ans[2]=ans[1]=ans[0];
}
else if(nc==2&&ans[2]>ans[1]){
    int tmp;
    tmp=ans[2],ans[2]=ans[1],ans[1]=tmp;
}*/
for(i=0;i<3;i++)
    for(j=i;j<3;j++){
    int t;
    if(ans[i]>ans[j]) t=ans[i],ans[i]=ans[j],ans[j]=t;
    }
if(nc)
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
else
    printf("no solution\n");

}
return 0;
}

ITSA7

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

int mark[50000], prime[50000], Pt = 0;

void sieve (){
 int i, j;
 for(i = 2; i <50000; i++) {
  if(mark[i] == 0) {
   prime[Pt++] = i;
   for(j = 2; j*i<50000; j++)
    mark[j*i] = 1;
  }
 }
}



int main(){
sieve();
int n,i;
scanf("%d",&n);
printf("%d=",n);
int tmp=n;
int p[200],pow[200],top=0;

for(i=0;prime[i]*prime[i]<tmp&&n;i++){
    if(n%prime[i]==0){
        p[top]=prime[i],pow[top]=0;
        while(n%prime[i]==0){
            n=n/prime[i];
            pow[top]++;
        }
        top++;
    }
}
if(top==0)
    printf("%d^1",n);
else{
    printf("%d^%d",p[0],pow[0]);
    for(i=1;i<top;i++)
        printf("*%d^%d",p[i],pow[i]);
}
puts("");
return 0;
}

這是許沁憲簡化版本的質因數分解

#include<stdio.h>
#include<stdlib.h>
int main()
{

int flag;
int g,num,i,n,x;
int p[100],pow[100],nc=0;

scanf("%d",&num);
printf("%d=",num);
n=num;
for(i=0;num%2==0;num=num/2,i++);
if(i>0)
p[nc]=2,pow[nc]=i,nc++;

for(g=3;g*g<=n && g<=num;g=g+2){
for(i=0;num%g==0;i++,num=num/g);
if(i>0)
p[nc]=g,pow[nc]=i,nc++;
}

if(num!=1) 
p[nc]=num,pow[nc]=1,nc++;


for(i=0;i<nc;i++){
if(i!=0)
printf("*");
printf("%d^%d",p[i],pow[i]);
}
printf("\n");
system("pause");
}

ITSA6

 
#include<stdio.h>

int main(){
int month[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int year,m,fday,i;

scanf("%d %d %d",&year,&m,&fday);
if(year%4==0&&year%100!=0||year%400==0) month[1]=29;
printf(" S  M  T  W  T  F  S\n");
printf("--------------------\n");
for(i=0;i<month[m-1]+fday;i++){
if(i%7==0&&i!=0)
    printf("\n");
else if(i%7!=0)
    printf(" ");
if(i<fday)
    printf("  ");
else
    printf("%2d",i-fday+1);
}

printf("\n--------------------\n");
return 0;
}

2012年12月23日星期日

部落格創立雜記

今天是第一天建立部落格的日子2012/12/23 4:51
參考演算法筆記：http://www.csie.ntnu.edu.tw/~u91029/about.html

一、整理國內學校沒有教，但是國外學校有教的演算法。例如麻省理工學院開設的課程：組合最佳化（數學所）、高等資料結構（電資所）、高等演算法（電資所）。

二、整理演算法競賽的常見演算法。以下列出一些知名的演算法競賽：例如專門為資訊科系大學生舉辦的 ACM-ICPC ，以及知名私人企業舉辦的 TopCoder Open: Algorithm 、 Google Code Jam 、 Facebook Hacker Cup 等等。

三、擷取期刊論文上面刊載的新穎演算法，匯整成系統。演算法的期刊論文、會議論文相當多，本站目前能力所及、能夠勉強關注的有 Algorithmica 、 SODA 、 COCOA 等等。

四、介紹計算機科學的應用，扭轉一般人對於資訊工程系的迷思──不該只是懂程式語言、懂電腦架構、懂軟體系統而已。

五、取網站內容的精華，出版成冊，作為輔助教材。

訂閱：文章 (Atom)

2012年12月26日 星期三

2012年12月24日 星期一

2012年12月23日 星期日

2012年12月26日星期三

2012年12月24日星期一

2012年12月23日星期日