ACM ICPC Team
思路：遍历
难度：Easy
#include<stdio.h>
int max_topics=0;
int result[500];
int main()
{
int T,N;
char ACM_Team[500][500];
scanf("%d%d",&T,&N);
for (int i = 0; i < T; i++)
{
getchar();
for (int j = 0; j < N; j++)
{
scanf("%c", &ACM_Team[i][j]);
}
}
for (int i = 0; i < T-1; i++)
for (int j = i+1; j < T; j++)
{
int topics = 0;
if (j == i)
continue;
for (int k = 0; k < N; k++)
{
if (ACM_Team[i][k] == '1' || ACM_Team[j][k] == '1')
topics++;
}
if (topics>max_topics)
max_topics = topics;
result[topics]++;
}
printf("%d\n%d\n", max_topics, result[max_topics]);
return 0;
}TaumB
思路：简单的比较，取小值就可（有极端数据，C的整形范围太小要溢出，int64 oj上编译过不了，double不会溢出了，但是丢失精度，纠结。。。最后只能找了段Python的代码）
难度：Easy
#!/usr/bin/py
if __name__ == '__main__':
t = input()
for _ in xrange(t):
b, w = map(int, raw_input().split())
x, y, z = map(int, raw_input().split())
print min(b*x, b*(y+z)) + min(w*(x+z), w*y)Sherlock and Squares
思路：求解两个方根之间有几个整数，注意边界的判断
难度：Easy
#include<stdio.h>
#include<math.h>
int Number[100];
int Full_Sqrt(int A, int B)
{
int a = ceil(sqrt((float)A));
int b = floor(sqrt((float)B));
if (a > b)
return 0;
else
{
return b - a+1;
}
}
int main()
{
int T, A, B;
scanf("%d",&T);
for (int i = 0; i < T; i++)
{
scanf("%d%d",&A,&B);
Number[i] = Full_Sqrt(A,B);
}
for (int i = 0; i < T; i++)
{
printf("%d\n",Number[i]);
}
return 0;
}Sherlock and GCD
思路：找数组有无一个最大公约数,且数组里有1的时候可直接确认为YES
难度：Easy
#include<stdio.h>
int arr[100];
int result[10];
int Mod(int a, int b)
{
int c=a%b;
while (c != 0)
{
a = b;
b = c;
c = a%b;
}
return b;
}
int GCD(int N)
{
if (N < 2)
return 0;
int temp=Mod(arr[0], arr[1]);
if (temp == 1)
return 1;
for (int i = 2; i < N; i++)
{
temp = Mod(arr[i], temp);
if (temp == 1)
return 1;
}
return 0;
}
int main()
{
int T, N;
scanf("%d",&T);
for (int i = 0; i < T; i++)
{
scanf("%d", &N);
for (int j=0; j < N; j++)
{
scanf("%d", &arr[j]);
}
result[i] = GCD(N);
}
for (int i = 0; i < T; i++)
if (result[i] == 1)
printf("YES\n");
else
printf("NO\n");
return 0;
}Sherlock and The Beast
思路：寻找数据是否满足此公式N=5x+3y 找到x和y后按照相应的位数输出一个最大整数值
难度：Easy
#include<stdio.h>
int result[20][2];
void Decent(int n, int i)
{
int temp = n;
if (n < 3)
result[i][0] = -1;
else
{
while (temp>0)
{
if (temp % 3 == 0)
break;
else
temp -= 5;
}
result[i][0] = temp;
result[i][1] = n - temp;
}
}
int main()
{
int T, Dec[20];
scanf("%d",&T);
for (int i = 0; i < T; i++)
{
scanf("%d",&Dec[i]);
Decent(Dec[i],i);
}
for (int i = 0; i < T; i++)
{
if (result[i][0] < 0)
printf("-1\n");
else
{
for (int j = 0; j < result[i][0]; j++)
{
printf("5");
}
for (int k = 0; k < result[i][1]; k++)
{
printf("3");
}
printf("\n");
}
}
return 0;
}Filling Jars
思路：又是纸老虎，记录个总数据再除以N就行（int会溢出，用long）
难度；Easy
#include<stdio.h>
int main()
{
long N, M;
long a, b, k, sum = 0;
scanf("%ld%ld",&N,&M);
for (int i = 0; i < M; i++)
{
scanf("%ld%ld%ld",&a,&b,&k);
sum += (b - a + 1)*k;
}
printf("%ld\n",sum/N);
return 0;
}Max Min
思路：查找数组内部方差最小的子集（子集大小需要输入），并输出子集的最大最小值的差。这题有数据，为了方便查找，需要提前排序，一般的排序会超时，这里使用C自带的快排。
难度：Moderate
#include<stdio.h>
#include<stdlib.h>
int comp(const void*a, const void*b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int N,K,Unfairness=99999999,temp;
int a[100000];
scanf("%d%d",&N,&K);
for (int i = 0; i < N; i++)
scanf("%d",&a[i]);
qsort(a, N, sizeof(int),comp);
for (int i = 0; i < N-K; i++)
{
temp = a[i+K-1]-a[i];
if (Unfairness> temp)
Unfairness = temp;
}
printf("%d\n",Unfairness);
return 0;
}Song of Pi
思路:思路真的没什么好说的，但是遇到个怪事：最初的代码的OJ测试结果和自己跑出来的不一样。。。可能是回车键缓存或者变量的不同？也或许是编译器的缘故？或者是C默认的字符串分割函数的问题？最后改成这样就过了
难度:Easy
#include<stdio.h>
#include<string.h>
int result[100];
int main()
{
int T, i , j ;
int Pi[29] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 3 };
char Song[500];
char YES[30] = "It's a pi song.", NO[30] = "It's not a pi song.";
scanf("%d", &T);
getchar();
for (i = 0; i < T; i++)
{
int k = 0,time = 0;
gets(Song);
for (int j = 0; j < strlen(Song); j++)
{
if (j == strlen(Song) - 1)
{
if (Pi[time] != (j - k+1))
{
result[i] = -1;
break;
}
}
if (Song[j] == ' ')
{
if (Pi[time] != (j - k) )
{
result[i] = -1;
break;
}
time++;
k = j+1;
}
}
}
for (i = 0; i < T; i++)
{
if (result[i]==0)
puts(YES);
else
puts(NO);
}
return 0;
}Identify Smith Numbers
思路：两个点：质因数的分解和位数分解（分解出整数的个十百千位等等），其中质因数分解采用Pollard Rho因数分解法（主要原理是从小到大每次挑一个数出来，看是否能与原数整除，这个方法很快也很简单，推荐使用），位数分解比较简单不作说明，注意输入的边界，如果是1，直接返回就行。
难度：Easy
#include<stdio.h>
int Digit_Sum(int n)
{
int sum = 0;
while (n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int main()
{
int n,i,j=0,sum,sum2=0;
int DIVISOR[100];
scanf("%d",&n);
if (n == 1)
{
printf("0\n");
return 0;
}
sum = Digit_Sum(n);
for (i = 2; i < n; i++)
{
while (n!=i)
if (n%i == 0){
DIVISOR[j++] = i;
n = n / i;
}
else
break;
}
DIVISOR[j++] = n;
for (i = 0; i < j; i++)
sum2 += Digit_Sum(DIVISOR[i]);
if (sum == sum2)
printf("1\n");
else
printf("0\n");
return 0;
}The Time in Words
思路：我觉的这道题难度标错了，太简单了
难度：Moderate
int main()
{
int hour,minute;
scanf("%d",&hour);
scanf("%d", &minute);
if (minute == 0)
printf("%s o' clock\n",word[hour]);
else
{
if (minute < 30)
{
if (minute == 15)
printf("quarter past %s", word[hour]);
else
printf("%s minutes past %s", word[minute], word[hour]);
}
else if (minute == 30)
printf("half past %s", word[hour]);
else
{
if (minute == 45)
printf("quarter to %s", word[hour+1]);
else
printf("%s minutes to %s", word[60-minute], word[hour+1]);
}
}
return 0;
}Modified Kaprekar Numbers
思路：换C++了，C语言对抗溢出我已经玩够了（貌似OJ不认识C的int64），还有注意没有结果要输出，INVALID RANGE，我就是这里没看见，下了数据才看见
难度：Easy
#include<iostream>
using namespace std;
int judge(long long i, long long length)
{
long long L, R, digit = length / 2, temp = (i*i);
if ((digit * 2) != length)
digit++;
for (long long i = 0; i < digit; i++)
temp /= 10;
L = temp;
for (long long i = 0; i < digit; i++)
temp *= 10;
R = (i*i) - temp;
if ((L + R) == i)
return i;
else
return -1;
}
int main()
{
long long p, q, j = 0, result[100000];
long long length=1,judge_length=10,temp;
cin >> p >> q;
while ((p*p) >= judge_length)
{
judge_length *= 10;
length++;
}
for (long long i = p; i <= q; i++)
{
if ((i*i) >= judge_length){
length++;
judge_length *= 10;
}
temp = judge(i, length);
if (temp != -1)
{
result[j] = temp;
j++;
}
}
if (j == 0)
{
printf("INVALID RANGE");
return 0;
}
for (long long i = 0; i < j; i++)
printf("%d ", result[i]);
return 0;
}Is Fibo
思路：一个循环和一个二分查找即可（PS：我差点记不住二分查找了）
难度：Easy
#include<iostream>
#include<string>
using namespace std;
string a = "IsFibo";
string b = "IsNotFibo";
int result[1000];
long long array[1000];
int IsFbi(long long N, int Right)
{
long long Left = 0;
long long Mid;
while (Left<=Right)
{
Mid = (Left + Right) / 2;
if (N == array[Mid])
return 1;
else if (N < array[Mid])
Right = Mid-1;
else
Left = Mid+1;
}
return 0;
}
int main()
{
long long fi,i=3,temp=1;
long long T, N;
array[1] = 1,array[2] = 1;
while (array[i - 1] <= 10000000000)
{
array[i] = array[i - 1] + array[i - 2];
i++;
}
cin >> T;
for (int k = 0; k < T; k++)
{
cin >> N;
if (IsFbi(N,i))
result[k] = 1;
}
for (int j = 0; j < T; j++)
{
if (result[j] == 1)
cout << a << endl;
else
cout << b << endl;
}
return 0;
}