[#M_풀이보기|접기|


A. Tetrahedral Stacks of Cannonballs

굉장히 쉬운 문제.
f(n)=1+2+..+n
g(n)=f(1)+f(2)+...+f(n)
g(n)을 구하는 문제이다.
n이 1000보다 작으므로 integer범위 안에 있어서
n(n+1)/2 의 등비수열의 합 공식으로 구하면 된다.

#include <iostream>

using namespace std;

int a[1003];

int main()
{
	a[0]=0;
	for(int i=1;i<1001;i++)
	{
		a[i]=a[i-1]+(i*(i+1))/2;
	}
	int t;
	cin >> t;
	for(int TestCase=0;TestCase<t;TestCase++)
	{
		int n;
		cin >> n;
		cout << TestCase+1 << ": "<< n << " " << a[n] << endl;
	}
	return 0;
}

B. Robot Roll Call - Cambot...Servo...Gypsy...Croooow"

파싱해서 문장에서 그 단어가 나오는지 검사하는 프로그램.
파싱을 좀 더럽게 한듯... 잘 할 수 있을텐데
어떻게 하면 될까?

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int testcase;
	cin >> testcase;
	for(int TestCase=0;TestCase<testcase;TestCase++)
	{
		map<string, int> dic1;
		map<int, string> dic2;
		vector<bool> result;
		int dicn;
		cin >> dicn;
		result.resize(dicn);
		fill(result.begin(), result.end(), false);
		for(int i=0;i<dicn;i++)
		{
			string word;
			cin >> word;
			dic1[word]=i;
			dic2[i]=word;
		}

		int sentences;
		cin >> sentences;
		getchar();
		for(int i=0;i<sentences;i++)
		{
			string sentence;
			getline(cin, sentence);
			string word;
			for(int j=0;j<(int)sentence.length();j++)
			{
				if(sentence[j]==' ')
				{
					if(dic1.find(word)!=dic1.end())
						result[dic1[word]]=true;
					word="";
				}
				else
					word+=sentence[j];						
			}
			if(word!="")
			{
				if(dic1.find(word)!=dic1.end())
					result[dic1[word]]=true;
				word="";
			}

			
		}
		cout << "Test set "<<TestCase+1 << ":"<<endl;
		for(int i=0;i<dicn;i++)
		{
			cout << dic2[i] << "is ";
			if(result[i])
				cout << "present"<<endl;
			else
				cout << "absent"<<endl;
		}
		cout << endl;
	}
}

D. Obstacle Cource

다익스트라로 풀어야 한다지만
BFS로 그냥 돌려도 나오는 문제.
DP로 어떻게 안되나 고민을 해보다가
시간을 낭비했음.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

vector<vector<int> > a;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
	int TC=1;
	int n;
	while(1)
	{
		cin >> n;
		if(n==0) break;
		a.clear();
		a.resize(n);
		for(int i=0;i<n;i++)
		{
			a[i].resize(n);
			for(int j=0;j<n;j++)
			{
				cin >> a[i][j];
			}
		}

		int cache[200][200];

		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				cache[i][j]=9999999;

		queue<pair<int, int> > q;
		q.push(make_pair(0,0));
		cache[0][0]=a[0][0];
		while(!q.empty())
		{
			int y=q.front().first;
			int x=q.front().second;
			q.pop();
			for(int i=0;i<4;i++)
			{
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(nx<0||ny<0) continue;
				if(nx>=n||ny>=n) continue;
				if(cache[y][x]+a[ny][nx]<cache[ny][nx])
				{
					cache[ny][nx]=a[ny][nx]+cache[y][x];
					q.push(make_pair(ny,nx));
				}
			}
		}


		cout << "Problem " <<TC++ << ": "<<cache[n-1][n-1]<< endl;
	}
	return 0;
}

E. Pencils from the 19th Century

n자루의 연필을 샀는데
그중 몇자루는 4센트이고
그중 몇자루는 2개에 1페니이고
그중 몇자루는 4개에 1페니일 때

n자루를 입력하면 가능한 경우의 수 출력하기.

사실 쉬운 문제인데
n<256이므로
4x+1/2y+1/4z=n이므로
16x+2y+z=4n을 만족하는 모든 경우의 수를 구해보면 된다.

식이 명확하게 떠오르지 않아서 시간을 좀 낭비했다 -_-

#include <iostream>
using namespace std;

