Uva 623 500!

#uva 623 #500!

題目來源：https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCMQFjABahUKEwj8_sWTt-XIAhXGGJQKHfQQBaY&url=https%3A%2F%2Fuva.onlinejudge.org%2Findex.php%3Foption%3Donlinejudge%26page%3Dshow_problem%26problem%3D564&usg=AFQjCNFKlOvVQ16qrVLkY6rPajXogo_Ydw&sig2=9n3XYj69Yzfy7Ilyi0noXQ

題意：1~1000！

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	#include<cstdlib>
	#include<string>
	#include<sstream>
	#include<fstream>
	#include<cmath>
	using namespace std;
	typedef long long int L_int;
	int p1[2001][1200],carry[1200];
	int main(){
	int tag1,n;
	memset(p1,0,sizeof(p1));
	memset(carry,0,sizeof(carry));
	tag1 = 1;
	p1[1][0] = 1;
	p1[0][0] = 1;
	p1[0][1199] = 1;
	for(int i=1;i<=1000;i++){
	int j;
	for(j=0;j<tag1;j++){
	p1[i][j]=p1[i][j]*i;
	p1[i][j]+=carry[j];
	carry[j+1] = p1[i][j]/1000;
	p1[i][j]%=1000;
	}
	p1[i][j]=carry[j];
	if(carry[tag1]) tag1++;
	p1[i][1199] = tag1;
	//memcpy(p1[i+1],p1[i],sizeof(p1[i]));
	for(int ll=0;ll<tag1;ll++)
	p1[i+1][ll] = p1[i][ll];
	memset(carry,0,sizeof(carry));
	}
	while(~scanf("%d",&n)){
	printf("%d!\n%d",n,p1[n][p1[n][1199]-1]);
	for(int i = p1[n][1199]-2;i>=0;i--){
	for(int h = 0;h<2-(int)log10(p1[n][i]);h++)
	printf("0");
	if(!p1[n][i]) cout<<"00";
	cout<<p1[n][i];
	}
	cout<<"\n";
	}
	}

view raw uva623.cpp hosted with ❤ by GitHub

Uva 495 Fibonacci Freeze

#uva 495  # Fibonacci Freeze
題目來源： https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0CCsQFjACahUKEwjIovKBteXIAhXKG5QKHQRBDyE&url=https%3A%2F%2Fuva.onlinejudge.org%2Findex.php%3Foption%3Dcom_onlinejudge%26Itemid%3D8%26page%3Dshow_problem%26problem%3D436&usg=AFQjCNHrnRFwsT4S7PfjJC0SMNVOhCniLg&sig2=4cde6Qx6bZLXPk83HzGT-A


題意：大數的費式數列，用C寫


程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	#include<cstdlib>
	#include<string>
	#include<sstream>
	#include<fstream>
	using namespace std;
	typedef long long int L_int;
	L_int p1[100],p2[100],temp[100];
	string s[5001] = {""};
	char h[100];
	int main(){
	int tag1,n=5000;
	s[0] = "0";
	s[1] = "1";
	s[2] = "1";
	ofstream fout("005.txt");
	memset(p1,0,sizeof(p1));
	memset(p2,0,sizeof(p2));
	memset(temp,0,sizeof(temp));
	tag1 = 1;
	p1[0] = 1;
	p2[0] = 1;
	for(int i=0;i<n-2;i++){
	memcpy(temp,p1,sizeof(p1));
	for(int j=0;j<tag1;j++){
	p1[j]=p1[j]+p2[j];
	p1[j+1] += p1[j]/1000000000000;
	p1[j]%=1000000000000;
	}
	memcpy(p2,temp,sizeof(temp));
	if(p1[tag1]) tag1++;
	for(int m=tag1-1;m>=0;m--){
	sprintf(h,"%lld",p1[m]);
	if(strlen(h)<12&&m!=tag1-1)
	for(int ii = 0;ii<12-strlen(h);ii++)
	s[i+3]+="0";
	s[i+3]+=h;
	}
	}
	//for(n = 0;n<=5000;n++){
	while(scanf("%d",&n)==1){
	printf("The Fibonacci number for %d is ",n);
	cout<<s[n];
	cout<<"\n";
	}
	}

view raw uva 495.cpp hosted with ❤ by GitHub

