ACM 10038 Jolly Jumpers

當n > 1，
用malloc分配n-1個空間，
0到n-2分別對應1到n-1。
對應要1對1剛剛好，不可少，不可多， 才符合jolly jumper。
這題一直RE，
最後不用free()就AC了，
偉哉ACM，不給free()。
真正在寫code，有malloc()就要有free()。
2011/10/13 update:
有一個地方free()會RE，
但其他地方可free()，真怪 orz。

/* ACM 10038 Jolly Jumpers
 * mythnc
 * 2012/03/31 21:03:04
 * run time: 0.008
 */
#include <stdio.h>
#include <stdlib.h>

typedef enum {FALSE = 0, TRUE} bool;

bool jolly(int);

int main(void)
{
    int n;

    while (scanf("%d", &n) != EOF) {
        if (n == 1) {
            scanf("%*d");
            printf("Jolly\n");
            continue;
        }
        if (jolly(--n))
            printf("Jolly\n");
        else
            printf("Not jolly\n");
    }
    return 0;
}

/* jolly: judge the sequence is jolly or not */
bool jolly(int interval)
{
    int i, x, next;
    bool *seq;

    seq = (bool *)malloc(sizeof(bool) * interval);
    for (i = 0; i < interval; i++)         /* initialize seq */
        seq[i] = FALSE;
    scanf("%d", &x);
    for (i = 0; i < interval; i++) {
        scanf("%d", &next);
        x = abs(x - next);
        /* x have to appear only once or not be a jolly jumper*/
        if (x > 0 && x <= interval && seq[x-1] == FALSE) {
            seq[x-1] = TRUE;
            x = next;
        }
        else {  /* eat remain input string */
            while (getchar() != '\n')
                ;
            /* free(seq); can not free or runtime error */
            return FALSE;
        }
    }
    for (i = 0; i < interval; i++)
        if (seq[i] == FALSE) {
            free(seq);
            return FALSE;
        }
    free(seq);
    return TRUE;
}

ACM 10035 Primary Arithmetic

取x跟y的個位數，相加，若進位，則carry數+1。
之後x與y各除以10，反覆之，到兩數除以10皆為0止。
需考慮99999 1的carry數。
carry數會影響下一個carry數的判斷，需注意。

/* ACM 10035
 * mythnc
 * 2u11/10/12 20:48:47   
 * run time = 0.02
 */
#include <stdio.h>

int carry(int, int);

int main(void)
{
    int x, y, n;

    while (scanf("%d %d", &x, &y) == 2) {
        if (x == 0 && y == 0)
            break;
        if ((n = carry(x, y)) == 1)
            printf("1 carry operation.\n");
        else if (n == 0)
            printf("No carry operation.\n");
        else
            printf("%d carry operations.\n", n);
    }
    return 0;
}

/* carry: calculate the carry times */
int carry(int x, int y)
{
    int n, c;

    c = n = 0;
    while (x != 0 || y != 0) {   /* same as !(x==0 && y==0) */
        if (x % 10 + y % 10 + c > 9) {
            n++;
            c = 1;
        }
        else
            c = 0;
        x /= 10;
        y /= 10;
    }
    return n;
}

ACM 10018 Reverse and Add

4,294,967,295為unsigned int的上限。
主要是reverse函數會寫，答案就出來了。
unsigned int好長一串，就用typedef了 -_-。

/* ACM 10018
 * mythnc
 * 2011/10/12 19:38:26
 * run time = 0.008
 */
#include <stdio.h>

#define MAXARY 15

typedef unsigned int number;

number reverse(number);

int main(void)
{
    int n, count;
    number x, y;

    scanf("%d", &n);
    while (n-- > 0) {
        scanf("%u", &x);
        count = 0;
        while (x != (y = reverse(x))) {
            x += y;
            count++;
        }
        printf("%d %u\n", count, x);
    }
    return 0;
}

/* reverse: reverse the digits of x */
number reverse(number x)
{
    number y;

    y = 0;
    do {
        y *= 10;
        y += x % 10;
        x /= 10;
    } while (x != 0);
    return y;
}

ACM 10008 What's Cryptanalysis?

還沒想到好的方法……
利用一個array[26]從0到25分別對應A(a)到Z(z)，
初始為0。
每次從stdin接收一個字母後，對應該字母的element + 1。
輸出時，從array[0]到array[25]找最大的element，
輸出之，輸出後把該element歸0。反覆，到所有elements為0為止。

/* ACM 10008
 * mythnc
 * 2011/10/13 09:10:55   
 * run time = 0.004
 */
#include <stdio.h>
#include <ctype.h>

int printout(int *s);

int main(void)
{
    int c;
    int alpha[26] = {0};

    scanf("%*d");
    while ((c = getchar()) != EOF)
        if (isupper(c))
            alpha[c - 'A']++;
        else if (islower(c))
            alpha[c - 'a']++;
    while (printout(alpha))
        ;
    return 0;
}

/* printout: print array s from high to low sequence */
int printout(int *s)
{
    int i, j, max;

    max = 0;
    for (i = 0; i < 26; i++)
        if (max < s[i]) {
            max = s[i];
            j = i;
        }
    if (max == 0)       /* if no letter have to be outputed */
        return 0;
    printf("%c %d\n", 'A' + j, max);
    s[j] = 0;
    return 1;
}

ACM 100 The 3n + 1 problem

直接做。 要小心i可能小於j的情況。

/* ACM 100 The 3n + 1 problem
 * mythnc
 * 2011/11/30 09:10:17
 * version 1.2
 * run time: 0.592
 */
#include <stdio.h>

int count(int);
int cal(int, int);

int main(void)
{
    int i, j;

    while (scanf("%d %d", &i, &j) == 2)
        printf("%d %d %d\n", i, j, j > i ? cal(i, j) : cal(j, i));

    return 0;
}

/* cal: find the big cycle len, and return it */
int cal(int small, int big)
{
    int i, max, tmp;

    for (max = 0, i = small; i <= big; i++) {
        tmp = count(i);
        if (max < tmp)
            max = tmp;
    }

    return max;
}

/* count: count the numbers of value n to 1 */
int count(int n)
{
    int c;

    for (c = 1; n != 1; c++)
        if(n % 2 == 0)
            n >>= 1;    /* n /= 2 */
        else 
            n = n * 3 + 1;

    return c;
}