2015年11月7日星期六

Uva 10602 Editor Nottoobad

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

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<string>
	using namespace std;
	int main(){
	int N,n,i,j,sum;//N->有幾筆測資，n->每筆測資有幾個數
	scanf("%d",&N);
	string st[1001],temp;
	while(N--){
	scanf("%d",&n);
	for(i=0;i<n;i++)
	cin>>st[i];
	sort(st,st+n);//依字典順序排序
	temp = st[0];
	sum = st[0].size();
	for(i=1;i<n;i++){
	for(j=0;j<temp.size();j++)
	if(st[i][j]!=temp[j]) break;
	sum+=(st[i].size()-j);
	temp = st[i];
	}
	cout<<sum<<endl;//輸出答案
	for(i=0;i<n;i++)
	cout<<st[i]<<endl;
	}
	}

view raw uva 10602.cpp hosted with ❤ by GitHub

2015年10月28日星期三

#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

2015年10月21日星期三

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 = 232833 ,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 = (aaa+bbb+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

2015年10月9日星期五

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 pexp(-x) + qsin(x) + rcos(x) + stan(x) + txx + 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

2015年10月5日星期一

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

2015年9月30日星期三

Uva 10371 Time Zones

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

題意：

題目開頭先給你時區的簡稱，Input ：time 時區1 時區2

Output：將在時區1的time 換算成在時區2的time 並輸出

胡言亂語：

這題，卡在12小時制時間的換算超久QAQ

而函式的用法和#uva 860差不多XD

可以點進去看就好，先附上debug兩天...的程式碼~~~

...最後竟然是我把720打成780....

	#include<iostream>
	#include<cstring>
	#include<cstdio>
	#include<cstdlib>
	#include<iomanip>
	#include<map>
	using namespace std;

	map <string,double> table;

	void init(){
	table["UTC"] = 0 , table["GMT"] = 0;
	table["BST"] = 1 , table["IST"] = 1;
	table["WET"] = 0 , table["WEST"] = 1;
	table["CET"] = 1 , table["CEST"] = 2;
	table["EET"] = 2 , table["EEST"] = 3;
	table["MSK"] = 3 , table["MSD"] = 4;
	table["AST"] = -4 , table["ADT"] = -3;
	table["NST"] = -3.5 , table["NDT"] = -2.5;
	table["EST"] = -5, table["EDT"] = -4;
	table["CST"] = -6, table["CDT"] = -5;
	table["MST"] = -7, table["MDT"] = -6;
	table["PST"] = -8, table["PDT"] = -7;
	table["HST"] = -10, table["AKST"] = -9;
	table["AKDT"] = -8 , table["AEST"] = 10;
	table["AEDT"] = 11 , table["ACST"] = 9.5;
	table["ACDT"] = 10.5 , table["AWST"] = 8;
	}


	int main(){
	init();//建表

	int N,time,short_hand,long_hand;//時針、分針
	string st,local,outside;//a.m/p.m、當地時間、外地時間
	int tag;



	scanf("%d",&N);//讀入有幾筆測資
	cin.get();//讀掉換行字元
	while(N--){
	tag = 0;
	char *p, str1[100] ;
	cin.getline(str1,100);
	p = strtok(str1, " :");
	while (p != NULL) {
	tag++;
	if(tag==1){
	if(isdigit(*p)) short_hand = atof(p);
	else {
	tag = 3;
	if(!strcmp(p,"noon")) time = 12*60;
	if(!strcmp(p,"midnight")) time = 0;
	}
	}
	else if(tag==2) long_hand = atof(p);
	else if(tag==3) {
	time = long_hand+ short_hand*60;
	if(time>=720&&time<780) time-=720;
	if(!strcmp(p,"p.m.")) {
	time+=720;
	}

	}
	else if(tag==4) local = p;
	else if(tag==5) outside = p;
	p = strtok(NULL, " :");
	}

	time =time+ (table[outside]-table[local])60+2460;

	time %=1440;//因為time可能為負
	short_hand = (time/60)%24;
	long_hand = time%60;
	//printf("%d ",time);
	if(time == 0)
	printf("midnight\n");
	else if(time == 720)
	printf("noon\n");
	else{
	cout<<(time/60%12?time/60%12:12)<<":"<<setw(2)<<setfill('0')<<(time%60)<<" ";
	cout<<(time>720?"p.m.":"a.m.")<<endl;

	}


	}

	}

view raw tet.cpp hosted with ❤ by GitHub

Uva 860 Entropy Text Analyzer

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

題意：

這題在luckycat沒有翻譯..有點難過，畢竟英文真的沒有很好。

first,他會先輸入一篇文章，你要按照公式，分別輸出他的單字總數、ET、Erel。

胡言亂語：

//記得當時我問同學題意時，它們都說：你帶公式就好啦，但我就是不懂公式的意思咩=3=

作法講起來真的蠻簡單的

首先你要會將句子中的單字擷取出來，所以會用到strtok( )這個函式，他的用法是：

	//開始分解str1,遇到, .:;!?()\"這些符號則分割成P
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	cout<<p<<endl;//輸出p

	//從剛剛還沒切玩的地方繼續切
	p = strtok(NULL, ", .:;!?()\"");
	}

view raw tet.cpp hosted with ❤ by GitHub

這樣就可以將單字取出來了！

//但要注意str1是 char[]喔~是cstring (char string)才可以使用=)

//比較兩個cstring是否相同可以使用strcmp(str1,str2)，相同回傳0，不同回傳非零數字~

取出來後就可以順便計算其出現頻率。因此就用到map了！

剛認識map時，覺得他的感覺很像hash(雜湊)，你的key會對應到一個抽屜，你可以在抽屜內放數字進去。因此在這邊，我們把剛剛取出的單字p當成key，把它出現頻率放到對應的抽屜裡：

	#include<map>
	using namespace std;

	map <string,int> tree;//key是string 抽屜裡放的是int
	map <string,int>::iterator it;

	//用法：
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	con++;
	if(p[0]<97) p[0]+=32;//單字要全小寫
	words=p;//將char[]->string
	it = tree.find(words);//尋找key對應到的抽屜
	if(it==tree.end()) tree[words] = 1;//沒找到
	else tree[words]++;//找到，代表前面有出現過
	p = strtok(NULL, ", .:;!?()\"");
	}

view raw tet.cpp hosted with ❤ by GitHub

最後再將答案計算並輸出就好 ^_____^

//n表示有幾種單字，爛瘩表示總共有幾個單字。

程式碼：

	#include<cstdio>
	#include<iostream>
	#include<cstring>
	#include<map>
	#include<cmath>
	using namespace std;

	map <string,int> tree;
	map <string,int>::iterator it;

	//計算並輸出
	void printf_out(int con){
	double ET = 0;
	for(it = tree.begin();it!=tree.end();it++)
	ET += it->second*(log10(con)-log10(it->second));

	ET/=con;
	printf("%d %.1lf %.0lf\n",con,ET,(ET/log10(con))*100);

	}

	int main(){
	string words;
	int con = 0;//計算總共有己的單字
	char *p, str1[100005] ;
	tree.clear();//清空map
	while(cin.getline(str1,100005)){
	if(!strcmp(str1,"**END_OF_INPUT**"))
	break;
	if(!strcmp(str1,"**END_OF_TEXT**")){
	printf_out(con);
	tree.clear();
	con = 0;
	}

	else{
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	con++;
	if(p[0]<97) p[0]+=32;
	words=p;
	it = tree.find(words);
	if(it==tree.end()) tree[words] = 1;//沒找到
	else tree[words]++;
	p = strtok(NULL, ", .:;!?()\"");
	}
	}
	}
	}

view raw tet.cpp hosted with ❤ by GitHub

2015年9月23日星期三

UVa10221 Satellites

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

胡言亂語：