#想睡了~~~期待真愛營 =)

Uva 10023 Square Root [java]

#uva10023  #Square Root 

題目來源：https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB0QFjAAahUKEwjW39alsuXIAhWFJZQKHdgtBKM&url=https%3A%2F%2Fuva.onlinejudge.org%2Findex.php%3Foption%3Dcom_onlinejudge%26Itemid%3D8%26page%3Dshow_problem%26problem%3D964&usg=AFQjCNEdusCFKiTWW21XfH1OuCHDocq1fg&sig2=R2tOaN_fMySbYllJPVYpaQ

解法：利用Binary Search

程式碼：

	import java.io.*;
	import java.util.*;
	import java.math.*;
	public class Main{
	Scanner scan = new Scanner(System.in);
	static final BigInteger two = new BigInteger("2");
	static final BigInteger one = new BigInteger("1");
	public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int N = scanner.nextInt();
	while(N-- >0){
	BigInteger y = scanner.nextBigInteger();
	BigInteger upper = y.divide(two) ,lower = one ,k;
	while(upper.compareTo(lower) >0){
	//System.out.println("upper " +upper+" lower "+ lower );
	k = (upper.add(lower)).divide(two);
	if(y.divide(k).compareTo(k)>0) lower = k.add(one);
	else upper = k;
	}
	//temp = y.divide(2);
	System.out.println(lower);
	if (N > 0)
	System.out.println();
	}
	}
	}

view raw uva 10023.java hosted with ❤ by GitHub

#原來工讀金申請表沒簽名，難怪薪水一直沒下來QAQ

#今天的臨時小打工好開心喔 ，一個心花怒放，而且看到自己設計的海報被貼在牆上，成就感UP UP

Uva 756 Biorhythms

#uva 756 #Biorhythms

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=697

題意：中國餘數定理的裸題，

INPUT=>a b c d 

OUTPUT=> ans

其中  (ans+d)%23==a，(ans+d)%28==b，，(ans+d)%33==c

胡言亂語：因此可以先求出(ans+d)在-d就是答案了！

這題簡單來說就是中國餘數定理(點我)，帶入公式就是答案的 =)

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cmath>
	#include<cstdlib>
	using namespace std;
	int GCD(int p,int q){
	while(p%=q)
	swap(p,q);
	return q;
	}
	int LCM(int a, int b) {
	if(a<b) swap(a,b);
	return a*b/GCD(a, b);
	}
	int test(int K2, int K) {
	int temp = K2;
	while (true) {
	if (K2 % K == 1) break;
	else
	K2 += temp;
	}
	return K2;
	}
	int main(){
	int Biorhythms = 23*28*33 ,k = 0,a ,b, c ,d,ans;
	int aa = test(28*33,23);
	int cc = test(23*28,33);
	int bb = test(23*33,28);
	while(scanf("%d %d %d %d",&a,&b,&c,&d)==4){
	k++;
	if(a==-1 and b==-1 and c==-1 and d==-1) break;
	ans = (aa*a+bb*b+cc*c-d+Biorhythms)%Biorhythms;
	if(!ans) ans = Biorhythms;
	printf("Case %d: the next triple peak occurs in %d days.\n",k,ans);
	}
	}

view raw Uva 756.cpp hosted with ❤ by GitHub

有點想睡...但好像原本要讀計組的說@@

Uva 10125 Sumsets

#uva 10125 #Sumsets

題目來源：http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1066

題意：第一個數字是N，表示接下來的序列會有幾個數字需要計算，當N等於0，就可以結束程式；需要判斷序列中是否有四個數字符合 a+b+c = d，並輸出最大的d

計算流程：

(1) 這題直接跑迴圈會過

(2) a+b+c=d --> a+b = d-c
我先計算 所有 d-c 的數，再計算a+b
最後比對是否有a+b==d-c

如果有，接著判斷a b c d 有無重複

程式碼：

Uva 10008 What's Cryptanalysis?

#uva 10008 #What's Cryptanalysis?

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=12&page=show_problem&problem=949


