# 演算法課程題解 - 暴力與窮舉 1

# UVa 100
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?100

## 解法 By Koios1143
### 想法
因為無法透過一個公式或有效率的方式得到每個數字的 cycle length，因此直接暴力跑過，計算每個數值的 cycle length，再留下最大值即可。
需要注意的是，題目中並沒有保證 $i$ $j$ 的大小關係。

### AC code

// By Koios1143
#include<iostream>
using namespace std;
int f(int n){
	if(n == 1)
		return 1;
	if(n%2 == 1)
		return f(3*n+1)+1;
	else
		return f(n/2)+1;
}
int main(){
	int i, j;
	while(cin>>i>>j){
		cout<<i<<" "<<j<<" ";
		if(i > j)
			swap(i, j);
		int ans=0;
		for(int k=i ; k<=j ; k++){
			ans = max(ans, f(k));
		}
		cout<<ans<<"\n";
	}
	return 0;
}

# UVa 12289
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?12289

## 解法 by tim25871014

### 想法

形如`on?`、`o?e`、`?ne`的都是1，五個字母的是3，剩下都是2。

### AC code

#include <iostream>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> in;
        int check = 2;
        if(s[0] == 'o' && s[1] == 'n') check = 1;
        if(s[0] == 'o' && s[2] == 'e') check = 1;
        if(s[1] == 'n' && s[2] == 'e') check = 1;
        if(s.size() == 5) check = 3;
        cout << check << endl;
    }
}

# UVa 10377
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10377

## 解法 By Koios1143
### 想法
跟著給定的操作走即可。
為了方便處理方向，我把 北(N)、東(E)、南(S)、西(W) 分別以 0、1、2、3 表示。
如此一來當我要向右轉，就只需要把方向加上 $1$，然後再模 $4$。
> 可以想成，$3$ 加上 $1$ 之後希望變成 $0$，所以需要再扣掉 $4$
> 用 mod 的方式也是相同

反之，如果要向左轉，就只需要把方向減去 $1$，當數字小於 $0$，就要回到 $3$，因此加上 $4$。

至於前進時要怎麼處理 $x, y$ 座標，我們可以製作兩個陣列，分別表示 $x, y$ 的變移量
我習慣上喜歡把列(row)當成 $x$ 軸，把行(column)當成 $y$ 軸，所以我可以整理出在面向不同方向時變化量分別是:

> $x$: $-1$, $0$, $1$, $0$
> $y$: $0$, $1$, $0$, $-1$

### AC Code

// By Koios1143
#include<iostream>
using namespace std;
string s;
int T, N, M, x, y, dir;
char op, arr[10000][10000];
char face[] = {'N', 'E', 'S', 'W'};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
	bool out = false;
	cin>>T;
	while(T--){
		if(out)
			cout<<"\n";
		else
			out = true;
		
		cin>>N>>M;
		getchar(); // To avoid getline receive new line (RF)
		for(int i=1 ; i<=N ; i++){
			getline(cin, s);
			for(int j=1 ; j<=M ; j++){
				arr[i][j] = s[j-1];
			}
		}
		cin>>x>>y;
		dir = 0;
		while(cin>>op && op != 'Q'){
			if(op == 'R'){
				dir = (dir + 1)%4;
			}
			else if(op == 'L'){
				dir--;
				if(dir < 0)
					dir += 4;
			}
			else if(op == 'F'){
				int nx = x + dx[dir];
				int ny = y + dy[dir];
				if(arr[nx][ny] == '*' || nx <= 0 || ny <= 0 || nx > N || ny > M)
					continue;
				x = nx;
				y = ny;
			}
		}
		cout<<x<<" "<<y<<" "<<face[dir]<<"\n";
	}
	
	return 0;
}

# UVa 608
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?608

## 解法 By Koios1143
### 想法
我沒有想到什麼很有效率的判斷方式，不過既然硬幣的數量很少，也知道必定只有一個假硬幣，也就是答案是唯一的，那麼可以直接假設每個硬幣是假硬幣的情況下，是否能符合每次秤重的結果即可。