找弧長和弦長的公式找好久喔 ... 再次要在code book加上新東西了XD

這題我犯的錯誤是，忘記輸出小數點後6位，輸出小數的話用printf 比較好寫

double x;

printf("%.nlf",x);

這樣就可以輸出小數點後n位了。=)

程式碼：

	#include<iostream>
	#include<cmath>
	#include<cstdio>
	using namespace std;
	int main(){
	double s,a;
	string str;
	while(cin>>s>>a>>str){
	if(str[0]=='m') a/=60;
	if(a>180) a=360-a;
	s+=6440;
	printf("%.6lf %.6lf\n",aacos(-1.0)/180.0s,2.0ssin(a*acos(-1.0)/180.0/2.0));

	}
	}

view raw 001.cpp hosted with ❤ by GitHub

Uva 478 Points in Figures: Rectangles, Circles, Triangles

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

胡言亂語：

這題原本我亂看題目，所以有重寫一次...

題目要求輸出一圖形順序，我以為先輸出完矩形、在圓形、在三角形...

因此思考了一下，要怎麼樣存圖形比較方便。分別設三個array存不一樣的圖形是笨方法。最後：

struct Point{

double x,y;

};

struct graph{

char ch; //判斷是什麼圖形

Point a,b,c;

double radius;

}P[11];

多設的變數可以不用理他，像是圓形就只需用到Point a，b,c根本用不到，但沒關係

這樣只要從P[1]~P[i]比較是否在圖形內就好

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cstdlib>
	#include<cmath>
	using namespace std;
	int sum;//計算測試點數量
	bool tag;//標記是否已有在圖形內

	//存點
	struct Point{
	double x,y;
	};

	//存圖形
	struct graph{
	char ch;
	Point a,b,c;
	double radius;
	}P[11];

	//計算三角形面積
	double get_area(Point a, Point b, Point c) {
	return fabs(0.5 * ((c.y-a.y)(b.x-a.x) - (b.y-a.y)(c.x-a.x)));
	}

	//判斷是否為矩形內
	void Test_rectangles(Point t,int i){
	if(t.x>P[i].a.x&&t.x<P[i].b.x&&t.y<P[i].a.y&&t.y>P[i].b.y){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	//判斷是否為圓形內
	void Test_circles(Point t,int i){
	if(sqrt((t.x-P[i].a.x)(t.x-P[i].a.x)+(t.y-P[i].a.y)(t.y-P[i].a.y))-P[i].radius<0.00001){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	//判斷是否在三角形內
	void Test_triangles(Point t,int i){
	if(get_area(t,P[i].b,P[i].c)+get_area(P[i].a,t,P[i].c)+get_area(P[i].a,P[i].b,t)
	-get_area(P[i].a,P[i].b,P[i].c)<0.00001){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	int main(){
	char ch1;//讀數圖形的圖案
	sum = 0;//計算點數量
	int m=0;//計算圖形數量
	while(cin>>ch1){
	m++;
	P[m].ch = ch1;
	if(ch1=='*') break;
	switch(ch1){
	case 'r':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].b.x>>P[m].b.y;
	break;
	}
	case 'c':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].radius;
	break;
	}
	case 't':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].b.x>>P[m].b.y>>P[m].c.x>>P[m].c.y;
	break;
	}
	}
	}

	Point point;
	while(cin>>point.x>>point.y){
	tag=true;
	sum++;//計算測試點數量
	if(point.x==9999.9&&point.y==9999.9) break;

	for(int i=1;i<=m;i++){
	switch(P[i].ch){
	case 't':{
	Test_triangles(point,i);
	break;
	}
	case 'c':{
	Test_circles(point,i);
	break;
	}
	case 'r':{
	Test_rectangles(point,i);
	break;
	}
	}
	}

	if(tag)
	printf("Point %d is not contained in any figure\n",sum);
	}
	}

view raw uva_191.cpp hosted with ❤ by GitHub

Uva 191 Intersection

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

胡言亂語：

剛看到這一題的時候，就想說，可能先要判斷線段和矩形的四個邊有沒有交點，在來判斷線段是否在矩形內，但想一想，會不會更簡單啊？？

突然想到，那把線段切成很多小點，判斷每個點是否在矩形內不就好了？

線段方程式：ax+by = c ==>千萬不要用這個，因為這樣就會有三個變數

y = ax+b ==>這樣只剩兩個變數而已

因此我已x為變化基準，計算x' = x+0.5為間距的點是否在矩形內，但這樣WA了。

測了一下，發現兩個錯誤

(1) 若為垂直線則無斜率，需要另外處理

(2) x' = x+0.1 之前間距(0.5)太大，會有漏掉的點

修改後終於AC了 ^___^

程式碼：

	#include<iostream>
	#include<algorithm>
	#include<cstdio>
	#include<cstdlib>
	using namespace std;

	struct Point {
	double x,y;
	};

	Point p1,p2;//設定矩形的左下和右下

	double a,b;//存入線段方程式的係數

	//判斷是否為矩形內
	//float不可能完全相同，有一定的誤差在
	bool Test_rectangles(Point t){
	if(t.x>p1.x-0.00001 && t.x<p2.x+0.00001 && t.y<p2.y+0.00001 && t.y>p1.y-0.0001)
	return true;
	else return false;
	}

	//計算線段的方程式
	void get_polynominal(Point m,Point n){
	a = (m.y-n.y)/(m.x-n.x);
	b = m.y-(a*m.x);
	}


	int main(){
	int N;
	bool tag;
	double u;
	scanf("%d",&N);
	Point line_point1,linr_point2,temp;
	while(N--){
	tag = false;
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&line_point1.x,&line_point1.y,&linr_point2.x,&linr_point2.y,&p1.x,&p1.y,&p2.x,&p2.y);
	//p1代表左下 p2代表右上
	if(p1.x>p2.x) swap(p1.x,p2.x);
	if(p1.y>p2.y) swap(p1.y,p2.y);

	//若為垂直線的情況，因為垂直線無斜率
	if(line_point1.x==linr_point2.x){
	if(line_point1.y>linr_point2.y) swap(line_point1.y,linr_point2.y);
	for(double i=line_point1.y;i<=linr_point2.y+0.0001;i+=0.003){
	temp.x = line_point1.x;
	temp.y = i;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}
	if(!tag) printf("F\n");
	continue;
	}

	//非垂直線情況
	if(line_point1.x> linr_point2.x) {
	temp = line_point1 ;
	line_point1 = linr_point2;
	linr_point2 = temp;
	}

	//取得斜率和係數 y=ax+b
	get_polynominal(line_point1,linr_point2);

	//注意：抓的點的密度要夠，不然會有誤差
	for(double i=line_point1.x;i<=linr_point2.x+0.0001;i+=0.05){
	temp.x = i;
	temp.y = a*i+b;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}

	if(!tag) printf("F\n");
	}
	}

view raw uva_191.cpp hosted with ❤ by GitHub

2015年8月1日星期六

UVa 10776 Determine The Combination

題目來源 : https://uva.onlinejudge.org/index.php

2015年7月29日星期三

Uva 10101 Bangla Numbers

題目來源 : https://uva.onlinejudge.org/external/101/p10101.pdf

http://zerojudge.tw/ShowProblem?problemid=a741[高中生解題系統]

2015年7月28日星期二

ITSA 桂冠賽 [Problem B4-易] Polynomials

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?a=11958

[Problem B4-易] Polynomials

成績: 0 / 倒扣: 0.8

Time Limit: 1 second
Problem Description

