[ACM] 100 – The 3n + 1 problem

/* Title:   100 - The 3n + 1 problem
 * Purpose: http://uva.onlinejudge.org/external/1/100.pdf 
 * Author:  lancetw@gmail.com aka Hsin-lin Cheng
 * Date:    2009/10/18
 *
 */

#include <stdio.h>

#define swap(x,y) (x^=y,y^=x,x^=y)


int cycle_len(int n)
{
	int cycle = 1;
	while (n != 1) {
		n = n % 2 ? 3 * n + 1 : n / 2;
		++cycle;
	}
	return cycle;
}

int q100(int v1, int v2)
{
	if (v1 <= 0 || v1 >= 1000000 || v2 <= 0 || v2 >= 1000000)
		return 0;

	int i, cycle, max;

	max = 0;
	for (i = v1; i <= v2; i++) {
		cycle = cycle_len(i);
		max = cycle > max ? cycle : max;
	}
	return max;
}

int main(void)
{
	#ifndef ONLINE_JUDGE
	/* [R] Input/Output data with specific files */
	freopen("sample.in", "rt", stdin);
	#endif

	/* Program Start */

	int i, j;
	while (scanf("%d %d", &i, &j) !=EOF) {
		printf("%d %d", i, j);
		if (i > j) {
			swap(i, j);
		}
		printf(" %d\n", q100(i, j));
	}
	
	/* Program End  */
	return 0;
}

給 ACM 用的 Makefile

CC = gcc
CFLAGS = -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE -Wall

SOURCE_FILES = $(wildcard *.c)
TARGET_FILES=$(patsubst %.c,%,$(SOURCE_FILES))

.PHONY:all

all:$(TARGET_FILES)

$(TARGET_FILES): % : %.c
	$(CC) $(CFLAGS) $< -o $@

clean:
	$(RM) $(TARGET_FILES)

a022: 迴文

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

#define MAXLENGTH 1024
#define TRUE (1==1)
#define FALSE (0==1)

int check(char *text);

main()
{
    char text[MAXLENGTH];
    while(scanf("%s", &text) != EOF)
    {
        if(check(text))
        {
            puts("yes");
        }
        else
        {
            puts("no");
        }
    }
    return 0;
}

int check(char *text)
{
    int i, count;
    int textlen = strlen(text);
    if (textlen % 2)
    {
        count = textlen / 2;
    } else {
        count = textlen / 2 - 1;
    }
    for (i = 0; i <= count; i++)
    {
        if(text[i] != text[textlen-1-i])
            return FALSE;
    }
    return TRUE;
}

a024: 最大公因數(GCD)

#include <stdio.h>

int gcd(int x, int y);

main()
{
    int x, y, tmp;
    while(scanf("%d %d", &x, &y) != EOF)
    {
        if(x < y)
        {
            x^=y^=x^=y;
        }
        printf("%d\n", gcd(x, y));
    }
    return 0;
}

int gcd(int x, int y)
{
    int tmp = x % y;
    x = y;
    y = tmp;
    if (tmp > 0)
    {
        return gcd(x, y);
    }
    else {
        return x;
    }
}

a020: 身分證檢驗

有更快的算法嗎?

#include <stdio.h>

#define MAXLENGTH 1024

int alphabet2num(char c);

main() 
{
    char s[MAXLENGTH];
    while(scanf("%s", &s) != EOF)
    {
        if(strlen(s) != 10)
            continue;
        int n = alphabet2num(*s);
        int res = (n % 10) * 9 + ((n / 10) % 10)
                + (*( s + 1 ) - '0') * 8 
                + (*( s + 2 ) - '0') * 7 
                + (*( s + 3 ) - '0') * 6
                + (*( s + 4 ) - '0') * 5 
                + (*( s + 5 ) - '0') * 4
                + (*( s + 6 ) - '0') * 3
                + (*( s + 7 ) - '0') * 2
                + (*( s + 8 ) - '0') * 1
                +  *( s + 9 ) - '0';
        if(!(res % 10))
        {
            printf("real\n");
        }
        else
        {
            printf("fake\n");
        }
    }
    return 0;
}

int alphabet2num(char c)
{
    int v[]= { 10, 11, 12, 13, 14, 15, 16, 17, 34, 18, 19, 20, 21, 22, 35, 23, 24, 25, 26, 27, 28, 29, 32, 30, 31, 33};
    /* A->0, ... , Z->25*/
    int i = c - 'A';
    return *(v + i);
}

a017: 五則運算

待補

#include <stdio.h>

a016: 數獨(SUDOKU)

看完痞子英雄完結篇後終於寫出來了XD

#include <stdio.h>

#define TRUE (1==1)  
#define FALSE (0==1)
#define ROW 9
#define COL ROW
#define BLOCKSIZE 3

int checkTable(int x[ROW][COL], int size, int checkcol);
int checkBlock(int x[ROW][COL], int rowstart, int rowlen, int colstart, int collen);

