---
# System prepended metadata

title: 程式設計研討專題

---



# Virtual Judge
https://vjudge.net/problem

# 程設第一周題目
## UVA459 集合數(DFS)
```cpp=
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <set>
#include <vector>
#include <deque>
using namespace std;
bool graph[26][26];
bool visited[26];
int n,nodes,count;
char maxAlphabet;
bool BFS(int num){
    if(visited[num]) return false;
    visited[num] = true;
    for(int i=0;i<nodes;i++){
        if(graph[num][i])
            BFS(i);
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    while(n--){
        memset(graph,false,sizeof(graph));
        memset(visited,false,sizeof(visited));
        count = 0;
        string temp;
        
        cin >> maxAlphabet;
        nodes = maxAlphabet-'A'+1;
        cin.ignore();
        while(getline(cin,temp)&&temp!=""){
            int node1 = temp[0] - 'A';
            int node2 = temp[1] - 'A';
            graph[node1][node2] = true;
            graph[node2][node1] = true;
        }
    
        for(int i=0;i<nodes;i++){
            if(BFS(i))
                count ++;
        }
        cout << count << endl;
        if(n!=0) cout << endl;
    }
}
```

## UVA10324 暴力解
```cpp=
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <set>
#include <vector>
#include <deque>
using namespace std;

string s;
int count = 0,n,i,j;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>s){
        count ++;
        cin >> n;
        cout << "Case " << count << ":\n";
        while(n--){
            cin >> i >> j;
            if(i>j) swap(i,j);
            bool same = true;
            for(int index=i;index<=j&&same;index++){
                if(s[index]!=s[i]) same = false;
            }
            if(same)
                cout << "Yes" << endl;
            else 
                cout << "No" << endl;
        }
    }

}
```
## UVA10142 模擬澳洲投票
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <cstring>
using namespace std;
bool flag = false;
int n,canditateNum,ballotsNum,votes[21],voteCount;
int maxVotes,minVotes;
string temp,candidate[21];
vector <int> maxIndex,minIndex;
vector <int> ballots[1000];
vector <int> elimated;
void refreshMin(int value,int index){
	for(int i=0;i<elimated.size();i++){
		if(index==elimated[i]) return;
	}
	if(value<minVotes){
		minIndex.clear();
		minVotes = value;
		minIndex.push_back(index);
	}
	else if(value==minVotes){
		minIndex.push_back(index);
	}
}

void countVotes(){
	double halfOfVotes = voteCount * 0.5;
	minVotes = 10000;
	for(int i=1;i<=canditateNum;i++){
		int vote = votes[i];
		if(vote >= halfOfVotes){
			flag = true;
			maxIndex.push_back(i);
			for(int j=i+1;j<=canditateNum;j++){
				if(votes[j]==vote){
					maxIndex.push_back(j);
					break;
				}
			}
			return;
		}//ended
		refreshMin(vote,i);
	}
}

void traverse(){
	memset(votes,0,sizeof(votes));
	voteCount = 0;
	for(int i=0;i<ballotsNum;i++){
		if(ballots[i].size()!=0){
			voteCount++;
			votes[ballots[i].front()] ++ ;
		}
	}
}

int main()
{	
	cin >> n;
	while(n--){
		maxIndex.clear();
		minIndex.clear();
		elimated.clear();
		for(int i=0;i<ballotsNum;i++) ballots[i].clear();
		flag = false;

		cin >> canditateNum;
		cin.ignore();
		for(int i=1;i<=canditateNum;i++){
			getline(cin,temp);
			candidate[i] = temp;
		}

		ballotsNum = 0;
		while(getline(cin,temp)&&temp!=""){
			int p;
			stringstream input(temp);
			while(input>>p){
				ballots[ballotsNum].push_back(p);
			}
			ballotsNum ++;
		}
		while(!flag){
			maxIndex.clear();
			minIndex.clear();
			traverse();
			countVotes();

			if(flag){
				for(int i=0;i<maxIndex.size();i++)
					cout << candidate[maxIndex[i]] << endl;
			}else{
				if(elimated.size()+minIndex.size()==canditateNum){
					for(int i=0;i<minIndex.size();i++)
						cout << candidate[minIndex[i]] << endl;
					break;
				}
				for(int i=0;i<minIndex.size();i++){
					elimated.push_back(minIndex[i]);
					for(int j=0;j<ballotsNum;j++){
						for(int k=0;k<ballots[j].size();k++){
							if(ballots[j][k]==minIndex[i]){
								ballots[j].erase(ballots[j].begin()+k);
							}
							
						}
					}
				}
					
			}
		}
		if(n!=0) cout << endl;
	}
}
```
## UVA10267 模擬小畫家
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <cstring>
#include <fstream>
using namespace std;
typedef char color;

char graph[251][251];
int m,n,x,y,x1,x2,y1,y2;
color c;
char instruction;
bool flag = false;

void dfs(int x,int y,color c,color nowcolor){
	if(x<1||y<1||x>m||y>n||graph[y][x]!=nowcolor) return;
	graph[y][x] = c;
	dfs(x+1,y,c,nowcolor);
	dfs(x-1,y,c,nowcolor);
	dfs(x,y+1,c,nowcolor);
	dfs(x,y-1,c,nowcolor);
}
void I(){
	memset(graph,'O',sizeof(graph));
}
void C(){
	memset(graph,'O',sizeof(graph));
}
void L(){
	graph[y][x] = c;
}
void V(){
	if(y1>y2) swap(y1,y2);
	for(int col=y1;col<=y2;col++)
		graph[col][x] = c;
}
void H(){
	if(x1>x2) swap(x1,x2);
	for(int row=x1;row<=x2;row++)
		graph[y][row] = c;
}
void K(){
	if(x1>x2) swap(x1,x2);
	if(y1>y2) swap(y1,y2);
	for(int row=x1;row<=x2;row++){
		for(int col=y1;col<=y2;col++)
			graph[col][row] = c;
	}
}
void F(){
	if(graph[y][x]!=c) dfs(x,y,c,graph[y][x]);
}
void S(string Name){
	cout << Name << endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cout << graph[i][j];
		cout << endl;
	}
}
int main()
{	
	while(!flag){
		cin >> instruction;
			if(instruction=='I'){
				cin >> m >> n;
				I();
			}
			else if(instruction=='C'){
				C();
			}
			else if(instruction=='L'){
				cin >> x >> y >> c;
				L();
			}
			else if(instruction=='V'){
				cin >> x >> y1 >> y2 >> c;
				V();
			}
			else if(instruction=='H'){
				cin >> x1 >> x2 >> y >> c;
				H();
			}
			else if(instruction=='K'){
				cin >> x1 >> y1 >> x2 >> y2 >> c;
				K();
			}
			else if(instruction=='F'){
				cin >> x >> y >> c;
				F();
			}
			else if(instruction=='S'){
				string name;
				cin >> name;
				S(name);
			}
			else if(instruction=='X')
			{
				flag = true;
			}else{
				string trash;
				getline(cin,trash);
			}
		}
}
```

