「AOJ1061～1070」の編集履歴（バックアップ）一覧はこちら

「AOJ1061～1070」(2013/02/06 (水) 22:19:24) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*1062 It's our delight!!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1062
飲食店の時間帯別接客成績を計算する問題。
何故か8分を5分と読み間違える謎のミスをしてしまう。
簡単な問題なので丁寧に書くだけです。

 #include<stdio.h>
 void calc(int n){
	double okLDM[3]={0,0,0},allLDM[3]={0,0,0};
	for(int i=0;i<n;i++){
		int hh,mm,mm2;
		char c;
		scanf("%d%c%d %d",&hh,&c,&mm,&mm2);
		int add;
		if(mm<=mm2){
			add=(mm2-mm)<=8;
		}else{
			add=(mm2+60-mm)<=8;
		}
		if(11<=hh&&hh<=14){
			okLDM[0]+=add;
			allLDM[0]++;
		}else if(18<=hh&&hh<=20){
			okLDM[1]+=add;
			allLDM[1]++;
		}else if(21<=hh||hh<=1){
			okLDM[2]+=add;
			allLDM[2]++;
		}
	}
	char text[3][10]={"lunch","dinner","midnight"};
	for(int i=0;i<3;i++){
		printf("%s ",text[i]);
		if(allLDM[i]!=0){
			printf("%d\n",(int)(okLDM[i]/allLDM[i]*100));
		}else{
			printf("no guest\n");
		}
	}
 }
 int main(){
	int n;
	while(scanf("%d",&n)){
		if(n==0)break;
		calc(n);
	}
 }







*1063 Watchin' TVA
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1063
絶対みたいテレビ番組のリストを基礎にテレビ番組の番組表から以下に多くの番組を見れるかを求める問題。
絶対見たい番組に重複がないか調べて、あれば-1を出力。
なければ絶対見たい番組と重複してる番組を削除したリストで開始時刻の小さい順に試していくだけです。
一週間を表す一次元配列を使った方が良かったかも？



 #include<stdio.h>
 #include<string>
 #include<iostream>
 #include<set>
 #include<map>
 #include<vector>
 #define mapSI std::map<std::string,int>
 void setData(int n){
	std::string name;
	int week,time,time1,time2;
	mapSI memo;
	for(int i=0;i<n;i++){
		std::cin>>name>>week>>time;
		memo[name]=week*1440+(time/100)*60+time%100;//時刻を分に直す;
	}
	mapSI::iterator it;
	int p;
	scanf("%d",&p);
	std::vector<std::string> bs;
	std::set<std::string> memo2;
	bool bad=false;
	for(int i=0;i<p;i++){
		std::cin>>name;
		time1=memo[name];
		memo2.insert(name);
		//絶対見なくてはいけない番組に重複がないか？
		for(int j=0;j<bs.size();j++){
			time2=memo[bs[j]];
			if(time1-30<time2&&time2<time1+30)bad=true;
		}
		bs.push_back(name);
	}
	//for(it=memo.begin();it!=memo.end();it++){
	//	printf("<%s %d>",(*it).first.c_str(),(*it).second);
	//}
	if(bad==true){
		printf("-1\n");
		return ;
	}
	for(int i=0;i<p;i++){
		//絶対にみないといけない番組にかぶる番組のリストを作る
		time1=memo[bs[i]];
		for(it=memo.begin();it!=memo.end();it++){
			time2=(*it).second;
			//絶対にみないといけない番組でなくかつ視聴時間が重複している
			if(time1-30<time2&&time2<time1+30&&memo2.find((*it).first)==memo2.end()){
				(*it).second=-1;
			}
		}
	}	
	std::set<int> lastTimes;
	for(it=memo.begin();it!=memo.end();it++){
		time1=(*it).second;
		if(time1!=-1)lastTimes.insert(time1);
	}
	std::set<int>::iterator sIt=lastTimes.begin();
	int ans=0;
	while(sIt!=lastTimes.end()){
		ans++;
		time1=(*sIt)+30;
		//printf("%d\n",(*sIt));
		sIt=lastTimes.lower_bound(time1);
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		setData(n);
	}
 }

*1062 It's our delight!!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1062
飲食店の時間帯別接客成績を計算する問題。
何故か8分を5分と読み間違える謎のミスをしてしまう。
簡単な問題なので丁寧に書くだけです。

 #include<stdio.h>
 void calc(int n){
	double okLDM[3]={0,0,0},allLDM[3]={0,0,0};
	for(int i=0;i<n;i++){
		int hh,mm,mm2;
		char c;
		scanf("%d%c%d %d",&hh,&c,&mm,&mm2);
		int add;
		if(mm<=mm2){
			add=(mm2-mm)<=8;
		}else{
			add=(mm2+60-mm)<=8;
		}
		if(11<=hh&&hh<=14){
			okLDM[0]+=add;
			allLDM[0]++;
		}else if(18<=hh&&hh<=20){
			okLDM[1]+=add;
			allLDM[1]++;
		}else if(21<=hh||hh<=1){
			okLDM[2]+=add;
			allLDM[2]++;
		}
	}
	char text[3][10]={"lunch","dinner","midnight"};
	for(int i=0;i<3;i++){
		printf("%s ",text[i]);
		if(allLDM[i]!=0){
			printf("%d\n",(int)(okLDM[i]/allLDM[i]*100));
		}else{
			printf("no guest\n");
		}
	}
 }
 int main(){
	int n;
	while(scanf("%d",&n)){
		if(n==0)break;
		calc(n);
	}
 }