int main()
{
	int TC=0;
	while(1)
	{
		int n;
		cin >>n;
		if(n==0) break;
		cout << "Case "<<++TC<<":"<<endl;
		cout << n << " pencils for " << n << " cents"<<endl;
		if(n==0) break;
		bool found=false;
		for(int i=1;i<n*4;i++)
		{
			int remain=4*n-16*i;
			for(int j=1;j<2*remain;j++)
			{
				int remain2=remain-j*2;
				if(remain2+i+j==n)
				if(remain2>0)
				{
					cout << i  << " at four cents each"<<endl;
					cout << j  << " at two for a penny"<<endl;
					cout << remain2 << " at four for a penny"<<endl;
					found=true;
					cout << endl;
				}
			}
		}
		if(!found)
			cout << "No solution found." << endl<<endl;


	}
}

F. Optimal Strategy for the ICPC

ICPC  대회에서 문제당 걸리는 시간을 주고
어떤 전략으로 풀면 가장 가장 많은 문제를 풀고 가장 적은 패널티를 받는가 하는 문제
같은 문제에 같은 패널티이면 앞의 문제를 먼저 풀기.

패널티로 먼저 소트한다음
제일 작은것은 1번사람이 무조건 풀고
나머지 문제들을 2번 3번 사람들에게 배정해보면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <ctime>
using namespace std;

pair<int,int> data[20];
int run[20];
int solved, penalty;
string sequence;
int minrun[20];

int N,st;

int inline calcp(int n)
{
	int p=0;
	int sum=0;
	int temp[4][20];
	int tempc[4]={0};
	for(int i=0;i<n;i++)
	{
		temp[run[i]][tempc[run[i]]++]=data[i].first;
	}

	for(int i=1;i<4;i++)
	{
		sort(temp[i],temp[i]+tempc[i]);
		sum=0;
		for(int j=0;j<tempc[i];j++)
		{
			sum+=temp[i][j];
			p+=sum;
		}
	}
	return p;
}

string calcoutput(int n)
{
	int p=0;
	int sum=0;
	pair<int,int> temp[4][20];
	int tempc[4]={0};
	for(int i=0;i<n;i++)
	{
		temp[run[i]][tempc[run[i]]++]=make_pair(data[i].first,data[i].second);
	}

	vector<pair<int, int> > v;
	for(int i=1;i<4;i++)
	{
		sort(temp[i],temp[i]+tempc[i]);
		sum=0;
		for(int j=0;j<tempc[i];j++)
		{
			sum+=temp[i][j].first;
			v.push_back(make_pair(sum,temp[i][j].second));
			p+=sum;
		}
	}
	sort(v.begin(), v.end());
	string ret;
	for(int i=0;i<(int)v.size();i++)
	{
		char temp[100];
		sprintf(temp,"%d",v[i].first);
		ret = ret + " " + (char)(v[i].second+'A');
	}
	return ret;
}


void dfs(int n, int a, int b, int c, int s)
{
	if(n>N) return;
	if(a>300) return;
	if(b>300) return;
	if(c>300) return;

	if(n>0)
	if(solved<s )
	{
		for(int i=0;i<20;i++)
			minrun[i]=run[i];
		solved=s;
		penalty=calcp(n);
		sequence=calcoutput(n);
	}	
	else if(solved==s && n>0)
	{
		int p=calcp(n);
		if(p<penalty)
		{
			for(int i=0;i<20;i++)
				minrun[i]=run[i];
			solved=s;
			penalty=p;
			sequence=calcoutput(n);
		}
		else if(p==penalty)
		{
			string se=calcoutput(n);
			if(se<sequence)
			{
				for(int i=0;i<20;i++)
					minrun[i]=run[i];
				sequence=se;
			}
		}
	}
	if(n==N) return;
	int &r=run[n];
	if(n==st) dfs(n+1,a,b,c,s);
	else
	{		
		r=1;
		dfs(n+1, a+data[n].first,b,c,s+1);
		if(a+data[n].first!=b)
		{
			r=2;
			dfs(n+1, a,b+data[n].first,c,s+1);
			if(b+data[n].first!=c)
			{
				r=3;
				dfs(n+1,a,b,c+data[n].first,s+1);	
			}
		}
		r=0;
	}
}

