// Run time: 0.010
#include <stdio.h>
#include <string.h>
int find(int *num, int len);
int calculate(int *num, int len, int base);
int main()
{
char str1[100], str2[100];
int arr1[100], arr2[100];
int len1, len2;
int i; // base1
int j; // base2
int x, y;
int m1, m2;
while (scanf("%s%s", str1, str2) == 2)
{
len1 = strlen(str1);
len2 = strlen(str2);
for ( i = 0; i < len1; i++)
{
if (str1[i] >= '0' && str1[i] <= '9')
arr1[i] = int(str1[i])-48;
else
arr1[i] = str1[i]- 'A' + 10;
}
for ( i = 0; i < len2; i++)
{
if (str2[i] >= '0' && str2[i] <= '9')
arr2[i] = int(str2[i])-48;
else
arr2[i] = str2[i] - 'A' + 10;
}
m1 = find(arr1, len1);
m2 = find(arr2, len2);
// printf("m1: %d, m2: %d\n", m1, m2);
bool state = false;
for ( i = m1; i <= 36; i++)
{
for ( j = m2; j <= 36; j++)
{
x = calculate(arr1, len1, i);
y = calculate(arr2, len2, j);
if (x < y)
break;
else
if (x == y)
{
state = true;
break;
}
}
if (state)
break;
}
if (!state) // no one can equal
printf("%s is not equal to %s in any base 2..36\n", str1, str2);
else
printf("%s (base %d) = %s (base %d)\n", str1, i, str2, j);
}
return 0;
}
int find(int *num, int len)
{
if (len == 1 && (num[0] == 0 || num[0] == 1))
return 2;
int i;
int max = num[0];
for ( i = 1; i < len; i++)
{
if (num[i] > max)
max = num[i];
}
return max+1;
}
int calculate(int *num, int len, int base)
{
int i;
int sum = 0;
int weight = 1;
for ( i = len-1; i >= 0; i--)
{
sum += num[i]*weight;
weight *= base;
}
return sum;
}
2009年2月13日 星期五
Q343: What Base Is This ?
Q679: Dropping Balls
/*
這題要用 binary 來想
假設 level = 4, times 可能 1~8 但會減1 就是 0~7
times binary system position
位數
012
0 1000 + 000 8+0
1 1000 + 100 8+4
2 1000 + 010 8+2
3 1000 + 110 8+6
4 1000 + 001 8+1
5 1000 + 101 8+5
6 1000 + 011 8+3
7 1000 + 111 8+7
Run time: 0.090
*/
#include <stdio.h>
int main()
{
int n;
int level;
int times;
int i;
int pos;
int weight;
scanf("%d", &n);
while (n--)
{
scanf("%d%d", &level, ×);
// 0 to 2^(level-1)-1 讓次數介於這個範圍
// 就可以用 binary 來表示了
times--;
// 要算 leaf 的第一個 node
// 同時也代表最後一層有幾個node
pos = 1;
for ( i = 0; i < level-1; i++)
pos *= 2;
// 用 level-1個 bits
// 因為node 編號最多也才 pos + pos - 1
bool arr[level-1];
// assign the bits to be zero
for ( i = 0; i < level-1; i++)
arr[i]= false;
// calculate the times to binary
for ( i = 0; i < level-1; i++)
{
arr[i] = times%2;
times /= 2;
}
// calculate the position
weight = 1;
for ( i = level-2; i >= 0; i--)
{
pos += weight*arr[i];
weight *= 2;
}
printf("%d\n", pos);
}
}
Q686: Goldbach's Conjecture(II)
/*
這題和 Q543類似
只是要算有幾個解
所以只要算到 N/2 即可(要相異解)
但注意 n = 4 = 2+2
這是和Q543不一樣的地方
n的限制是從4到32767
Run time: 0.000
*/
#include <stdio.h>
#define N 32768
int main()
{
int n;
int i, j;
bool arr[N+1];
for ( i = 3; i < N; i+=2)
arr[i] = true;
for ( i = 3; i*i < N; i+=2)
if (arr[i])
for ( j = 3*i; j < N; j+=i)
if (arr[j])
arr[j] = false;
while (scanf("%d", &n))
{
if (!n) break;
int cnt = 0;
if (n == 4)
{
printf("1\n");
continue;
}
for ( i = 3; i <= n/2; i+=2)
{
if (arr[i])
{
j = n-i;
if (arr[j])
cnt++;
}
}
printf("%d\n", cnt);
}
}
Q661: Blowing Fuses
// Run time: 0.000
#include <stdio.h>
#define N 20
int arr[N];
bool state[N];
int main()
{
int n; // how many electric
int m; // time's? open or close
int c; // capacity
int i; // for loop's count
int sum; // total
int tmp; // using for scanf
int max; // maximum
int count = 0; // which sequence?
bool blown; // blown or not
while (scanf("%d%d%d", &n, &m, &c))
{
if (!n && !m && !c) break;
// n台電器的電流，而且初始都是關著
for ( i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
state[i] = false;
}
max = 0;
sum = 0;
blown = false;
for ( i = 0; i < m; i++)
{
scanf("%d", &tmp);
// 原本是open
if (state[tmp-1])
{
sum -= arr[tmp-1];
state[tmp-1] = false;
}
// 原本是close
else
{
sum += arr[tmp-1];
if (sum > c)
blown = true;
if (max < sum)
max = sum;
state[tmp-1] = true;
}
}
printf("Sequence %d\n", ++count);
if (blown)
printf("Fuse was blown.\n\n");
else
{
printf("Fuse was not blown.\n");
printf("Maximal power consumption was %d amperes.\n\n", max);
}
}
return 0;
}
2009年2月12日 星期四
Q612: DNA Sorting
// Run time: 0.110
#include <stdio.h>
typedef struct {
char str[51];
int cnt;
int sort;
} string;
string DNA[100];
int calculate(char *str, int len);
void print(string *s, int n);
int main()
{
int num;
int len, n;
int i, j;
scanf("%d", &num);
while (num--)
{
scanf("%d%d\n", &len, &n);
// DNA string input
for ( i = 0; i < n; i++)
{
gets(DNA[i].str);
DNA[i].sort = i;
}
// calculate the length of each DNA's string
for ( i = 0; i < n; i++)
DNA[i].cnt = calculate(DNA[i].str, len);
if (n != 1)
print(DNA, n);
// if only one input
else
printf("%s\n", DNA[0].str);
if (num)
printf("\n");
}
return 0;
}
int calculate(char *str, int len)
{
int i, j;
int cnt = 0;
for ( i = 0; i < len-1; i++)
for ( j = i+1; j < len; j++)
if (str[i] > str[j])
cnt++;
return cnt;
}
void print(string *s, int n)
{
int i, j;
int index;
int count = 0;
int min;
bool state[n];
for ( i = 0; i < n; i++)
state[i] = true;
for (;;)
{
for ( i = 0; i < n; i++)
if (state[i])
break;
min = s[i].cnt;
index = i;
state[i] = false;
for ( j = 0; j < n; j++)
{
if (min > s[j].cnt && state[j])
{
// 如果發現更小的，要把之前的 state 還原成true
state[index] = true;
min = s[j].cnt;
state[j] = false;
index = j;
}
}
printf("%s\n", s[index].str);
if (++count == n)
return;
}
}
Q587: There's treasure everywhere!
/*
這題要注意誤差，因為double會有誤差
Run time: 0.010
*/
#include <stdio.h>
#include <stdlib.h> // atoi(str) 要用
#include <string.h> // strlen(str), strcmp(str)要用
#include <ctype.h> // isdigit(ch) 判斷是否為數字用的
#include <math.h> // sqrt(2.0) 和 EPS 要用
#define EPS pow(10, -9) // 誤差要用的, double容易有誤差
#define sqrt2 sqrt(2.0)
char str[201];
int main()
{
int i;
int len;
double move;
double x, y;
int cnt = 0;
while (gets(str))
{
if (!strcmp(str, "END")) break;
len = strlen(str);
x = y = 0.0;
for (i = 0; i < len; i++)
{
move = atoi(str+i); // 取出數字
while (isdigit(str[i])) // 跳過數字到非數字
i++;
// N, E, S, W 四種方向其中之一
if (str[i+1] == ',' || str[i+1] == '.')
{
switch (str[i])
{
case 'N': y += move; break;
case 'E': x += move; break;
case 'S': y -= move; break;
case 'W': x -= move; break;
}
i++;
}
// NE, NW, SE, SW 四種方向其中之一
else
{
// 座標要取cos(PI/4), sin(PI/4)
move /= sqrt2;
switch (str[i])
{
case 'N':
x += (str[i+1] == 'E') ? move : -move;
y += move;
break;
case 'S':
x += (str[i+1] == 'E') ? move : -move;
y -= move; break;
}
i+=2;
}
}
printf("Map #%d\n", ++cnt);
printf("The treasure is located at (%.3lf,%.3lf).\n", EPS+x, EPS+y);
printf("The distance to the treasure is %.3lf.\n\n", EPS+sqrt(x*x+y*y));
}
}
Q576: Hiaku Review
// Run time: 0.000
#include <stdio.h>
#include <string.h>
bool test(char ch);
bool check(int turn, int cnt);
char str[201];
int main()
{
int len;
int cnt;
int i, j;
while (gets(str))
{
if (!strcmp("e/o/i", str)) break;
len = strlen(str);
cnt = 0;
bool state = false;
for ( i = 0, j = 1; i < len; i++)
{
if (str[i] == '/')
{
if (check(j, cnt))
{
cnt = 0;
j++;
state = false;
continue;
}
else
{
printf("%d\n", j);
break;
}
}
if (test(str[i]) && !state)
{
state = true;
cnt++;
}
else
if (!test(str[i]))
state = false;
}
if (i == len)
{
if (check(j, cnt)) printf("Y\n");
else printf("3\n");
}
}
return 0;
}
bool test(char ch)
{
if (ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'||ch=='y')
return true;
else
return false;
}
bool check(int turn, int cnt)
{
if (turn == 1)
{
if (cnt == 5)
return true;
else
return false;
}
else
if (turn == 2)
{
if (cnt == 7)
return true;
else
return false;
}
else
if (turn == 3)
{
if (cnt == 5)
return true;
else
return false;
}
}
Q573: The Snail
/*
注意:蝸牛不會爬負的，只有晚上會滑下去一個高度
Run time: 0.000
*/
#include <stdio.h>
int main()
{
double H, init, down, factor;
double slide;
double sum;
double last;
int day;
while (scanf("%lf%lf%lf%lf", &H, &init, &down, &factor))
{
if (!H) break;
day = 1;
sum = init;
slide = init*(factor/100);
last = init;
while (true)
{
// morning
if (sum > H)
{
printf("success on day %d\n", day);
break;
}
// night
sum -= down;
if (sum < 0)
{
printf("failure on day %d\n", day);
break;
}
day++;
sum += last-slide;
if (slide != init)
last = last-slide;
}
}
return 0;
}
Q568: Just the Facts
// Run time: 0.010
#include <stdio.h>
int main()
{
int n;
int i;
long long int prod;
while (scanf("%d", &n) != EOF)
{
prod = 1;
for ( i = 2; i <= n; i++)
{
prod *= i;
while (!(prod%10)) prod /= 10;
prod %= 100000;
}
printf("%5d -> %lld\n", n, prod%10);
}
return 0;
}
2009年2月11日 星期三
Q555: Bridge Hands
/*
用gets(str)才會對
用scanf("%c%c", &a, &b);會Time limit exceeded
Run time: 0.060
*/
#include <stdio.h>
#define N 0
#define E 1
#define S 2
#define W 3
typedef struct {
int dir;
char suit;
char rank;
} Card;
Card card[52];
int arr[4][13];
void assign(Card p);
int index(char ch);
void print(int turn);
char reverse(int index);
int main()
{
char ch;
int i, j;
int aspect;
while (1)
{
scanf("%c\n", &ch);
if (ch == '#') return 0;
if (ch == 'N')
aspect = N;
else
if (ch == 'E')
aspect = E;
else
if (ch == 'S')
aspect = S;
else
aspect = W;
char str[53];
gets(str);
for ( i = 0, j = 0; i < 52; i+=2)
{
card[j].suit = str[i];
card[j].rank = str[i+1];
card[j].dir = (aspect+j+1)%4;
j++;
}
gets(str);
for ( i = 0; i < 52; i+=2)
{
card[j].suit = str[i];
card[j].rank = str[i+1];
card[j].dir = (aspect+j+1)%4;
j++;
}
for ( i = 0; i < 52; i++)
assign(card[i]);
printf("S:"); print(S); printf("\n");
printf("W:"); print(W); printf("\n");
printf("N:"); print(N); printf("\n");
printf("E:"); print(E); printf("\n");
}
return 0;
}
void assign(Card p)
{
int x = index(p.rank);
if (p.suit == 'C')
arr[0][x] = p.dir;
else
if (p.suit == 'D')
arr[1][x] = p.dir;
else
if (p.suit == 'S')
arr[2][x] = p.dir;
else
if (p.suit == 'H')
arr[3][x] = p.dir;
}
int index(char ch)
{
if (ch >= '2' && ch <= '9')
return ch-'0'-2;
if (ch == 'T')
return 8;
if (ch == 'J')
return 9;
if (ch == 'Q')
return 10;
if (ch == 'K')
return 11;
if (ch == 'A')
return 12;
}
void print(int turn)
{
int i, j;
for ( i = 0; i < 4; i++)
for ( j = 0; j < 13; j++)
if (arr[i][j] == turn)
{
if (i == 0)
printf(" C");
else
if (i == 1)
printf(" D");
else
if (i == 2)
printf(" S");
else
if (i == 3)
printf(" H");
printf("%c", reverse(j));
}
}
char reverse(int index)
{
if (index >= 0 && index <= 7) return index+'2';
if (index == 8) return 'T';
if (index == 9) return 'J';
if (index == 10) return 'Q';
if (index == 11) return 'K';
if (index == 12) return 'A';
}
2009年2月10日 星期二
Q543: Goldbach's Conjecture
/*
先算完全部，算質數的方法：用篩的(sieve)
不用管even部分，因為這裡已經把質數除了2以外都是odd
Run time: 0.090
*/
#include <stdio.h>
#define N 1000000
int main()
{
int n;
int i, j;
bool arr[N+1];
for ( i = 3; i < N; i+=2)
arr[i] = true;
for ( i = 3; i*i < N; i+=2)
if (arr[i])
for ( j = 3*i; j < N; j+=i)
if (arr[j])
arr[j] = false;
while (scanf("%d", &n))
{
if (!n) break;
bool s = false;
for ( i = 3; i <= n/2; i+=2)
{
if (arr[i])
{
j = n-i;
if (arr[j])
{
printf("%d = %d + %d\n", n, i, j);
s = true;
break;
}
}
}
if (!s)
printf("Goldbach's conjecture is wrong\n");
}
}
Q530: Binomial Showdown
// Run time: 0.000
#include <stdio.h>
void combination(int N, int M);
int main()
{
int N, M;
while (true)
{
scanf("%d%d", &N, &M);
if (!N && !M) break;
if (M > N/2)
M = N - M;
combination(N, M);
}
return 0;
}
void combination(int N, int M)
{
int i;
double prod = 1;
for ( i = 0; i < M; i++)
prod *= double(N--)/double(i+1);
printf("%.0lf\n", prod);
}
Q516: Prime Land
// Run time: 0.320
#include <stdio.h>
void trans(int n);
bool isprime(int n);
int arr[15];
// 因為最大數為32767，所以平方根只要到181就可以了
int p[42]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
149,151,157,163,167,173,179,181};
int main()
{
int i, j;
int num;
int root;
int prod;
while (scanf("%d", &root))
{
if (!root) break;
arr[0] = root;
for ( i = 1; ; i++)
{
scanf("%d", &arr[i]);
if (getchar() == '\n')
break;
}
num = ++i;
prod = 1;
for ( i = 0; i < num; i += 2)
for ( j = 0; j < arr[i+1]; j++)
prod *= arr[i];
prod--; // 減1
trans(prod);
}
return 0;
}
void trans(int n)
{
if (isprime(n))
{
printf("%d 1\n", n);
return;
}
int i, j;
int cnt;
bool state = false;
for ( i = n/2; i >= 2; i--)
{
if (!(n%i) && isprime(i))
{
cnt = 0;
while (true)
{
if (!(n%i))
{
cnt++;
n /= i;
}
else
{
if (state)
printf(" %d %d", i, cnt);
else
{
printf("%d %d", i, cnt);
state = true;
}
break;
}
}
}
}
printf("\n");
}
bool isprime(int n)
{
int i;
for ( i = 0; p[i]*p[i] <= n; i++)
if (!(n%p[i]))
return false;
return true;
}
Q498: Polly the Polynomial
// Run time: 0.530
#include <stdio.h>
#define N 1000
int arr[N];
void calculate(int x, int num);
int main()
{
int i;
int num;
int x;
while (true)
{
for ( i = 0; ; i++)
{
if (scanf("%d", &arr[i]) != EOF)
{
if (getchar() == '\n')
break;
}
else
return 0;
}
num = i; // <=
while (true)
{
if (scanf("%d", &x) != EOF)
{
calculate(x, num);
if (getchar() == '\n')
{
putchar('\n');
break;
}
else
putchar(' ');
}
}
}
return 0;
}
void calculate(int x, int num)
{
int i, j;
int sum = 0;
int product;
int weight = num;
for ( i = 0; i <= num; i++)
{
product = 1;
for ( j = 0; j < weight; j++)
product *= x;
sum += arr[i]*product;
weight--;
}
printf("%d", sum);
}
2009年2月9日 星期一
Q492: Pig-Latin
// Run time: 0.090
#include <stdio.h>
#include <ctype.h>
bool test(char ch);
int main()
{
int i, j;
char ch;
char root;
bool s;
while (true)
{
i = 0;
while (true)
{
ch = getchar();
if (ch == EOF)
return 0;
if (isalpha(ch)) // 如果是字母的話
{
if (!i) // 是一個單字的第一個字母
{
s = test(ch);
if (s)
printf("%c", ch);
else
root = ch;
i++;
}
else
printf("%c", ch);
}
else // 如果不是字母的話
{
if (!i)
{
printf("%c", ch);
break;
}
if (s)
printf("ay%c", ch);
else
printf("%cay%c", root, ch);
break;
}
}
}
return 0;
}
bool test(char ch)
{
if (ch == 'A' || ch == 'a')
return true;
if (ch == 'E' || ch == 'e')
return true;
if (ch == 'I' || ch == 'i')
return true;
if (ch == 'O' || ch == 'o')
return true;
if (ch == 'U' || ch == 'u')
return true;
return false;
}
2009年2月8日 星期日
Q490: Rotating Sentences
/*
輸入最後一行需加上 Ctrl + Z
Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#define N 100
char arr[N+1][N+1];
int len[N+1];
int main()
{
int i, j;
int max = 0;
int level;
for ( i = 0; ; i++)
if (gets(arr[i]) == NULL)
break;
else
{
len[i] = strlen(arr[i]);
if (max < len[i])
max = len[i];
}
level = i;
for (i = 0; i < max; i++)
{
for ( j = level-1; j >= 0; j--)
{
if (arr[j][i] != '\0')
printf("%c", arr[j][i]);
else
printf(" ");
}
printf("\n");
}
return 0;
}
Q484:The Department of Redundancy Department
/*
輸入最後一行需加上 Ctrl + Z
Run time: 0.070
*/
#include <stdio.h>
#define N 10000
int arr[N];
int sum[N];
int main()
{
int kind = 0;
int i, j;
int num;
while (scanf("%d", &num) == 1)
{
for ( i = 0; i < kind; i++)
{
// 開始搜尋是否有符合的種類
// 如果找到的話就加一
if (arr[i] == num)
{
sum[i]++;
break;
}
}
// 表示每個種類都找過了，但都沒找到，所以種類要新增一個
if (i == kind)
{
kind++;
arr[i] = num;
sum[i] = 1;
}
}
for ( i = 0; i < kind; i++)
printf("%d %d\n", arr[i], sum[i]);
}
Q483: Word Scramble
// Run time: 0.010
#include <stdio.h>
#include <string.h>
#define N 1000
char str[N];
int main()
{
int i;
int len;
while (true)
{
while (true)
{
if (scanf("%s", str) == EOF) return 0;
len = strlen(str);
for ( i = len-1; i >= 0; i--)
printf("%c", str[i]);
if (getchar() == '\n')
break;
putchar(' ');
}
printf("\n");
}
}
Q482: Permutation Arrays
/*
pos[2] = 0 pos[0] = 1 pos[1] = 2
arr[0] = 32.0 arr[1] = 54.7 arr[2] = -2
先印 1 所對到的 再印2 再印3
=> arr[pos[0]] -> arr[pos[1]] -> arr[pos[2]]
Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#define N 1000
int pos[N];
char arr[N][N];
int main()
{
int n;
int i;
int tmp;
int cnt;
bool state = true;
scanf("%d\n", &n);
while (n--)
{
if (!state) printf("\n");
state = false;
cnt = 0;
while (true)
{
scanf("%d", &tmp);
pos[tmp-1] = cnt++;
if (getchar() == '\n') // 當讀到尾巴
break;
}
for ( i = 0; i < cnt; i++)
scanf("%s", arr[i]);
for ( i = 0; i < cnt; i++)
printf("%s\n", arr[pos[i]]);
}
}
訂閱：
文章 (Atom)