*1063 Watchin' TVA
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1063
絶対みたいテレビ番組のリストを基礎にテレビ番組の番組表から以下に多くの番組を見れるかを求める問題。
絶対見たい番組に重複がないか調べて、あれば-1を出力。
なければ絶対見たい番組と重複してる番組を削除したリストで開始時刻の小さい順に試していくだけです。
一週間を表す一次元配列を使った方が良かったかも？



 #include<stdio.h>
 #include<string>
 #include<iostream>
 #include<set>
 #include<map>
 #include<vector>
 #define mapSI std::map<std::string,int>
 void setData(int n){
	std::string name;
	int week,time,time1,time2;
	mapSI memo;
	for(int i=0;i<n;i++){
		std::cin>>name>>week>>time;
		memo[name]=week*1440+(time/100)*60+time%100;//時刻を分に直す;
	}
	mapSI::iterator it;
	int p;
	scanf("%d",&p);
	std::vector<std::string> bs;
	std::set<std::string> memo2;
	bool bad=false;
	for(int i=0;i<p;i++){
		std::cin>>name;
		time1=memo[name];
		memo2.insert(name);
		//絶対見なくてはいけない番組に重複がないか？
		for(int j=0;j<bs.size();j++){
			time2=memo[bs[j]];
			if(time1-30<time2&&time2<time1+30)bad=true;
		}
		bs.push_back(name);
	}
	//for(it=memo.begin();it!=memo.end();it++){
	//	printf("<%s %d>",(*it).first.c_str(),(*it).second);
	//}
	if(bad==true){
		printf("-1\n");
		return ;
	}
	for(int i=0;i<p;i++){
		//絶対にみないといけない番組にかぶる番組のリストを作る
		time1=memo[bs[i]];
		for(it=memo.begin();it!=memo.end();it++){
			time2=(*it).second;
			//絶対にみないといけない番組でなくかつ視聴時間が重複している
			if(time1-30<time2&&time2<time1+30&&memo2.find((*it).first)==memo2.end()){
				(*it).second=-1;
			}
		}
	}	
	std::set<int> lastTimes;
	for(it=memo.begin();it!=memo.end();it++){
		time1=(*it).second;
		if(time1!=-1)lastTimes.insert(time1);
	}
	std::set<int>::iterator sIt=lastTimes.begin();
	int ans=0;
	while(sIt!=lastTimes.end()){
		ans++;
		time1=(*sIt)+30;
		//printf("%d\n",(*sIt));
		sIt=lastTimes.lower_bound(time1);
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		setData(n);
	}
 }





*1069　Squid Multiplication
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1069
与えられた数字列とルールから元の数字列を再現する問題。

解法
まず偶数の部分に注目します。
偶数の積を小さい方から並べて隣り合う差分を取った時これより小さい値になりませんし、差分全体の最小公倍数より大きな値になりません。
偶数が判明したらこれをりようして奇数を求めます。
偶数はとりあえず考えられる最大値を求めこれを使って暫定的な奇数の倍数とします、後は奇数と何倍差かチェックするだけです。



 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 #include<math.h>
 long long int gcd (long long int a,long long int b ){
 	long long int c;
  	while ( a != 0 ) {
   	   c = a; a = b%a;  b = c;
    	}
   	return b;
 }
 
 void calc(int n){
 	std::vector<long long int> vKi,vGu;
 	long long int num,num2,num3;
 	for(int i=0;i<((n+1)*n)/2;i++){
 		std::cin>>num;
 		if(num%2==0)vGu.push_back(num);
 		else vKi.push_back(num);
 	}
 	std::sort(vGu.begin(),vGu.end());
 	std::sort(vKi.begin(),vKi.end());
 	long long int min=vGu[0];
 	for(int i=1;i<vGu.size();i++){
 		num=vGu[i]-vGu[i-1];
		if(num!=0)min=gcd(num,min);
 	}
 	for(int i=0;i<vGu.size();i++)vGu[i]/=min;
 	std::vector<long long int> vMul,v2;
 	for(int i=0;i<vGu.size();i++){
 		for(int j=i+1;j<vGu.size();j++){
 			vMul.push_back(vGu[i]*vGu[j]);
 		}
 	}
 	std::sort(vMul.begin(),vMul.end());
 	long long int base=1;
 	for(int i=0;i<vMul.size();i++){
 		num =vMul[i];
 		num2=vKi[i];
 		num3=num2/num;
 		base=base*(num3/gcd(num3,base));
 	}
 	base=sqrt(base);
 	std::cout<<min/base<<"\n";
 	for(int i=0;i<vGu.size();i++){
 		if(i>0)std::cout<<" ";
 		std::cout<<vGu[i]*base;
 	}
 	std::cout<<"\n";
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		calc(n);
 	}
 }