UVA 10327 C++

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1268

#include<iostream>
using namespace std;

int main()
{
int *data;
int N = 0,count=0;
while (cin >> N)
{
data = new int[N];
count = 0;
for (int i = 0; i <= N - 1; i++)
cin >> data[i];
for (int j = 0; j <= N - 2;j++)
for (int k = j + 1; k <= N-1;k++)
if (data[k] < data[j])
count++;
delete data;
cout << "Minimum exchange operations : " << count << endl;
}
return 0;
}

UVA 476 C++

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=417

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<string>
using namespace std;
struct point
{
double x;
double y;
};
int main()
{
vector<point>left;
vector<point>right;
point garbage;
garbage.x = 0;
garbage.y = 0;
string input="",tmp="";
double x = 0.0, y = 0.0, number = 0.0;
int line=0,count, pos, point_number=1;
bool flag;
while(getline(cin,input))
{
if (input[0] == '*')
break;
count = 0,pos=2;
int len = input.length();
for (int i = 2; i <= len; i++)
{
if (input[i] == '\0' || input[i]=='\n')
{
for (int j = pos; j <= i-1; j++)
tmp = tmp + input[j];
number = atof(tmp.c_str());
count++;
tmp = "";
}
else if (input[i]== ' ')
{
for (int k = pos; k <= i - 1; k++)
tmp = tmp + input[k];
number = atof(tmp.c_str());
count++;
tmp = "";
pos = i + 1;
}
switch (count)
{
case 1:
left.push_back(garbage);
left[line].x = number;
break;
case 2:
left[line].y = number;
break;
case 3:
right.push_back(garbage);
right[line].x = number;
break;
case 4:
right[line].y = number;
break;
}
}
line++;
}
while (true)
{
cin >> x;
cin >> y;
flag = 0;
if (x == 9999.9 && y == 9999.9)
break;
for (int i = 0; i <= line-1; i++)
{
if (x > left[i].x && x < right[i].x && y< left[i].y && y> right[i].y)
{
cout << "Point " << point_number << " is contained in figure " << i+1 << endl;
flag = 1;
}
}
if (flag == 0)
cout << "Point " << point_number << " is not contained in any figure" << endl;
point_number++;
}
return 0;
}

UVA 458 C++

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=399

#include<iostream>
#include<string>
using namespace std;
int main()
{
string input = "";
string output="";
char change;
int count = 0;
while (getline(cin, input))
{
output = "";
for (int i = 0; i <= input.length() - 1; i++)
{
change = input[i];
change = change - 7;
output = output + change;
}
cout << output << endl;
}
return 0;
}

UVA 272 C++

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=208

#include<iostream>
#include<string>
using namespace std;
int main()
{
string input = "";
string output="";
int count = 0;
//cin >> input;
while (getline(cin, input))
{
output = "";
for (int i = 0; i <= input.length() - 1; i++)
{
if (input[i] == '\"')
{
count++;
if (count % 2 == 1)
output = output + "``";
else
output = output + "''";;
}
else
output = output + input[i];
}
cout << output << endl;
}
return 0;
}

複雜度筆記

○(n)   :  f(n) <= c*g(n)           bigO最多會執行幾次

       

Ω(n)   :  f(n) >= c*g(n)           Omega最少會執行幾次

Θ(n)   :  c1*g(n)<=f(n) <= c2*g(n)  theta執行次數會被夾在範圍內

Ex:

     3n+2
          可知bigO是○(n)，知道g(n)=n，代表意思 3n+2<=c*n其中C=4且n>=2。

EX:

A程式的時間複雜度是T1(N)

B程式的時間複雜度是T2(N)

                 A做完接著做B，整體的BIGO=MAX( T1(N) , T2(N) )

         A內呼叫B做遞迴，整體的BIGO=T1(N)*T2(N)

常用的大小表：C < LOGN < LOG^2 N < N < NLOGN < N^2 < N^3 <2^N

UVA 10107 C++

#include<iostream>
#include<stdio.h>
using namespace std;
long long data[10000];
void print(long long);
int main()
{
long long X,count=0,trace;
while(cin>>X)
{
if(count==0)
{
data[0]=X;
count++;
print(count);
}
else
{
trace=count;
if(X>=data[trace-1])
{
data[trace]=X;
count++;
print(count);
}
else
{
while(X<=data[trace-1])
{
data[trace]=data[trace-1];
trace--;
}
data[trace]=X;
count++;
print(count);
}

}
}
return 0;
}
void print(long long tmp)
{
if( (tmp%2)!=0)
cout<<data[tmp/2]<<endl;
else
cout<<(data[tmp/2]+data[tmp/2-1])/2<<endl;
}

UVA 10077 C++

#include<iostream>
#include<string>
using namespace std;
int main()
{
START:
string path="";
int m,n;
while(cin>>m,cin>>n)
{
if( m==1 && n==1)
break;
int uppertop=1,upperdown=0,lowertop=0,lowerdown=1;
int midtop,middown;
double mid,mn;
while(true)
{
midtop=uppertop+lowertop;
middown=upperdown+lowerdown;
mid=midtop*1.0/middown;
mn=m*1.0/n;
if(midtop==m && middown==n)
{
cout<<path<<endl;
goto START;
}
else if(mid>=mn)
{
uppertop=midtop;
upperdown=middown;
path=path+'L';
}
else
{
lowertop=midtop;
lowerdown=middown;
path=path+'R';
}
}

}
return 0;
}