### AC Code

// By Koios1143
#include<iostream> 
using namespace std;
int T, coins[20];
string LeftItem[3], RightItem[3], Res[3];

bool check(){
	bool ret = true;
	for(int i=0 ; i<3 ; i++){
		int L=0, R=0;
		for(int j=0 ; j<LeftItem[i].size() ; j++){
			L += coins[LeftItem[i][j]-'A'];
		}
		for(int j=0 ; j<RightItem[i].size() ; j++){
			R += coins[RightItem[i][j]-'A'];
		}
		if((L == R && Res[i] == "even") || (L > R && Res[i] == "up") || (L < R && Res[i] == "down"))
			ret &= true;
		else
			ret &= false;
	}
	return ret;
}

int main(){
	cin>>T;
	while(T--){
		bool found = false;
		for(int i=0 ; i<3 ; i++){
			cin>>LeftItem[i]>>RightItem[i]>>Res[i];
		}
		for(int fake=0 ; fake<12 ; fake++){ // 枚舉誰是假幣的情況
			for(int w=-1 ; w<=1 && !found ; w+=2){ // 枚舉假幣是輕或重
				//init
				for(int i=0 ; i<12 ; i++){
					coins[i] = 0;
				}
				coins[fake] = w;
				if(check()){
					found = true;
					if(w == -1)
						cout<<(char)('A'+fake)<<" is the counterfeit coin and it is light.\n";
					else
						cout<<(char)('A'+fake)<<" is the counterfeit coin and it is heavy.\n";
				}
			}
			
		}
	}
	return 0;
}

# UVa 101
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?101
## 解法 by baie
### 想法
題目要求的四個動作可以歸納成兩種，分別是放到別堆和放回原本的位置，所以用sb實作放回原本的位置，用sb1放到別堆，再分別依照四種要求作細部修改
### 程式碼

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pob pop_back
int n,b[30];
int x,y,w,e,k;
vector<int> a[30];

void sb(int x)
{
	for(int i=0;i<a[b[x]].size();i++) 
		if(a[b[x]][i]==x) w = i+1;
	while(!a[b[x]].empty()&&a[b[x]].size()>w)
	{
		k = a[b[x]].back();
		a[b[x]].pob();
		a[k].pb(k);
		b[k] = k;
	}
}
void sb1(int x)
{
	for(int i=0;i<a[b[x]].size();i++) 
		if(a[b[x]][i]==x) w = i;
	a[b[y]].pb(a[b[x]][w]);
	for(int i=w+1;i<a[b[x]].size();i++)
		a[b[y]].pb(a[b[x]][i]),b[a[b[x]][i]] = b[y];
	while(!a[b[x]].empty()&&a[b[x]].size()>w)
		a[b[x]].pob();
}
int main()
{
	string s,s1;
	while(cin>>n)
	{
		for(int i=0;i<n;i++) a[i].clear();
		for(int i=0;i<n;i++) a[i].pb(i),b[i]=i;
		while(cin>>s)
		{
			if(s=="quit") break;
			else cin>>x>>s1>>y;
			if(b[x]==b[y]) continue;
			w=0,e=0;
			if(s=="move"&&s1=="onto")
			{
				sb(x);
				sb(y);
				a[b[y]].pb(a[b[x]].back()),a[b[x]].pob(); 
			}
			else if(s=="move"&&s1=="over")
			{
				sb(x);
				a[b[y]].pb(a[b[x]].back()),a[b[x]].pob(); 
			}
			else if(s=="pile"&&s1=="onto")	sb(y),sb1(x);
			else if(s=="pile"&&s1=="over")	sb1(x);
			b[x] = b[y];
		}
		for(int i=0;i<n;i++)
		{
			cout<<i<<":";
			for(int j=0;j<a[i].size();j++) cout<<" "<<a[i][j];
			cout<<endl;
		}
	}
	return 0;
}