## UVA10137 模擬分錢
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <int> v;
bool cmp(int n1,int n2){
  return n1 > n2;
}
int main(){
  int n,avg,rem,ans,t1,t2,tmp;
  while(cin >> n && n!=0){
    v.clear();
    avg = ans = 0;
    for(int i=0;i<n;i++){
      scanf("%d.%d",&t1,&t2);
      tmp = 100*t1 + t2;
      v.push_back(tmp);
      avg += tmp;
    }
    sort(v.begin(),v.end(),cmp);
    rem = avg % n;
    avg/=n;
    for(int i=0;i<rem;i++){
      ans += abs(v[i]-(avg+1)); //pay more person
    }
    for(int i=rem;i<v.size();i++){
      ans += abs(v[i]-avg); //pay less person
    }
    printf("$%.2f\n",ans/200.0);
  }


}
```
# 程設第二周題目

## UVA10191 模擬一天最長休息時間
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool visitTime[480];
int s,h1,m1,h2,m2,day=1;
int startMinute,napMinute,maxNapMinute,maxStartMinute;
string temp;
int convertMinute(int h,int m){
  return (h-10)*60 + m;
}
void findLongestNap(){
  startMinute = 0;
  napMinute = 0;
  maxNapMinute = 0;
  bool naping = false;
  for(int i=0;i<480;i++){
    if(!naping&&!visitTime[i]){
      startMinute = i;
      naping = true;
      napMinute ++;
    }else if(naping&&!visitTime[i]){
      napMinute ++;
    }else if(!naping&&visitTime[i]){
      continue;
    }else{
      naping = false;
      if(napMinute > maxNapMinute){
        maxNapMinute = napMinute;
        maxStartMinute = startMinute;
      }
      napMinute = 0;
    }

    if(i==479&&naping){
      if(napMinute > maxNapMinute){
        maxNapMinute = napMinute;
        maxStartMinute = startMinute;
      }      
    }
  }
}

void printAnswer(){
  int ansStartHour = 10 + (maxStartMinute /60);
  int ansStartMinute = maxStartMinute % 60;
  int ansLastHour = maxNapMinute / 60;
  int ansLastMinute = maxNapMinute % 60;
  if(ansLastHour == 0){
    if(ansStartMinute < 10){
      printf("Day #%d: the longest nap starts at %d:0%d and will last for %d minutes.\n",day++,ansStartHour,ansStartMinute,ansLastMinute);
    }else{
      printf("Day #%d: the longest nap starts at %d:%d and will last for %d minutes.\n",day++,ansStartHour,ansStartMinute,ansLastMinute);
    }
  }else{
    if(ansStartMinute < 10){
      printf("Day #%d: the longest nap starts at %d:0%d and will last for %d hours and %d minutes.\n",day++,ansStartHour,ansStartMinute,ansLastHour,ansLastMinute);
    }else{
      printf("Day #%d: the longest nap starts at %d:%d and will last for %d hours and %d minutes.\n",day++,ansStartHour,ansStartMinute,ansLastHour,ansLastMinute);
    }
  }
}
int main ()
{
  while(scanf("%d",&s)!=EOF){
    memset(visitTime,false,sizeof(visitTime));
    while(s--){
      scanf("%d:%d %d:%d",&h1,&m1,&h2,&m2); getline(cin,temp);
      int startMinute = convertMinute(h1,m1);
      int endMinute = convertMinute(h2,m2);
      for(int i=startMinute;i<endMinute;i++) visitTime[i] = true;
    }
    findLongestNap();
    //printf("%d %d\n",maxStartMinute,maxNapMinute);
    printAnswer();
  }

  return 0;
}
```
## UVA10152 模擬烏龜
```cpp=
#include <bits/stdc++.h>
using namespace std;
int k,n;

vector <string> origin;
vector <string> target;

int main(){
  cin >> k;
  for(int i=0;i<k;i++){
    cin >> n;
    cin.ignore();
    origin.clear();
    target.clear();
    for(int i=0;i<n;i++) {
      string temp;
      getline(cin,temp);
      origin.push_back(temp);
    }
    for(int i=0;i<n;i++) {
      string temp;
      getline(cin,temp);
      target.push_back(temp);
    }
    int pointerTarget,pointerOrigin;
    pointerTarget = pointerOrigin = n - 1;
    while(pointerOrigin >= 0){
      if(origin[pointerOrigin]==target[pointerTarget]) pointerTarget--;
      pointerOrigin --;
    }
    while(pointerTarget>=0){
      cout << target[pointerTarget--] << endl;
    }
    cout << endl;
  }
  
}
```
## UVA10026 greedy
```cpp=
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int n,c,minute,fine,number;
string temp;
struct work{
  int num;
  double priority;
  work(int minute,int fine,int num){
    this->priority = fine * 1.0 / minute;
    this->num = num;
  }
};
bool cmp(work a,work b){
  if(a.priority!=b.priority) return a.priority > b.priority;
  return a.num < b.num;
}
int main()
{	
  ios_base::sync_with_stdio(0);
  cin >> n;
  while(n--){
    vector <work> v;
    number = 1;
    cin >> c;
    for(int i=0;i<c;i++) {
      cin >> minute >> fine;
      work w(minute,fine,number ++);
      v.push_back(w);
    }

    sort(v.begin(),v.end(),cmp);
    for(auto w:v){
      cout << w.num;
      if(w.num!=v.back().num) cout << ' ';
    }
    cout << endl;
    if(n!=0) cout << endl;
  }

}
```
## UVA10044 題目輸入很奇怪的BFS==
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int s,p,n;
string temp,fName,lName;
vector <string> names;
map<string,set<string> > m;
map<string,lli> level;
void BFS(){
  queue <pair<string,lli> > q;
  level["Erdos,P."] = 0;
  q.push({"Erdos,P.",0});
  while(!q.empty()){
    string name = q.front().first; 
    lli l = q.front().second;
    q.pop();
    for(auto n:m[name]){    
      if(level.count(n)==0){
        level[n] = l + 1;
        q.push({n,l+1});
      }
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> s;
  for(int i=1;i<=s;i++){
    cout << "Scenario " << i << endl;
    m.clear();
    level.clear();
    cin >> p >> n;
    cin.ignore();

    while(p--){
      names.clear();
      getline(cin,temp);
      int cnt = 0;
      string name;
      for(int j=0;j<temp.size();j++){
        if(temp[j]==':')
          break;
        cnt += (temp[j]==',');
        if(cnt%2==0&&temp[j]==','){
          names.push_back(name);
          name = "";
          j ++;
        }
        else if (temp[j]==' ')
          continue;
        else
          name += temp[j];
      }
      names.push_back(name);
      for(int j=0;j<names.size();j++){
        for(int k=j+1;k<names.size();k++){
          m[names[j]].insert(names[k]);
          m[names[k]].insert(names[j]);
        }
      }
    }
    BFS();
    while(n--){
      getline(cin,temp);
      string name = "";
      for(int i=0;i<temp.length();i++){
        if(temp[i]!=' ')
          name += temp[i];
      }
      cout << temp << ' ';
      if(!level.count(name)){
        cout << "infinity" << endl;
      }else{
        cout << level[name] << endl;
      }
    }
  }
}
```
## UVA10138 模擬高速公路收費
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct photo{
  int hour,time,dis;
  bool first;
  photo(int d,int h,int m,bool first,int dis):
  hour(h),first(first),dis(dis){
    time = d * 24 * 60 + hour * 60 + m;
  }
  bool operator < (photo r) const{
    return this->time < r.time;
  }
};
int rate[24];
int main(){
  int c;
  int m,d,h,dis;
  char tmp;
  string s,license,status;
  cin >> c;
  while(c--){
    for(int i=0;i<24;i++)
      cin >> rate[i];
    cin.ignore();
    map<string,vector <photo>> licenseMap;
    while(getline(cin,s)&&!s.empty()){
      stringstream ss(s);
      ss >> license >> m >> tmp >> d >> tmp >> h >> tmp >> m >> status >> dis;
      photo p(d,h,m,(status=="enter"),dis);
      licenseMap[license].push_back(p);
    }
    for(auto l:licenseMap){
      sort(l.second.begin(),l.second.end());
      int sum = 200;
      for(int i=0;i<l.second.size();i++){
        if(l.second[i].first && i+1<l.second.size()&&!l.second[i+1].first){
          sum += (abs(l.second[i+1].dis-l.second[i].dis))*rate[l.second[i].hour] + 100;
        }
      }
      if(sum != 200){
        printf("%s $%.2f\n",l.first.c_str(),sum / 100.0);
      }
    }
    if(c)
      cout << '\n';
  }
}
```
# 程設第三周題目

## UVA10150 字串BFS+store path
```cpp=
#include <bits/stdc++.h>
using namespace std;
int parent[25500];
vector <string> v;
bool isDoublets(string s1,string s2){
  if(s1.length()!=s2.length())
    return false;
  if(s1==s2)
    return false;
  int cnt = 0;

  for(int i=0;i<s1.length()&&cnt<=1;i++){
    if(s1[i]!=s2[i])
      cnt ++;
  }
  return cnt == 1;
}

void printPath(int startPos,int endPos){
  if(startPos!=endPos)
    printPath(startPos,parent[endPos]);
  cout << v[endPos] << endl;
}
int main()
{	
  vector <string> words[17];
  string tmp,startStr,endStr;
  for(int i=1;i<17;i++){
    words[i].push_back("");
  }
  while(getline(cin,tmp)&&tmp.size()){
    words[tmp.size()].push_back(tmp);
  }

  int c = 0;
  while(cin >> startStr >> endStr){
    if(c++)
      cout << endl;
    if(startStr.size() != endStr.size()){
      cout << "No solution." << endl;
      continue;
    }
    int sSize = startStr.size();
    v = words[sSize];
    int startPos = find(v.begin(),v.end(),startStr)-v.begin();
    int endPos = find(v.begin(),v.end(),endStr)-v.begin();

    if(startPos==v.size()||endPos==v.size()){
      cout << "No solution." << endl;
      continue;
    }

    memset(parent,0,sizeof(parent));
    parent[startPos] = startPos;
    queue <int> q;
    q.push(startPos);
    while(!q.empty()&&q.front()!=endPos){
      int u = q.front();
      q.pop();

      for(int w=0;w<v.size();w++){
        if(!parent[w]&&isDoublets(v[u],v[w])){
          parent[w] = u;
          q.push(w);
        }
      }
    }

    if(!parent[endPos])
      cout << "No solution." << endl;
    else
      printPath(startPos,endPos);
  }
}
```

## UVA719 
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n,len,targetIndex;
string str; 
string targetStr;
int main()
{	
  cin >> n;
  while(n--){
    cin >> str;
    targetIndex = 0;
    len = str.length();
    string targetStr = str;
    str += str;
    for(int i=1;i<len;i++){
      string temp = str.substr(i,len);
      if(temp < targetStr){
        targetIndex = i;
        targetStr = temp;
      }
    }
    cout << targetIndex + 1 << endl;
  }
  return 0;
}

```
## UVA10298 KMP algorithm
```cpp=
#include <bits/stdc++.h>
using namespace std;
int nexts[1000001];
string s;
void getnext(){
  int j=0,k=-1;
  nexts[0] = -1;
  while(j<s.length()){
    if(k==-1||s[j]==s[k])
      nexts[++j] = ++k;
    else {
      while(k!=-1 && s[j]!=s[k])
        k = nexts[k];
    }
  }
}
int main(){
  while(cin >> s&&s!="."){
    getnext();
    int repeatLen = s.length() - nexts[s.length()];
    // for(int i=0;i<s.length();i++)
    //   cout << nexts[i] << ' ';
    if(s.length()%repeatLen==0)
      cout << s.length() / repeatLen << endl;
    else
      cout << 1 << endl;
  }

}
```
## UVA10679 (可用KMP or 函式庫)
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
  int c,n;
  char s[100001],subs[1001];
  cin >> c;
  while(c--){
    cin >> s;
    cin >> n;
    while(n--){
      cin >> subs;
      cout << (strstr(s,subs)?"y":"n") << endl;
    }
  }
}
```
## UVA10234 子字串暴力解
```cpp=
#include <bits/stdc++.h>
using namespace std;

map <string,int> m;
int main(){
  string s;
  int t;
  int len;
  while(getline(cin,s)){
    for(auto &ch:s){
      if(isupper(ch))
        ch = ch - ('A'-'a');
    }
    cin >> t;
    while(t--){
      m.clear();
      int maxCnt = -1;
      string ans;
      cin >> len;
      for(int i=0;i<s.size()-len+1;i++){
        string tmp = s.substr(i,len);
        if(!m.count(tmp)){
          m[tmp] = 1;
          if(m[tmp]>maxCnt){
            maxCnt = m[tmp];
            ans = tmp;
          }else if(m[tmp]==maxCnt){
            if(ans>tmp)
              ans = tmp;
          }
        }
        else{
          m[tmp]++;
          if(m[tmp]>maxCnt){
            maxCnt = m[tmp];
            ans = tmp;
          }else if(m[tmp]==maxCnt){
            if(ans>tmp)
              ans = tmp;
          }
        }
      }
      cout << m[ans] << ' ' << ans << endl;
    }
    cin.ignore();
  }
}
```

# 程設第四周題目

## UVA10023 開大數根號(Babylonian method)
```python=
t = int(input())

for i in range (t):
    n = input()
    n = int(input())
    if(i>0):
        print('')
    
    x = 1
    y = n
    while(abs(x-y) > 0.001):
        x = (x+y)//2
        y = n//x

    print(x)
```
## UVA10127 ONEs
```cpp=
#include <bits/stdc++.h>
using namespace std;
int num,cnt;
int main(){
  int n;
  while(cin >> n){
    num = cnt = 1;
    while(num%n!=0){
      num %= n;
      num *= 10;
      num += 1;
      cnt ++;
    }
    cout << cnt << endl;
  }
  return 0;
}
```
## UVA10083 大數運算求餘數((a^b-1) mod (a^c-1) if b%c==0)
```python=
import math
while 1:
  try:
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    c = int(c)
    ans = 0
    if b%c==0 and a!=1:
      if b==c:
        ans = 1
      elif (b-c)*math.log(a,10)+1 < 100: #ans is less than 100
        ans = (a**b-1) // (a**c-1)
    
    print(f"({a}^{b}-1)/({a}^{c}-1) ",end="")
    if ans:
      print(ans)
    else:
      print("is not an integer with less than 100 digits.")
  except EOFError:
    break

```

## UVA10202 
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n,temp,t;
vector<int> nums;
bool flag;

int main(){
  while(cin>>n){
    nums.clear();
    flag = false;
    t = n*(n-1)/2;
    for(int i=0;i<t;i++){
      cin >> temp;
      nums.push_back(temp);
    }
    sort(nums.begin(),nums.end());
    

    for(int i=2;i<nums.size();i++){
      bool notSol = false;
      vector <int> ans;
      vector <int> v = nums;
      int s0 = v[0],s1 = v[1],s2 = v[i]; //s2 = a1+a2 s1 = a2+a0 s0 = a1+a0
      int a0 = (s0+s1-s2)/2;
      ans.push_back(a0);
      ans.push_back(v[0]-a0);//a1
      ans.push_back(v[1]-a0);//a2
      v.erase(v.begin()+i); v.erase(v.begin()); v.erase(v.begin());//remove a0,a1,a2
      for(int j=3;j<n&&!notSol;j++){
        ans.push_back(v.front()-a0);
        v.erase(v.begin()); //a[j] = v[0]-a0
        for(int k=1;k<j;k++){
          int t = ans[j] + ans[k]; // erase a[j]+a[k],1<=k<j
          auto it = find(v.begin(),v.end(),t);
          if(it!=v.end()){
            v.erase(it);
          }else{
            notSol = true;
          }
        }
      }

      if(!notSol&&ans[ans.size()-1]+ans[ans.size()-2]==nums.back()){ //prevent a0+a2!=v[2]
        for(int i=0;i<ans.size();i++){
          if(i)
            cout << ' ';
          cout << ans[i];
        }
        cout << '\n';
        flag = true;
        break;
      }
    }
    
    if(!flag)
      cout << "Impossible\n"; 
  }
  return 0;
}
```

## UVA11264 greedy
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <int> v;
int main(){
  int c,t,tmp,ans,sum,last_coin;
  cin >> c;
  while(c--){
    v.clear();
    cin >> t;
    while(t--){
      cin >> tmp;
      v.push_back(tmp);
    }
    sort(v.begin(),v.end());
    ans = sum = 0;
    for(int i=0;i<v.size();i++){
      if(sum<v[i]){
        ans ++;
        sum += v[i];
      }else{
        sum -= last_coin;
        sum += v[i];
      }
      last_coin = v[i];
    }
    cout << ans << endl;
  }

}
```

# 程設第五周題目

## UVA10128 身高排列組合
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long unsigned int llu;
llu dp[14][14][14] = {0};
int t,n,p,r;
void countPermutation(){
  dp[1][1][1] = 1;
  for(int i=2;i<=13;i++){
    for(int j=1;j<=i;j++){
      for(int k=1;k<=i;k++){
        dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j][k-1] + (i-2)*dp[i-1][j][k];
      }
    }
  }
}
int main(){
  countPermutation();
  cin >> t;
  while(t--){
    cin >> n >> p >> r;
    cout << dp[n][p][r] << endl;
  }
}
```

## UVA10157 括號排列組合(dp recursion)
```python=
dp = [[0 for _ in range (151)]for _ in range(151)]
visit = [[0 for _ in range (151)]for _ in range(151)]
#dp[i][j] means i pairs(),max depth is j

def DP(n: int,d: int)->int:
  if visit[n][d]:
    return dp[n][d]
  
  visit[n][d] = 1

  if n==0:
    dp[n][d] = 1
    return 1
  if n>0 and d==0:
    dp[n][d] = 0
    return 0
  dp[n][d] = 0
  for i in range(n):
    dp[n][d] += DP(i,d-1) * DP(n-i-1,d)
  
  return dp[n][d]

while True:
  try:
    string = str(input())
    n,d = string.split()
    n = int(n)
    d = int(d)
    n//=2
    print(DP(n,d)-DP(n,d-1))
  except EOFError:
    break
```

## UVA10590 完全背包
```python=
maxnum = 5001
dp = [0 for i in range(maxnum)]

def countWays():
  dp[0] = 1
  for i in range(1,maxnum):
    for j in range(i,maxnum):
      dp[j] += dp[j-i]

countWays()
while True:
  try:
    n = int(input())
    print(dp[n])
  except EOFError:
    break

```
## UVA11038 算有多少0
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define u_int unsigned int 
u_int countZero(u_int n){
  u_int digit = 1,target;
  u_int sum = 0,N = n;
  while(N>=10){
    target = N%10; //nth num
    N/=10;
    if(target >=1) 
      sum += N*digit; 
    else // target == 0
      sum += (N-1)*digit + n%digit + 1;
    digit *= 10;
  }
  return sum;
}
int main(){
  u_int n1,n2;
  while(cin >> n1 >> n2&&n1!=-1){
    u_int ans = countZero(n2) - countZero(n1);
    if (n1==0)
      ans ++;
    while(n1!=0){
      if(n1%10==0)
        ans ++;
      n1 /= 10;
    }
    cout << ans << endl;
  }

}
```

# 程設第六周題目

## UVA10664 01背包問題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int t,sum,n;
bool dp[40001];
vector<int> values;
string temp;
int main(){
  cin >> t;
  cin.ignore();
  while(t--){
    memset(dp,false,sizeof(dp));
    dp[0] = true;
    values.clear();
    sum = 0;
    getline(cin,temp);
    stringstream ss(temp);
    while(ss>>n){
      sum += n;
      values.push_back(n);
    }
    if(sum % 2!=0){
      cout << "NO" << endl;
      continue;
    }
    sum = sum >> 1;
    for(auto v:values){
      for(int i = sum-v;i>=0;i--)
        if(dp[i]&&!dp[i+v])
          dp[i+v] = true;
    }
    if(dp[sum])
      cout << "YES" << endl;
    else  
      cout << "NO" << endl;

  }
}
```
## UVA10261 01背包變化題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int c,tmp;
bool dp[201][10001];
bool route[201][10001];
vector <int> cars;
vector <int> sum;
int totalCarLen = 0;
int maxCar,maxLen,len;
int main(){
  cin >> c;
  while(c--){
    cin >> len;
    len *= 100;
    cars = {0};
    sum = {0};
    memset(dp,0,sizeof(dp));
    totalCarLen = maxCar = maxLen = 0;
    while(cin >> tmp && tmp != 0){
      cars.push_back(tmp);
      totalCarLen += tmp;
      sum.push_back(totalCarLen);
    }
    dp[0][0] = 1;
    for(int i=1;i<cars.size();i++){
      for(int j=0;j<=len;j++){
        if(j>=cars[i]&&dp[i-1][j-cars[i]]){ //put left
          maxCar = i;
          maxLen = j;
          dp[i][j] = 1;
          route[i][j] = 0; // put left
        }
        if(sum[i]-j<=len && dp[i-1][j]){ //put right
          maxCar = i;
          maxLen = j;
          dp[i][j] = 1;
          route[i][j] = 1; // put right
        }
      }
      if(maxCar != i) break; //can't put left nor right
    }

    cout << maxCar << endl;

    int i = maxCar,j = maxLen;
    stack <bool> pos;
    while(i){ // track the route
      pos.push(route[i][j]);
      if(!route[i][j]) // put left
        j -= cars[i];
      i --;
    }
    while(!pos.empty()){
      bool p = pos.top(); pos.pop();
      if(!p) // left
        cout << "starboard" << endl;
      else  //right
        cout << "port" << endl;
    }

    if(c)
      cout << endl;
  }
  return 0;
}
```
## UVA10482 01背包變化題
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool dp[641][641]; //dp[i][j] means children get value i,j and wSum-i-j
vector <int> w; //candies' weight
int findMax(int i,int j,int k){
  return max(i,max(j,k));
}
int findMin(int i,int j,int k){
  return min(i,min(j,k));
}
int main(){
  int t,tmp,numCandy,wSum,ans;
  cin >> t;
  for(int c=1;c<=t;c++){
    w.clear();
    memset(dp,false,sizeof(dp));
    dp[0][0] = 1;
    wSum = 0;
    ans = INT32_MAX;

    cin >> numCandy;
    while(numCandy--){
      cin >> tmp;
      w.push_back(tmp);
      wSum += tmp;
    }

    for(int k=0;k<w.size();k++){
      for(int i=wSum;i>=0;i--){
        for(int j=wSum;j>=0;j--){
          dp[i][j] = (dp[i][j]||(i>=w[k]&&dp[i-w[k]][j])||(j>=w[k]&&dp[i][j-w[k]]));//for first or second or third child
        }
      }
    }
    for(int i=0;i<=wSum;i++){
      for(int j=i;j<=wSum;j++){
        if(dp[i][j]){
          int wThird = wSum - i - j;
          ans = min(ans,findMax(i,j,wThird)-findMin(i,j,wThird));
        }
      }
    }
    printf("Case %d: %d\n",c,ans);
  }


}
```
## UVA10032 背包問題空間壓縮(bits operation)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int c,n,tmp,wSum;
vector<int> w;
long long int bitsHalf;// the w.size()/2 bit = 1
long long int dp[45001];//dp[i] means weight i consists of people
// using bits operation to find ans

void sol(){
  if(w.size()==1){
    printf("%d %d\n",0,wSum);
    return;
  }

  bitsHalf = (1ll << (w.size()/2));
  int lighter,heavier;
  int minDiff = INT_MAX;

  for(int i=0;i<w.size();i++){
    for(int j=wSum;j>=w[i];j--){
      dp[j] |= (dp[j-w[i]] << 1); //knapstack problem
    }
  }

  for(int i=1;i<=wSum;i++){
    if((dp[i] & bitsHalf)==bitsHalf){
      if(minDiff > abs(wSum-i-i)) { // finding min difference (wSum-i) = weight1, i = weight2
        minDiff = abs(wSum-i-i);
        lighter = min(i,wSum-i);
        heavier = wSum - lighter;
      }
    }
  }
  printf("%d %d\n",lighter,heavier);
}

int main(){
  cin >> c;
  while(c--){
    w.clear();
    memset(dp,0,sizeof(dp));
    wSum = 0;
    dp[0] = 1; 
    cin >> n;
    while(n--){
      cin >> tmp;
      wSum += tmp;
      w.push_back(tmp);
    }
    sol();
    if(c)
      printf("\n");
  }
}
```
## UVA11372 dp recursion
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct problem{
  string id;
  char level;
  char type;
  int favor;
  bool operator < (const problem& p) const{
    return this->id < p.id;
  };
}p[210];
pair<string,int> dp[210][7][3][3][5][4][4]; //string: problems, int: sum
//dp[problem[N]][remain][easy][hard][DPproblem][MathProblem][GraphProblem]
int n;

void init(){
  for(int i=0;i<210;i++){
    for(int j=0;j<7;j++){
      for(int k=0;k<3;k++){
        for(int l=0;l<3;l++){
          for(int m=0;m<5;m++){
            for(int n=0;n<4;n++){
              for(int o=0;o<4;o++){
                dp[i][j][k][l][m][n][o].first = "";
                dp[i][j][k][l][m][n][o].second= -1;
              }
            }
          }
        }
      }
    }
  }
}

pair<string,int> DP(int N,int remain,int easy,int hard,int D,int M,int G){
  if(n-N<remain)  // not sol
    return dp[N][remain][easy][hard][D][M][G] = make_pair("",0);
  if(remain == 0){
    if(easy==2 && hard==2 && D>=2 && M>=1 && G>=1) // is sol
      return dp[N][remain][easy][hard][D][M][G] = make_pair("",1);
    else //not sol
      return dp[N][remain][easy][hard][D][M][G] = make_pair("",0);
  }
  if(easy>2 || hard>2 || D>4 || M>3 || G>3 ){ // not sol
    return dp[N][remain][easy][hard][D][M][G] = make_pair("",0);
  }

  if(dp[N][remain][easy][hard][D][M][G].second != -1) // avoid remarking
    return dp[N][remain][easy][hard][D][M][G];

  int te = easy,th = hard,td = D,tm = M,tg = G;
  if(p[N].level=='E') te ++;
  if(p[N].level=='H') th ++;
  if(p[N].type=='D') td ++;
  if(p[N].type=='M') tm ++;
  if(p[N].type=='G') tg ++;
  pair<string,int> temp,pick,notPick;
  temp.first = "",temp.second = 0;
  pick = DP(N+1,remain-1,te,th,td,tm,tg);
  if(pick.second > temp.second){
    temp.second = pick.second + p[N].favor;
    if(pick.first == ""){
      temp.first = p[N].id;
    }else{
      temp.first = p[N].id + " " + pick.first;
    }
  }
  notPick = DP(N+1,remain,easy,hard,D,M,G);
  if(notPick.second > temp.second){
    temp = notPick;
  }
  return dp[N][remain][easy][hard][D][M][G] = temp;

}

void sol(){
  string tmp;
  while(cin>>n&&n){
    init();
    for(int i=0;i<n;i++){
      cin >> p[i].id >> tmp >> p[i].level >> p[i].type >> p[i].favor;
    }
    sort(p,p+n);
    pair <string,int> ans = DP(0,6,0,0,0,0,0);
    if(ans.second == 0)
      printf("No solution.\n");
    else
      cout << ans.first << endl;
  }
}

int main(){
  sol();
}
```

# 程設第七周題目

## UVA10069 LCS算路徑數
```python=
t = int(input())
while(t):
  t -= 1
  s1 = " "
  s2 = " "
  s1 += str(input())
  s2 += str(input())
  dp = [[0 for i in range (len(s1)+1)]for j in range(len(s2)+1)]
  for i in range(len(s1)):
    dp[0][i] = 1
  for i in range(1,len(s2)):
    for j in range(1,len(s1)):
      if s2[i] == s1[j]:
        dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
      else:
        dp[i][j] = dp[i][j-1]

  print(dp[len(s2)-1][len(s1)-1])
```
## UVA164 LCS track路徑
```cpp=
#include <bits/stdc++.h>
#define N 21

using namespace std;
int dp[N][N];
int procedure[N][N];
string a,b;

///find the optimized option
void findIdealPath(int i,int j){
  int p = 0;
  if(dp[i][j]>dp[i-1][j] + 1){
    dp[i][j] = dp[i-1][j] + 1;
    p = 1; //delete
  }
  if(dp[i][j]>dp[i][j-1] + 1){
    dp[i][j] = dp[i][j-1] + 1;
    p = 2; //insert
  }
  if(dp[i][j]>dp[i-1][j-1]+(a[i-1]==b[j-1]?0:1)){
    dp[i][j] = dp[i-1][j-1]+(a[i-1]==b[j-1]?0:1);
    if(a[i-1]!=b[j-1])
      p = 3;//change
    else
      p = 0;//do nothing
  }
  procedure[i][j] = p;//mark the path
}

/// print answer by prodedure[i][j]
void printAnswer(int i,int j){
  if(i==0&&j==0) return;
  if(i<0||j<0) return;
  if(procedure[i][j]==1){ //delete a[i-1], position j+1
    printAnswer(i-1,j);
    printf("D%c%02d",a[i-1],j+1);
  }
  if(procedure[i][j]==2){ //insert b[j-1], position j
    printAnswer(i,j-1);
    printf("I%c%02d",b[j-1],j);
  }
  if(procedure[i][j]==3){
    printAnswer(i-1,j-1);
    printf("C%c%02d",b[j-1],j); //a[i-1] = b[j-1] position j
  }
  if(procedure[i][j]==0){
    printAnswer(i-1,j-1);
  }
}
int main(){
  while(cin >> a && a!="#"){
    cin >> b;
    dp[0][0] = 0;
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        dp[i][j] = 10000000; //initialize
      }
    }
    for(int i=0;i<=a.size();i++){
      dp[i][0] = i;
      procedure[i][0] = 1;
    }
    for(int i=0;i<=b.size();i++){
      dp[0][i] = i;
      procedure[0][i] = 2;
    }
    for(int i=1;i<N;i++){
      for(int j=1;j<N;j++){
        findIdealPath(i,j);
      }
    }
    printAnswer(a.size(),b.size());
    printf("E\n");
  }
}
```
## UVA10154 Moore's 
```cpp=
#include <bits/stdc++.h>
using namespace std;