● English
Given a product (ax² + bx + c)^d, write a program to compute the coefficients of the resulting polynomial. For example, if (a, b, c, d) = (1, 2, 3, 2), we have (x² + 2x + 3)² = x⁴ + 4x³ + 10x² + 12x + 9 and your program outputs the coefficients 1, 4, 10, 12 and 9. In this problem, a, b, c, d are all integers and d is at most three.
● Chinese
給定一個多項式乘積形式如下 : (ax² + bx + c)^d ，本題的工作是要算出多項式乘積展開後的各項係數。例如，給定 (a, b, c, d) = (1, 2, 3, 2) ，則 (x² + 2x + 3)² = x ⁴+ 4x³ + 10x² + 12x + 9 ，你的程式需要輸出係數 1, 4, 10, 12 和 9 。在這個問題裏，每個所給的數字皆為整數，而且 d 不會超過 3 。

Technical Specification

● English

All the given numbers are integers.

The range of each number is as follows:

-100 ≤ a ≤ 100 and a ≠ 0

-100 ≤ b ≤ 100

-100 ≤ c ≤ 100

1 ≤ d ≤ 3

● Chinese

每個所給的數字皆為整數

每個數的限制範圍如下 :

-100 ≤ a ≤ 100 且 a ≠ 0

-100 ≤ b ≤ 100

-100 ≤ c ≤ 100

1 ≤ d ≤ 3

Input Format

● English
The first line is an integer which indicates the number of test cases. Each test case consists of four integers a, b, c, d, separated by spaces, in a line.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試資料都用一行四個整數 a , b, c, d 來表示，整數之間以一個以上的空格分開。

Output Format

● English
For each test case, output the coefficients of (ax² + bx + c)^d in a line by the descending power of x , separated by spaces.
● Chinese
針對每一筆測試資料，依降冪順序輸出多項式的係數。兩筆資料之間以一個斷行隔開，兩係數之間以一個空格隔開。

Example

Sample Input:	Sample Output:
4 1 2 3 2 1 10 100 1 10 0 10 3 20 0 -1 2	1 4 10 12 9 1 10 100 1000 0 3000 0 3000 0 1000 400 0 -40 0 1

解法 : 想不到更簡單的方法~"~，因為題目表示d不超過3 ，所以我就用的暴力法....分開解
如果d==1則直接輸出，d==2則係數相乘一次，d==3則再乘一次

2015年7月27日星期一

ITSA 桂冠賽 [Problem B7-中] The Maximum Bottleneck Spanning Tree

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23652

[Problem B7-中] The Maximum Bottleneck Spanning Tree

成績: 0 / 倒扣: 0.8

Time Limit: 3 second
Problem Description

● English
Let G = (V, E) be a graph to denote a communication network, in which the nodes represent sites that want to communicate. Each edge eis a communication link with a given available bandwidth b(e). For each pair of nodes u, v, we want to select a single u-v path P on which the pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the values of b(P).
It is very complicated to keep track of a path for each pair of nodes. Thus, we want to find a spanning tree T of G such that for every pair of nodes u, v, the unique u-v path in the tree can attain the best achievable bottleneck rate for u, v in G. Please write a program to construct a spanning tree T in which, for each u, v in V, the bottleneck rate of the u-v path in T is as large as possible among all possible spanning trees.
● Chinese
令 G = (V, E) 為一個圖形代表通訊網路，其中點代表通訊站，而邊代表連結二站的通訊線，每一個邊 e 皆設有一個頻寬 b (e) 表示此通訊線的最高傳輸量。任二點 u , v, 我們可以選擇一條 u -v 路徑 P ，這條路徑的瓶頸 b (P) 定義為這條路徑所有邊中的最小頻寬， u 和 v 的最佳連結路徑為所有 u -v 路徑中具有最大瓶頸的路徑。
對任意二點都紀錄其最佳連結路徑是很複雜的工作，因此我們想要找出一個生成樹，使得 u 和 v 在此生成樹的唯一路徑具有最佳的瓶頸值。請撰寫一個程式找出一個生成樹 T ，使得 T 中的任意 u -v 路徑的瓶頸在所有生成樹中是最佳的。

Technical Specification

● English

All the given numbers are integers and there is no sign.

● Chinese

每個所給數字皆為整數且無正負符號

Input Format

● English
The first line is an integer which indicates the number of test cases. Each test case contains m+1 lines defining an n-node graph. The first line consists of two integers. The first integer is n, 1 ≤ n ≤ 1000, which is the number of nodes in the graph. The nodes are given by their unique labels which are integers from 0 to n-1. The second integer is m, n ≤ m ≤ n(n-1)/2, which is the number of edges in the graph. For the next m lines, each line consists of three numbers x, y, and b((x,y)) separated by a space indicating the edge (x, y) and the bandwidth of (x,y).
● Chinese
第一列是一個整數代表測試資料有幾筆。每一筆測試資料包含 m +1 列定義一個圖形，第一列是二個數字 n 和 m ，第一個數字 n 表示此圖的節點數， 1 ≤ n ≤ 1000 ，每一個節點用一個數字唯一代表， n 個點的編號由 0 到 n -1 ，第二個數字 m 表示此圖的邊數， n ≤ m ≤ n(n-1)/2 ，剩下的 m 列標示此圖的邊，每一列都含三個數字以空白隔開，分別是 x ， y 和 b ((x,y)) 代表一個邊 (x, y) 和它的頻寬 b ((x,y)) 。

Output Format

● English
For each test case, output the sum of each b(e) for e in the spanning tree T in one line.
● Chinese
針對每一筆測試資料，輸出此生成樹所有邊的頻寬和。

Example

Sample Input: Sample Output:

2
5 7
0 1 3
1 2 1
1 3 8
2 3 10
2 4 5
3 4 9
4 0 6
8 12
0 2 9
0 4 4
1 2 3
1 5 6
2 3 5
2 4 8
3 4 3
3 5 7
5 7 4
5 6 1
6 4 3
6 7 4 33
43

這題是Maximum Spanning Tree的問題，只是他要找的是阻抗值最大的cost，可以使用Kruskal 演算法來完成，判斷cycle的方法是用Disjaint Set。

ITSA 桂冠賽 [Problem B3-易] Unique elements

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23648

[Problem B3-易] Unique elements

成績: 0 / 倒扣: 0.8

Time Limit: 1 second
Problem Description

● English
Given a sequence of integers, please find the unique elements those occur only once in the sequence.
● Chinese
給定一個整數數列，請找出數列中單獨的元素，也就是只出現一次的整數。

Technical Specification

● English

The number of integers in the sequence is n, where 1 ≤ n ≤ 1000.

The integers in the sequence are 32-bit integers.

● Chinese

數列中整數的個數為 n ， 1 ≤ n ≤ 1000 。

數列中的整數是 32 位元整數。

Input Format

● English
The input contains several test cases. Each test case contains two lines: the first line is an integer n which indicates the number of integers in the sequence; the second line contains a sequence of n integers, and consecutive integers are separated by a blank.
● Chinese
輸入包含若干測資，每筆測資包含兩行資料：第一行是一個整數 n 代表數列中有 n 個整數；第二行則是包含 n 個整數的數列，相鄰整數間以空格隔開。

Output Format

● English
For each test case, output the unique elements in increasing order in one line, and consecutive numbers are separated by a blank. If there is no unique element, output “N/A”.
● Chinese
針對每一筆測試資料，由小至大輸出單獨元素在一行中，相鄰數字間以空格隔開。如果沒有單獨元素，則輸出 “N/A” 。

Example

Sample Input:	Sample Output:
8 1 1 1 9 9 2 2 2 5 1 2 3 4 5 10 8 7 7 1 0 0 9 2 2 6	N/A 1 2 3 4 5 1 6 8 9

[註]這題是找出數列中唯一出現一次的數，因此可以設一個array，計算數出現的頻率，並將頻率為1的值輸出

ITSA 桂冠賽 [Problem B2-易] 各位數和的排序

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23647

[Problem B2-易] 各位數和的排序

成績: 0 / 倒扣: 0.8

Time Limit: 1 second
Problem Description