int main()
{
	clock_t start=clock();
	int Cases;
	cin >> Cases;
		memset(run,0,sizeof(run));
	for(int TC=0;TC<Cases;TC++)
	{
		cout << "Data set "<<TC+1<<":";
		cin >> N;
		int m=9999, mindex;
		for(int i=0;i<N;i++)
		{
			cin >> data[i].first;
			data[i].second= i;
			if(m>data[i].first)
			{
				m=data[i].first;
				mindex=i;
			}
		}

		sort(data, data+N);
		memset(run,0,sizeof(run));
		memset(minrun,0,sizeof(minrun));
		run[0]=1;
		minrun[0]=1;
		solved=1;		
		penalty=m;
		st=0;
		sequence = calcoutput(1);
		calcp(1);
		dfs(0,m,0,0,1);

		cout <<sequence << " " <<solved << " " << penalty << endl;
	}
	clock_t end=clock();
//	cout << "time : " << (end-start)/(double)(CLOCKS_PER_SEC) << endl;
	return 0;
}

J. PropBot

원점에서 출발해서
앞으로 가거나, 45도 방향을 오른쪽으로 틀 수 있는 로봇이 있다.
가거나 돌때는 1초씩 걸리는데
최대 n초후에 목표 지점에 얼마나 가까이 갈 수 있는지 계산하는 문제.

8번 넘게 돌아가는 경우는 고려해볼 필요가 없다.

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <ctime>


struct status{
	float x,y;	
	short d;
	short time;
};

using namespace std;


float dx[8],dy[8];

float xx[100],yy[100];
float mindis[100];
int sec[100];

int main()
{	
	clock_t start=clock();
	for(int i=0;i<8;i++)
		dx[i]=cos(2.0*M_PI*((float)i/8.0))*10.0;
	for(int i=0;i<8;i++)
		dy[i]=sin(2.0*M_PI*((float)-i/8.0))*10.0;

	int TestCases;
	cin >> TestCases;
	for(int i=0;i<TestCases;i++)
	{
		cin >> sec[i] >> xx[i] >> yy[i];
	}

	{
		status init;
		init.x=0;
		init.y=0;
		init.time=0;
		init.d=0;

		queue<status> q;

		q.push(init);
		for(int i=0;i<TestCases;i++)
			mindis[i]=(xx[i]*xx[i]+yy[i]*yy[i]);
		while(!q.empty())
		{
			status cur=q.front();
			q.pop();
			for(int i=0;i<TestCases;i++)			
			{
				if(sec[i]>=cur.time)
				{
					float dis=((cur.x-xx[i])*(cur.x-xx[i])+(cur.y-yy[i])*(cur.y-yy[i]));
					mindis[i]=min(dis,mindis[i]);
				}
			}

			if(cur.time<24)
			{
				status newcur=cur;
				newcur.time++;				
				newcur.y+=dy[cur.d];
				newcur.x+=dx[cur.d];
				q.push(newcur);

				newcur=cur;
				newcur.time++;
				newcur.d++;
				newcur.d%=8;
				q.push(newcur);
			}
		}
	}


	for(int i=0;i<TestCases;i++)
		printf("%.6lf\n",sqrt(mindis[i]));
	clock_t end=clock();
	cout << end-start << endl;
	return 0;
}

K. "Ancient" Calculator

문제가 길이서 어쩔까 고민하다가 대회시간안에 못푼 문제
쉬웠다.

#include <iostream>
#include <cstring>

using namespace std;

int spend[3000];

int seg[10]={6,2,5,5,4,5,6,3,7,6};

int calc(int a)
{
	if(a<-999 || a>999) return -9999999;
	if(spend[a+1000]!=-1) return spend[a+1000];

	int &ret = spend[a+1000];
	ret=0;
	if(a<0){ ret++; a=-a;}
	if(a==0) ret=seg[0];
	while(a>0)
	{
		ret+=seg[a%10];
		a/=10;
	}
	
	return ret;
}

int main()
{
	memset(spend,-1,sizeof(spend));
	while(1)
	{
		int a,b,c;
		cin >>a;
		if(a==0) break;
		cin >> b;
		cin >> c;
		int cnt=0;
		for(int i=-999;i<1000;i++)
			if(calc(i)*5==a)
				for(int j=-999;j<1000;j++)
				{
					if(calc(j)*5==b)
					{
						if(c==calc(i+j)*5)
							cnt++;
						if(c==calc(i-j)*5)
							cnt++;
						if(c==calc(i*j)*5)
							cnt++;
						if(j!=0&&c==calc(i/j)*5)
							cnt++;
					}
				}
		if(cnt>1 || cnt==0)
			cout << cnt << " solutions for "<<a<< " " << b << " " << c<< endl;
		else
			cout << cnt << " solution for "<<a<< " " << b << " " << c<< endl;
	}
	
	return 0;
}

_M#]