struct turtle{
  int weight;
  int strength;
  turtle(int w,int s):weight(w),strength(s){}
  inline bool operator < (const turtle& r) const{
    return this->weight < r.weight;
  }
};
bool cmp(turtle l,turtle r){
  if(l.strength < r.strength)
    return true;
  if(l.strength == r.strength)
    return l.weight < r.weight;
  return false;
}
vector <turtle> tVec;
int main(){
  int w,s;
  int wSum = 0;
  while(cin >> w >> s&&w!=-1){
    turtle t(w,s);
    tVec.push_back(t);
  }
  sort(tVec.begin(),tVec.end(),cmp);
  priority_queue <turtle> q;
  for(int i=0;i<tVec.size();i++){
    q.push(tVec[i]);
    wSum += tVec[i].weight;
    if(wSum > tVec[i].strength){
      wSum -= q.top().weight;
      q.pop();
    }
  }
  cout << q.size() << endl;
}
```

## UVA10131 LIS紀錄路徑
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct Elephant{
  int n,w,s; // number,weight,smart
  Elephant(int n,int w,int s):n(n),w(w),s(s){}
  bool operator < (const Elephant &right) const{
    if(w==right.w){
      return s > right.s;
    }
    return w < right.w;
  }
};
int dp[1001];
int path[1001];
int w,s,c=1;
vector <Elephant> v;

void DFS(int n,int d){
  if(n==1){
    cout << v[d].n << endl;
  }else{
    DFS(n-1,path[d]);
    cout << v[d].n << endl;
  }
}
int main(){
  while(cin >> w >> s){
    Elephant e(c,w,s);
    v.push_back(e);
    c++;
  }
  int maximum = 1;
  sort(v.begin(),v.end());
  for(int i=0;i<v.size();i++)
    dp[i] = 1;
  for(int i=1;i<v.size();i++){
    for(int j=0;j<i;j++){ // check previous elephant
      if(v[i].w > v[j].w && v[i].s < v[j].s && dp[i]<dp[j]+1){
        dp[i] = dp[j] + 1;
        path[i] = j;
        maximum = max(maximum,dp[i]);
      }  
    }
  }
  cout << maximum << endl;
  
  for(int i=v.size()-1;i>=0;i--){
    if(dp[i]==maximum){
      DFS(maximum,i);
      break;
    }
  }
}
```
## UVA10201 dp
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483637
struct gas_station{
  int dis;
  int val;
};
int dp[105][205]; //dp[i][j] means at the i gas station,j oil min cost
int n,dis,val,endDis;
vector <gas_station> v;
string temp;
int main(){
  cin >> n;
  cin.ignore(); cin.ignore();
  while(n--){
    v.clear();
    v.push_back({0,0});
    cin >> endDis;
    cin.ignore();
    while(getline(cin,temp)&&temp!=""){
      stringstream ss(temp);
      ss >> dis >> val;
      if(dis<endDis){
        gas_station g = {dis,val};
        v.push_back(g);
      }
    }
    for(int i=0;i<101;i++){
      for(int j=0;j<201;j++)
        dp[i][j] = INF;
    }
    dp[0][100] = 0;
    for(int i=1;i<v.size();i++){ //i gas_station
      int temp = v[i].dis - v[i-1].dis;
      for(int j=0;j<=200;j++){ // j
        for(int k=0;k<=j;k++){ // add k oil
          if(j + (temp - k)<=200&&dp[i-1][j+(temp-k)]!=INF&&dp[i][j]>dp[i-1][j+temp-k]+v[i].val*k){
            dp[i][j] = dp[i-1][j+temp-k]+v[i].val*k;
          }
        }
      }
    }
    if(endDis-v.back().dis>100 || dp[v.size()-1][endDis-v.back().dis+100]==INF)
      cout << "Impossible\n";
    else
      cout << dp[v.size()-1][endDis-v.back().dis+100] << '\n';
    if(n)
      cout << '\n';
  }

}
```
# 程設第八周題目
## UVA11064 Euler's formula、primes、factors
```cpp=
#include <bits/stdc++.h>
#define N 150000
using namespace std;
#define print(i) cout << #i << ' ' << i << '\n';
bool visited[N];
int n;
vector <int> primes;
int powers[N],bases[N];
int main(){
  fill(visited,visited+N,0);


  for(int i=2;i<N;i++){
    if(!visited[i]){
      primes.push_back(i);
      for(int j=i;j<N;j+=i){
        visited[j] = true;
      }
    }
  }

  while(cin >> n && n){
    fill(bases,bases+N,0);
    fill(powers,powers+N,0);
    int c = 0,m = n;
    for(auto b:primes){
      if(n<=1) break;
      if(n%b==0){
        bases[c] = b;
        while(n%b==0){
          n/=b;
          powers[c]++;
        }
        c++;
      }
    }
    // n is prime
    if(n > 1) {
      bases[c] = n;
      powers[c] = 1;
      c ++;
    }
    long long e = m;
    for(int i=0;i<c;i++){
      e = e*(bases[i]-1)/bases[i]; // Euler's formula
    }
    //print(e);
    int f = 1;
    for(int i=0;i<c;i++){
      f = f*(powers[i]+1); //factors' count
    }
    //print(f);
    cout << m - e - f + 1 << '\n'; //gcd(1,n) = 1 and 1 must be a factor of any num
  }


}
```
## UVA10110 平方數
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
  unsigned int n;
  while(cin>>n && n!=0){
    unsigned int s = sqrt(n);
    if(s*s==n){
      cout << "yes" << endl;
    }else{
      cout << "no" << endl;
    }
  }
}
```
## UVA10104 輾轉相除法
```cpp=
#include<bits/stdc++.h>
#define print(i) cout << #i << " value is " << i << '\n';
using namespace std;
struct ans{
  int x,y,d;
};

ans find_gcd(int a,int b){
  if(a%b==0){ // b = gcd(a,b)
    return (ans){0,1,b};
  }else if(b%a==0){ // a = gcd(a,b)
    return (ans){1,0,a};
  }else if(a >= b){
    ans tmp = find_gcd(a-b*(a/b),b);
    int x = tmp.x,y = tmp.y - tmp.x*(a/b);
    return (ans){x,y,tmp.d};
  }else {
    ans tmp = find_gcd(a,b-a*(b/a));
    int x = tmp.x - tmp.y*(b/a),y = tmp.y;
    return (ans){x,y,tmp.d};
  }
}
int main(){
  int a,b;
  while(cin >> a >> b){
    ans t = find_gcd(a,b);
    cout << t.x << ' ' << t.y << ' ' << t.d << endl;
  }

  return 0;
}
```