● English
The digit sum of a number, say 9122, is just the sum of the digits, 9+1+2+2=14.
Given N positive integers, sort these N integers in ascending order of their digit sums. In the case that two integers have the same digit sum, the smaller integer should appear before the larger one. For example, both 3128 and 9122 have the same digit sum (i.e., 14). As 3128 < 9122, 3128 should appear before 9122.
● Chinese
對於任意一個整數 a ，令 a.digitSum 為 a 每個位數的和 (the digit sum of the number a) 。例如 a =9122 ，則 a.digitSum =9+1+2+2=14 。
給你 N 個整數，請依每個整數的 digit sum 由小到大排序這 N 個整數。若兩個整數的 digit sum 是一樣的，那便依整數的值由小到大排序。
舉例而言，令 9122 ， 3128 ，以及 5112 是給定的 3 個整數（即 N =3 ）。 9122.digitSum=14 ， 3128.digitSum=14 ，且 5112.digitSum=9 。所以你要輸出 5112 、 3128 、 9122 。在這個例子中， 3128 的 digit sum 和 9122 的 digit sum 都是 14 ，但因為 3128<9122 ，所以 3128 要排在 9122 的前面。
Technical Specification

● English

2 ≤ N ≤ 10

All the given numbers are positive integers.

The number of digits in a given number is from 3 to 7.

The number of test cases is 5.

● Chinese

2 ≤ N ≤ 10

每個所給數字皆為整數且無正負符號

每個數字的位數是 3 到 7

共有 5 個測資

Input Format

● English
The first line is an integer which indicates the number of test cases. Each test case consists of two lines.
This first line of a test case is an integer indicates N. The second line of the test case contains N integers delimited by a space.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試包含了 2 行。
第一行是一個整數，其代表 N 。
第二行包含了 N 個整數，每個整數用空白隔開
Output Format

● English
For each test case, sort N integers based on the rule mentioned in the problem description section. You should separate the output integers by a space.
● Chinese
針對每一筆測試資料，依問題描述一節所說的規則來排序。在排序的串列中，每個整數請以空白隔開。
Example

Sample Input: Sample Output:

5
3
9122 3128 5112
4
1725 3821 2011 1428
4
1925 2011 3210 9215
4
4145 1245 1485 1478
7
5584 12635 7894 12365 98453 56487 2134567 5112 3128 9122
2011 3821 1428 1725
2011 3210 1925 9215
1245 4145 1485 1478
12365 12635 5584 7894 2134567 98453 56487

ITSA 桂冠賽 [Problem B1-易] Square and Cube

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23646

[Problem B1-易] Square and Cube

成績: 0 / 倒扣: 0.8

Time Limit: 1 second
Problem Description

● English
Ali is a primary school student and is learning multiplication of integers. He has a homework assignment asking for calculate the squares and cubes of integers. You are asked to write a program to verify the answers of his math homework.
● Chinese
阿里是一位正在學習整數乘法的小學生。他有一個算整數平方與立方的作業。本題要求你寫一程式來驗證他的答案。

Technical Specification

● English

All the given numbers are integers and there is no sign.

The range of numbers is from 1 to 100.

● Chinese

每個所給數字皆為整數且無正負符號
每個數字的大小是 1 到 100

Input Format

● English
The first line is an integer which indicates the number of test cases. Each test case is a number in one line. There are at most 10 cases.
● Chinese
第一行是一個整數代表測試資料有幾筆。每一筆測試資料都給定一個數值。至多有十組測資。

Output Format

● English
For each test case, output the square and cube of the given number in a line.
● Chinese
針對每一筆測試資料，在一行中輸出給定數值的平方及立方值並以一個空格隔開。

Example

Sample Input:	Sample Output:
2 4 5	16 64 25 125

ITSA 37 Problem 4 計算炸彈數

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22217

[Problem 4] 計算炸彈數

成績: 0 / 倒扣: 0.8

問題描述：
模擬踩地雷遊戲，計算出周圍炸彈數量。
輸入一個二維陣列，每一格用 0 與 1 代表是否為炸彈， 0 代表該格不為炸彈， 1 代表該格為炸彈
例如：

	1	2	3	4
1	1	0	1	1
2	1	0	0	0
3	1	1	0	1
4	0	1	1	0

上述表格代表
炸彈： (1,1), (1,3),(1,4), (2,1), (3,1), (3,2), (3,4), (4,2), (4,3)
非炸彈： (1,2), (2,2), (2,3), (2,4), (3,3), (4,1), (4,4)
請找出非炸彈的格子中周圍八格有幾顆炸彈。

1	1	0
0	x	1
1	1	0

上述表格 x 的值應為 5
若 x 本身就是代表一顆炸彈，則值應為 0
輸入說明：
5
1 0 0 1 1
0 1 0 1 0
1 0 1 0 1
0 0 0 1 0
0 1 1 1 0
5 代表陣列大小 ( 最大為 9 ，最小為 3) ，之後為每一格的值
輸出說明：
依序輸出，中間以空白隔開，最後必須有換行字元。
範例：

輸入範例	輸出範例
5 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 0	0 2 3 0 0 3 0 4 0 4 0 3 0 4 0 2 4 5 0 3 1 0 0 0 2

解法：

因為炸彈是1 ，因此我們可以先判斷是否為炸彈，若是炸彈則輸出0，其餘的就將它四周的值加起來(因為炸彈是1，所以全加起來就知道數目)。

但邊界問題要小心，可以將測資用1~N存邊界都設0

這樣就不用判斷邊界了 ^&^

ITSA 37 Problem 3 最佳排程

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22215

[Problem 3] 最佳排程

成績: 0 / 倒扣: 0.8

問題描述：
尾牙到了，因經濟不景氣，許多表演團體紛紛表示有意願前來表演餘興節目，員工希望在節目秀場中看到最多的表演，但受限於尾牙派對時間長度，公司必須決定邀請哪些團體來表演。請為公司寫一個程式讀入公司尾牙派對的時間和所有有意願前來表演的團體所需的表演時間，計算出公司最多可邀請多少團體來表演。例如，若公司派對長度為 200 分鐘，各表演團體所需的時間為 :
27 6 50 21 3 14 16 8 42 33 21 9
則最多可排入 11 個團體表演（ 27+6+21+3+14+16+8+42+33+21+9=200 ）。
輸入說明：
第一行為一個正整數 N ，代表共有幾家公司。之後接下來有 N 行，每行第一個為正整數 M （ 0 < M < 1000 ），代表該公司的派對時間限制，接下來有數個（不超過 100 個）整數，以 0 結束，代表前來申請的各個表演所需的表演時間。
輸出說明：
將每個公司最多可邀請的表演團體數目輸出於一行，最後必須有換行字元。
範例：

輸入範例	輸出範例
3 200 27 6 50 21 3 14 16 8 42 33 21 9 0 70 20 5 3 6 12 8 4 0 30 13 12 10 5 3 6 15 0	11 7 4

解法：先將整串數字存入array內,其中array[0]代表總共可表演時間
再將array[1]~array[i]的數字依小到大排序，並一一用a[0]-a[j]，
若a[0]<a[j]代表時間不夠第j個團體表演，則跳出迴圈並輸出答案

ITSA 37 Problem 2 解加密的電話號碼

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22213

[Problem 2] 解加密的電話號碼

成績: 0 / 倒扣: 0.8

問題描述：
給定一個 key 值及一連串已經編碼過的整數列，以空白分隔開來，請將其還原成原來的電話號碼。
電話號碼的每一個數字 n 編碼方式說明如下：
Step1. 以亂數 (1~100) 產生一個 key 值 k 。
Step2. 以 (10-n) 結果為 p , 若 p 的值 10 ，則 p = 0 。
Step3. 將 p 的值，轉成數字轉成 ASCII 碼，其值為 a 。
Step4. a + k 的值 c 即為編碼的值，並將編碼的值 c 輸出。
Step5. 重複 Step2~Step4 將電話號碼每一個數字編碼。
ASCII 碼如下所示：

