#include <stdio.h>
int dir[100][100];
int mtx[100][100];
int path[100];
int main()
{
int a, b, c, min;
int i, j, row, col, a_dir, c_dir;
while (scanf("%d %d",&row,&col)==2)
{
for (i=1 ; i<=row ; i++)
for (j=1 ; j<=col ; j++)
scanf("%d",&mtx[i][j]);
for (j=col-1 ; j>=1 ; j--)
{
for (i=1 ; i<=row ; i++)
{
if (i-1<1)
{
a_dir = -1;
a = mtx[i][j] + mtx[row][j+1];
} else
{
a_dir = 0;
a = mtx[i][j] + mtx[i-1][j+1];
}
if (i+1>row)
{
c_dir = -1;
c = mtx[i][j] + mtx[1][j+1];
} else
{
c_dir = 0;
c = mtx[i][j] + mtx[i+1][j+1];
}
b = mtx[i][j] + mtx[i][j+1];
if (a<=b && a<=c)
{
mtx[i][j] = a;
if (a_dir<0)
{
if (a==b) { dir[i][j] = i; }
else if (a==c) { dir[i][j] = i+1; }
else { dir[i][j] = row; }
} else {
if (a==c && c_dir<0) dir[i][j] = 1;
else dir[i][j] = i-1;
}
}
else if (b<=a && b<=c)
{
mtx[i][j] = b;
if (b==a)
{
if (a_dir<0)
{
dir[i][j] = i;
} else
{
dir[i][j] = i-1;
}
} else if (b==c)
{
if (c_dir<0)
{
dir[i][j]=1;
} else
{
dir[i][j]=i;
}
} else
{
dir[i][j] = i;
}
}
else if (c<=a && c<=b)
{
mtx[i][j] = c;
if (c_dir<0)
{
dir[i][j] = 1;
} else {
if (c==a) { dir[i][j]=i-1; }
else if (c==b) { dir[i][j]=i; }
else { dir[i][j]=i+1; }
}
}
}
}
for (i=1, min=mtx[1][1], path[1]=1 ; i<=row ; i++)
{
if (mtx[i][1]<min)
{
min = mtx[i][1];
path[1] = i;
}
}
printf("%d",path[1]);
for (j=2 ; j<=col ; j++)
{
path[j] = dir[path[j-1]][j-1];
printf(" %d",path[j]);
}
printf("\n%d\n",min);
}
return 0;
}
Sunday, December 04, 2011
[UVa] 116 - Unidirectional TSP
Saturday, November 26, 2011
[UVa] 11945 - Financial Management
Too simple. It doesn't even need a search :P. But while solving this I learned of using C Locales. Look at how I printed the value. Didn't even had to put an if for the commas.
/* Faith-M */
//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
using namespace std;
int main()
{
/*freopen("input.txt","r+",stdin);
freopen("output.txt","w+",stdout);/**/
// TEST CASE //
int kase=1, kounter=1;/**/
int i;
double sum, blnc;
scanf("%d",&kase);
setlocale(LC_ALL, "en_US.UTF-8");
while (kase--)
{
for (i=1, sum=0 ; i<=12 ; i++)
{
scanf("%lf",&blnc);
sum += blnc;
}
printf("%d $%'.2lf\n", kounter++, sum / 12.0);
}
return 0;
}
Tuesday, November 22, 2011
[UVa] 11614 - Etruscan Warriors Never Play Chess
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long long n, lim, x1, x2;
int tst;
cin >> tst;
while (tst--)
{
cin >> n;
lim = (int)(ceil(sqrt(double(n*2))));
x1 = lim * (lim+1) / 2;
x2 = (lim-1)*lim/2;
if (x1 <= n)
{
cout << lim << endl;
} else if (x2<=n)
{
cout << lim-1 << endl;
} else
{
cout << lim-2 << endl;
}
}
return 0;
}
[UVa] 12364 - In Braile
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
class nmb
{
public:
string br;
int ser;
};
nmb nums[10] = { {".***..",0},{"*.....",1},{"*.*...",2},{"**....",3},{"**.*..",4},{"*..*..",5},{"***...",6},{"****..",7},{"*.**..",8},{".**...",9} };
int main()
{
int n, i, j, k, tst;
string str, temp;
string strs[3];
while (getline(cin,str))
{
if (str == "0")
break;
getline(cin,str);
if (str == "S")
{
getline(cin,str);
for (i=0 ; i<3 ; i++)
{
for (j=0 ; j<str.size() ; j++)
if (!j) cout << nums[str[j]-'0'].br.substr(i*2,2);
else cout << " " << nums[str[j]-'0'].br.substr(i*2,2);
cout << endl;
}
}
else
{
getline(cin,strs[0]);
getline(cin,strs[1]);
getline(cin,strs[2]);
for (j=0 ; j<strs[0].size() ; j+=3)
{
temp = "";
for (i=0 ; i<3 ; i++)
{
temp += strs[i].substr( j, 2 );
}
for (k=0 ; k<10 ; k++)
{
if (temp == nums[k].br)
{
cout << k;
break;
}
}
}
cout << endl;
}
}
return 0;
}
[UVa] 12036 - Stable Grid
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, i, j, t, tst, kase=1;
scanf("%d",&tst);
while ( tst-- )
{
scanf("%d",&n);
int count[200]={0};
bool valid = true;
for (i=1 ; i<=n ; i++)
{
for (j=1 ; j<=n ; j++)
{
scanf("%d",&t);
count[t]++;
if (count[t]>n)
{
valid=false;
}
}
}
if (valid) printf("Case %d: yes\n",kase++);
else printf("Case %d: no\n",kase++);
}
return 0;
}
Sunday, November 20, 2011
[UVa] 11679 - Sub Prime
At a first glance, in particular after reading the name, at least I thought it's about Primes :P. It's pure ad hoc, simulation.
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
class bank
{
public:
int tot_money;
vector< pair<int,int> > dList;
void init() {tot_money=0; dList.clear();}
};
bank banks[30];
int main()
{
//freopen("in.txt","r+",stdin);
//freopen("out.txt","w+",stdout);
int b, n, d, c, m, i, j, increase, decrease;
bool valid;
while (scanf("%d %d",&b,&n)==2)
{
if (!b && !n)
break;
// Input Start
for (i=1 ; i<=b ; i++)
{
banks[i].init();
scanf("%d",&banks[i].tot_money);
}
for (i=1 ; i<=n ; i++)
{
scanf("%d %d %d",&d,&c,&m);
banks[d].dList.push_back( make_pair(c,m) );
}
// Input End
// Process Start
for (i=1 ; i<=b ; i++)
{
for (j=0 ; j<banks[i].dList.size() ; j++)
{
increase = banks[i].dList[j].first;
decrease = banks[i].dList[j].second;
banks[increase].tot_money+=decrease;
banks[i].tot_money-=decrease;
}
}
for (i=1, valid=true ; i<=b ; i++)
{
if (banks[i].tot_money<0)
{
valid = false;
break;
}
}
if (valid) printf("S\n");
else printf("N\n");
// Process End
}
return 0;
}
Wednesday, November 16, 2011
[UVa LIVE] 4493 - This is your queue
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
deque<int> M;
stack<int> Q;
int main()
{
int P, C, i, SER, print, m, t, kase=1;
char CHR[10];
while (scanf("%d %d",&P,&C)==2)
{
if (!P && !C)
break;
printf("Case %d:\n",kase++);
//getchar();
//cout << "---> " << endl;
M.clear();
m = min(P,1000);
for (i=1 ; i<=m ; i++)
{
M.push_back(i);
}
for (i=1 ; i<=C ; i++)
{
t = scanf("%s",CHR);
if (!strcmp(CHR,"N"))
{
print = M.front();
M.pop_front();
printf("%d\n",print);
M.push_back(print);
} else if (!strcmp(CHR,"E"))
{
scanf("%d",&SER);
while (!Q.empty()) Q.pop();
//cout << "------------------------" << endl;
//printf("-> %d\n",SER);
while (!M.empty() && M.front() != SER)
{
//cout << M.front() << endl;
Q.push(M.front());
M.pop_front();
}
if(!M.empty()) M.pop_front();
//cout << "------------------------" << endl;
while (!Q.empty())
{
M.push_front(Q.top());
Q.pop();
}
M.push_front(SER);
}
}
}
return 0;
}
Subscribe to:
Posts (Atom)
Connect Rapoo MT750S with Linux (Tested on Manjaro)
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...
-
I like coding a lot, keeps me glued to the PC for hours. For that reason it's a need to edit the Syntax Highlighter to suit my eyes for... -
Method: The problem at first glance seems too straightforward but it's not that much. Think a bit about the lines "Erin can add ...
-
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...