main() 
{
    while(1)
    {
        int x[ROW][COL];
        int i, j, k, l;
        for(i = 0; i < ROW; i++)
        {
            for(j = 0; j < COL; j++)
            {
                if((scanf("%d", &x[i][j])) == EOF)
                {
                    return 0;
                }                  
            }
        }      
        int flag;
        if(checkTable(x, ROW, 0) && checkTable(x, COL, 1))
        {
            flag = TRUE;
            k = 0;
            l = 0;
            for(i = 0; i < (ROW / BLOCKSIZE * COL / BLOCKSIZE); i++)
            {
                if(checkBlock(x, k, BLOCKSIZE, l, BLOCKSIZE))
                {
                    flag = TRUE;
                    k += BLOCKSIZE;
                    if((i + 1) % BLOCKSIZE == 0)
                    {
                        k = 0;
                        l += BLOCKSIZE;
                    }
                }
                else
                {
                    flag = FALSE;
                    break;
                }
            }
            if(flag)
            {
                printf("yes\n");    
            }
            else
            {
                printf("no\n");    
            }
        }
        else
        {
            printf("no\n");
        }
    }
    return 0;
}

checkTable(int x[ROW][COL], int size, int checkcol)
{
    int flag = TRUE;
    int i, j, n;
    int mask[size];
    for(i = 0; i < size; i++)
    {
        int k;
        for(k = 0; k < size; k++)
        {
            mask[k] = 0;
        }        
        for(j = 0; j < size; j++)
        {
            if(checkcol)
                n = x[j][i];
            else
                n = x[i][j];    /* check row */
            /*printf("%d", n);*/
            if(mask[n-1] == 0)
            {
                mask[n-1] = 1;
            }
        }
        for(k = 0; k < size; k++)
        {
            if(mask[k] == 0)
            {
                flag = FALSE;
            }
        }      
        /*printf("\n");*/
    }
    return flag;
}

int checkBlock(int x[ROW][COL], int rowstart, int rowlen, int colstart, int collen)
{
    int flag = TRUE;
    int i, j, n, k;
    int mask[ROW];
    for(k = 0; k < ROW; k++)
    {
        mask[k] = 0;
    }
    for(i = rowstart; i < rowstart + rowlen; i++)
    {
        for(j = colstart; j < colstart + collen; j++)
        {
            n = x[i][j];
            /*printf("%d ", n);*/
            if(mask[n-1] == 0)
            {
                mask[n-1] = 1;
            }            
        } 
        /*printf("\n");*/
    }
    for(k = 0; k < ROW; k++)
    {
        if(mask[k] == 0)
        {
            flag = FALSE;
        }
    }    
    return flag;
}

a015: 矩陣的翻轉

還有更快的方法嗎?

#include <stdio.h>

main() 
{
    int row, col;
    while(scanf("%d %d", &row, &col) != EOF)
    {
        int x[row][col];
        int i, j;
        for(i = 0; i < row; i++)
        {
            for(j = 0; j < col; j++)
            {
                scanf("%d", &x[i][j]);
            }
        }
        for(i = 0; i < col; i++)
        {
            for(j = 0; j < row; j++)
            {
                printf("%d ", x[j][i]);
            }
            printf("\n");
        }        
    }
    return 0;
}

a013: 羅馬數字

buggy QQ (底下的程式碼不會過…)

#include <stdio.h>

#define MAXLENGTH 1024

int getValue(char c);
char* getRome(int x, int k);
int rome2num(char *s);
char* num2rome(int x);

main() 
{   
    char x[MAXLENGTH], y[MAXLENGTH];
    while(scanf("%s %s", &x, &y) != EOF)
    {
        if(x == "#")
        {
            break;    
        }
        int i = rome2num(x);
        int j = rome2num(y);
        int ans = i - j > 0 ? i - j : j - i;
        /*printf("i:%d j:%d\n", i, j);*/
        printf("%s\n", num2rome(ans));
        /*printf("a: %d\n", ans);*/
    }
    return 0;
}

int getValue(char c)
{
    switch(c)
    {
        case 'I':
            return 1;
        case 'V':
            return 5;
        case 'X':
            return 10;
        case 'L':
            return 50;
        case 'C':
            return 100;
        case 'D':
            return 500;
        case 'M':
            return 1000;
        default:
            return 0;
    }
}

char* getRome(int x, int k)
{
    static char *r4[] = {"", "M", "MM", "MMM"};
    static char *r3[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    static char *r2[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    static char *r1[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    
    switch(k)
    {
        case 1:
            return r1[x];    
        case 2:
            return r2[x];
        case 3:
            return r3[x];
        case 4:
            return r4[x];
        default:
            return "OVERFLOW";
    }
}

int rome2num(char *s)
{
    int sum = 0;
    int c = 0;
    int v[MAXLENGTH];
    while(*s)
    {
        v[c] = getValue(*s++);
        c++;
    }
    int i;
    for(i = 0; i < c; i++)
    {
        if(v[i+1] > v[i])
        {
            sum -= v[i];    
        }
        else
        {
            sum += v[i];
        }
    }
    if(sum < 0)
        sum = sum*-1;
    return sum;
}

char* num2rome(int x)
{
    static char ans[MAXLENGTH];
    if(x == 0)
    {
        return "ZERO";
    }   
    if(x < 4000 && x > 0)
    {
        sprintf(ans, "%s%s%s%s", getRome(x / 1000, 4), getRome((x / 100) % 10, 3), getRome((x / 10) % 10, 2), getRome(x % 10, 1));
        return ans;
    }
    return "OVERFLOW";
}

a012: Hashmat的戰役

在 Dev-C++ 會跑出錯誤的答案…..真怪 @@

#include <stdio.h>

main() 
{   
    long long int i, j;
    while(scanf("%lld %lld", &i, &j) != EOF) 
    {
        printf("%lld\n", i - j > 0 ? i - j : j - i);
    }
    return 0;
}