題意：計算字母出現的次數

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	#include<algorithm>
	using namespace std;
	struct P{
	int times;//次數
	char ch;//代表字母
	};
	int comp(const P x,const P y){
	if(x.times==y.times)//若次數相等，依字母排序
	return x.ch<y.ch;
	return x.times>y.times;//出現次數多的排前面
	}
	int main(){
	char ch,str[10000];
	int N;
	P a[27];
	for(int i=0;i<26;i++){
	a[i].times = 0;
	a[i].ch = i+65;
	}//先做初始化
	scanf("%d\n",&N);
	while(N--){
	cin.getline(str,10000);
	for(int i=0;i<strlen(str);i++)
	if(isalpha(str[i])){//判斷是不是英文字母
	if(islower(str[i])) str[i]-=32;//如果是小寫則轉成大寫
	a[(int)str[i]-65].times++;//次數+1
	}
	}
	sort(a,a+26,comp);//排序
	for(int i=0;i<26,a[i].times>0;i++)//按照次數輸出，但沒出現過的不用輸出
	cout<<a[i].ch<<" "<<a[i].times<<endl;
	}

view raw uva 10008.cpp hosted with ❤ by GitHub

Uva 175 Keywords

#uva175
題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=111

題意：

P：間距 、Keywords_1、Keywords_2.....、Keywords_n

T：各種標題!@#$%^^&*((()

將文章T中的單字倆倆配一對，若兩個Keywords中間所格的字母<=P給的間距，則符合並輸出T的編號

胡言亂語：