## UVA10006 數論
```cpp=
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
bool prime[65001];
ll mod(ll n,ll a,ll N){
  if(n==0) return 1;
  if(n==1) return a;
  ll modValue = mod(n/2,a,N);
  if(n%2==0) 
    return (modValue*modValue)%N;
  else
    return ((modValue*modValue)%N)* a % N;
}
int main(){
  fill(prime,prime+65001,false);
  for(int i=2;i<=65000;i++){
    if(!prime[i]){
      for(int j=i*2;j<=65000;j+=i)
        prime[j] = true;
    }
  }
  int n;
  while(cin >> n && n){
    bool flag = true;
    if(!prime[n])
      flag = false;
    for(int i=2;i<n&&flag;i++){
      if(mod((ll)n,(ll)i,(ll)n)!=i)
        flag = false;
    }
    if(flag)
      printf("The number %d is a Carmichael number.\n",n);
    else
      printf("%d is normal.\n",n);
  }
  return 0;
}
```
## UVA10139 legendre symbol
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool visited[50001];
int prime[50001];
int power[50001];
int save[50001];
int cnt = 0;
void init(){
  for(int i=2;i<50000;i++){
    if(!visited[i]){
      visited[i] = true;
      prime[cnt++] = i;
      for(int j=2*i;j<50000;j+=i){
        visited[j] = true;
      }
    }
  }
}