ASCII 碼十進位	48	49	50	51	52	53	54	55	56	57
數字	0	1	2	3	4	5	6	7	8	9

例如：某一電話號碼經過編碼後的整數列為 68 74 77 76 75 7473 72 71 70 ，其 key 值 k = 20 ，則經過解碼後，還原回來的電話號碼為 0412345678 。
輸入說明：
輸入一連串的整數列，以空白分隔。第一個整數代表 key 值，其後為經過編碼後的整數列。
輸出說明：
經過解碼後，還原回來的電話號碼，最後必須有換行字元。
範例：

輸入範例	輸出範例
20 68 74 77 76 75 74 73 72 71 70	0412345678

ITSA 37 Problem 1 計算總和、乘積、差、商和餘數

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22211

[Problem 1] 計算總和、乘積、差、商和餘數

成績: 0 / 倒扣: 0.8

問題描述：
撰寫一個程式，要求使用者輸入兩個數字，再從使用者取得這兩個數字，然後印出這兩個數字的總和、乘積、差、商、和餘數。
輸入說明：
依序輸入兩個整數，整數範圍不超過 1000 。
輸出說明：
輸出總和、乘積、差、商、和餘數(注意格式)，最後必須有換行字元。
範例：

輸入範例	輸出範例
7 3	7+3=10 7*3=21 7-3=4 7/3=2...1

ITSA 38 Problem 4 迷宮路徑

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?a=11600

[Problem 4] 迷宮路徑

成績: 0 / 倒扣: 0.8

