# 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;
}
```
Sign in with Wallet
Connect another wallet