int legendre(int n,int p){
  if(n<p) return 0;
  return legendre(n/p,p) + n/p;
}
int main(){
  memset(visited,0,sizeof(visited));
  init();
  int n,m;
  while (cin >> n >> m)
  { 
    int t = m,index = 0,s = 0;
    memset(power,0,sizeof(power));
    while(t>1&&index<cnt){
      while(t%prime[index]==0){
        t /= prime[index];
        save[s] = prime[index];
        power[s]++;
      }
      if(power[s]>0) s++;
      index ++;
    }
    // for(int i=0;i<s;i++){
    //   cout << save[i] << ' ' << power[i] << ' ';
    if(t>1){
      save[s] = t;
      power[s] = 1;
      s++;
    }
      
    bool flag = true;

    for(int i=0;i<s;i++){
      if(legendre(n,save[i])<power[i]){
        flag = false;
        break;
      }
    }
      
    if(flag&&m)
      printf("%d divides %d!\n",m,n);
    else
      printf("%d does not divide %d!\n",m,n);
  
  }
  
  return 0;
}
```
# 程設第九周題目
## UVA10199 articulation point(要跑多次dfs)
```cpp=
#include <bits/stdc++.h>
using namespace std;
map <string,int> m;
map <int,string> m1;
set<int> edge[101];
set<int> ans;
int low[101];
int dfn[101];
int n,tmp,root;
string s,s1;
int num;
void tarjan(int u,int p){
  int cnt = 0;
  low[u] = dfn[u] = ++num;
  for(auto v:edge[u]){
    if(v==u) continue;
    if(!dfn[v]){
      tarjan(v,u);
      low[u] = min(low[u],low[v]);
      if(low[v]>=dfn[u]){
        cnt ++;
        if(u!=root||cnt>1){
          ans.insert(u);
        }
      }
    }else if(p!=v)
      low[u] = min(low[u],dfn[v]);
  }
}
int main(){
  int t = 0;
  while(cin >> n && n){
    if(t)
      cout << '\n';
    for(int i=0;i<101;i++)
      edge[i].clear();
    m.clear();
    m1.clear();
    ans.clear();

    for(int i=1;i<=n;i++){
      cin >> s;
      m[s] = i;
      m1[i] = s;
    }
    cin >> tmp;
    for(int i=0;i<tmp;i++){
      cin >> s >> s1;
      edge[m[s]].insert(m[s1]);
      edge[m[s1]].insert(m[s]);
    }

    memset(dfn,0,sizeof(dfn));
    for(int i=1;i<=n;i++){
      if(!dfn[i]){
        num = 0;
        root = i;
        tarjan(i,-1);
      }
    }
    cout << "City map #"<< ++t << ": " << ans.size() << " camera(s) found\n";
    set<string> ansSet;
    for(auto n:ans)
      ansSet.insert(m1[n]);
    for(auto s:ansSet)
      cout << s << '\n';
  }

}
```
## UVA10307 BFS + MST
```cpp=
#include <bits/stdc++.h>
#define N 55
using namespace std;
int m,n,kase,ptcnt;
string g[N];
int dis[N*N],f[N*N];
bool vis[N][N];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct edge{
  int u,v,w;
  bool operator < (edge o) const{
    return w < o.w;
  }
};
struct point{
  int x,y;
  bool operator == (point o) const {return x==o.x&&y==o.y;}
}p[N*N];

vector <edge> e;

int find_root(int n){
  if(f[n]==n) return n;
  return find_root(f[n]);
}

int kruskal(){
  sort(e.begin(),e.end());
  // for(auto i:e) cout << i.w << ' ';
  int cnt = 0,ans = 0;
  for(int i=0;i<ptcnt;i++)
    f[i] = i;
  for(auto i:e){
    if(cnt == ptcnt-1) break;
    int f1 = find_root(i.u),f2 = find_root(i.v);
    if(f1 == f2) continue;
    f[f1] = f2;
    cnt ++;
    ans += i.w;
  }
  return ans;
}

void BFS(int x,int y,int idx){
  memset(vis,false,sizeof(vis));
  int step[N][N] = {0};
  step[x][y] = 0;
  vis[x][y] = true;
  point u = (point){x,y};
  queue <point> q;
  q.push((point){x,y});
  while(!q.empty()){
    point v = q.front(); q.pop(); 
    for(int i=0;i<ptcnt;i++){
      if(i==idx) break;
      if(p[i]==v){
        e.push_back((edge){idx,i,step[v.x][v.y]});
      }
    }
    for(int i=0;i<4;i++){
      int xx = v.x + dir[i][0];
      int yy = v.y + dir[i][1];
      if(xx>=0&&xx<n&&yy>=0&&yy<m&&g[xx][yy]!='#'&&!vis[xx][yy]){
        vis[xx][yy] = true;
        step[xx][yy] = step[v.x][v.y] + 1;
        q.push((point){xx,yy});
      }
    }
  }
}

int main(){
  cin >> kase;
  while(kase --){
    e.clear();
    fill(dis,dis+N*N,2000000000);
    ptcnt = 0;
    cin >> m >> n;
    cin.ignore();
    for(int i=0;i<n;i++)
      getline(cin,g[i]);
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(g[i][j]=='A'||g[i][j]=='S')
          p[ptcnt++] = (point){i,j};
      }
    }
    for(int i=0;i<ptcnt;i++) 
      BFS(p[i].x,p[i].y,i);
    // for(auto i:e)
    //   cout << i.w << endl;
    cout << kruskal() << '\n';
  }
  return 0;
}
```
## UVA10158 disjoint set
```cpp=
#include <bits/stdc++.h>
#define print(i) std::cout << #i << ' ' << i << '\n'
int f[10000*2];
int n,ins,n1,n2;
int find_root(int num){
  // std::cout << num << '\n';
  if(f[num]!=num)
    return find_root(f[num]);
  return num;
}
int main(){
  std::cin >> n;
  std::cin.ignore();
  for(int i=0;i<(n<<1);i++)
    f[i] = i;
  while(std::cin >> ins >> n1 >> n2&&ins != 0){
    int f1 = find_root(n1),e1 = find_root(n1+n);
    int f2 = find_root(n2),e2 = find_root(n2+n);
    switch(ins){
      case 1: //set friend
        if(f1==e2) std::cout << -1 << '\n';
        else{
          f[f1] = f2;
          f[e1] = e2;
        }
        break;
      case 2: //set enemy
        if(f1==f2) std::cout << -1 << '\n';
        else {
          f[f1] = e2;
          f[e1] = f2;
        }
        break;
      case 3:
        if(f1==f2) std::cout << 1 << '\n';
        else std::cout << 0 << '\n';
        break;
      case 4:
        if(f1==e2) std::cout << 1 << '\n';
        else std::cout << 0 << '\n';
        break;
    }
  }
}
```
## UVA10600 最小、次小生成樹
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct edge{
  int u,v,w;
  bool operator < (const edge& other) const{
    return this->w < other.w;
  }
  bool operator == (const edge& other) const{
    return (this->u == other.u&&this->v == other.v);
  }
};
int t,n,m,u,v,w;
int minCost,secondMinCost;
int f[100];
vector <edge> e;
vector <edge> mst;
int findRoot(int n){
  if(f[n]!=n)
    return findRoot(f[n]);
  return n;
}
int main(){
  cin >> t;
  while(t--){
    e.clear();
    mst.clear();
    cin >> n >> m;
    for(int i=0;i<m;i++){
      cin >> u >> v >> w;
      e.push_back({u,v,w});
    }
    sort(e.begin(),e.end());
    // for(auto edge:e)
    //   cout << edge.w << ' ';
    // cout << '\n';
    for(int i=1;i<=n;i++)
      f[i] = i;
    minCost = 0;
    for(auto edge:e){
      int f1 = findRoot(edge.u);
      int f2 = findRoot(edge.v);
      if(f1==f2) continue;
      f[f1] = f2;
      minCost += edge.w;
      mst.push_back(edge);
    }
    // cout << minCost << '\n';
    

    secondMinCost = 2147483647;
    for(auto edge:mst){
      int cost = 0;
      int cnt = 0;
      for(int i=1;i<=n;i++)
        f[i] = i;
      for(auto edges:e){
        if(edges == edge) continue;
        int f1 = findRoot(edges.u);
        int f2 = findRoot(edges.v);
        if(f1 == f2) continue;
        f[f1] = f2;
        cnt ++;
        cost += edges.w;
        if(cnt == n-1){
          secondMinCost = min(secondMinCost,cost);
          break;
        }
      }     
    }
    cout << minCost << ' ' << (secondMinCost==2147483647?minCost:secondMinCost )<< '\n';
  }
}
```

## UVA10099 最大生成樹
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n,m,s,d,t,u,v,w;
int g[101][101];
int f[101];
int find_root(int n){
  if(f[n]==n) return n;
  return find_root(f[n]);
}
struct e{
  int u,v,w;
  bool operator < (e o) const{
    return w > o.w;
  }
};
vector <e> edge;

int main(){
  // FILE *fi = fopen("output.txt","w");
  int cnt = 0;
  while(cin >> n >> m && (n||m)){
    int flow = 2000000000;
    edge.clear();
    for(int i=0;i<m;i++){
      cin >> u >> v >> w;
      edge.push_back((e){u,v,w-1});
    }

    cin >> s >> d >> t;
    sort(edge.begin(),edge.end());
    for(int i=1;i<=n;i++)
      f[i] = i;
    for(auto i:edge){
      int f1 = find_root(i.u),f2 = find_root(i.v);
      if(f1==f2) continue;
      f[f1] = f2;
      if(find_root(s)==find_root(d)){
        flow = i.w;
        break;
      }
      
    }
    int ans = t/flow;
    if(t%flow!=0) ans ++;
    printf("Scenario #%d\n",++cnt);
    printf("Minimum Number of Trips = %d\n\n",ans);
  }
  return 0;
}

```

# 程設第十周題目
## UVA10537 dijkstra
```cpp=
#include <bits/stdc++.h>
#define ll long long unsigned int 
#define INF 9999999999999999
#define N 52
using namespace std;
bool visit[N];
set<int> g[N];
int fa[N];
ll d[N];
int tmp;
int s,e,c = 1;
char u,v;
ll items;

int toInt(char ch){
  if(isupper(ch))
    return ch - 'A'; //0~25: upper
  return ch - 'a' + 26; //26~51: lower
}
char toChar(int n){
  if(n<=25)  
    return 'A'+ n;
  return 'a' + n - 26;
}
ll countItem(int p,ll num){
  if(p < 26) //town
    return ceil(num*20/19.0);
  return num + 1; //village
}