程式碼：

	#include<iostream>
	#include<cstring>
	#include<map>
	#include<cstdlib>
	#include<string>
	#include<cstdio>
	using namespace std;
	typedef pair<string,string> P;
	map<P ,int> table[50];
	map<P ,int>::iterator it;
	int store[500] ,store2[500] ;
	bool find_keywords(P key,int i,int j){
	it = table[i].find(key);
	if(it!=table[i].end() && it->second >= j) return true;
	else return false;
	}
	string ss[251];
	void save(int k,int u,int x){
	P store_keywords;
	for(int i=0;i<k-1;i++){
	for(int j=i+1;j<k;j++){
	store_keywords = make_pair(ss[i],ss[j]);
	table[u][store_keywords] = x;
	store_keywords = make_pair(ss[j],ss[i]);
	table[u][store_keywords] = x;
	}
	}
	}
	int main(){
	//x->threshold ;u->the number of P ;t->the number of T
	int x,u = 0,t = 0,t1,k ;
	char ch;
	//store_T->store TXT of T ;str->T組成單字使用
	string store_T[251][1000],str;
	//make_pair of keywords
	P store_keywords;
	while(scanf("%c: ",&ch))//P or T
	{
	if(ch=='P'){
	u++;k = 0;
	table[u].clear();
	scanf("%d ",&x);//threshold
	store[u] = x;//將p的最大threshold存起來
	char *p, str1[5000] ;
	cin.getline(str1,5000);
	p = strtok(str1, " ");
	while (p != NULL) {
	ss[k] = p;
	k++;
	p = strtok(NULL, " ");
	}
	save(k,u,x);
	}
	if(ch=='T'){
	t++;t1 = 0;
	str = "";
	while(cin.get(ch)){
	if(ch>=97&&ch<=97+26)
	str=str+ch;
	if(ch>=65&&ch<=(65+26)){
	ch+=32;
	str=str+ch;
	}
	if(ch==32||ch=='\t') {
	if(str=="") continue;
	t1++;
	store_T[t][t1] = str;
	str = "";
	}
	if(ch=='|'){
	if(str=="") break;
	t1++;
	store_T[t][t1] = str;
	break;
	}
	}
	store2[t] = t1;
	}
	if(ch=='#')
	break;
	}
	bool flag,flag2;
	//從P1開始找配對
	for(int i=1;i<=u;i++){
	//從T下手
	flag = false;
	printf("%d: ",i);
	for(int j=1;j<=t;j++){
	//倆倆配一組
	flag2 = false;
	for(int m=0;m<=store[i];m++){
	for(int n=1;(n+m+1)<=store2[j];n++){
	store_keywords = make_pair(store_T[j][n],store_T[j][n+m+1]);
	if(find_keywords(store_keywords,i,m)){
	flag2=true;
	}
	}
	}
	if(flag2){
	if(flag) printf(",%d",j);
	else {flag = true;printf("%d",j);}
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw uva 175.cpp hosted with ❤ by GitHub

Uva 10341 Solve It

#uva 10341
題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1282

胡言亂語：f( )這個函數是個遞減數列

程式碼：

	#include<cstdio>
	#include<cmath>
	int p,q,r,s,t,u;
	double f(double x){
	return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u ;
	}
	int main(){
	double upper,lower,k;
	while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)==6){
	upper = 1.0;
	lower = 0.0;
	int N = 100;
	while(N--){
	k = (upper+lower)/2;
	if(f(k)>0)
	lower = k;
	else
	upper = k;
	}
	if(fabs(f(k))>1e-10)
	printf("No solution\n");
	else
	printf("%.4f\n",k);
	}
	}

view raw uva 10341.cpp hosted with ❤ by GitHub

Uva 714 Copying Books

#uva 714 #binary search

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=655

題意：先給有N筆測資，以前的書是手抄的，現在有k本書和m位工人，希望你寫出一個程式，讓每位工人分到的頁數是相近的，且每位工人都要分到，若有多組解，以index較大的工人，頁數較多，並以 ' / ' 分隔，輸出答案於一行。

胡言亂語：

一開始以為要排序，就將book依頁數由小排到大，但最後發現根本不用XD。

這題使用的方法是Binary Search，演算法如下：

	while(upper_bound>lower_bound){
	//從上限和下限中間取中間值 u
	//u表示每個工人最多可分到的頁數
	u = (upper_bound+lower_bound)/2;
	//計算k本書是否可以剛剛好分成m份
	if(不行)
	then range：u~ upper_bound
	else
	then range：lower_bound ~u
	}

view raw .cpp hosted with ❤ by GitHub

當upper_bound<lower_bound的時候就可以跳出迴圈(loop)，一開始是想說找到了，就可以跳出來，但發現有時候找到的非最小值，所以要持續找到最小值才正確

而最後輸出的部分，因為題目要求若有多組解，後面工人的頁數盡量多一點，別想太複雜，從後面分配輸出就好了XD，思考一下，最後用的stack，因為可以從後面開始存，最後pop掉就好：

	for(int i=0 ;i<m ;i++){
	tag = u;//剛剛找到的臨界值
	//j>=(m-i-1)表示書要大於等於工人數
	//因為每個人都要拿到書
	while(tag>0&&j>=(m-i-1)){
	tag-=book[j];
	if(tag>=0) {str.push(book[j]);j--;}
	}
	str.push(-1);//打入tag，等等output的時候
	//如果讀到'-1'則輸出 ' / '
	}

view raw .cpp hosted with ❤ by GitHub

[補]stack的用法：

	#include<stack>
	//宣告stack ：str
	stack <int> str;
	//stack是先入後出
	//有點像是在疊書，最後放的書可以最先拿起來
	str.pop();//把stack的書拿起來
	str.push();//將書疊到stack中
	int x = str.top();//x = stack最上面那本書

view raw .cpp hosted with ❤ by GitHub

程式碼：

	#include<cstdio>
	#include<stack>
	#include<iostream>
	#include<algorithm>
	using namespace std;
	stack <long long int> str;
	int main(){
	long long int m,N,k,upper,lower,u;
	long long int book[502];
	scanf("%lld",&N);
	while(N--){
	scanf("%lld %lld",&k,&m);
	upper = 0;
	lower = 0;
	for(int i=0;i<k;i++){
	scanf("%lld",&book[i]);
	upper += book[i];
	}
	long long int tag,j;
	while(upper>lower){
	u = (upper+lower)/2;
	j = 0;
	for(int i=0 ;i<m ;i++){
	tag = u;
	while(tag>0){
	tag-=book[j];
	if(tag>0) j++;
	}
	}
	if(j<k) lower = u+1;
	else upper = u;
	}
	j = k-1;
	for(int i=0 ;i<m ;i++){
	tag = u;
	while(tag>0&&j>=(m-i-1)){
	tag-=book[j];
	if(tag>=0) {str.push(book[j]);j--;}
	}
	str.push(-1);
	}
	str.pop();
	while(str.size()){
	if(str.top()>=0) printf("%lld",str.top());
	else printf("/");
	str.pop();
	if(str.size()) printf(" ");
	}
	printf("\n");
	}
	}

view raw uva 714.cpp hosted with ❤ by GitHub