### 複雜度分析
m為指令次數，時間複雜度為 $O(nm)$

# UVa 102
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?102
## 解法 by baie
### 想法
因答案需求如果搬移量一樣的話，以最小字典序輸出，且桶子只有三個。所以可以直接建好字典序表，直接窮舉每一個不同字典序的搬移量，最小最前的就是答案
### 程式碼

#include<bits/stdc++.h>
using namespace std;


int main()
{
	int a[3][3];
	bool b[3][3];
	int w[6][3] = {{0,2,1},{0,1,2},{2,0,1},{2,1,0},{1,0,2},{1,2,0}};
	while(cin>>a[0][0])
	{
		cin>>a[0][1]>>a[0][2];
		for(int i=1;i<3;i++) 
			for(int j=0;j<3;j++)
				cin>>a[i][j];
		memset(b,0,sizeof(b));
		int x,y,z,mi = 2147483647;
		for(int k=0,sum=0;k<6;sum=0,k++)
		{
			b[0][w[k][0]] = 1, b[1][w[k][1]] = 1, b[2][w[k][2]] = 1; 
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<3;j++)
				{
					if(!b[i][j]) 
						sum += a[i][j];
					else 
						b[i][j] = 0;
				}
			}
			if(sum < mi)
				x = w[k][0], y = w[k][1], z = w[k][2] , mi = sum;
		}
		char q[3] = {'B','G','C'};
		cout<<q[x]<<q[y]<<q[z]<<" "<<mi<<endl;
	}
	return 0;
} 

### 複雜度分析
時間複雜度為$O(1)$

# UVa 573
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?573
## 解法 by baie
### 想法
蝸牛一天的順序是爬->滑->變累，只要依照題目要求實作(注意變累是取締一天爬的長度的10%)，因結果只會有出井和滑回井底兩種，故break的條件如下：
1. 爬出井(要在滑之前判斷)
2. 滑回井底

如果達成條件則輸出狀況和目前天數，即為答案
### 程式碼

#include<bits/stdc++.h>
using namespace std;

int main()
{
    double h,u,d,f;
    while(cin>>h>>u>>d>>f&&h!=0)
    {
    	double sum = 0,e = (u * f) / 100;
		int w = 1;
        while(true)
        {
        	if(w>1) u -= e;
        	if(u<0) u = 0; 
        	sum += u;
            if(sum>h)
            {
            	cout<<"success on day "<<w<<endl;
                break;
            }
            sum -= d;
            if(sum<0)
            {
            	cout<<"failure on day "<<w<<endl;
                break;
            }
            w++;
        }
    }
    return 0;
}

### 複雜度分析
時間複雜度即為爬的天數w $O(w)$

# UVa 10310
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10310

## 解法 By Koios1143
### 想法
針對每一個洞，分別去計算到田鼠和狗之間的距離，判斷田鼠是否可以逃走。
需要注意的是，如果田鼠和狗同時到達洞，算是成功逃走的。

### AC Code

// By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int n;
double Gx, Gy, Dx, Dy, Hx, Hy, Rx, Ry;

double dis(double Ax, double Ay, double Bx, double By){
	return (pow(abs(Ax-Bx), 2) + pow(abs(Ay-By), 2));
}

int main(){
	while(cin>>n>>Gx>>Gy>>Dx>>Dy){
		bool escape=false;
		for(int i=0 ; i<n ; i++){
			cin>>Hx>>Hy;
			if(!escape && (dis(Hx, Hy, Gx, Gy) <= dis(Hx, Hy, Dx, Dy)/4.0)){
				escape = true;
				Rx = Hx;
				Ry = Hy;
			}
		}
		if(escape)
			cout<<fixed<<setprecision(3)<<"The gopher can escape through the hole at ("<<Rx<<","<<Ry<<").\n";
		else
			cout<<"The gopher cannot escape.\n";
	}
	return 0;
}

###### tags: `SCIST 演算法 題解`