void printPath(int p){
  if(p == e)
    cout << toChar(p) << '\n';
  else{
    cout << toChar(p) << '-';
    printPath(fa[p]);
  }
    
}
void dijkstra(){
  fill(visit,visit+N,false);
  fill(d,d+N,INF);
  d[e] = items;
  for(int i=0;i<N;i++){
    ll minI = INF;
    int u = -1;
    for(int j=0;j<N;j++){
      if(!visit[j]&&minI >d[j]){
        minI = d[j];
        u = j;
      }
    }
    if(u==-1) break; //no minimum point

    visit[u] = true;
    ll item = countItem(u,d[u]);
    for(auto v:g[u]){
      if(!visit[v]){
        if(d[v] > item){
          d[v] = item;
          fa[v] = u; 
        }else if(d[v]==item && fa[v]>u) //lexicographically smaller
          fa[v] = u;
      }
    }
  }
}
int main(){
  while(cin >> tmp&&tmp!=-1){
    for(int i=0;i<52;i++)
      g[i].clear();
    for(int i=0;i<tmp;i++){
      cin >> u >> v;
      int t1 = toInt(u),t2 = toInt(v);
      g[t1].insert(t2);
      g[t2].insert(t1);
    }
    cin >> items >> u >> v;
    s = toInt(u),e = toInt(v);
    dijkstra();
    printf("Case %d:\n",c++);
    cout << d[s] << '\n';
    printPath(s);
  }
}
```
## UVA10342 次小路徑(spfa)
```cpp=
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
vector <int> adj[101];
int n,r,u,v,wei,tmp;
int w[101][101];
int d[101][2];
bool vis[101];

void relax(int v,int cost,queue <int> &q){
  if(cost!=d[v][0]&&cost < d[v][1]){
    d[v][1] = cost;
    if(d[v][1]<d[v][0]) swap(d[v][0],d[v][1]);
    if(!vis[v]){
      vis[v] = true;
      q.push(v);
    }
  }
}
void sol(int s){
  fill(vis,vis+101,false);
  fill(d[0],d[101],INF);
  d[s][0] = 0;

  queue <int> q;
  q.push(s);
  while(!q.empty()){
    int u = q.front(); q.pop();
    vis[u] = false;
    for(auto v:adj[u]){
      relax(v,d[u][0] + w[u][v],q);
      relax(v,d[u][1] + w[u][v],q);
    }
  }
}
int main(){
  int c = 0;
  while(cin >> n >> r){
    cout<< "Set #" << ++c << '\n';
    for(int i=0;i<=100;i++)
      adj[i].clear();
    
    for(int i=0;i<r;i++){
      cin >> u >> v >> wei;
      w[u][v] = wei;
      w[v][u] = wei;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }

    cin >> tmp;
    while(tmp--){
      cin >> u >> v;
      sol(u);
      if(d[v][1]!=INF)
        cout<< d[v][1] << '\n';
      else
        cout<< '?' << '\n';
    }
  }
  return 0;
}
```
## UVA12144 dijkstra、紀錄路徑
```cpp=
#include <bits/stdc++.h>
#define INF 2147483647
#define print(i) cout << #i << ' ' << i << endl;
using namespace std;
ofstream op("output.txt");
vector <int> adj[500];
vector <pair<int,int> >visEdge;
int w[500][500];
bool vis[500];
unsigned int dis[500],p[500];
int n,m,s,t;
void mark_path(int u){
  // cout << u << endl;
  if(p[u]==u) return;
  visEdge.push_back({p[u],u});
  mark_path(p[u]);
}
int dijkstra(){
  memset(vis,0,sizeof(vis));
  fill(dis,dis+500,INF);
  dis[s] = 0,p[s] = s;
  for(int i=0;i<n;i++){
    int minD = INF,u = -1;
    for(int j=0;j<n;j++){
      // cout << dis[j] << ' ';
      if(!vis[j]&&minD>dis[j]){
        minD = dis[j];
        u = j;
      }
    }
    if(u==-1) break;
    
    vis[u] = true;
    for(auto v:adj[u]){
      if(dis[v]>=dis[u]+w[u][v]){
        if(find(visEdge.begin(),visEdge.end(),(pair<int,int>){u,v})!=visEdge.end()){
          continue;
        }
        dis[v] = dis[u] + w[u][v];
        p[v] = u;
      }
    }
  }
  if(dis[t]!=INF) return dis[t];
  return -1;
}
int main(){
  while(cin >> n >> m){
    if(n==0&&m==0) break;

    visEdge.clear();
    for(int i=0;i<n;i++)
      adj[i].clear();
    fill(dis,dis+500,INF);
    cin >> s >> t;
    if(m==0){
      cout << -1 << '\n';
      continue;
    }
    for(int i=0;i<m;i++){
      int u,v,wei;
      cin >> u >> v >> wei;
      adj[u].push_back(v);
      w[u][v] = wei;
    }
    int first = dijkstra(); mark_path(t);
    int ans = -1;
    while(true){
      ans = dijkstra();
      if(ans == -1||ans!=first) break;
      mark_path(t);
    }

    if(ans == first) 
      cout << -1 << endl;
    else
      cout << ans << endl;
  }
  return 0;
}
```

## UVA10278 spfa
```cpp=
#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;

int c,f,section,u,v,wei,tmp;
int dis[501];
bool vis[501];
vector <int> adj[501];
vector <int> fire;
string s;
int w[501][501];
void spfa(int n){
  memset(vis,0,sizeof(vis));
  dis[n] = 0;
  queue <int> q;
  q.push(n);
  while(!q.empty()){
    u = q.front(); q.pop();
    vis[u] = false;
    for(auto v:adj[u]){
      if(dis[v]>dis[u]+w[u][v]){
        dis[v] = dis[u] + w[u][v];
        if(!vis[v]){
          vis[v] = true;
          q.push(v);
        }
      }
    }
  }
}
int main(){
  cin >> c;
  for(int i=0;i<c;i++){
    if(i!=0) cout << '\n';
    fire.clear();
    fill(dis,dis+501,INF);
    fill(w[0],w[501],1000000000);
    cin >> f >> section;
    for(int j=1;j<=section;j++)
      adj[j].clear();
    for(int j=0;j<f;j++){
      cin >> tmp;
      fire.push_back(tmp);
    }
    cin.ignore();
    while(getline(cin,s)&&s.size()){
      stringstream ss(s);
      ss >> u >> v >> wei;
      w[u][v] = w[v][u] = wei;
      adj[u].push_back(v); adj[v].push_back(u);
    }
    // cout << "complete\n";
    for(auto t:fire)
      spfa(t);

    int ans = INF,ansN;
    int tmpDis[501];
    for(int j=1;j<=section;j++) tmpDis[j] = dis[j];


    for(int j=1;j<=section;j++){
      spfa(j);
      int mx = -INF;
      for(int k=1;k<=section;k++){
        if(mx<dis[k])
          mx = dis[k];
      }
      if(ans > mx){
        ans = mx;
        ansN = j;
      }
      for(int k=1;k<=section;k++) dis[k] = tmpDis[k];
    }
    cout << ansN << '\n';
  }
}
```

## UVA104 dp
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define print(i) cout << #i << ' ' << i << endl;
double dp[21][21][21];
double path[21][21][21];
int n;

void printPath(int t,int i,int j){
  if(t==0){
    printf("%d %d",i,j);
    return;
  }
  printPath(t-1,i,path[t][i][j]);
  printf(" %d",j);
}

int main(){
  while(cin >> n){
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(i==j)
          dp[0][i][j] = 1.0;
        else
          cin >> dp[0][i][j];
      }
    }

    bool flag = false;
    for(int t=1;t<n&&!flag;t++){
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          dp[t][i][j] = -1.0;

          for(int k=1;k<=n;k++){
            if(dp[t][i][j]<dp[t-1][i][k]*dp[0][k][j]){
              dp[t][i][j] = dp[t-1][i][k]*dp[0][k][j];
              path[t][i][j] = k;
            }
          }
        }
        
        if(dp[t][i][i]>=1.01){
          printPath(t,i,i);
          cout << '\n';
          flag = true;
          break;
        }
      }
    }

    if(!flag)
      cout << "no arbitrage sequence exists\n";
  }
  return 0;
}
```

# 程設第十一周題目
## UVA10709 計算幾何學(hardcore)
```cpp=
#include <bits/stdc++.h>
#define EPS 1e-5
using namespace std;
ofstream op("output.txt");
string s1,s2;
struct p{
  double x,y;
  bool operator == (p other) const{
    return x == other.x && y == other.y;
  }
  p operator - (p other) const {
    return (p){x-other.x,y-other.y};
  }
}pt[4];

double dx(p p1,p p2){
  return p2.x-p1.x;
}
double dy(p p1,p p2){
  return p2.y-p1.y;
}
double dis(p p1,p p2){
  return sqrt(pow(dx(p1,p2),2)+pow(dy(p1,p2),2));
}
double dot(p a,p b){
  return a.x*b.x+a.y*b.y;
}
double cross(p a,p b){
  return a.x*b.y-b.x*a.y;
}
int sgn(p a,p b,p c){
  double det = cross(b-a,c-a);
  return abs(det)>EPS?(det>0?1:-1):0;
}
bool onseg(p a,p b,p c){
  return sgn(a,b,c)==0&&min(a.x,b.x)<=c.x&&max(a.x,b.x)>=c.x&&min(a.y,b.y)<=c.y&&max(a.y,b.y)>=c.y;
}
bool segseg(p a,p b,p c,p d){
  if(onseg(a,b,c)||onseg(a,b,c)||onseg(c,d,a)||onseg(c,d,b))
    return true;
  return sgn(a,b,c)*sgn(a,b,d)==-1&&sgn(c,d,a)*sgn(c,d,b)==-1;
}
double PTL(p a,p b,p c){
  return abs(cross(b-a,c-a))/dis(a,b);
}
double PTS(p a,p b,p c){
  if(dot(b-a,c-a)<0) return dis(a,c);
  if(dot(a-b,c-b)<0) return dis(b,c);
  return PTL(a,b,c);
}


int main(){
  while(true){
    for(int i=0;i<2;i++)
      cin >> pt[i].x >> pt[i].y;
    cin >> s1;
    for(int i=2;i<4;i++)
      cin >> pt[i].x >> pt[i].y;
    cin >> s2;
    if(s1=="END") break;
    double ans;
    p a = pt[0],b = pt[1],c  = pt[2],d = pt[3];
    if(s1 == "L" && s2 == "L"){
      if(abs(cross(b-a,d-c))>EPS)
        ans = 0;
      else ans = PTL(a,b,c);
    }
    else if(s1 == "LS" && s2 == "LS"){
      if(segseg(a,b,c,d)) ans = 0;
      else ans = min({PTS(a,b,c),PTS(a,b,d),PTS(c,d,a),PTS(c,d,b)});
    }
    else{
      if(s1 == "LS"){
        swap(a,c);
        swap(b,d);
      }
      if(sgn(a,b,c)==0||sgn(a,b,d)==0||sgn(a,b,c)*sgn(a,b,d)==-1)
        ans = 0;
      else
        ans = min(PTL(a,b,c),PTL(a,b,d));
    }
    cout << fixed << setprecision(5) << ans << '\n';
  }
  return 0;
}
```
## UVA10245 算兩點最小距離(近乎暴力解)
```cpp=
#include <bits/stdc++.h>
using namespace std;
// ofstream cout("output.txt");
int n;
double x,y;
struct pt{
  double x,y;
  bool operator < (const pt &other) const{
    return x < other.x;
  };
  inline double countDis(const pt other) const{
    return sqrt((x-other.x)*(x-other.x)+(y-other.y)*(y-other.y));
  };  
};

vector <pt> v;
double minDis;
int main(){
  while(cin >> n && n){
    v.clear();
    for(int i=0;i<n;i++){
      cin >> x >> y;
      v.push_back({x,y});
    }
    sort(v.begin(),v.end());
    minDis = 200000000;
    for(int i=0;i<v.size();i++){
      for(int j=i+1;j<v.size();j++){
        if(v[i].x+minDis < v[j].x) break;
        minDis = min(minDis,v[i].countDis(v[j]));
      }
    }
    if(minDis >= 10000)
      cout << "INFINITY\n";
    else
      cout << fixed << setprecision(4) << minDis << '\n';
      
  }
}
```