問題描述：
在一張 n×n 大小的地圖中，座標由上往下由左往右從 0 開始到 n -1 。從起點 (1,1) 到終點 (n-2, n-2) 的路徑，保證只會存在一條路徑，若遇到十字路口判斷時，判斷順序為下、上、左、右，陣列中的值 1 代表牆壁， 0 代表可以通過的點。
輸入說明：
第一個數字代表陣列大小 n ( n ≤ 20 ) ，後續資料為地圖配置。
輸出說明：
井字 (#) 代表正確路徑，星號 (*) 代表經過但不是正確的路徑，最後必須有換行字元。
範例：

輸入範例

輸出範例

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1
1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1
1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 # 1 1 1 1 1 * * * 1 1 1 1 0 0 0 1 1 1
1 # 1 1 1 1 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # # # 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # 1 # 1 * 1 * 1 1 1 1 0 1 0 1 1 1
1 # 1 # 1 # 1 * 1 * 1 1 1 0 0 1 0 1 1 1
1 # 1 # 1 # * * 1 1 1 1 1 1 1 1 0 1 1 1
1 # 1 # 1 # 1 * 1 1 1 1 1 1 1 1 0 1 1 1
1 # 1 # 1 # 1 # # # # # # # # # # 1 1 1
1 # # # 1 # # # 1 1 1 1 1 1 1 1 # 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 # # # # # 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # 1 1 1 * 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 # # # # # # # 1
1 1 1 1 1 1 1 1 1 1 1 1 * 1 1 1 * 1 # 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

作法 : 用stack實作DFS

2015年7月26日星期日

ITSA 38 Problem 5 Pseudo Random Generation

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22956

[Problem 5] Pseudo Random Generation

成績: 0 / 倒扣: 0.8

Problem Description
Random numbers are usually used in computer program. Computer can't produce pure random numbers but can produce pseudo random numbers. There are some pseudo random generators in our program language library which are usually used.
There is a method which is usually used to produce pseudo random numbers. The method is called linear congruential method. This method needs 4 parameters:

m
a
c
X₀

a modulus
a multiplier
a addend
a initial number(seed number)

m > 0
0 < a < m0 ≤ c < m
0 ≤ X₀ < m

The pseudo random numbers are produced by follow program states:
X_n₊₁ = ( aX_n + c ) mod m
For example, if a = 7, c = 5, m =12, and X₀ = 4 then the program produces a series of the pseudo random numbers as follow:

X_n	aX_n + c	X_n+ ₁= ( aX_n+ c ) mod m
4 9 8 1 0 5	33 68 61 12 5 40	9 8 1 0 5 4

In this case, the cycle length of a pseudo random numbers sequence is 6. In other words, the program produces six different pseudo random numbers and the series of the pseudo random numbers will repeat. Theoretically, the cycle length cannot exceed m hat is produced by the method (because mod m).

In this problem, you are given a, c, m, and X₀ and asked to computer the cycle length. Note that, the repetition is not necessarily from the first seed. For example, if the pseudo random number sequence is {3, 7, 2, 10, 17, 8, 2, 10, 17, 8, ...} then the cycle length is 4.
Input File Format
In the first line, there is a integer n indicating how many cases. Followed the first line, there are four integers separated by a space in each line. The four integers indicate the numbers of a, c, m and X₀ in this order.
Output Format
Output the cycle length of every case line by line.
Example

Sample Input:	Sample Output:
2 2179 1839 3279 1511 3561 5353 6219 1234	546 345

題意 : 給你亂數的seed 尋找第一次出現重複數字x和第一次出現x中間隔了幾個數

做法 : 我先設一個array-> test[]並預設為0 當test[x]為0代表x是第一次出現設test[x] = sum,記錄她出現的位置 , 因此若test[x]!=0則代表找到第一個cycle(重複的數),並輸出 sum-test[x](他們之間差幾個數)

ITSA 38 Problem 3 糖果分享

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22951

[Problem 3] 糖果分享

成績: 0 / 倒扣: 0.8

問題描述：
兒童節前夕，老師把全班同學的座位排成格子狀，並且準備了一袋一袋的糖果要分給小朋友們。老師把一袋一袋的糖果放在某幾個同學的抽屜裡，拿到一袋糖果的同學必須而且只能把糖果分給他前後左右的同學。請寫一個程式幫老師檢查看看，是不是全班的同學都可以拿到糖果呢？
輸入說明：
輸入檔中第一行為一個正整數 N ，代表共有幾組測試資料。之後接下來每筆資料的第一行為三個數字 n 、 m 和 L ， 1 ≤ n ≤ 20, 1 ≤ m ≤ 20, 1 ≤ L ≤ 100 ，以空格隔開，表示座位共有 n 行、 m 列以及糖果共有 L 袋，第二行開始每行有 2 個數字 x 和 y ，以一個空格隔開，共有 L 行，每一組 x 、 y 代表糖果放在第 x 行、第 y 列的抽屜裡。
輸出說明：
若全部的同學都可以拿到糖果，則輸出 Y ，否則輸出 N ；每筆測試資料輸出於一行，最後必須有換行字元。
範例：

輸入範例	輸出範例
3 2 3 1 1 1 4 3 4 1 2 2 2 3 2 4 2 5 4 5 1 3 2 1 3 4 4 1 5 3	N Y N

ITSA 38 Problem 2 井字遊戲

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22949

[Problem 2] 井字遊戲

成績: 0 / 倒扣: 0.8

問題描述：
輸入 0 、 1 、 2 代表 * 、 Y 、 X ，直橫斜三個連成一線者為獲勝，無人獲勝則顯示 Tie 。
輸入說明：
輸入 0 、 1 、 2 至 3 × 3 的矩陣。
輸出說明：
符號轉換 0 、 1 、 2 為 * 、 Y 、 X 並輸出 ( 中間不用隔開，但要換行 ) 。
Y 符號獲勝輸出 Y bingle 、 X 符號獲勝輸出 X bingle ，其他結果輸出 Tie ，最後必須有換行字元。
範例：

輸入範例	輸出範例
1 0 2 2 1 0 0 0 1	YX XY **Y Y bingle

解法 : 先把矩陣存成一維陣列

1	2	3
4	5	6
7	8	9

然後仔細觀察看看，最後你會發現，若可連線，它們的位置後減前會相等
EX : 1-5-9 -> 9-5 = 5-1
1-4-7 -> 7-4 = 4-1
因此我將數字1的位置存入y[]，數字2的存入x[]
判斷並輸出結果

ITSA 38 Problem 1 英哩轉公里

題目來源 : http://140.116.249.152/e-Tutor/mod/programming/view.php?id=22947

[Problem 1] 英哩轉公里

成績: 0 / 倒扣: 0.8

問題描述：
試撰寫一程式，可由鍵盤輸入英哩，程式的輸出為公里，其轉換公式如下：
1 英哩 = 1.6 公里
輸入說明：
輸入欲轉換之英哩數 (int < 1000) ，不超過 50 筆。
輸出說明：
輸出公里 (double) ，四捨五入取到小數點以下第一位，最後必須有換行字元。
範例：

輸入範例	輸出範例
90 95	144.0 152.0

2015年7月25日星期六

ITSA 39 _ 解答

題意: 在不採到炸彈的情況下求最短路徑

方法 : BFS

2015年7月23日星期四

[Uva 10112 Myacm Triangles]

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

題意 : 找出最大三角形面積而那個三角形裡面不能有其他點喔~

方法 : 三個點一抓抓到後再判斷裡面是不是有其他點

[Codeforces Round #308 (Div. 2) D. Vanya and Triangles]

題目來源 : http://codeforces.com/contest/552/problem/D

題意 : 找出所有點共可以圍成多少的三角形

作法 : 用三個迴圈跑每抓三個點就計算他們面積是否為0
若為0則代表是三點共線因此不是三角形
非0則 ans++

2015年7月22日星期三

[Problem - 456B - Codeforces Fedya and Maths]

题目来源： http://codeforces.com/problemset/problem/456/B

题意：求出算式中答案

解法：我一开始先将n都带入算式中看看

          有看到规律吗？XD
            原来只要n是四的倍数答案就是4
            其余都是0

            //n有点大所以用string存比较方便 =）

[Uva 11310 - Delivery Debacle ]

题目来源： http://7xjob4.com1.z0.glb.clouddn.com/14d2a0ad052a0accf5481f9180a98745

题意：求有几种蛋糕装法

解法： DP

[Uva 11000 Bee]

题目来源： http://7xjob4.com1.z0.glb.clouddn.com/6e44785eb5d7eb3526d096bd83ff4b8e

题意：蜜蜂生产完都会死翘翘 , 但只有最开始的母蜜蜂不会死翘翘 , 母的蜜蜂生公蜜蜂 , 公的蜜蜂生一男一女,

解法 : 所以只要将目前男蜜蜂的数量加上1（不会死的母蜜蜂）就是明年的母蜜蜂数量, 将目前的公蜜蜂数量加上目前母蜜蜂的数量就是明年的公蜜蜂数量

[Uva 10104 Euclid Problem]

题目来源： http://7xjob4.com1.z0.glb.clouddn.com/b10ac4b75a1ebfce51b98250b2cbcb4c

解法：题目一看大概就知道这题要用到GCD（最大公因数）,因此一定会想到辗转相除法
但系数X Y要怎麽求得呢？我们先套到公式里面看看

套完大概就发现可以在GCD递回中顺便求得了

下面附上程式码 ^&^

2015年7月21日星期二

[Uva 12086 Potentiometers]

題意 : 先輸入一串數字更新其值或找出區間和

方法 : fenwick tree
今天上課筆記抄不多>"<

但fenwick tree的重點蠻好懂得
簡單來說就是先將位置換成二進位
[更新] 最後的1加1
[查詢] 最後的1減1
找最後一個1的方法就是跟其二的補數做AND --> x&(-x)

[更新] 更a[x+x&(-x)];
[查詢] 查a[x -x&(-x)];

[Uva 12532 Interval Product]

題意 : 將區段內的數字成積之正負號顯示出來
方法 :
1. Segment Tree 左右邊界真的卡很久~但最後才發現是自己想得太複雜了
2. 利用struct 可以同時將值和左右邊界存進去蠻簡單的 =)

網上看到一篇富圖解的blog : http://pavelsimo.blogspot.tw/2012/11/uva-12532-interval-product.html

下面附上debug五小時的程式碼-..-

2015年7月20日星期一

[CodeForces 550A Two Substrings]

題目網址 : http://codeforces.com/problemset/problem/550/A

題意 : 是否能在題目給你的string中找到一個AB和BA ，順序沒差

解法 : 因為ABA或BAB可以同時為AB或BA ，所以可以有三種case

1. ABA/BAB 配 AB

2. ABA/BAB 配 BA

3. BA 配 AB

	#include <iostream>
	#include <cstring>

	using namespace std;

	int main()
	{
	char a[100000];

	cin >> a;

	int l = strlen(a);
	int flag1 = 0 ,flag2 = 0 ,flag3 = 0 ,flag18 = 0 ;


	for(int i = 0 ; i < l ; )
	{
	int k = i ;
	if(((a[i] == 'A' && a[i+1] == 'B' && a[i+2] == 'A') \|\| (a[i] == 'B' && a[i+1] == 'A' && a[i+2] == 'B') ) && i <= l-3){flag1 = 1 ; i = i+3 ; }
	if(a[i] == 'A' && a[i+1] == 'B' && i <= l-2) { flag2 = 1 ; i = i+2 ; }
	if(a[i] == 'B' && a[i+1] == 'A' && i <= l-2) { flag3 = 1 ; i = i+2 ; }

	if(k == i) i++;

	if(flag1 == 1 && flag2 == 1) flag18 = 1 ;
	if(flag1 == 1 && flag3 == 1) flag18 = 1 ;
	if(flag2 == 1 && flag3 == 1) flag18 = 1 ;
	}
	if(flag18 == 1) cout << "YES" << endl ;
	else cout << "NO" << endl ;

	}

view raw gistfile1.cpp hosted with ❤ by GitHub

[ACM_ICPC 7150 - Amalgamated Artichokes]

題目網址 : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5162

題意 : 給一個合成函式，尋找其中最大的下降高度

注意 : 若跑兩個for迴圈會TLE

	#include<iostream>
	#include<cmath>
	#include<iomanip>
	#include <limits>

	using namespace std;
	typedef numeric_limits< double > dbl;
	double test[1000001];
	double p,a,b,c,d,n;
	double price(double k){
	return p * (sin(a * k + b) + cos(c * k + d) + 2);
	}

	int main(){

	while(cin>>p>>a>>b>>c>>d>>n){
	for(int y=1;y<=n;y++) {
	test[y] = price(y);

	}
	double ans = 0;
	double maxi = test[1];
	for(int i=2;i<=n;i++){
	if(test[i]>maxi) maxi = test[i];
	else ans = max(maxi-test[i],ans);
	}
	//max1 = maxi-minj;
	cout.precision(dbl::digits10);
	if(ans==0) cout<<"0.00"<<endl;
	else cout<<ans<<endl;
	}


	}

view raw gistfile1.cpp hosted with ❤ by GitHub

最长回文

以前有曾经遇过回文问题但是怎末写都TLE （哭哭
结果是今天看到的这一篇BLOG交会我的
http://my.oschina.net/pathenon/blog/63575
做法就是以其中一点为中心找出他最大回文的半径
所以像ASDSA
找到以D（str[3])为中心的最大半径是3 然后他后面的S(str[4])位置是4< 3+3(半径）-1 , 因此可以不用重复计算他的回文半径因为他跟前面那个S（str[2]）是对称的所以可以直接套用
如果有找到新的最大半径则要记得更新哦
答案就是最大回文半径*2-1～～
附上code 但因为是看的当参考的所以应该跟blog上的很雷同

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	using namespace std;
	#define max 110010 * 2

	int main(){
	char ch[max],pre[max];
	int ans[max];

	while(scanf("%s",ch)!=EOF){
	int length = strlen(ch);
	pre[0] = '#';
	pre[1] = '#';
	for(int i=0;i<length;i++){
	pre[i*2+2] = ch[i];
	pre[i*2+3] = '#';
	}
	int n = length*2+2;
	//memset(ans,0,sizeof(int));
	/**
	ans:以pre[i]为中心的最长回文串的半径为ans[i]。

	idx:已经找出的能够右延伸最远距离的回文子串的起始位置。

	m:已经找出的能够右延伸最远距离的回文子串的结束位置。
	**/
	pre[n] = '0';
	int idx = 0,m = 0;

	for(int i=1;i<n;i++){
	if(m>i) ans[i] = ans[idx2-i] < (m-i)?ans[idx2-i] : (m-i);
	else ans[i] = 1;
	for(; pre[i + ans[i]]==pre[i - ans[i]]; ans[i]++);
	if(ans[i] + i > m)
	{
	m = ans[i] + i;
	idx = i;
	}
	}

	int t = 0;
	for(int i=2;i<n;i++){
	if(ans[i]>t) t = ans[i];
	}printf("%d\n",t-1);
	}

	}

view raw gistfile1.cpp hosted with ❤ by GitHub

2015年7月17日星期五

[poj 1979 Red and Black]

题目网址： http://poj.org/problem?id=1979

这题的题意简单来说就是“找出起点附近最大的连续黑色区块“
因此我利用BFS寻找最多可以走几步的想法来计算它
（不知道这题用DFS会不会比较快>"<

	#include<iostream>
	#include<cstdio>
	#include<queue>
	using namespace std;

	int p[101][101],times;
	typedef pair<int,int> Point;//存入坐标
	int xt[4] = {-1, 1, 0, 0};//前后左右寻找
	int yt[4] = { 0, 0, 1,-1};


	int BFS(int x,int y){
	queue <Point> Queue;//建立queue
	Queue.push(make_pair(x,y));//将起点push进去
	times = 1;//步数设为1
	while(!Queue.empty()){//若queue为零则跳出回圈
	Point now = Queue.front();
	int r = now.first,c = now.second;
	Queue.pop();
	for(int i=0;i<4;i++){
	int tx,ty;
	tx = r+xt[i];
	ty = c+yt[i];
	if(p[tx][ty]==1){
	Queue.push(make_pair(tx,ty));
	p[tx][ty] = -1;//将走过的点作记号
	times++;
	}

	}

	}
	return times;//回传步数
	}
	int main(){
	int N,M,x,y;
	char ch;
	while(scanf("%d %d",&N,&M)&&(M\|\|N)){//读入空间大小
	for(int i=0;i<=M+1;i++){
	for(int j=0;j<=N+1;j++){
	if(i==0\|\|i == M+1\|\|j==0\|\|j==N+1) p[i][j] = 0;//将边界设为不能走
	else{
	cin>>ch;
	if(ch == '.') p[i][j] = 1;//黑色空格设为1 代表可以走
	if(ch == '#') p[i][j] = 0;//红色空格设为0 代表不能走
	if(ch == '@') {p[i][j] = -1;x = i;y = j;}//将起点记录起来
	}
	}
	}
	//开始BFS广度搜寻
	cout<<BFS(x,y)<<endl;

	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

[Codeforces Round #304 (Div. 2) Soldier and Cards]

题目链接： http://codeforces.com/contest/546/problem/C

卡片问题
题目算蛮好懂得看图大概就可以知道题意
将两堆卡片的最上面拿一张拿起来相比,若A堆上的那一张比B堆小,则将两张卡片由小到大放入B堆的底部 ,若A堆上的那一张比B堆大,则反之.

这题我是直接用queue实作
比较快也比较好懂（虽然还没想到第二种方法的说XD

	#include<iostream>
	#include<queue>
	using namespace std;
	int main(){
	queue<int> q1;
	queue<int> q2;
	int n,x,y;
	cin>>n;//总卡片数量直接读掉就好
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>x;
	q1.push(x);
	}
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>x;
	q2.push(x);
	}
	int times = 0;
	while(!q1.empty()&&!q2.empty()&&times<10000){
	//取出第一个数相比较并pop掉
	x = q1.front();
	y = q2.front();
	q1.pop();
	q2.pop();
	//将两数依小到大存入比较大的数的queue
	if(x<=y){
	q2.push(x);
	q2.push(y);
	}
	else{
	q1.push(y);
	q1.push(x);
	}
	//总比较次数++ 进入无穷回圈则跳出
	times++;
	}

	if(times>=10000) cout<<"-1"<<endl;
	else {
	cout<<times;
	if(!q2.empty()) cout<<" 2"<<endl;
	else cout<<" 1"<<endl;
	}

	}

view raw gistfile1.cpp hosted with ❤ by GitHub

2015年7月16日星期四

[Uva11352 - Crazy King]

今天一次過欸(灑花~~
明天再來寫註解，先來睡了

[Uva 534 Frogger]

[Uva1235 - Anti Brute Force Lock]

這題有點懶寫註解XD
方法也是MST
題目問最少密碼轉動次數
可以把每一組密碼都看成一個點
點跟點之間的距離是他們需要旋轉的次數
因為是求MST所以哪一點開始並不重要
但最後要加上"0000"到其中一點的最短距離才會是答案
而點的存法用string 網路上也有人用int 因此是看個人

但array要設夠大(今天不知道為什麼一直RE
轉動次數也要算對可以往前轉或往後取最少值
[ex]9->1就要取2不是8

[Uva10397 Connect the Campus]

方法 : MST
將edges由小至大排序
如果沒有形成cycle則取它
判斷cycle的方法是用Disjaint Set

[Uva908 Re-connecting Computer Sites]

方法 : MST

將edges由小至大排序
如果沒有形成cycle則取它
判斷cycle的方法是用Disjaint Set

2015年7月14日星期二

[Uva 10696 f91]

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

作法 : 遞迴
題意：給你兩個函數用它下去跑遞迴就好 =)

[Uva 11516 WiFi]

方法 : binary search

题意：寻找在题目提供的ap数量下半径最小值

做法： Binary Serach

因为房子一定要被包到所以可以假设房子刚好被ap覆盖到的情况下之最少距离
因此以房子为準依直径向外扩张最后题目所求的半径再用所得直径/2即得

Problem - 557B - Codeforces__Pasha and Tea

題目 : http://codeforces.com/problemset/problem/557/B

POJ 1989 The Cow Lineup

題意 :

農場主人請"牛"排成一row

想請問最小幾個數形成的數列不能從牛序列取得子序列(可以不連續取得)

網路上的方法是用Greedy

做法 : Greedy
參考作法 : http://www.acmerblog.com/hdu-2712-the-cow-lineup-4312.html

	#include<iostream>
	#include<cstdio>
	#include<cstring>
	using namespace std;

	int a[100001];//記錄牛隻編號
	bool visit[100001];//紀錄是否此數字已經有了!

	int main(){

	long int i,n,k,j,ans = 0;
	scanf("%d %d",&n,&k);//輸入牛的數目根編號範圍
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]);//讀入牛的編號

	j = 0;
	memset(visit,false,sizeof(bool));//陣列初始化

	for(i=1;i<=n;i++){
	if(!visit[a[i]]){
	visit[a[i]] = true;
	j++;
	}
	if(j == k){
	for(int m=1;m<=n;m++){
	visit[m] = 0;
	}
	j = 0;
	ans++;
	}
	}
	printf("%d\n",ans+1);
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

[Uva 10608 ]Friends

方法 : Disjaint Sat

	#include<iostream>
	#include<cstdio>
	using namespace std;

	int p[100001],N,sum[100000];

	//陣列初始化
	void init(){
	for(int k=1;k<=N;k++)
	{
	p[k] = k;
	sum[k] = 0;
	}
	}

	//尋找父親
	int Find(int x)
	{

	if (x == p[x]) return x;
	p[x] = Find(p[x]);//順手作壓縮
	return p[x];
	}

	//將x y連起來
	void Union(int x,int y){
	int fx = Find(x);
	int fy = Find(y);
	p[fx] = fy;//x的root連在y的root之屁屁上

	}


	int main(){
	int T,M,i,j;
	char ch;
	scanf("%d",&T);//輸入幾筆測資
	while(T--){
	scanf("%d %d",&N,&M);//輸入幾個住戶和幾筆關係
	init();//陣列初始化

	while(M--){
	scanf("%d %d",&i,&j);//輸入關係並相連
	Union(i,j);
	}
	for(i=N;i>=0;i--){
	sum[Find(i)]++;//將關係相同root++ 若Find[i]==6 then sum[6]++
	}
	j = 0;
	for(i=N;i>=0;i--){
	j = max(sum[i],j);//輸出最多關係的關係人數
	}
	cout<<j<<endl;
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

2015年6月13日星期六

原住民概論之烤山豬

學期即將結束
今天，也就是眾所期待的烤山豬之日的到來 ~~

上學期就曾聽說，原住民概論期末會有烤山豬吃，就衝著"吃"而修了"進發學長"的課ヽ(✿ﾟ▽ﾟ)ノ

原住民概論雖然在學期中我並不怎麼感興趣，但是從中得到的知識與想法卻是無價的，以前的我根本不知道原住民們面臨的文化衝擊、部落人口老化、與自然災害的衝擊有多大，他們樂天的個性，背後那種種的努力，是我鮮少認真看待的事物。但是自從上完學長的課以後，漸漸地，想要到原住民部落走走，看看那學長口中所說的山中美景、美食。那古老的手工藝、那熟練的狩獵技巧，天籟般的歌聲，或許今年暑假，小旅行的目的地默默地決定了呢！

=====================開始烤全豬了囉！======================

早上剛到集合地，發現 "wow~人怎麼那麼多啊Σ(ﾟДﾟ；≡；ﾟдﾟ) "哈哈原來有三個班一起烤呢！這樣食物會不會不夠阿(<--超貪吃)，但看到"烤全豬"時一切都不擔心了阿~~因為真的超~大~隻~的~

烤全豬欸~~(有看到那尾巴嗎?)

第一次看到烤全豬，真的超興奮的！在介紹完烤全豬後，學長開始為我們介紹關於原住民陷阱的製作，獵人的陷阱相當聰明，但是用紙上說明的我功力還不夠阿...請自行google吧>"<

陷阱製作中

陷阱介紹完後，就是第二重頭戲！！！"搗麻糬"，學長說，原本她想要準備用小米搗的，但是小米要現場煮，所以他決定用糯米搗，記得以前好像有搗過的感覺，但是在哪呢？我還真想不起來。

學長挖糯米，準備開始搗麻糬

搗完麻糬就可以準備開動了耶~~

學長準備超多食物der，有炒米粉，炒麵，飲料，還有小米酒、麻糬和烤全豬，完全吃到飽的說！！ヽ(∀ﾟ )人(ﾟ∀ﾟ)人( ﾟ∀)人(∀ﾟ )人(ﾟ∀ﾟ)人( ﾟ∀)ﾉ

麻糬真的不太好夾，謝謝不認識的朋友們幫忙，最後班上同學用大夾子夾真的超聰明的>"<，力氣也超大，麻糬加上蜂蜜或黑糖漿根本超讚，超Q超香，不愛吃一般市售麻數的我卻整整吃了兩碗阿。

超黏的麻吉

再來烤全豬也是超好吃的！！沒吃過的人一生一定必吃！！超嫩超多汁，會想要一口接著一口的吃，這是實話不要懷疑，快點google"田媽媽烤全豬"吧！

在吃烤豬時，一口接ㄧ口的喝著小米酒，非常香，非常順口，(下次寢聚可能我會拿出一大罐小米酒吧....)下次上課我一定要問學長小米酒去哪買，今天我整整喝了3杯，但因為要騎車...不然好想喝下去喔 -3-

最後，我要謝謝今天所有同學和學長、學長的哥哥、還有烤全豬的大哥們，因為你們，今天才會如此開心，有如此豐富的課程和獨特的體驗。謝謝你們 :))今天真的很開心

學長也辛苦了，你的用心我們都看到了 <3

訂閱：文章 (Atom)

Sample Input:	Sample Output:
2 5 7 0 1 3 1 2 1 1 3 8 2 3 10 2 4 5 3 4 9 4 0 6 8 12 0 2 9 0 4 4 1 2 3 1 5 6 2 3 5 2 4 8 3 4 3 3 5 7 5 7 4 5 6 1 6 4 3 6 7 4	33 43

Sample Input:	Sample Output:
5 3 9122 3128 5112 4 1725 3821 2011 1428 4 1925 2011 3210 9215 4 4145 1245 1485 1478 7 5584 12635 7894 12365 98453 56487 2134567	5112 3128 9122 2011 3821 1428 1725 2011 3210 1925 9215 1245 4145 1485 1478 12365 12635 5584 7894 2134567 98453 56487

2015年11月7日 星期六

2015年10月28日 星期三

2015年10月21日 星期三

2015年10月9日 星期五

2015年10月5日 星期一

2015年9月30日 星期三

2015年9月23日 星期三

2015年8月2日 星期日

2015年8月1日 星期六

2015年7月29日 星期三

2015年7月28日 星期二

[Problem B4-易] Polynomials

2015年7月27日 星期一

[Problem B7-中] The Maximum Bottleneck Spanning Tree

[Problem B3-易] Unique elements

[Problem B2-易] 各位數和的排序

[Problem B1-易] Square and Cube

[Problem 4] 計算炸彈數

[Problem 3] 最佳排程

[Problem 2] 解加密的電話號碼

[Problem 1] 計算總和、乘積、差、商和餘數

[Problem 4] 迷宮路徑

2015年7月26日 星期日

[Problem 5] Pseudo Random Generation

[Problem 3] 糖果分享

[Problem 2] 井字遊戲

[Problem 1] 英哩轉公里

2015年7月25日 星期六

[Problem 1] 3x+1數列產生

[Problem 2] 矩陣分素乘積

[Problem 3] 爬樓梯

[Problem 4] 文字接龍

[Problem 5] Cable Car Assignment

2015年7月23日 星期四

2015年7月22日 星期三

2015年7月21日 星期二

2015年7月20日 星期一

2015年7月17日 星期五

2015年7月16日 星期四

2015年7月14日 星期二

題意 :

農場主人請"牛"排成一row

想請問最小幾個數形成的數列 不能從牛序列取得子序列(可以不連續取得)

網路上的方法是用Greedy

做法 : Greedy 參考作法 : http://www.acmerblog.com/hdu-2712-the-cow-lineup-4312.html

2015年6月13日 星期六

2015年11月7日星期六

2015年10月28日星期三

2015年10月21日星期三

2015年10月9日星期五

2015年10月5日星期一

2015年9月30日星期三

2015年9月23日星期三

2015年8月2日星期日

2015年8月1日星期六

2015年7月29日星期三

2015年7月28日星期二

2015年7月27日星期一

2015年7月26日星期日

2015年7月25日星期六

2015年7月23日星期四

2015年7月22日星期三

2015年7月21日星期二

2015年7月20日星期一

2015年7月17日星期五

2015年7月16日星期四

2015年7月14日星期二

想請問最小幾個數形成的數列不能從牛序列取得子序列(可以不連續取得)

做法 : Greedy
參考作法 : http://www.acmerblog.com/hdu-2712-the-cow-lineup-4312.html

2015年6月13日星期六