題目連結
TLE 幾百次後 才發現原因在 board[0][k] 居然不等於 board[k/4][k%4]，
改一下就AC了...害我一直對ida*優化到0秒
/* 題目: UVa 10181 - 15-Puzzle Problem
* Language: C++
* Created on: 2016年10月02日
* Author: hanting
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int board[4][4];
int table[16][2];
inline bool canSolve(int x)
{
int result = 0;
for(int i = 0; i < 16; i++)
{
for(int j = i+1; j < 16; j++)
{
if(board[j/4][j%4] and board[i/4][i%4] and board[j/4][j%4] < board[i/4][i%4]) result++;
}
}
return (result+x)&1;
}
inline int getStatus()
{
int cnt = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
if(board[i][j]) cnt += abs(table[board[i][j]][0] - i) + abs(table[board[i][j]][1] - j);
}
}
return cnt;
}
char ansStk[100];
char stk[100];
int stki;
enum
{
UP, DOWN, LEFT, RIGHT
};
int maxd;
int tmpMaxd;
int Htable[4][4][16]; // Htable[i][j][num] // num在[i][j]的cost
bool no;
bool dfs(int depth, int i, int j, int prePos, int status)
{
if(depth > 50)
{
no = true;
return false;
}
if(depth + status*4/3 > maxd)
{
tmpMaxd = min(tmpMaxd, depth + status*4/3);
if(depth == 0) maxd = tmpMaxd;
return false;
}
if(status == 0)
{
stk[stki] = 0;
cout << stk;
return true;
}
if(prePos != UP and i+1 < 4)
{
swap(board[i][j], board[i+1][j]);
stk[stki++] = 'D';
int nextStatus = status;
nextStatus -= Htable[i+1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i+1, j, DOWN, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i+1][j]);
}
if(prePos != LEFT and j+1 < 4)
{
swap(board[i][j], board[i][j+1]);
stk[stki++] = 'R';
int nextStatus = status;
nextStatus -= Htable[i][j+1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j+1, RIGHT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j+1]);
}
if(prePos != DOWN and i-1 >= 0)
{
swap(board[i][j], board[i-1][j]);
stk[stki++] = 'U';
int nextStatus = status;
nextStatus -= Htable[i-1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1, i-1, j, UP, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i-1][j]);
}
if(prePos != RIGHT and j-1 >= 0)
{
swap(board[i][j], board[i][j-1]);
stk[stki++] = 'L';
int nextStatus = status;
nextStatus -= Htable[i][j-1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j-1, LEFT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j-1]);
}
maxd = tmpMaxd;
return false;
}
int main()
{
for(int i = 1; i < 16; i++)
{
table[i][0] = (i-1) / 4;
table[i][1] = (i-1) % 4 ;
}
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
for(int k = 1; k < 16; k++)
{
Htable[i][j][k] = abs(table[k][0] - i) + abs(table[k][1] -j);
}
}
}
int n;
cin >> n;
while(n--)
{
int x0, y0;
memset(ansStk, 0, sizeof(ansStk));
int ti = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
cin >> board[i][j];
if(board[i][j] == 0)
{
x0 = i;
y0 = j;
}
}
}
if(!canSolve(x0))
{
cout << "This puzzle is not solvable." << endl;
continue;
}
int status = getStatus();
maxd = status;
no = false;
for(;;)
{
tmpMaxd = 0x3fffffff;
stki = 0;;
if(dfs(0, x0, y0, -1, status))
{
break;
}
if(no)
{
cout << "This puzzle is not solvable." ;
break;
}
}
cout << endl;
}
return 0;
}
2016年10月2日 星期日
[UVA] 10181 - 15-Puzzle Problem
2016年7月12日 星期二
[UVA] 10428 - The Roots
題目連結
這題ac uva rank 1耶真是感動到快暴動了
程式碼:
/* 題目: UVa 10428 - The Roots
* Language: C++
* Created on: 2016年7月12日
* Author: hanting
*/
#include <iostream>
#include <cstring> // memset
#include <iomanip> // setprecision
#include <cmath> // fabs
#include <algorithm> // sort
#include <vector>
#include <cstdio>
using namespace std;
double a[6];
double f(double x) // 高效率求一元多次多項式的值
{
double result = a[5];
for(int i = 4; i >= 0; i--)
{
result = result * x + a[i];
}
return result;
}
double f1(double x)
{
double result = a[5]*5;
for(int i = 4; i > 0; i--)
{
result = result * x + a[i]*i;
}
return result;
}
double newtonsMethod(double x0)
{
double x1 = x0;
int cnt = 0;
do
{
if(++cnt == 100) break;
x0 = x1;
if(fabs(f(x0)) < 1e-10) return x0;
x1 = x0 - f(x0)/f1(x0);
}
while(fabs(x1 - x0) > 1e-10);
return x1;
}
void PolynomialDivision(double b, double c) // f div (bx+c)
{
for(int i = 5; i > 0; i--)
{
a[i-1] -= a[i] / b * c;
a[i] /= b;
}
for(int i = 0; i < 5; i++)
{
a[i] = a[i+1];
}
a[5] = 0;
}
void findRoot(vector<double> &root, int N)
{
double oneRoot;
while(root.size() < N)
{
oneRoot = newtonsMethod(0);
root.push_back(oneRoot);
PolynomialDivision(1, -oneRoot);
}
}
int main()
{
int N;
int caseN = 1;
while(/*cin >> N*/scanf("%d", &N) == 1 and N)
{
memset(a, 0, sizeof(a));
for(int i = N; i >= 0; i--)
{
//cin >> a[i];
scanf("%lf", a+i);
}
vector<double> root;
findRoot(root, N);
sort(root.begin(), root.end());
printf("Equation %d:", caseN++);
//cout << "Equation " << caseN++ << ":" ;
for(int i = 0; i < N; i++)
{
printf(" %.4lf", root[i]);
//cout << " " << fixed << setprecision(4) << root[i];
}
printf("\n");
//cout << endl;
}
return 0;
}2016年7月9日 星期六
[UVA] 684 - Integral Determinant
題目連結
程式碼:
/* 題目: UVa 684 - Integral Determinant
* Language: C++
* Created on: 2016年7月10日
* Author: hanting
*/
#include <iostream>
#include <vector>
using namespace std;
long long gcd(long long a1, long long b1)
{
unsigned long long a, b;
if(a1 < 0) a1 *= -1;
if(b1 < 0) b1 *= -1;
a = a1;
b = b1;
while(a and b)
{
(a > b) ? (a %= b) : (b %= a);
}
return a ? a : b;
}
long long lcm(long long a, long long b)
{
return a / gcd(a, b) * b; // a要先/gcd
}
struct Real
{
long long mom, son;
Real(int s = 0, int m = 1):mom(m), son(s) {}
void simple()
{
if(mom < 0)
{
son *= -1;
mom *= -1;
}
long long _gcd = gcd(mom, son);
mom /= _gcd;
son /= _gcd;
}
Real operator * (Real b)
{
Real result = *this;
long long gcd1, gcd2;
gcd1 = gcd(result.mom, b.son);
gcd2 = gcd(result.son, b.mom);
result.mom /= gcd1;
b.son /= gcd1;
result.son /= gcd2;
b.mom /= gcd2;
result.mom *= b.mom;
result.son *= b.son;
result.simple();
return result;
}
Real operator / (Real b)
{
Real result = *this;
long long gcd1, gcd2;
gcd1 = gcd(result.mom, b.mom);
gcd2 = gcd(result.son, b.son);
result.mom /= gcd1;
b.mom /= gcd1;
result.son /= gcd2;
b.son /= gcd2;
result.mom *= b.son;
result.son *= b.mom;
result.simple();
return result;
}
void operator -=(Real b)
{
long long lcm1 = lcm(mom, b.mom);
long long a1, b1;
a1 = lcm1 / mom;
b1 = lcm1 / b.mom;
son = son*a1 - b.son*b1;
mom = lcm1;
simple();
}
void operator *= (Real b)
{
long long gcdMom, gcdSon;
gcdMom = gcd(mom, b.son);
gcdSon = gcd(son, b.mom);
mom /= gcdMom;
b.son /= gcdMom;
son /= gcdSon;
b.mom /= gcdSon;
mom *= b.mom;
son *= b.son;
simple();
}
void operator /= (Real b)
{
long long gcd1, gcd2;
gcd1 = gcd(mom, b.mom);
gcd2 = gcd(son, b.son);
mom /= gcd1;
b.mom /= gcd1;
son /= gcd2;
b.son /= gcd2;
mom *= b.son;
son *= b.mom;
simple();
}
friend istream& operator >> (istream &in, Real &r)
{
in >> r.son;
r.mom = 1;
return in;
}
friend ostream& operator << (ostream &out, Real r)
{
out << r.son;
if(r.mom != 1 and r.son) out << '/' << r.mom;
return out;
}
};
void doDownTriangle(vector<vector<Real> > &vec) // 讓矩陣對角線以下全變為0
{
for(int k = 0; k < vec.size(); k++)
{
int index = k; // find first element not zero
while(index < vec.size() and vec[index][k].son == 0) index++;
if(index == vec.size())
{
vec[0][0] = 0;
return ;
}
if(index != k)
{
swap(vec[index], vec[k]);
for(int i = k; i < vec.size(); i++)
{
vec[k][i].son *= -1;
}
}
Real tmp = vec[k][k];
for(int i = k+1; i < vec.size(); i++)
{
Real r = vec[i][k] / tmp;
for(int j = k; j < vec[i].size(); j++)
{
vec[i][j] -= vec[k][j] * r;
}
}
}
}
Real Determinant(vector<vector<Real> > &vec)
{
doDownTriangle(vec);
Real result(1);
for(int i = 0; i < vec.size(); i++)
{
result *= vec[i][i]; // 因下三角全為0，故對角線乘積為答案
}
return result;
}
int main()
{
int n;
while(cin >> n and n)
{
vector<vector<Real> > matrix(n, vector<Real>(n));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cin >> matrix[i][j];
}
cout <<Determinant(matrix) << endl;
}
cout << "*" << endl;
return 0;
}
2016年5月22日 星期日
[UVA] 11995 - I Can Guess the Data Structure!
/* 題目: UVa 11995 - I Can Guess the Data Structure!
* Language: C++
* Created on: 2016年5月22日
* Author: hanting
*/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
int N;
while(cin >> N)
{
bool test[3] = {};
queue<int> que;
priority_queue<int> pque;
stack<int> stk;
int op;
int num;
for(int i = 0; i < N; i++)
{
cin >> op >> num;
if(op == 1)
{
que.push(num);
pque.push(num);
stk.push(num);
}
else //if(op == 2)
{
int tmp;
if(test[0] == 0)
{
if(que.size())
{
tmp = que.front();
if(tmp != num)
{
test[0] = 1;
}
else
{
que.pop();
}
}
else
{
test[0] = 1;
}
}
if(test[1] == 0)
{
if(pque.size())
{
tmp = pque.top();
if(tmp != num)
{
test[1] = 1;
}
else
{
pque.pop();
}
}
else
{
test[1] = 1;
}
}
if(test[2] == 0)
{
if(stk.size())
{
tmp = stk.top();
if(tmp != num)
{
test[2] = 1;
}
else
{
stk.pop();
}
}
else
{
test[2] = 1;
}
}
}
}
int cnt = 0;
for(int i = 0; i < 3; i++)
{
if(test[i] == 0) cnt++;
}
if(cnt == 0)
{
cout << "impossible" << endl;
}
else if(cnt == 1)
{
if(test[0] == 0)
{
cout << "queue" << endl;
}
else if(test[1] == 0)
{
cout << "priority queue" << endl;
}
else
{
cout << "stack" << endl;
}
}
else
{
cout << "not sure" << endl;
}
}
return 0;
}
2016年5月7日 星期六
[UVA] 11195 - Another n-Queen Problem
題目連結
==================================================
==================================================
程式碼:
/* 題目: UVa 11195 - Another n-Queen Problem
* Language: C++
* Created on: 2016年05月08日
* Author: hanting
*/
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
#pragma warning(disable:4996)
int ans;
vector<int > arr;
vector<string> vec;
void DFS(int row, int ld, int rd, int N, int cnt)
{
if (cnt == N)
{
ans++;
return;
}
int next = row | ld | rd;
for (int i = 0; i < N; i++)
{
int mask = 1 << i;
if (!(next & mask) && vec[cnt][i] != '*')
{
DFS(row|mask, (ld|mask) << 1, (rd|mask) >> 1, N, cnt + 1);
}
}
}
int main()
{
int N;
int CaseN = 1;
while (cin >> N && N)
{
ans = 0;
arr.assign(N, 0);
vec.assign(N, "");
for (int i = 0; i < N; i++)
{
cin >> vec[i];
}
DFS(arr[0], 0, 0, N, 0);
cout << "Case " << CaseN++ << ": " << ans << endl;
}
}
2016年5月1日 星期日
[UVA] 11956 - Brainfuck
/* 題目: UVa 11956 - Brainfuck
* Language: C++
* Created on: 2016年05月01日
* Author: hanting
*/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int CaseN = 1;
int testCase = 0;
cin >> testCase;
cin.get();
while(testCase--)
{
cout << dec << "Case " << CaseN++ << ":";
string ins;
getline(cin, ins);
unsigned char memory[100] = {};
int ptr = 0;
for(int i = 0; i < ins.size(); i++)
{
if(ins[i] == '+') memory[ptr]++;
else if(ins[i] == '-') memory[ptr]--;
else if(ins[i] == '>') ptr++;
else if(ins[i] == '<') ptr--;
if(ptr < 0) ptr = 99;
else if(ptr > 99) ptr = 0;
}
for(int i = 0; i < 100; i++)
{
cout << " ";
cout << setw(2);
cout << uppercase << setfill('0') << hex << (int)memory[i];
}
cout << endl;
}
return 0;
}
2016年4月7日 星期四
[UVA] 112 - Tree Summing
/* 題目: UVa 112 - Tree Summing
* Language: C++
* Created on: 2016年4月7日
* Author: hanting
*/
#include <iostream>
#include <cstring> // memset
#include <sstream>
using namespace std;
const int maxN = 100000;
int arr[maxN];
bool arr2[maxN];
string tree;
stringstream sin;
bool check;
void buildTree(int ptr)
{
if(ptr < maxN)
{
char ch;
sin >> ch;
sin >> ch;
if(ch == '*')
{
int num;
sin >> num;
arr[ptr] = num;
arr2[ptr] = true;
buildTree(ptr*2);
buildTree(ptr*2+1);
sin >> ch;
}
/*else if(ch == ')')
{
}*/
}
}
void init()
{
memset(arr, 0, sizeof(arr));
memset(arr2, 0, sizeof(arr2));
tree.clear();
check = false;
int flag = 0;
char c;
char last;
while(c = cin.get())
{
if(tree.size()) last = tree[tree.size()-1];
if(c == ' ' or c == '\n') continue;
if(c == '(') flag++;
else if(c == ')') flag--;
else if(isdigit(c) and (last != '-' and !isdigit(last)))
{
tree += '*';
}
else if(c == '-')
{
tree += '*';
}
if(flag >= 0) tree += c;
if(flag == 0) break;
}
sin.clear();
sin.str(tree);
}
void DFS(int index, int n)
{
if(index < maxN and arr2[index])
{
n -= arr[index];
if(!arr2[index*2] and !arr2[index*2+1] and n == 0)
{
check = true;
return ;
}
DFS(index*2, n);
DFS(index*2+1, n);
}
}
int main()
{
int n;
int i = 1;
while(cin >> n)
{
init();
buildTree(1);
if(arr2[1])DFS(1, n);
cout << (check ? "yes\n":"no\n");
}
return 0;
}
訂閱：
文章 (Atom)