## UVA10809 球座標(不要寫，除非你想被摧殘)
```cpp=
#include <bits/stdc++.h>
#define PI 3.141592653589
using namespace std;
double lat1,lat2,long1,long2;
double bestx,alpha;
// lat1 + lat2 == 0&& abs(long1-long2)==180 -> undefined
// use vector to solve the problem
// vector c = s * vector a + (1-s)*vector b
// vector a equals point x1,y1,z1
// vector b equals point x2,y2,z2
struct VC{
  double x,y,z;
  VC(){}
  VC(double x,double y,double z):x(x),y(y),z(z){}
  VC(double lat,double lon){
    x = sin(lat*PI/180); //x = sin(fi)
    y = sin(lon*PI/180)*cos(lat*PI/180); //y = cos(fi)*sin(theta)
    z = cos(lon*PI/180)*cos(lat*PI/180); // z = cos(fi)*cos(theta)
  }
  VC operator*(double scale){
    return (VC){x*scale,y*scale,z*scale};
  }
  VC operator+(VC v){
    return (VC){x+v.x,y+v.y,z+v.z};
  }
  void normalize(){
    double l = sqrt(x*x+y*y+z*z);
    x/=l;
    y/=l;
    z/=l;
  }
}a,b,c;

void run(double s){
  if(s<0||s>1) return ;
  c = a*s + b*(1-s);
  c.normalize();
  if(c.x>bestx){
    bestx = c.x;
    alpha = s;
  }

}
int main(){
  int n;
  int deg,sec;
  char dir;
  cin >> n;
  while(n--){
    cin >> deg >> dir >> sec >> dir;
    lat1 = deg + sec/60.0;
    if(dir == 'S') lat1 = -lat1;
    cin >> deg >> dir >> sec >> dir;
    long1 = deg + sec/60.0;
    if(dir == 'W') long1 = -long1;
    cin >> deg >> dir >> sec >> dir;
    lat2 = deg + sec/60.0;
    if(dir == 'S') lat2 = -lat2;
    cin >> deg >> dir >> sec >> dir;
    long2 = deg + sec/60.0;
    if(dir == 'W') long2 = -long2;   
    // cout << lat1 << ' ' << long1 << ' ' << lat2 << ' ' << long2 << '\n'; 
    if(lat1 == -lat2&&abs(long1-long2)==180){ //diagonal points
      printf("undefined\n");
      continue;
    }  
    a = VC(lat1,long1),b = VC(lat2,long2);
    bestx = -2;
    run(0); run(0.5); run(1);
    for(double delta = 0.5;delta > 0.00000000001;delta*=0.5){
      run(alpha + delta); run(alpha - delta);
    }
    if(bestx >= 0){
      int north = floor((180*asin(bestx)/PI)*60+0.5);
      printf("%d,%dN\n",north/60,north%60);
    }else{
      int south = floor((180*asin(-bestx)/PI)*60+0.5);
      printf("%d,%dS\n",south/60,south%60);
    }
  }
}
```

## UVA10136 高中數學
```cpp=
#include <bits/stdc++.h>
#define ESP 1e-5

using namespace std;
ofstream op("output.txt");
const double r = 2.5;
struct p{
  double x,y;
  double dis(p o){
    return sqrt(pow(x-o.x,2)+pow(y-o.y,2));
  }
}point[205];
p circleL,circleR;

void circle(p a,p b){
  double d = sqrt(pow(r,2)-pow(a.dis(b)/2,2));
  if(a.x==b.x){
    circleL.y = circleR.y = (a.y+b.y)/2;
    circleL.x = a.x - d;
    circleR.x = a.x + d;
  }else{
    double theta = atan((b.x-a.x)/(a.y-b.y));
    circleR.x = (a.x+b.x)/2+d*cos(theta);
    circleR.y = (a.y+b.y)/2+d*sin(theta);
    circleL.x = (a.x+b.x)/2-d*cos(theta);
    circleL.y = (a.y+b.y)/2-d*sin(theta);
  }
}
int t,cnt;
string s;
int main(){
  cin >> t; cin.ignore(); cin.ignore();
  while(t--){ 
    cnt = 0;
    while(getline(cin,s)&&s.size()){
      stringstream ss(s);
      ss >> point[cnt].x >> point[cnt].y;
      cnt++;
    }

    int ans = 1;
    for(int i=0;i<cnt;i++){
      for(int j=i+1;j<cnt;j++){
        if(point[i].dis(point[j])<=5){
          circle(point[i],point[j]);
          int lcnt = 0,rcnt = 0;
          for(int k=0;k<cnt;k++){
            if(circleL.dis(point[k])<=2.5+ESP)
              lcnt ++;
            if(circleR.dis(point[k])<=2.5+ESP)
              rcnt ++;
          }
          ans = max({ans,lcnt,rcnt});
        }
      }
    }
    cout << ans << '\n';
    if(t) cout << '\n';
  }
}
```

## UVA10173 convex hull(graham) 
```cpp=
#include <bits/stdc++.h>
using namespace std;
ofstream op("output.txt");
double sx,sy;
struct p{
  double x,y;
};
p st;
double cross(p p0,p p1,p p2){
  return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
}

double inner(p p0,p p1,p p2){
  return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}

double dis(p a,p b){
  return pow(a.x-b.x,2) + pow(a.y-b.y,2);
}

bool cmp(p a,p b){
  double tana,tanb;
  if(a.x-st.x!=0)
    tana = (a.y-st.y)/(a.x-st.x);
  else
    tana = -10000;
  if(b.x-st.x!=0)
    tanb = (b.y-st.y)/(b.x-st.x);
  else
    tanb = -10000;  
  if(tana == tanb) return(dis(a,st)<dis(b,st));
  if(tana >=0 && tanb<0) return true;
  if(tana <0 & tanb>=0) return false;
  return tana < tanb;
}

vector<p> graham(vector <p> v){
  vector<p> hull;
  for(auto pt:v){
    hull.push_back(pt);
    while(hull.size()>2&&cross(hull[hull.size()-3],hull[hull.size()-2],hull.back())<=0){
      hull.erase(hull.end()-2);
    }
  }
  return hull;
}

int main(){
  double x,y;
  int n;
  while(cin >> n && n){
    vector <p> v;
    for(int i=0;i<n;i++){
      cin >> x >> y;
      if(i==0){
        sx = x,sy = y;
      }else{
        if(y < sy || (y==sy&&x<sx)){
          sx = x,sy = y;
        }
      }
      v.push_back((p){x,y});
    }
    st.x = sx,st.y = sy;
    for(auto &pt:v){
      if(pt.x == sx && pt.y == sy){
        swap(pt,v[0]);
        break;
      }
    }
    sort(v.begin()+1,v.end(),cmp);
    vector <p> hull = graham(v);
    // cout << endl;
    // for(auto pt:hull)
    //   cout << pt.x << ' ' << pt.y << endl;
    if(hull.size()<3){
      cout << "0.0000" << endl;
      continue;
    }
    double ans = 2000000000;
    int b,l,r,t,b1;
      r = t = 1;
    for(b = 0;b<hull.size();b++){
      b1 = ((b+1)%hull.size()); // b b1 is bottom line
      //finding top point
      while(cross(hull[b],hull[b1],hull[t])<cross(hull[b],hull[b1],hull[(t+1)%hull.size()])){
        t = (t+1)%hull.size();
      }
      //finding rightest point
      while(inner(hull[b],hull[b1],hull[r])<inner(hull[b],hull[b1],hull[(r+1)%hull.size()])){
        r = (r+1)%hull.size();
      }
      //finding leftest point
      l = t;
      while(inner(hull[b],hull[b1],hull[l])>inner(hull[b],hull[b1],hull[(l+1)%hull.size()])){
        l = (l+1)%hull.size();
      }
      // cout << hull[t].x << ' ' << hull[t].y << ' ' << hull[l].x << ' ' << hull[l].y << ' ' << hull[r].x << ' ' << hull[r].y << endl;
      double d = dis(hull[b],hull[b1]);
      double area = (cross(hull[b],hull[b1],hull[t])*(inner(hull[b],hull[b1],hull[r])-inner(hull[b],hull[b1],hull[l]))/d);
      ans = min(ans,area);
    }
    cout << fixed << setprecision(4) << ans << endl;

  }
  return 0;
}
```
# 程設第十二周題目
## UVA10002 找質心
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
double sx,sy,sa;
struct p{
  double x,y;
};

double cross(p p0,p p1,p p2){
  return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
}
double a(p p0,p p1,p p2){
  return (cross(p0,p1,p2))/2;
}
bool cmp(p a,p b){
  if(cross((p){sx,sy},a,b)<=0) return false;
  return true;
}
int main(){
  while(cin >> n && n>=3){
    sx = 2000000000,sy = 2000000000;
    vector <p> v;
    for(int i=0;i<n;i++){
      double x,y;
      cin >> x >> y;
      v.push_back((p){x,y});
    }
    
    sx = v[0].x,sy = v[0].y;
    sort(v.begin()+1,v.end(),cmp);
    sx = sy = sa = 0;
    for(int i=2;i<v.size();i++){
      double area = a(v[0],v[i-1],v[i]);
      sa += area;
      sx += (v[0].x+v[i-1].x+v[i].x)*area;
      sy += (v[0].y+v[i-1].y+v[i].y)*area;
    }
    printf("%.3f %.3f\n",sx/sa/3,sy/sa/3);
  }
}
```
## UVA10005 外接圓、海龍、國中數學
```cpp=
#include <bits/stdc++.h>
using namespace std;
ofstream op("output.txt");
struct p{
  int x,y;
}pt[101];
double dis(p a,p b){
  return sqrt(pow(b.x-a.x,2)+pow(b.y-a.y,2));
}
double dis2(p a,p b){
  return pow(b.x-a.x,2)+pow(b.y-a.y,2);
}
int n;
double r;

double findR(int i,int j,int k){
  double a2 = dis2(pt[i],pt[j]);
  double b2 = dis2(pt[i],pt[k]);
  double c2 = dis2(pt[j],pt[k]);
  if((a2+b2<c2)||(b2+c2<a2)||(a2+c2<b2))
    return 0;
  double a = sqrt(a2),b = sqrt(b2),c = sqrt(c2);
  double s = (a+b+c)*0.5; //heron's formula
  double area = sqrt(s*(s-a)*(s-b)*(s-c)); // area = a*b*c/4r
  return a*b*c/area/4.0;
}

int main(){
  while(cin >> n && n){
    for(int i=0;i<n;i++){
      cin >> pt[i].x >> pt[i].y;
    }
    cin >> r;
    double tarR = 0;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++)
        tarR = max(dis(pt[i],pt[j])*0.5,tarR);
    }
    
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        for(int k=j+1;k<n;k++)
          tarR = max(tarR,findR(i,j,k));
      }
    }
    if(r >= tarR)
      cout << ("The polygon can be packed in the circle.\n");
    else
      cout << ("There is no way of packing that polygon.\n");
  }
  

  return 0;
}
```
## UVA10029 紀錄路徑
```cpp=
#include <bits/stdc++.h>
using namespace std;
unordered_map <string,int> idx;
vector <string> v;
vector <int> g[25005];
int path[25005];
string s;

