SGU 127: Telephone directory

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=127

题目大意:

      一个同学要做一本电话簿,电话号码有四个数字组成,开头不含0和8,封面和说明用了2页,每页不能超过K个号码,每个新号码为第一个数字的要另起一页,每个号码按照递增顺序。给你n个号码,问最少需要用多少页纸。

解题思路:

     因为页码只跟每个开头数字的号码数量有关,比如1开头的号码有7个,每页最大号码数是5,那么1开头的号码要用2页,每个数字开头的都算出来,然后加上2页封面和说明就是答案。

解题代码:

#include<iostream>
#include<cstring>
using namespace std;
int s[10];
int main(){
	int k,n;
	while(cin>>k>>n){
		int t;
		memset(s,0,sizeof(s));
		while(n--){
			cin>>t;
			s[t/1000]++;
		}
		int sum=0;
		for(int i=1;i<10;i++){
			if(s[i]%k)
				sum+=s[i]/k+1;
			else
				sum+=s[i]/k;
		}
		sum+=2;
		cout<<sum<<endl;
	}
}

扩展知识:http://www.a0598.com/lifetool/main/areacode.htm

SGU 112:a^b-b^a

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=112

题目大意:

      输入a,b输出a^b-b^a的值。(1<=a,b<=100)

解题思路:

      肯定是用高精度算法,可是比较懒阿,先用JAVA写一个,然后C++的以后写吧。

解题代码:

import java.math.*;
import java.io.*;
import java.util.*;
public class Solution{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        int  a,b;
        while(cin.hasNext()){
            a=cin.nextInt();
            b=cin.nextInt();
            System.out.println(BigInteger.valueOf(a).pow(b).subtract(BigInteger.valueOf(b).pow(a)));
        }
    }
}

扩展知识:http://blog.csdn.net/soberman/archive/2009/03/10/3978074.aspx

SGU 113: Nearly prime numbers

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=113

题目大意:

      如果一个数可以分解成2个素数的乘积,那么就输出yes否则输出no.

解题思路:

      先筛选出素数,然后判断找到那个能整除这个数的素数,判断商是否为素数就行啦!起先题目给看错了以为是相邻的素数的积。

解题代码:

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define Max 50000
bool isprime[Max];
int prime[Max];
int cp;
void mkprime(){
	cp=1;
	memset(isprime,true,Max);
	prime[0]=2;
	for(int i=2;i<Max;i++){
		if(isprime[i]==true){
			prime[cp++]=i;
			for(int j=1;i*j<Max;j++)
				isprime[i*j]=false;
		}
	}
}
bool isp(int n){
	if(n==1) return false;
	if(((n!=2)&&!(n%2))||((n!=3)&&!(n%3))||
	   ((n!=5)&&!(n%5))||((n!=7)&&!(n%7)))
			return false;
	int t=sqrt(n);
	for(int i=2;i<t;i++)
		if(n%i==0)
			return false;
	return true;
}
int main(){
	mkprime();
	int cas;
	cin>>cas;
	while(cas--){
		int n;
		cin>>n;
		int flag=0;
		for(int i=0;i<cp;i++){
			if(n%prime[i]==0)
				if(isp(n/prime[i])){
						flag=1;
						break;
				}
		}
		if(flag)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Primality_test

SGU 107: 987654321 problem

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=107

题目大意:

      求出多少个N位数的平方末尾是987654321。

解题思路:

      因为末尾多少是跟后几位相乘有关的,所以先试探一些值,9位以下都没有解,9位有8个,10位有8*9个,递推下去11位以上就是8*9*(n-10)个。因为n的范围是10^6,所以用公式不能算,会溢出,这里用了一个小技巧,因为后面都是0,所以算10位后面就直接输出输出72然后加上(n-10)个0。

解题代码:

#include<iostream>
using namespace std;

int main(){
	int n;
	cin>>n;
	if(n<9)
		cout<<0<<endl;
	else if(n==9)
		cout<<8<<endl;
	else if(n==10)
		cout<<72<<endl;
	else{
		cout<<72;
		for(int i=1;i<=n-10;i++)
			cout<<0;
		cout<<endl;
	}
	return 0;
}

扩展知识:http://blog.csdn.net/ZERO2046/archive/2007/05/20/1618507.aspx

SGU 184: Patties

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=184

题目大意:

      一个人喜欢办Party,家里有3种东西,知道要举办一个party每种东西需要的量,问家里的东西能过举办几场party.

解题思路:

      分别求出每种东西能办几场,最小的值就是答案。

解题代码:

#include<iostream>
using namespace std;
int main(){
	int p,m,c,k,r,v;
	while(cin>>p>>m>>c>>k>>r>>v){
		int a=p/k,b=m/r,d=c/v;
		int n=a;
		if(n>b) n=b;
		if(n>d) n=d;
		cout<<n<<endl;
	}
	return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Vegetable

SGU 135: Drawing Lines

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=135

题目大意:

     n条直线能把平面分成最多几个空间。

解题思路:

      可以推出f(n)=f(n-1)+n;然后扩展得到$$f(n)=\frac{n*(n+1)}{2}+1$$.

解题代码:

#include<iostream>
using namespace std;
int main(){
	long long n;
	cin>>n;
	cout<<(n*(n+1)/2+1)<<endl;
	return 0;
}

扩展知识:http://mathworld.wolfram.com/CircleDivisionbyLines.html