#include<stdio.h> #include<string.h> int main() { // freopen("input.txt","r",stdin); char ch[1000]; while(gets(ch)!=NULL) { if(strcmp(ch,"e/o/i")==0)break; int i=0,j,k,l,m=0,n=1,f=0,l1=0,l2=0,l3=0; while(ch[i]!='/') { if(ch[i]=='a'||ch[i]=='e'||ch[i]=='i'||ch[i]=='o'||ch[i]=='u'||ch[i]=='y') { m=1; } else { if(m==1) l1++; m=0; } i++; } if(m==1) { l1++; m=0; } i++; while(ch[i]!='/') { if(ch[i]=='a'||ch[i]=='e'||ch[i]=='i'||ch[i]=='o'||ch[i]=='u'||ch[i]=='y') { m=1; } else { if(m==1) l2++; m=0; } i++; } if(m==1) { l2++; m=0; } i++; ch[strlen(ch)]='/'; while(ch[i]!='/') { if(ch[i]=='a'||ch[i]=='e'||ch[i]=='i'||ch[i]=='o'||ch[i]=='u'||ch[i]=='y') { m=1; } else { if(m==1) l3++; m=0; } i++; } if(m==1) { l3++; m=0; } i++; if(l1!=5)printf("1\n"); else if(l2!=7)printf("2\n"); else if(l3!=5)printf("3\n"); else printf("Y\n"); } return 0; }
Showing posts with label uva. Show all posts
Showing posts with label uva. Show all posts
Saturday, August 30, 2014
uva : 576 - Haiku Review
uva : 573 - The Snail
#include <iostream> using namespace std; int main() { double h,u,d,f; while (cin>>h>>u>>d>>f) { if (h==0) break; int day=0; double fatigue=u*f/100.0,height=0; while (height<h && height>=0) { double climbed=u-fatigue*day; if (fatigue<=climbed) height+=climbed; day++; if (height>h) break; height-=d; // cout<<"height = "<<height<<endl; } if (height>=h) cout<<"success on day "<<day<<endl; else if (height<0) cout<<"failure on day "<<day<<endl; } return 0; }
uva : 572 - Oil Deposits
#include<cstdio> #include<queue> using namespace std; int main() { //freopen("input.txt","r",stdin); int row,col; while(scanf("%d %d\n",&row,&col)==2&&(row+col)!=0) { int number[row+1][col+1]; for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) { char ch=getchar(); if(ch=='*')number[i][j]=0; else if(ch=='@')number[i][j]=1; } getchar(); } int count=0; for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) { if(number[i][j]==1) { count++; queue<int>r,c; r.push(i); c.push(j); while(!r.empty()) { int x=r.front(),y=c.front(); r.pop();c.pop(); if(x-1>0&&number[x-1][y]==1) { r.push(x-1);c.push(y);number[x-1][y]=0; } if(y-1>0&&number[x][y-1]==1) { r.push(x);c.push(y-1);number[x][y-1]=0; } if(x+1<=row&&number[x+1][y]==1) { r.push(x+1);c.push(y);number[x+1][y]=0; } if(y+1<=col&&number[x][y+1]==1) { r.push(x);c.push(y+1);number[x][y+1]=0; } if(x-1>0&&y-1>0&&number[x-1][y-1]==1) { r.push(x-1);c.push(y-1);number[x-1][y-1]=0; } if(x-1>0&&y+1<=col&&number[x-1][y+1]==1) { r.push(x-1);c.push(y+1);number[x-1][y+1]=0; } if(x+1<=row&&y-1>0&&number[x+1][y-1]==1) { r.push(x+1);c.push(y-1);number[x+1][y-1]=0; } if(x+1<=row&&y+1<=col&&number[x+1][y+1]==1) { r.push(x+1);c.push(y+1);number[x+1][y+1]=0; } } } } } printf("%d\n",count); } return 0; }
uva : 568 - Just the Facts
#include<stdio.h> int main() { int n; while(scanf("%d",&n)==1) { if(n==0) break; long num1[300000],lnum1=1,i,j,k,m,r=0,sum=0; num1[0]=1; for(i=2;i<=n;i++) { for(j=0;j<lnum1;j++) { m=(num1[j]*i+r)%10; r=(num1[j]*i+r)/10; num1[j]=m; } while(r!=0) { num1[lnum1++]=r%10; r=r/10; } } for(i=0;i<lnum1;i++) { if(num1[i]>0) break; } printf("%5d -> %d\n",n,num1[i]); } return 0; }
Friday, August 29, 2014
uva : 429 - Word Transformation
#include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<cmath> #include<iostream> #include<vector> #include<map> using namespace std; int main() { //freopen("input.txt","r",stdin); int test,y=1; scanf("%d",&test); getchar(); getchar(); while(test--) { if(y>1)printf("\n"); y=3; map<string,int>word; vector<string>s; int i,j,k,l,m,n,c=1; string s1,s2,s3; while(cin >> s1 && s1!="*") { word[s1]=c++; s.push_back(s1); } sort(s.begin(),s.end()); int graph[s.size()][s.size()]; for(i=0;i<s.size();i++) { for(j=0;j<s.size();j++)graph[i][j]=0; } for(i=0;i<c-1;i++) { for(j=0;j<c-1;j++) { if(s[i].length()==s[j].length()&&i!=j) { int count=0; for(k=0;k<s[i].length();k++) { if(s[i][k]!=s[j][k])count++; } if(count==1) { m=word[s[i]]-1; n=word[s[j]]-1; graph[m][n]=1; //graph[n][m]=1; } } } } char temporary[50]; int len; char *p; cin.getline(temporary, sizeof(temporary)); // eat new line while (cin.getline(temporary, sizeof(temporary))){ len = strlen(temporary); if (len == 0) break; p = strtok(temporary, " \n\t"); string start(p); p = strtok(NULL, " \n\t"); string end(p); int color[c],d[c]; for(i=0;i<c;i++) { color[i]=d[i]=0; } queue<int>q; int source=word[start]-1; int destination=word[end]-1; //printf("%d %d\n",source,destination); q.push(source); color[source]=1; while(!q.empty()) { int u=q.front(); q.pop(); if(u==destination)break; for(i=0;i<c-1;i++) { if(graph[u][i]==1&&color[i]==0) { color[i]=1; q.push(i); d[i]=d[u]+1; } } } cout << start << " " << end << " " << d[destination] << endl; } } return 0; }
Monday, August 25, 2014
uva : 541 - Error Correction
#include < stdio.h > #include < string.h > int main() { int n; while (scanf("%d", & n) == 1 && n != 0) { int num1[200][200], i, j, k, l, m = 0, row, col, c1 = 0, c2 = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", & num1[i][j]); } } for (i = 0; i < n; i++) { k = 0; for (j = 0; j < n; j++) { k = k + num1[i][j]; } if (k % 2 == 1) { c1++; row = i; } } for (j = 0; j < n; j++) { k = 0; for (i = 0; i < n; i++) { k = k + num1[i][j]; } if (k % 2 == 1) { c2++; col = j; } } if (c1 == 0 && c2 == 0) { printf("OK\n"); } else if (c1 == 1 && c2 == 1) { printf("Change bit (%d,%d)\n", row + 1, col + 1); } else { printf("Corrupt\n"); } } return 0; }
uva : 540 - Team Queue
#include < cstdio > #include < iostream > #include < cmath > #include < map > #include < queue > #include < algorithm > #include < vector > using namespace std; int main() { int team, y = 1; while (scanf("%d", & team) == 1 && team != 0) { printf("Scenario #%d\n", y++); queue < int > q[team + 1]; int i, j, k, l = 0, m, n, co = 0, num[200003]; map < int, int > number; map < int, int > index; queue < int > start; for (i = 1; i <= team; i++) { scanf("%d", & n); for (j = 0; j < n; j++) { scanf("%d", & m); number[m] = i; } } string s; while (cin >> s && (s != "STOP")) { if (s == "ENQUEUE") { scanf("%d", & n); m = number[n]; q[m].push(n); for (i = l; i < co; i++) { if (num[i] == m) break; } if (i == co) { num[co++] = m; } } if (s == "DEQUEUE") { int f = 0; for (i = l; i < co; i++) { m = num[i]; while (!q[m].empty()) { printf("%d\n", q[m].front()); q[m].pop(); f = 1; break; } if (q[m].empty()) l++; if (f == 1) break; } } } printf("\n"); } return 0; }
uva: 558 - Wormholes
#include<stdio.h> const int INF = 10000000; const int MX = 2050; int m,n,d[MX]; struct Node { int u,v,w; }nodes[MX]; void initializeSingleSource(int s) { for(int i=0;i<n;i++) { d[i]=INF; d[s]=0; } } void relax(int u,int v ,int w) { if(d[v]>d[u]+w) { d[v]=d[u]+w; } } bool bellmanFord(int s) { initializeSingleSource(s); int i,j,k; for(i=0;i<n-1;i++) { for(j=0;j<m;j++) { relax(nodes[j].u,nodes[j].v,nodes[j].w); } } for(j=0;j<m;j++) { if (d[nodes[j].v] > d[nodes[j].u] + nodes[j].w) return false; } return true; } int main() { int test; scanf("%d",&test); while(test--) { scanf("%d %d",&n,&m); int i,j,k,l; for(i=0;i<m;i++) { scanf("%d %d %d",&nodes[i].u,&nodes[i].v,&nodes[i].w); } if(!bellmanFord(0))printf("possible\n"); else printf("not possible\n"); } return 0; }
uva : 567 - Risk
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<queue> #include<vector> using namespace std; int main() { //freopen("input.txt","r",stdin); int i,j,k,l,m,n,y=1; while(scanf("%d",&n)==1) { vector<int>country[1000]; for(i=1;i<=n;i++) { scanf("%d",&m); country[1].push_back(m); country[m].push_back(1); } for(i=2;i<20;i++) { scanf("%d",&n); for(j=1;j<=n;j++) { scanf("%d",&m); country[i].push_back(m); country[m].push_back(i); } } int n; scanf("%d",&n); printf("Test Set #%d\n",y++); while(n--) { int source,destination,d[21],color[21]; scanf("%d %d",&source,&destination); for(i=1;i<=20;i++) { color[i]=0; } queue<int>q; q.push(source); while(!q.empty()) { int u=q.front(); q.pop(); if(u==destination)break; for(i=0;i<country[u].size();i++) { int v=country[u][i]; if(color[v]==0) { q.push(v); color[v]=color[u]+1; } } } printf("%2d to %2d: %d\n",source,destination,color[destination]); } printf("\n"); } return 0;
uva :544 - Heavy Cargo
#include<cstdio> #include<iostream> #include<map> #include<vector> #include<queue> #include<algorithm> #include<string> using namespace std; int main() { int i,j,k,l,m,n,vertex,road,y=0; while(scanf("%d %d",&vertex,&road)==2) { if((vertex+road)==0)break; int graph[vertex+1][vertex+1]; for (i=1;i<=vertex;i++) { for(j=1;j<=vertex;j++) graph[i][j]=0; } int c=1; string s1,s2; map<string, int>number; for(i=0;i<road;i++) { cin >> s1 >> s2 >> n; if(number[s1]==0)number[s1]=c++; if(number[s2]==0)number[s2]=c++; j=number[s1]; k=number[s2]; graph[j][k]=n; graph[k][j]=n; } for(int k=1;k<=vertex;k++) { for(int i=1;i<=vertex;i++) { for(int j=1;j<=vertex;j++) { graph[i][j]=max(graph[i][j],min(graph[i][k],graph[k][j])); } } } cin >> s1 >> s2; cout << "Scenario #" << ++y << endl; cout << graph[number[s1]][number[s2]]<<" tons" << endl << endl; } return 0; }
uva : 543 - Goldbach's Conjecture
#include<stdio.h> #include<math.h> int main() { long num; while(scanf("%ld",&num)==1) { if(num==0) break; long i,j,k,l,m=0,n=0,nn=0; for(i=2;i<=(num/2)+1;i++) { n=0; for(j=2;j<=sqrt(i);j++) { if(i%j==0) n++; } if(n==0) { m=num-i;k=0; for(j=2;j<=sqrt(m);j++) { if(m%j==0) { k++; } } if(k==0) { nn=1; break; } } } if(nn==0) { printf("Goldbach's conjecture is wrong.\n"); } else { printf("%ld = %ld + %ld\n",num,i,m); } } return 0; }
uva : 537 - Artificial Intelligence?
#include <iostream> #include <stdlib.h> #include <iomanip> using namespace std; int main(){ char ls[] = {'P', 'I', 'U'}; string alls[] = {"WmkM", "AmkM", "VmkM"}; char unds[] = {'W', 'A', 'V'}; string dats[3]; double ddats[3]; string funds[3]; int cases; cin >> cases; cin.get(); for(int c=1; c<=cases; ++c){ cout << "Problem #" << c << endl; string problem; getline(cin, problem); for(int i=0; i<3; ++i){ string aux = " "; aux += ls[i]; aux += '='; int f = problem.find(aux); if(f!=-1) f+=3; else if(f==-1 && problem[0]==ls[i] && problem[1]=='=') f=2; dats[i] = ""; ddats[i] = -1; funds[i] = ""; if(f!=-1){ int f2 = problem.find_first_of(alls[i],f); int f3 = problem.find_first_of(unds[i],f2); dats[i] = problem.substr(f, f2-f); ddats[i] = atof(dats[i].data()); funds[i] = problem.substr(f2, f3-f2+1); if(funds[i].size()>1){ if(funds[i][0] == 'm') ddats[i] /= 1000; else if(funds[i][0] == 'k') ddats[i] *= 1000; else if(funds[i][0] == 'M') ddats[i] *= 1000000; } } } if(dats[0] == ""){ double P = ddats[1] * ddats[2]; cout << "P=" << fixed << setprecision(2) << P << "W" << endl; }else if(dats[1] == ""){ double I = ddats[0] / ddats[2]; cout << "I=" << fixed << setprecision(2) << I << "A" << endl; }else if(dats[2] == ""){ double U = ddats[0] / ddats[1]; cout << "U=" << fixed << setprecision(2) << U << "V" << endl; } cout << endl; } return 0; }
uva :536 - Tree Recovery
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 30;
char preOrder[MAXN];
char midOrder[MAXN];
struct Node{
char c;
Node *left;
Node *right;
Node(char c){
this->c = c;
this->left = left;
this->right = right;
}
};
Node *root;
Node* createTree(char *pre , char *mid , int len){
if(len == 0)
return NULL;
int k = 0;
while(mid[k] != pre[0])
k++;
Node *root = new Node(pre[0]);
root->left = createTree(pre+1 , mid , k);
root->right = createTree(pre+k+1 , mid+k+1 , len-k-1);
return root;
}
void output(Node *u){
if(u != NULL){
output(u->left);
output(u->right);
printf("%c" , u->c);
}
}
void solve(){
int len = strlen(preOrder);
root = createTree(preOrder , midOrder , len);
output(root);
puts("");
}
int main(){
while(scanf("%s" , preOrder) != EOF){
scanf("%s" , midOrder);
solve();
}
return 0;
}
uva : 534 - Frogger
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cctype> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <sstream> #include <cmath> #include <bitset> #include <utility> #include <set> #define INT_MAX 2147483647 #define INT_MIN -2147483648 #define pi acos(-1.0) #define N 1000000 #define LL long long using namespace std; double power (int b, int p) { double ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; } int main () { int stones; int cases = 0; while ( scanf ("%d", &stones) && stones ) { int x [200 + 10]; int y [200 + 10]; for ( int i = 0; i < stones; i++ ) scanf ("%d %d", &x [i], &y [i]); double d [200 + 10] [200 + 10]; for ( int i = 0; i < stones; i++ ) { for ( int j = i + 1; j < stones; j++ ) d [i] [j] = d [j] [i] = sqrt (power (x [i] - x [j], 2) + power (y [i] - y [j], 2)); } for ( int k = 0; k < stones; k++ ) { for ( int i = 0; i < stones; i++ ) { for ( int j = 0; j < stones; j++ ) d [i] [j] = min (d [i] [j], max (d [i] [k], d [k] [j])); } } printf ("Scenario #%d\n", ++cases); printf ("Frog Distance = %.3lf\n\n", d [0] [1]); } return 0; }
uva : 532 - Dungeon Master
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include < cstdio > #include < queue > using namespace std; char dungeon[32][32][32]; int Distance[32][32][32]; int L, R, C; const int direction[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } }; struct point_type { int x; int y; int z; }; int BFS(int i, int j, int k) { Distance[i][j][k] = 0; queue < point_type > q; q.push(point_type { i, j, k }); dungeon[i][j][k] = '#'; point_type cur, nxt; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i < 6; ++i) { nxt.x = cur.x + direction[i][0]; nxt.y = cur.y + direction[i][1]; nxt.z = cur.z + direction[i][2]; if (nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue; if (dungeon[nxt.x][nxt.y][nxt.z] != '#') { Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1; if (dungeon[nxt.x][nxt.y][nxt.z] == 'E') return Distance[nxt.x][nxt.y][nxt.z]; dungeon[nxt.x][nxt.y][nxt.z] = '#'; q.push(nxt); } } } return -1; } int main() { while (scanf("%d%d%d", & L, & R, & C)) { if (!L && !R && !C) break; int start_i, start_j, start_k; for (int i = 0; i < L; ++i) { for (int j = 0; j < R; ++j) { scanf("%s", dungeon[i][j]); for (int k = 0; k < C; ++k) if (dungeon[i][j][k] == 'S') { start_i = i; start_j = j; start_k = k; } } } int minute = BFS(start_i, start_j, start_k); if (minute != -1) printf("Escaped in %d minute(s).\n", minute); else printf("Trapped!\n"); } return 0; } |
Subscribe to:
Posts (Atom)