void change(string cur,int l,int u){
  for(int i=0;i<l;i++){
    for(char j = cur[i]+1;j<='z';j++){
      string t = cur;
      t[i] = j;
      if(idx.count(t)>0){
        int v = idx[t];
        g[u].push_back(v);
      }
    }
  }
}

void del(string cur,int l,int u){
  for(int i=0;i<l;i++){
    string t=cur;
    t.erase(t.begin()+i);
    if(idx.count(t)>0){
      int v = idx[t];
      if(u<v) g[u].push_back(v);
    }
  }
}

void ins(string cur,int l,int u){
  for(int i=0;i<=l;i++){
    for(char c = 'a';c<='z';c++){
      string t = cur;
      t.insert(t.begin()+i,c);
      if(idx.count(t)>0){
        int v = idx[t];
        if(u<v) g[u].push_back(v);
      }
    }
  }
}

int find_path(int x){
  if(path[x]>0) return path[x];
  int mx = 0;
  for(auto i:g[x]){
    int t = find_path(i);
    mx = max(t,mx);
  }
  path[x] = mx + 1;
  return path[x];
}
int main(){
  int n = 0;
  memset(path,0,sizeof(path));

  while(cin >> s){
    v.push_back(s);
    idx[s] = n++;
  }
  for(int i=0;i<v.size();i++){
    change(v[i],v[i].size(),i);
    del(v[i],v[i].size(),i);
    
    ins(v[i],v[i].size(),i);
  }
  int ans = 0;
  for(int i=0;i<v.size();i++)
    ans = max(ans,find_path(i));
  cout << ans << '\n';
  return 0;
}
```

## UVA10917 最短路徑樹
```cpp=
#include <bits/stdc++.h>
using namespace std;
int d[1001];
int m,n,u,v,wei;
vector <int> adj[1001];
int w[1001][1001];
int path[1001];
void spfa(int s){
  bool vis[1001] = {0};
  queue <int> q;
  fill(d,d+1001,2000000000);
  d[s] = 0;
  q.push(s);
  while(!q.empty()){
    int u = q.front(); q.pop();
    vis[u] = false;
    for(auto v:adj[u]){
      if(d[v]>d[u]+w[u][v]){
        d[v] = d[u] + w[u][v];
        if(!vis[v]){
          vis[v] = true;
          q.push(v);
        }
      }
    }
  }
}

int dfs(int x){
  if(path[x]!=-1) return path[x];
  path[x] = 0;
  for(auto v:adj[x]){
    if(d[x]<d[v])
      path[x] += dfs(v);
  }
  return path[x];
}
int main(){
  while(cin >> n && n){
    cin >> m;
    for(int i=1;i<=n;i++)
      adj[i].clear();
    for(int i=0;i<m;i++){ 
      cin >> u >> v >> wei;
      w[u][v] = w[v][u] = wei;
      adj[u].push_back(v),adj[v].push_back(u);
    }
    fill(path,path+1001,-1);
    path[1] = 1;
    spfa(2);
    
    cout << dfs(2) << '\n';
  }

}
```

## UVA11235 segment tree
```cpp=
#include <bits/stdc++.h>
#define N 100001
using namespace std;
int n,q,tmp,s,a,b;
struct tree{
  int l,r,v;
}node[4*N];
struct NUM{
  int l,r,f,v;
}num[N];

void buildTree(int l,int r,int x){
  node[x].l = l;
  node[x].r = r;
  if(l == r){
    node[x].v = num[l].f;
    return;
  }
  int mid = (l+r)/2;
  buildTree(l,mid,(x<<1));
  buildTree(mid+1,r,(x<<1)+1);
  node[x].v  = max(node[(x<<1)].v,node[(x<<1)+1].v);
}

int findAns(int l,int r,int x){
  if(num[l].v == num[r].v) return r - l + 1;

  int ans = 0;
  if(l > num[l].l){
    ans = num[l].r - l + 1;
    l = num[l].r + 1;
  }

  if(r < num[r].r){
    ans = max(ans,r - num[r].l + 1);
    r = num[r].l - 1;
  }

  if(l > r) return ans;
  if(node[x].l >= l && node[x].r <= r) return node[x].v;
  int mid = (node[x].l + node[x].r) / 2;
  if(l <= mid) ans = max(ans,findAns(l,r,(x<<1)));
  if(mid < r) ans = max(ans,findAns(l,r,(x<<1)+1));
  return ans;
}
int main(){
  while(cin >> n &&n){
    cin >> q;
    s = 1;
    for(int i=1;i<=n;i++){
      cin >> tmp;
      num[i].v = tmp;
      if(num[i].v != num[i-1].v){
        for(int j=s;j<i;j++){
          num[j].l = s;
          num[j].r = i-1;
          num[j].f = i-s;
        }
        s = i;
      }
    }
    for(int j=s;j<=n;j++){
      num[j].l = s;
      num[j].r = n;
      num[j].f = n-s+1;
    }
    buildTree(1,n,1);
    for(int i=0;i<q;i++){
      cin >> a >> b;
      cout << findAns(a,b,1) << '\n';
    }
  }
}
```
# 程設第十三周題目
## UVA10480 最大網路流&&最小割
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define N 51
int n,m,u,v,w;
int g[N][N];
int flow[N][N];
int a[N];
int p[N];
struct edge{
  int u,v;
}e[501];

void maxflow(){
  fill(flow[0],flow[N],0);
  while(true){
    queue <int> q;
    fill(a,a+N,0);
    a[1] = 100000000;
    q.push(1);
    // BFS
    while(!q.empty()){
      int u = q.front(); q.pop();
      if(u == 2) break;
      for(int v=1;v<=n;v++){  
        if(!a[v]&&flow[u][v]<g[u][v]){
          p[v] = u;
          a[v] = min(a[u],g[u][v]-flow[u][v]);
          q.push(v);
        }
      }
    }

    if(a[2]==0) break;
    for(int u=2;u!=1;u=p[u]){
      flow[p[u]][u] += a[2]; // reverse path
      flow[u][p[u]] -= a[2]; // forward path
    }
  }
}
int main(){
  while(cin >> n >> m && n){
    fill(g[0],g[N],0);
    for(int i=0;i<m;i++){
      cin >> u >> v >> w;
      e[i].u = u,e[i].v = v;
      g[u][v] = g[v][u] = w;
    }
    maxflow();
    for(int i=0;i<m;i++){
      int u = e[i].u,v = e[i].v;
      if((!a[u]&&a[v])||(!a[v]&&a[u]))
        cout << u << ' ' << v << endl;
    }
    cout << endl;
  }
}
```

## UVA10330 最大網路流(變化)

```cpp=
#include <bits/stdc++.h>
using namespace std;
#define N 250
int g[N][N],f[N][N];
int n,m;
void getInput(){
  fill(g[0],g[N],0);
  fill(f[0],f[N],0);
  for(int i=1;i<=n;i++){
    cin >> g[i+n][i];
  }
  cin >> m;
  int a,b,c;
  for(int i=0;i<m;i++){
    cin >> a >> b >> c;
    g[a][b+n] = c;
  }
  cin >> a >> b;
  for(int i=0;i<a;i++){
    cin >> c;
    g[0][c+n] = 2000000000;
  }
  for(int i=0;i<b;i++){
    cin >> c;
    g[c][n + n + 1] = 2000000000;
  }
}

int maxflow(){
  queue <int> q;
  int t = 2*n + 1;
  int p[N],a[N], ans = 0;
  while(true){
    fill(p,p+N,0);
    fill(a,a+N,0);
    a[0] = 2000000000;
    q.push(0);
    while(!q.empty()){
      int u = q.front(); q.pop();
      for(int v=0;v<=t;v++){
        if(!a[v]&&g[u][v]>f[u][v]){
          p[v] = u;
          q.push(v);
          a[v] = min(a[u],g[u][v]-f[u][v]);
        }
      }
    }
    if(a[t]==0) break;
    ans += a[t];
    for(int u=t;u!=0;u=p[u]){
      f[p[u]][u] += a[t];
      f[u][p[u]] -= a[t];
    }
  }
  return ans;
}
int main(){
  while(cin >> n){
    getInput();
    cout << maxflow() << endl;
  }
  return 0;
}
```
## UVA836 最大子矩陣
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define N 26
string g[N];

bool isOne(int col,int s,int e){
  for(int i=s;i<e;i++)
    if(g[col][i]!='1') return false;
  return true;
}

int main(){
  int t,s;
  cin >> t;
  cin.ignore();
  while(t--){
    cin.ignore();
    getline(cin,g[0]);
    s = g[0].size();
    for(int i=1;i<s;i++)
      getline(cin,g[i]);
    int ans = 0,maxsize = 0;
    for(int len=1;len<=s;len++){
      for(int i=0;i+len<=s;i++){
        maxsize = 0;
        for(int j=0;j<s;j++){
          if(isOne(j,i,i+len))
            maxsize += len;
          else
            maxsize = 0;
          ans = max(ans,maxsize);
        }
      }
    }

    cout << ans << '\n';
    if(t) cout << '\n';
  }
  return 0;
}
```
## UVA193 backtracking
```cpp=
#include <bits/stdc++.h> 
#define N 101
using namespace std;
int m,t,u,v,k;
int msize;
int color[N];
vector <int> adj[N];
vector <int> tmp,ans;
void DFS(int n){
  if(n>m){
    if(tmp.size()>msize||(tmp.size()==msize&&color[m-1]==1)){
      msize = tmp.size();
      ans = tmp;
    }
    return;
  }

  bool bk = true;
  for(auto v:adj[n])
    if(color[v]==1) bk = false;
  if(bk){
    tmp.push_back(n);
    color[n] = 1;
    DFS(n+1);
    tmp.pop_back();
    color[n] = 0;
  }
  color[n] = 0;
  DFS(n+1);
}
int main(){
  cin >> t;
  while(t--){
    for(int i=0;i<N;i++)
      adj[i].clear();
    tmp.clear();
    memset(color,0,sizeof(color));
    msize = 0;

    cin >> m >> k;
    for(int i=0;i<k;i++){
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    DFS(1);
    cout << msize << '\n';
    for(int i=0;i<ans.size();i++){
      if(i!=0) cout << ' ';
      cout << ans[i];
    }
    cout << '\n' ;
  }
}
```

## UVA10364 backtracking
```cpp=
#include <bits/stdc++.h>
using namespace std;
int l[21];
bool vis[21];
int slen,sum,n;
bool cmp(int a,int b){
  return a>b;
}
bool backtrack(int len,int c,int idx){

  if(len==slen){
    idx = len = 0;
    c ++;
    if(c==3)
      return true;
  }

  for(int i=idx;i<n;i++){
    if(!vis[i]){
      if(len+l[i]<=slen){
        vis[i] = true;
        if(backtrack(len+l[i],c,i+1)) 
          return true;
        vis[i] = false;
      }
    }
  }
  return false;
}

int main(){
  int kase;
  cin >> kase;
  while(kase--){
    cin >> n;
    sum = 0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++) {
      cin >> l[i];
      sum += l[i];
    }
    if(sum%4!=0){
      cout << "no\n";
      continue;
    }
    slen = sum>>2;
    sort(l,l+n,cmp);
    if(backtrack(0,0,0))
      cout << "yes\n";
    else
      cout << "no\n";
  }
  return 0;
}
```