#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define MAX 50003
#define MAXINT 2147483647
bool ver[MAX]={false};
int ps[MAX], cnt[MAX][2];
int gen(int hiMAX) {
int i, j, k=0;
for (i=2 ; i<=hiMAX ; i++) {
if (!ver[i])
ps[k++]=i;
for (j=i*i ; j>0 && j<=hiMAX ; j+=i*2) {
ver[j]=true;
}
}
return k;
}
int get_count(int n, int p) {
/*printf("get_count(%d, %d)\n",n,p);*/
int sum=0, f=1;
while (n/f>0) {
f*=p;
if (f<0)
break;
sum+=n/f;
}
return sum;
}
int main() {
int i;
int c, m, n, tmp_n, tmp_m, count, p = gen(50000);
bool div;
/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/
while (scanf("%d %d",&n,&m)!=EOF) {
tmp_m = m;
tmp_n = n;
if (m==0 || n==0) {
if (m==1)
printf("%d divides %d!\n",m,n);
else
printf("%d does not divide %d!\n",m,n);
continue;
}
if (m<=n) {
printf("%d divides %d!\n",m,n);
continue;
}
div = false;
for (i=0 ; i<p && ps[i]*ps[i]<=m ; i++) {
if (m%ps[i]==0) {
div = true;
break;
}
}
if (div==false) {
printf("%d does not divide %d!\n",m,n);
continue;
}
for (i=0, c=0 ; i<p && ps[i]*ps[i]<=tmp_m ; i++) {
if (tmp_m%ps[i]==0) {
cnt[c][0]=ps[i];
cnt[c][1]=0;
while (tmp_m%ps[i]==0) {
tmp_m = tmp_m/ps[i];
cnt[c][1]++;
}
c++;
}
}
if (tmp_m>1) {
cnt[c][0]=tmp_m;
cnt[c][1]=1;
c++;
}
/*for (i=0 ; i<c ; i++) {
printf("%d %d %d\n",m,cnt[i][0],cnt[i][1]);
}*/
for (i=0 ; i<c ; i++) {
tmp_n = n;
count = get_count(n,cnt[i][0]);
if (count<cnt[i][1])
break;
}
if (i<c) printf("%d does not divide %d!\n",m,n);
else printf("%d divides %d!\n",m,n);
}
return 0;
}
Wednesday, September 29, 2010
10139 - Factovisors
From a the perspective of a beginner, I think this problem has a lot of gotchas or holes. But you can't blame the judge for being too strict as they are totally inside the statements clever selection of limits and primes.
Thursday, September 16, 2010
Linkin Park - Thousands of light years ahead
Please note that this post may be highly affected by my fairly high liking towards the band. It's completely fine I guess, otherwise.
I'm not in a place where I can buy original CDs of Linkin Park, here after referred to as LP. So, yes I heard their CDs pirated MP3 320 Kbps version. And my judgment is based on that.
I guess LP's habit has become to release albums with a 3 year gap. No wonder, it helps them change their style every time. This time is no different. 2007's static electricity shocks have now turned out to be the 440 Volts. Far away from Hybrid Theory or Meteora or even their closest change Minutes to Midnight, LP has, in my opinion outdone every work they have done so far. A completely different set of sound still hanging onto the same darkness that makes LP so attractive. It's nice how they manage it. The album is a strange mix of Genres. I don't know much about distinguishing them from their way of sounding in between others but it's pure mix of many things. Pop, Rock, Alternative, Reggae, Metal etc. Here's my personal way of seeing at the tracks.
1. The Requiem & The Radiance: The most creative intro by LP so far. It's got every reason to send a shiver down my spine. Feels like a nuclear blast when the girly mixed voice is overshadowed by the flanging and then the oldey vooice telling things while a huge blast takes place multiple times.
2. Burning in the Skies: One thing to note and always remember throughout this album is that it's extensively blended. It's real hard to separate tracks. Mike's voice in this track soothes the lines "I used the dead wood to.....". And Chester's "I'm swimming in the smoke.." really gives the great sounds that were incomplete in "Rock-n-Roll" which he did some years back. The track is a beat based piece of rock backed with some guitars.
3. Empty Spaces & When they come for me: A perfect intro for such a song, Empty Spaces employs some army guys talking during a war or some test run, dunno. Then the African Military beat really is creative piece of music. As always, LP's good tracks never sound good at first time. But suddenly all the sounds mixed up to make the song a huge blast. Awesome rapping from mike and totally unexpected vocals form Chazzy really brought the mood up. "Oh, when they come for me.." those lines are mind-blowing.
4. Robot Boy: Probably we've heard this kind of sound a lot in other bands but I don't know why it just seems like all these years this sound just missed one thing and that's Chester. This is a chorus based song that builds itself up from a piano piece and then turns out with a blast flanged form the background. The lyrics are really good on this. Probably a lot of people will be able to connect themselves to it.
5. Jornada Del Muerto & Waiting for the end: I personally didn't like this kind of Hawaiian sound that Jornada gave me. But the blender builds up into a nice piece that I liked and then that mind blowing song Waiting for the End. My personal favorite on the album. It's a usual mix up of Reggae and some other style that I don't know about but have heard a lot. Still, I guess what makes the song so special to me is the way LP presents it. I've never heard other artists mix this sound with industrial beats so good.
6. Blacout: The intro of this song is my personal favorite. On the internet some people are saying that the way Chester sings fast in this piece is Rapping but I'm sure it's otherwise. It's some style I hear a lot in other RnRs. The way Chazzy builds up the going-crazy mood combined with the calm beats and sounds, it's something nobody's ever heard, I'm sure. The ending is truly great when Mike sings "Hold on..".
7. Wretches & Kings: It's already grown a lot in popularity and I don't think there's much about this song. Expect Fort Minor feat. Linkin Park. But the singing styles are great. Mike sound more like some Jamaican or African guy to me. I kind of liked his piece here. But this songs hasn't caught much of my liking domain. Still would like a lot of Mike's this rapping style.
8. Wisdom, Justice & Love & Iridescent: Martin Luther King has become very famous recently with many artists. It's some lecture he gave from some time back, whatever. Then Iridescent is a really soft piece which sound more like the 2007 "Shadow of the Day".
9. Fallout: It's just the "Burning in the Skies" lines sung from some robotic voice. Good intro to welcome the best song on the album.
10. The Catalyst: The best song on the whole album. Everybody who listens to it will definitely have his own impression of it. But I'm purely freaked out by this. My favourite lines are "Lift me up, let me go". Truly feels like the guys are screaming to the havens. A must try for anyone.
11. The Messanger: I personally liked this track a lot. Chester sounds so "taking-out-lungs" in it. The lyrics are awesome in this.
What I found out after writing this review? Well, I can't write well about songs. Particularly songs that I like so much. Whatever genre you're used to or like I prefer trying this album at least once. Even if LP has abandoned their old styles, they're doing great pieces of the music they are working on. LP ForevAH.
I'm not in a place where I can buy original CDs of Linkin Park, here after referred to as LP. So, yes I heard their CDs pirated MP3 320 Kbps version. And my judgment is based on that.
I guess LP's habit has become to release albums with a 3 year gap. No wonder, it helps them change their style every time. This time is no different. 2007's static electricity shocks have now turned out to be the 440 Volts. Far away from Hybrid Theory or Meteora or even their closest change Minutes to Midnight, LP has, in my opinion outdone every work they have done so far. A completely different set of sound still hanging onto the same darkness that makes LP so attractive. It's nice how they manage it. The album is a strange mix of Genres. I don't know much about distinguishing them from their way of sounding in between others but it's pure mix of many things. Pop, Rock, Alternative, Reggae, Metal etc. Here's my personal way of seeing at the tracks.
1. The Requiem & The Radiance: The most creative intro by LP so far. It's got every reason to send a shiver down my spine. Feels like a nuclear blast when the girly mixed voice is overshadowed by the flanging and then the oldey vooice telling things while a huge blast takes place multiple times.
2. Burning in the Skies: One thing to note and always remember throughout this album is that it's extensively blended. It's real hard to separate tracks. Mike's voice in this track soothes the lines "I used the dead wood to.....". And Chester's "I'm swimming in the smoke.." really gives the great sounds that were incomplete in "Rock-n-Roll" which he did some years back. The track is a beat based piece of rock backed with some guitars.
3. Empty Spaces & When they come for me: A perfect intro for such a song, Empty Spaces employs some army guys talking during a war or some test run, dunno. Then the African Military beat really is creative piece of music. As always, LP's good tracks never sound good at first time. But suddenly all the sounds mixed up to make the song a huge blast. Awesome rapping from mike and totally unexpected vocals form Chazzy really brought the mood up. "Oh, when they come for me.." those lines are mind-blowing.
4. Robot Boy: Probably we've heard this kind of sound a lot in other bands but I don't know why it just seems like all these years this sound just missed one thing and that's Chester. This is a chorus based song that builds itself up from a piano piece and then turns out with a blast flanged form the background. The lyrics are really good on this. Probably a lot of people will be able to connect themselves to it.
5. Jornada Del Muerto & Waiting for the end: I personally didn't like this kind of Hawaiian sound that Jornada gave me. But the blender builds up into a nice piece that I liked and then that mind blowing song Waiting for the End. My personal favorite on the album. It's a usual mix up of Reggae and some other style that I don't know about but have heard a lot. Still, I guess what makes the song so special to me is the way LP presents it. I've never heard other artists mix this sound with industrial beats so good.
6. Blacout: The intro of this song is my personal favorite. On the internet some people are saying that the way Chester sings fast in this piece is Rapping but I'm sure it's otherwise. It's some style I hear a lot in other RnRs. The way Chazzy builds up the going-crazy mood combined with the calm beats and sounds, it's something nobody's ever heard, I'm sure. The ending is truly great when Mike sings "Hold on..".
7. Wretches & Kings: It's already grown a lot in popularity and I don't think there's much about this song. Expect Fort Minor feat. Linkin Park. But the singing styles are great. Mike sound more like some Jamaican or African guy to me. I kind of liked his piece here. But this songs hasn't caught much of my liking domain. Still would like a lot of Mike's this rapping style.
8. Wisdom, Justice & Love & Iridescent: Martin Luther King has become very famous recently with many artists. It's some lecture he gave from some time back, whatever. Then Iridescent is a really soft piece which sound more like the 2007 "Shadow of the Day".
9. Fallout: It's just the "Burning in the Skies" lines sung from some robotic voice. Good intro to welcome the best song on the album.
10. The Catalyst: The best song on the whole album. Everybody who listens to it will definitely have his own impression of it. But I'm purely freaked out by this. My favourite lines are "Lift me up, let me go". Truly feels like the guys are screaming to the havens. A must try for anyone.
11. The Messanger: I personally liked this track a lot. Chester sounds so "taking-out-lungs" in it. The lyrics are awesome in this.
What I found out after writing this review? Well, I can't write well about songs. Particularly songs that I like so much. Whatever genre you're used to or like I prefer trying this album at least once. Even if LP has abandoned their old styles, they're doing great pieces of the music they are working on. LP ForevAH.
[UVa] 10523 - Very Easy!
It's a Big Number problem. Since the limits and the numbers are given, used a simple DP approach to solve it. Had to use two separate multiplication functions since the pointing system yielded some errors unresolvable by me.
#include <iostream>
#include <cstdio>
#define MAXC 2600
#define REPR(i, a, b) for(i=b ; i>=a ; i--)
#define REP(i, a, b) for(i=a ; i<b ; i++)
using namespace std;
char pow[20][160][MAXC]={0};
char mls[20][160][MAXC]={0};
char fin[20][160][MAXC]={0};
int RES[MAXC];
char RES2[MAXC];
int NUM, POW;
char NUMS[1023];
char IPOW[100];
int strpow(char *num, char *ml) {
int SP1 = strlen(num) - 1;
int SP2 = strlen(ml) - 1;
int SP3 = 0 ;
int I, J, K, CUR, CAR;
REPR(I, 0, SP1) {
for (K=SP3, J=SP2, CAR=0 ; J>=0 ; J--, K++) {
CUR = ((num[I]-'0')*(ml[J]-'0')) + RES[K] + CAR;
CAR = 0;
if (CUR>9) {
CAR = CUR/10;
CUR = CUR%10;
} else {
CAR = 0;
}
RES[K]=CUR;
}
if (CAR!=0) RES[K]=CAR;
SP3++;
}
while (RES[K]==0) K--;
for (I=0, K ; K>=0 ; K--, I++) {
pow[NUM][POW][I] = RES[K]+'0';
RES[K] = 0;
}
if (I==0) {
pow[NUM][POW][I++]='0';
}
pow[NUM][POW][I]='\0';
return 0;
}
int strmls(char *num, char *ml) {
int SP1 = strlen(num) - 1;
int SP2 = strlen(ml) - 1;
int SP3 = 0 ;
int I, J, K, CUR, CAR;
REPR(I, 0, SP1) {
for (K=SP3, J=SP2, CAR=0 ; J>=0 ; J--, K++) {
CUR = ((num[I]-'0')*(ml[J]-'0')) + RES[K] + CAR;
CAR = 0;
if (CUR>9) {
CAR = CUR/10;
CUR = CUR%10;
} else {
CAR = 0;
}
RES[K]=CUR;
}
if (CAR!=0) RES[K]=CAR;
SP3++;
}
while (RES[K]==0) K--;
for (I=0, K ; K>=0 ; K--, I++) {
mls[NUM][POW][I] = RES[K]+'0';
RES[K] = 0;
}
if (I==0) {
mls[NUM][POW][I++]='0';
}
mls[NUM][POW][I]='\0';
return 0;
}
int stradd(char *NUM1, char *NUM2) {
int LN_1 = strlen(NUM1);
int LN_2 = strlen(NUM2);
int TEMP, CAR, CUR, I, J, K;
char num1[MAXC], num2[MAXC];
strcpy(num1,NUM1);
strcpy(num2,NUM2);
if (LN_2 > LN_1) { /*-------Swap routine incase of the reverse------*/
TEMP = LN_2;
LN_2 = LN_1;
LN_1 = TEMP;
strcpy(RES2, num1);
strcpy(num1, num2);
strcpy(num2, RES2);
}
for (I=LN_1, CAR=0, J=LN_2, CAR=0, K=0 ; I>0 ; I--, J--, K++) {
CUR = (num1[I-1]-'0') + (J<1?0:num2[J-1]-'0') + CAR;
CAR = 0;
if (CUR>9) {
CAR = 1;
CUR = CUR%10;
} else {
CAR = 0;
}
RES2[K] = CUR + '0';
}
if (CAR) RES2[K++] = CAR + '0';
for (--K, I=0 ; K>=0 ; K--, I++) {
fin[NUM][POW][I] = RES2[K];
}
fin[NUM][POW][I] = '\0';
return 0;
}
int main() {
int I, N, A;
NUM = 1;
POW = 1;
for (I=0 ; I<160 ; I++) {
strcpy(pow[1][I],"1");
strcpy(pow[0][I],"0");
}
REP(NUM, 1, 20) {
sprintf(NUMS,"%d",NUM);
strcpy(pow[NUM][0],"0");
strcpy(pow[NUM][1],NUMS);
strcpy(mls[NUM][1],NUMS);
strcpy(fin[NUM][1],NUMS);
REP(POW, 2, 160) {
strpow(pow[NUM][POW-1],NUMS);
sprintf(IPOW,"%d",POW);
strmls(pow[NUM][POW],IPOW);
stradd(fin[NUM][POW-1],mls[NUM][POW]);
}
}
while (scanf("%d %d",&N,&A)!=EOF) {
if (N==0 || A==0) printf("0\n");
else printf("%s\n",fin[A][N]);
}
return 0;
}
Saturday, September 11, 2010
[UVa] 11437 - Triangle Fun
A very naive solution method. I found the theorems and applied them in the most funny way possible. Wish I knew better methods.
Methods used:
1. Hiron's for getting the area of the triangle from the lengths
2. High School straight lines theorems.
Methods used:
1. Hiron's for getting the area of the triangle from the lengths
2. High School straight lines theorems.
#include <iostream.h>
#include <math.h>
#define DEN (Y4-Y3)*(X2-X1) - (X4-X3)*(Y2-Y1)
int fraction(double Ax, double Ay, double Bx, double By, double &Px, double &Py) {
double Ka=1, Kb=2;
Px = (Ka*Bx + Kb*Ax)/(Ka + Kb);
Py = (Ka*By + Kb*Ay)/(Ka + Kb);
return 0;
}
int intersection(double &X, double &Y, double X1, double X2, double X3, double X4, double Y1, double Y2, double Y3, double Y4) {
double UA;
double UB;
UA = ((X4-X3)*(Y1-Y3) - (Y4-Y3)*(X1-X3)) / (DEN);
UB = ((X2-X1)*(Y1-Y3) - (Y2-Y1)*(X1-X3)) / (DEN);
X = X1 + UA*(X2-X1);
Y = Y1 + UA*(Y2-Y1);
return 0;
}
int length(double X1,double X2,double Y1,double Y2,double &len) {
len = sqrt(pow(X1-X2,2) + pow(Y1-Y2,2));
}
int main() {
/*freopen("11437_in.txt","r",stdin);*/
double Ax, Ay, Bx, By, Cx, Cy, Ka, Kb, Px, Py, Area1, Area2;
double F_1x, F_1y, F_2x, F_2y, F_3x, F_3y;
double F_Ax, F_Ay,F_Bx,F_By,F_Cx,F_Cy;
double a, b, c, s;
int n;
scanf("%d",&n);
while (n--) {
scanf("%lf %lf",&Ax,&Ay);
scanf("%lf %lf",&Bx,&By);
scanf("%lf %lf",&Cx,&Cy);
fraction(Ax,Ay,Bx,By,F_1x,F_1y);
fraction(Bx,By,Cx,Cy,F_2x,F_2y);
fraction(Cx,Cy,Ax,Ay,F_3x,F_3y);
intersection(F_Ax, F_Ay,F_2x,Ax,F_1x,Cx,F_2y,Ay,F_1y,Cy);
intersection(F_Bx,F_By,F_2x,Ax,F_3x,Bx,F_2y,Ay,F_3y,By);
intersection(F_Cx,F_Cy,F_1x,Cx,Bx,F_3x,F_1y,Cy,By,F_3y);
length(F_Ax,F_Bx,F_Ay,F_By,a);
length(F_Bx,F_Cx,F_By,F_Cy,b);
length(F_Cx,F_Ax,F_Cy,F_Ay,c);
s = (double)1/2 * (a+b+c);
printf("%.0lf\n",(double)sqrt(s*(s-a)*(s-b)*(s-c)));
}
return 0;
}
Friday, September 10, 2010
[UVa] 232 - Crossword Answers
First of all, the Problem Description is wrong. The limit is not 10. It's 100 above.
I tried a lot of things including wrong ideas about the output (numbering part).
Explicitly check if the block you're processing starts the word, even though the primary condition of "white" holds.
I tried a lot of things including wrong ideas about the output (numbering part).
Explicitly check if the block you're processing starts the word, even though the primary condition of "white" holds.
#include <stdio.h>
char CW[1000][1000];
char ACC[1000][1000];
char DOW[1000][1000];
int D_LIST[1000], A_LIST[1000];
int NUM[1000][1000];
int main() {
/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/
int I, J, A, D, K, X, Y, CON, COUNTER=1;
while (scanf("%d",&X)==1) {
if (X==0) break;
if (COUNTER>1) printf("\n");
printf("puzzle #%d:\n",COUNTER++);
scanf("%d",&Y);
getchar();
for (I=0 ; I<X ; I++) {
gets(CW[I]);
}
/*for (I=0 ; I<=X ; I++) {
CW[I][0]=CW[0][I]='*';
}*/
A = D = 0;
CON = 0;
for (I=0 ; I<X ; I++) {
for (J=0 ; J<Y ; J++) {
if (CW[I][J]!='*' && (!I || !J || CW[I-1][J]=='*' || CW[I][J-1]=='*')) {
NUM[I][J] = ++CON;
if (!J | CW[I][J-1]=='*') {
for (K=J ; K<Y && CW[I][K]!='*' ; K++) {
ACC[A][K-J]=CW[I][K];
}
ACC[A][K-J]='\0';
A_LIST[A]=NUM[I][J];
A++;
}
if (!I || CW[I-1][J]=='*') {
for (K=I ; K<X && CW[K][J]!='*' ; K++) {
DOW[D][K-I]=CW[K][J];
}
DOW[D][K-I]='\0';
D_LIST[D]=NUM[I][J];
D++;
}
}
}
}
printf("Across\n");
for (I=0 ; I<A ; I++) {
printf("%3d.%s\n",A_LIST[I],ACC[I]);
}
printf("Down\n");
for (I=0 ; I<D ; I++) {
printf("%3d.%s\n",D_LIST[I],DOW[I]);
}
}
return 0;
}
Thursday, September 09, 2010
[UVa] 227 - Puzzle
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char BOARD[7][7];
char STEPS[1000];
int main() {
int COUNT=1, I, J, X, Y, K;
while (1) {
for (X=0 ; X<5 ; X++) {
for (Y=0 ; Y<5 ; Y++) {
BOARD[X][Y] = getchar();
if (BOARD[X][Y]=='Z') {
exit(0);
} else if (BOARD[X][Y]==' ') {
I=X;
J=Y;
}
}
getchar();
}
if (COUNT>1) putchar('\n');
printf("Puzzle #%d:\n",COUNT++);
strcpy(STEPS,"");
while (1) {
gets(&STEPS[strlen(STEPS)]);
if (STEPS[strlen(STEPS)-1]=='0')
break;
}
for (K=0 ; STEPS[K]!='0' ; K++) {
if (STEPS[K]=='A') {
if (I-1>=0) {
BOARD[I][J]=BOARD[I-1][J];
BOARD[I-1][J]=' ';
I--;
} else {
break;
}
} else if (STEPS[K]=='B') {
if (I+1<5) {
BOARD[I][J]=BOARD[I+1][J];
BOARD[I+1][J]=' ';
I++;
} else {
break;
}
} else if (STEPS[K]=='L') {
if (J-1>=0) {
BOARD[I][J]=BOARD[I][J-1];
BOARD[I][J-1]=' ';
J--;
} else {
break;
}
} else if (STEPS[K]=='R') {
if (J+1<5) {
BOARD[I][J]=BOARD[I][J+1];
BOARD[I][J+1]=' ';
J++;
} else {
break;
}
}
}
if (STEPS[K]!='0') {
printf("This puzzle has no final configuration.\n");
} else {
for (I=0 ; I<5 ; I++) {
for (J=0 ; J<5 ; J++) {
putchar(BOARD[I][J]);
if (J<4) {
putchar(' ');
}
}
putchar('\n');
}
}
}
}
[UVa] 555 - Bridge Hands
Well this seems to be a crazy code but it actually gave me a 5th rank.
#include <stdio.h>
#include <string.h>
char chk[14] = "23456789TJQKA";
typedef struct pl {
bool C[100]; //-------|
bool D[100]; //|For recording which
bool S[100]; //|cards does he have
bool H[100]; //-------|
} player;
char STR[10], DEAL1[100], DEAL2[100];
/*------------------------------
TEAM[P%4] Gets the team member
.C .D .S .H are the four Suits
.X[DEAL[I+1]] set that card
--------------------------------*/
int main() {
int I, P;
while (gets(STR)) {
if (!strcmp(STR,"#"))
break;
else if (!strcmp(STR,"N"))
P = 1;
else if (!strcmp(STR,"E"))
P = 2;
else if (!strcmp(STR,"S"))
P = 3;
else
P = 4;
gets(DEAL1);
gets(DEAL2);
player TEAM[5]={false,false,false,false};
for (P, I=0 ; DEAL1[I]!='\0' ; I+=2) {
if (DEAL1[I]=='C') {
TEAM[P++%4].C[DEAL1[I+1]] = true;
}
else if (DEAL1[I]=='D') {
TEAM[P++%4].D[DEAL1[I+1]] = true;
}
else if (DEAL1[I]=='S') {
TEAM[P++%4].S[DEAL1[I+1]] = true;
}
else if (DEAL1[I]=='H') {
TEAM[P++%4].H[DEAL1[I+1]] = true;
}
}
for (P, I=0 ; DEAL2[I]!='\0' ; I+=2) {
if (DEAL2[I]=='C') {
TEAM[P++%4].C[DEAL2[I+1]] = true;
}
else if (DEAL2[I]=='D') {
TEAM[P++%4].D[DEAL2[I+1]] = true;
}
else if (DEAL2[I]=='S') {
TEAM[P++%4].S[DEAL2[I+1]] = true;
}
else if (DEAL2[I]=='H') {
TEAM[P++%4].H[DEAL2[I+1]] = true;
}
}
for (P=2 ; P<6 ; P++) {
if (P == 2) {
printf("S:");
} else if (P == 3) {
printf("W:");
} else if (P == 4) {
printf("N:");
} else {
printf("E:");
}
for (I=0 ; I<14 ; I++) {
if (TEAM[P%4].C[chk[I]]) {
printf(" C%c",chk[I]);
}
}
for (I=0 ; I<14 ; I++) {
if (TEAM[P%4].D[chk[I]]) {
printf(" D%c",chk[I]);
}
}
for (I=0 ; I<14 ; I++) {
if (TEAM[P%4].S[chk[I]]) {
printf(" S%c",chk[I]);
}
}
for (I=0 ; I<14 ; I++) {
if (TEAM[P%4].H[chk[I]]) {
printf(" H%c",chk[I]);
}
}
printf("\n");
}
}
return 0;
}
Finding the highest array position needed for linear representation of a Binary Tree
If a binary tree has suppose 9 nodes then array position for storing its highest possible Root is found like this:
9 = 2^3 + 1
So it’s possible maximum Root is 2^3 – 1 = 7.
So it will take 7 x 2 = 14 places to linearly represent that tree.
And if we are to store even the possible NULLs then it takes 14 x 2 + 1 = 29 Places to linearly represent that tree.
It actually corresponds to the 2^d + 1 formula.
See, if 9 is the maximum node then the tree’s depth is actually 4. And the highest node or Root possible at that level is simply 2^d-1.
9 = 2^3 + 1
So it’s possible maximum Root is 2^3 – 1 = 7.
So it will take 7 x 2 = 14 places to linearly represent that tree.
And if we are to store even the possible NULLs then it takes 14 x 2 + 1 = 29 Places to linearly represent that tree.
It actually corresponds to the 2^d + 1 formula.
See, if 9 is the maximum node then the tree’s depth is actually 4. And the highest node or Root possible at that level is simply 2^d-1.
Wednesday, September 08, 2010
[UVa] 422 - Word Search Wonders
Just brute-force through the matrix and you're done. Using an array for the directions to move in will decrease the amount of coding significantly.
#include <stdio.h>
char INPUT[102][102];
int search(int I, int J, char *Q, int *LI, int *LJ) {
int X_D[9] = { 0, -1, -1, -1, 0, 1, 1, 1};
int Y_D[9] = {-1, -1, 0, 1, 1, 1, 0, -1};
int X, Y, T, S;
for (T=0 ; T<8 ; T++) {
for (X=I, Y=J, S=0 ; Q[S]!='\0' ; S++) {
if (INPUT[X][Y]!=Q[S]) {
break;
} else {
X+=X_D[T];
Y+=Y_D[T];
}
}
if (Q[S]=='\0') {
*LI = X-X_D[T];
*LJ = Y-Y_D[T];
return 1;
}
}
return 0;
}
int main() {
int L, I, J, LI, LJ, FOUND;
char Q[102];
scanf("%d",&L);
for (I=0 ; I<L ; I++) {
scanf("%s",INPUT[I]);
}
while(scanf("%s",Q)==1) {
if (!strcmp(Q,"0"))
break;
for (I=0, FOUND=0 ; I<L && !FOUND ; I++) {
for (J=0 ; J<L ; J++) {
if(INPUT[I][J]==Q[0]) {
if (search(I,J,Q,&LI,&LJ)) {
printf("%d,%d %d,%d\n",I+1, J+1, LI+1, LJ+1);
FOUND = 1;
break;
}
}
}
}
if (!FOUND)
printf("Not found\n");
}
return 0;
}
[UVa] 10050 - Hartals
It's just a simulation. Mods and Mods that's all.
#include <stdio.h>
int parties[101];
int main() {
int I, J, T, N, P, COUNT;
scanf("%d",&T);
while (T--) {
scanf("%d",&N);
scanf("%d",&P);
for (I=0 ; I<P ; I++) {
scanf("%d",&parties[I]);
}
for (I=1, COUNT=0 ; I<=N ; I++) {
if ((I%7)!=6 && (I%7)!=0) {
for (J=0 ; J<P ; J++) {
if (!(I%parties[J])) {
COUNT++;
break;
}
}
}
}
printf("%d\n",COUNT);
}
return 0;
}
[UVa] 10066 - The Twin Towers
Algorithms Used: Longest Common Subsequence
#include <stdio.h>
int C[102][102];
int main() {
int A[102], B[102], I, J, ONE, TWO, MAX, CASES=1;
while (scanf("%d %d",&ONE, &TWO)==2 && ONE && TWO) {
for (I=0 ; I<ONE ; I++) {
scanf("%d",&A[I]);
}
for (I=0 ; I<TWO ; I++) {
scanf("%d",&B[I]);
}
if (TWO>=ONE) MAX = TWO;
else MAX = ONE;
for (I=0 ; I<MAX ; I++) {
C[0][I] = C[I][0] = 0;
}
for (I=1 ; I<=ONE ; I++) {
for (J=1 ; J<=TWO ; J++) {
if (A[I-1] == B[J-1]) {
C[I][J] = C[I-1][J-1] + 1;
} else if (C[I-1][J]>=C[I][J-1]) {
C[I][J] = C[I-1][J];
} else {
C[I][J] = C[I][J-1];
}
}
}
printf("Twin Towers #%d\nNumber of Tiles : ",CASES++);
printf("%d\n\n",C[I-1][J-1]);
}
return 0;
}
[UVa] 10107 - What is the Median
Algorithms used: Insertion Sort
I think with C++ maps this can be solved with a better runtime.
I think with C++ maps this can be solved with a better runtime.
#include <stdio.h>
long int list[10050];
int main() {
long int IN, R, I;
int C=1;
list[0]=-9999;
while (scanf("%ld",&IN)!=EOF) {
for (I=C++ ; IN<list[I-1] ; I--) {
list[I]=list[I-1];
}
list[I] = IN;
if (C%2) {
R = (long int)(( list[(int)C/2] + list[(int)C/2 + 1] )/2);
} else {
R = (long int)list[(int)C/2];
}
printf("%ld\n",R);
}
return 0;
}
[UVa] 10282 - Babelfish
1000000 is no problem. A structure that can contain 2 strings is a good solution. There's a great function in the string.h library called strtok() that can parse the two words. Use qsort() and bsearch() and 0.136s runtime is yours. I got 92nd rank with this so I think it's a moderate solution, or at the very least a solution.
Just FYI, for searching using bsearch() you need to have the query in a similar structure, not in just a string.
Just FYI, for searching using bsearch() you need to have the query in a similar structure, not in just a string.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct w {
char en[25], xx[25];
} word;
word dict[1000002] = {0,0};
int cmp(const void *a, const void *b) {
return strcmp(((word *)a)->xx,((word *)b)->xx);
}
int main() {
int I=0, J;
char INPUT[100], *p;
word *q, QUERY;
while(gets(INPUT)) {
if (!strcmp(INPUT,""))
break;
p = strtok(INPUT," ");
strcpy(dict[I].en,p);
p = strtok(NULL," ");
strcpy(dict[I].xx,p);
I++;
}
qsort(dict,I,sizeof(word),cmp);
while(scanf("%s",QUERY.xx)!=EOF) {
q = bsearch(&QUERY,dict,I,sizeof(word),cmp);
if (q!=NULL) {
printf("%s\n",q->en);
} else {
printf("eh\n");
}
}
return 0;
}
[UVa] 11470 - Square Sums
I think this problem needs no extra explanations. Just be careful for Odd Ordered matrices. For them subtract the middle number at the very last SUM.
The output cannot have space at the very end of each line.
Take the Columns and Rows separately for the SUM. And beware of the corners being added twice.
The code is too rough. A useless separation for Even/Odd comparison. But I'm feeling too tired to correct it right now and I don't like forgetting about posting the codes.
The output cannot have space at the very end of each line.
Take the Columns and Rows separately for the SUM. And beware of the corners being added twice.
The code is too rough. A useless separation for Even/Odd comparison. But I'm feeling too tired to correct it right now and I don't like forgetting about posting the codes.
#include <stdio.h>
int MATRIX[12][12];
int main() {
/*freopen("INPUT.TXT","r",stdin);*/
int ROW, PRO, COLUMN, SIZE, SUM, CASES=1;
while ( scanf("%d",&SIZE)==1 && SIZE!=0 ) {
printf("Case %d: ",CASES++);
/* -----INPUT PROCESS START------ */
for (ROW=0 ; ROW<SIZE ; ROW++) {
for (COLUMN=0 ; COLUMN<SIZE ; COLUMN++) {
scanf("%d",&MATRIX[ROW][COLUMN]);
}
}
/* -----INPUT PROCESS END-------- */
/* -----SUMMING PROCESS START ---*/
if (!(SIZE%2) ) {
for (PRO=0, SUM=0 ; PRO<(int)SIZE/2 ; PRO++) { /* ---SECTIONING TILL HALF LIMIT--- */
/* ----FOR FIRST AND LAST ROWS OF THE SECTION---- */
SUM=0;
for (COLUMN=PRO ; COLUMN<SIZE-PRO ; COLUMN++) {
/*printf("%d %d\n",MATRIX[PRO][COLUMN],MATRIX[SIZE-PRO-1][COLUMN]);*/
SUM += MATRIX[PRO][COLUMN] + MATRIX[SIZE-PRO-1][COLUMN];
}
for (ROW=PRO+1 ; ROW<SIZE-PRO-1 ; ROW++) {
SUM += MATRIX[ROW][PRO] + MATRIX[ROW][SIZE-PRO-1];
}
if (PRO!=((int)SIZE/2)-1) printf("%d ",SUM);
else printf("%d",SUM);
}
} else {
for (PRO=0, SUM=0 ; PRO<=(int)SIZE/2 ; PRO++) { /* ---SECTIONING TILL HALF LIMIT--- */
/* ----FOR FIRST AND LAST ROWS OF THE SECTION---- */
SUM = 0;
for (COLUMN=PRO ; COLUMN<SIZE-PRO ; COLUMN++) {
/*printf("%d %d\n",MATRIX[PRO][COLUMN],MATRIX[SIZE-PRO-1][COLUMN]);*/
SUM += MATRIX[PRO][COLUMN] + MATRIX[SIZE-PRO-1][COLUMN];
}
/*MIDDLEMOST ELEMENT*/
for (ROW=PRO+1 ; ROW<SIZE-PRO-1 ; ROW++) {
SUM += MATRIX[ROW][PRO] + MATRIX[ROW][SIZE-PRO-1];
}
if (PRO!=(int)SIZE/2) printf("%d ",SUM);
}
SUM -= MATRIX[PRO-1][COLUMN-1];
printf("%d",SUM);
}
printf("\n");
}
return 0;
}
[UVa] 11462 - Age Sort
Used algorithm: Counting Sort
Just count how many times an age appeared.
If anybody knows some better algorithm or Input/Output method for faster performance please contact.
Just count how many times an age appeared.
Loop (i = 1 -> 100) {
if (table[i] has some value) {
Show i for that amount of times.
}
}
If anybody knows some better algorithm or Input/Output method for faster performance please contact.
#include <stdio.h>
int main() {
int I, N, J, AGE, maxAGE, PPL[101]={0};
while (scanf("%d",&N) && N!=0) {
maxAGE = 0;
for (I=0 ; I<N ; I++) {
scanf("%d",&AGE);
if (AGE>maxAGE)
maxAGE = AGE;
PPL[AGE]++;
}
for (I=0 ; I<101 ; I++) {
if (PPL[I])
for (J=0 ; J<PPL[I] ; J++) {
if (I==maxAGE && J==PPL[I]-1) printf("%d\n",I);
else printf("%d ",I);
}
PPL[I] = 0;
}
}
return 0;
}
Tuesday, September 07, 2010
[UVa] 11278 - One-Handed Typist
Be careful with the Backslash and Quote signs. You need to C Escape both. Use mappings instead of linear search.
#include <stdio.h>
#define REP(i, a, b) for (i=a ; i<b ; i++)
#define FILE freopen("input.txt","r",stdin)
char *ns = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
char *nsr = "`123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'";
char *s = "~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>?";
char *sr = "~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\"";
char tab[256];
int main() {
int I, LEN1 = strlen(sr), LEN2 = strlen(nsr);
char ch;
REP(I, 0, LEN1) {
tab[s[I]] = sr[I];
}
REP(I, 0, LEN2) {
tab[ns[I]] = nsr[I];
}
while (scanf("%c",&ch)==1) {
if (ch=='\n') putchar('\n');
else if (ch==' ') putchar(' ');
else {
putchar(tab[ch]);
}
}
return 0;
}
[UVa] 11233 - Deli Deli
Everything is given, even the conditions. Just do it the way it's given. Use a structure for the Irregular words and be careful on the 3rd case that's all.
#include <stdio.h>
#define REP(i, a, b) for (i=a ; i<b ; i++)
typedef struct ir {
char word[100], rep[100];
} irr;
irr words[25]={0,0};
int check(char ch[]) {
if (ch[1]=='o' || ch[1]=='s' || ch[1]=='x') return 1;
if (!strcmp(ch,"ch") || !strcmp(ch,"sh")) return 1;
return 0;
}
int main() {
int L, N, I, J, K, LEN, FOUND;
char ch[3], input[25];
scanf("%d %d",&L,&N);
REP(I, 0, L) {
scanf("%s %s",words[I].word, words[I].rep);
}
REP(I, 0, N) {
scanf("%s",input);
FOUND = 0;
REP(J, 0, L) {
if (!strcmp(input,words[J].word)) {
printf("%s\n",words[J].rep);
FOUND = 1;
}
}
if (!FOUND) {
LEN = strlen(input);
ch[0]=input[LEN-2];
ch[1]=input[LEN-1];
ch[2]='\0';
if (ch[0]!='a' && ch[0]!='e' && ch[0]!='i' && ch[0]!='o' && ch[0]!='u' && ch[1]=='y') {
REP(K, 0, LEN-1) {
putchar(input[K]);
}
printf("ies\n");
} else if (check(ch)) {
printf("%ses\n",input);
} else {
printf("%ss\n",input);
}
}
}
return 0;
}
Monday, September 06, 2010
Check out my other site
I'm just a bit freaky about testing scripts, don't know why! Nobody pays me for that, it's a shame I guess. Anyways, I've been using Blogger for such a long time that I got bored. So, and for obvious want of a personal website, I created a Joomla based site. Found some generous people letting me have no ads and helping me install things on the fly. The other site is a good place for keeping records categorized. Thought you might like it. Click here.
You can also check Byethost if you're feeling like having a site of your own, not some go-post-get-out blog. They let you do awesome things like installing new scripts and managing your site explicitly via FTP and what not. I personally installed my own favorite Joomla version there by uploading it there. Not from some script loader.
You can also check Byethost if you're feeling like having a site of your own, not some go-post-get-out blog. They let you do awesome things like installing new scripts and managing your site explicitly via FTP and what not. I personally installed my own favorite Joomla version there by uploading it there. Not from some script loader.
[UVa] 10293 - Word Length and Frequency
Not too simple, yet fun to solve. For the very first time a problem that made me think about building my own input routines. But not yet, I just processed them a lil' bit that's all. I think a smarter code could generate a lot better run time and a lot better ranking though.
#include <stdio.h>
#include <string.h>
int count[100];
char coll[100][100];
int stlen(char in[]) {
int i, count=0;
for (i=0 ; in[i]!='\0' ; i++) {
if ((in[i]>='a'&&in[i]<='z') || (in[i]>='A'&&in[i]<='Z'))
count++;
}
return count;
}
int pro(char in[]) {
int w=0, j=0, i;
for (i=0 ; in[i]!='\0' ; i++, j++) {
if (in[i]=='?' || in[i]=='!' || in[i]==',' || in[i]=='.') {
coll[w][j]='\0';
w++; j=-1;
} else {
coll[w][j]=in[i];
}
}
if (j<0) {
j++;
}
coll[w][j]='\0';
return w;
}
int main() {
char input[100], tmp[100];
int i, j;
strcpy(tmp,"");
while (scanf("%s",input)==1) {
/*---If the end of input is - ---*/
if (input[strlen(input)-1]=='-') {
strcpy(tmp,input);
continue;
}
if (!strcmp(input,"#")) {
for (i=1 ; i<100 ; i++) {
if (count[i]) {
printf("%d %d\n",i,count[i]);
}
count[i]=0;
}
printf("\n");
continue;
}
if (strlen(tmp)) {
/*printf("SEND: %s%s\n",tmp,input);*/
for (i=strlen(tmp), j=0 ; input[j]!='\0' ; j++, i++) {
tmp[i]=input[j];
}
tmp[i]='\0';
j=pro(tmp);
for (i=0 ; i<=j ; i++) {
count[stlen(coll[i])]++;
}
strcpy(tmp,"");
} else {
/*printf("SEND: %s\n",input);*/
j=pro(input);
for (i=0 ; i<=j ; i++) {
count[stlen(coll[i])]++;
}
}
}
return 0;
}
[UVa] 865 - Substitution Cypher
All you need is a table, and because it's such a small limit of possible letters, all you need is a hardly 150-200 sized array in which you can directly map the letters rather than search for them. Helps you access them in 0(1).
#include <stdio.h>
#include <stdlib.h>
char tab[10000];
int main() {
char demo[100], ch, input[1000], plain[200];
int i, t;
scanf("%d",&t);
getchar();
gets(demo);
while (t--) {
for (i=0 ; i<200 ; i++) {
tab[i]=0;
}
gets(plain);
i=0;
while ((ch=getchar())!='\n') {
tab[plain[i++]] = ch;
putchar(ch);
}
putchar('\n');
puts(plain);
while (gets(input)) {
if (!strcmp(input,""))
break;
else {
for (i=0 ; input[i]!='\0' ; i++) {
if (tab[input[i]])
putchar(tab[input[i]]);
else
putchar(input[i]);
}
}
printf("\n");
}
if (t) printf("\n");
}
return 0;
}
Easily changing and editting default lexers in Code::Blocks
It's quite an easy task to accomplish. All you need to do is file replacement. Go to the Code::Blocks directory > share > CodeBlocks > lexers.
Then choose any lexer ".xml" and make a copy of it.
Now rename the older one with something like "oldname"+x.xml and the rename the new copies so that they become replacements.
Now edit the file as you want to meet your needs.
I did this for adding a "Default" color to the HTML/PHP lexer. It helped me build a theme. The default Lexer didn't have any Default color defined. So I increased the amount of Styles it had and just added "Default" from the Cpp Lexer. Neat thing just let me have a new Syntax Highlighter for PHP & HTML.
Then choose any lexer ".xml" and make a copy of it.
Now rename the older one with something like "oldname"+x.xml and the rename the new copies so that they become replacements.
Now edit the file as you want to meet your needs.
I did this for adding a "Default" color to the HTML/PHP lexer. It helped me build a theme. The default Lexer didn't have any Default color defined. So I increased the amount of Styles it had and just added "Default" from the Cpp Lexer. Neat thing just let me have a new Syntax Highlighter for PHP & HTML.
Saturday, September 04, 2010
[UVa] 10699 - Count the Factors
It's a slight modification of the code I used for 583. Simple enough.
#include <stdio.h>
#include <math.h>
#include <string.h>
int primes[7000];
bool marks[60000];
int sieve2(int n)
{
int i, j, k;
memset(marks,true,n);
marks[0] = marks[1] = false;
for (i=4 ; i<n ; i+=2)
marks[i]=false;
for (i=3 ; i*i<n ; i+=2)
{
if (marks[i]==true)
{
for (j=i*i ; j<n ; j+=(2*i))
marks[j]=false;
}
}
for (i=2, j=0 ; i<=n ; i++)
{
if (marks[i]==true)
{
primes[j++]=i;
}
}
return j-1;
}
int main() {
int i, j, kounter=0, q;
int mark=sieve2(50000);
while (scanf("%d",&q) && q)
{
kounter=0;
printf("%d : ",q);
for (j=0 ; primes[j]<q && j<mark ; j++)
{
if (q%primes[j]==0) kounter++;
while (q%primes[j]==0)
{
q/=primes[j];
}
}
if (q>1)
kounter++;
printf("%d\n",kounter);
}
return 0;
}
[UVa] 10789 - Prime Frequency
I tried to solve this problem at the very start of my UVa solving sessions. Then I used a stupid method, bubble sort, non sieve etc. Well, that's what you call improvement I guess, solving it the smarter way.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
bool prime[3000];
char input[2005];
int gen(int n)
{
int i, j;
memset(prime,true,n);
prime[0] = prime[1] = false;
for (i=4 ; i<n ; i+=2)
prime[i]=false;
for (i=3 ; i*i<n ; i+=2)
{
if (prime[i]==true)
{
for (j=i*i ; j<n ; j+=(2*i))
{
prime[j]=false;
}
}
}
return 0;
}
int cmp(const void *a, const void *b)
{
return (*(const char *)a-*(const char *)b);
}
int main()
{
gen(3000);
int t, i, j, kounter=1, len, val=0;
scanf("%d",&t);
while (t--)
{
scanf("%s",input);
printf("Case %d: ",kounter++);
len=strlen(input);
val=0;
qsort(input,len,sizeof(char),cmp);
for (i=0 ; i<len ; )
{
for (j=i ; input[j]==input[i] ; j++);
if (prime[j-i]==true)
{
printf("%c",input[i]);
val++;
}
i=j;
}
if (!val)
printf("empty");
printf("\n");
}
return 0;
}
Friday, September 03, 2010
[UVa] 350 - Pseudo Random Numbers
Straightforward and simulation.
#include <stdio.h>
long int coll[10001]={0};
int main()
{
long int z, i, m, l, p, f, next, s, cas=1;
while (scanf("%ld %ld %ld %ld",&z,&i,&m,&l)==4)
{
p=0;
f=0;
if (z==0 && i==0 && m==0 && l==0)
break;
/***MAIN CODE***/
while (1)
{
next = ((z*l)+i)%m;
for (s=0 ; s<p ; s++)
{
if (coll[s]==next)
{
f=1;
break;
}
}
if (f) break;
coll[p++]=next;
l=next;
}
printf("Case %ld: %ld\n",cas++,p);
}
return 0;
}
Linkin Park - The Catalyst
An awesome song and as always, an awesome video from LP. I just love it. An official HD version is available at the "linkinparktv" YouTube channel. 1080p version is mind blowing.
[UVa] 583 - Prime Factors
All that is gonna keep you from solving this is some TLE, RTE and maybe a bit WA 'cuz of impatient carelessness to higher bounds. Generate a prime table using a sieve. Then do just what you have to do. Don't wanna explain the outputs here, see the code.
Just test it with these inputs before submitting:
Output will be:
Just test it with these inputs before submitting:
2147483647
-2147483647
Output will be:
2147483647 = 2147483647
-2147483647 = -1 x 2147483647
#include <stdio.h>
#include <math.h>
#include <string.h>
int primes[7000];
bool marks[60000];
int sieve2(int n)
{
int i, j, k;
memset(marks,true,n);
marks[0] = marks[1] = false;
for (i=4 ; i<n ; i+=2)
marks[i]=false;
for (i=3 ; i*i<n ; i+=2)
{
if (marks[i]==true)
{
for (j=i*i ; j<n ; j+=(2*i))
marks[j]=false;
}
}
for (i=2, j=0 ; i<=n ; i++)
{
if (marks[i]==true)
{
primes[j++]=i;
}
}
return j-1;
}
int main() {
int i, j, q;
int mark=sieve2(60000);
while (scanf("%d",&q) && q)
{
printf("%d =",q);
if (q<0)
{
printf(" -1 x");
q=-q;
}
if (q==1)
{
printf(" 1\n");
continue;
}
for (j=0 ; primes[j]<q && j<mark ; j++)
{
while (q%primes[j]==0)
{
q/=primes[j];
if (q>1)printf(" %d x",primes[j]);
else printf(" %d",primes[j]);
}
}
if (q>1)
printf(" %d",q);
printf("\n");
}
return 0;
}
Thursday, September 02, 2010
[UVa] 612 - DNA Sorting
Very simple if you think with Structures and stdlib's qsort. Nothing can beat you. No blank line at the end and this is counting your solved list up.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
typedef struct th {
char word[55];
int sort;
} DNA;
DNA str[110]={0,0};
int cmp(const void *a, const void *b) {
return (((DNA *)a)->sort-((DNA *)b)->sort);
}
int main() {
int i, j, k, t, n, m;
char blank[10];
scanf("%d",&t);
getchar();
while (t--) {
gets(blank);
scanf("%d %d",&n,&m);
for (i=0 ; i<m ; i++) {
str[i].sort=0;
scanf("%s",str[i].word);
for (j=0 ; j<n ; j++) {
for (k=j+1 ; k<n ; k++) {
if (str[i].word[j]>str[i].word[k]) {
str[i].sort++;
}
}
}
}
qsort(str,m,sizeof(DNA),cmp);
for (i=0 ; i<m ; i++) {
printf("%s\n",str[i].word);
}
if (t) printf("\n");
getchar();
}
return 0;
}
[UVa] 621 - Secret Research
After getting used to so many critical problems in UVa, you simply can't take this so simply while it is one of the silliest problems. Even the exception condition doesn't really needs a care.
#include "stdio.h"
int main() {
int n, len;
char in[10010];
scanf("%d",&n);
while(n--) {
scanf("%s",in);
if (!strcmp(in,"1") || !strcmp(in,"4") || !strcmp(in,"78"))
printf("+");
else {
len=strlen(in);
if (in[len-2]=='3' && in[len-1]=='5') printf("-");
else if (in[0]=='9' && in[len-1]=='4') printf("*");
else if (in[0]=='1' && in[1]=='9' && in[2]=='0') printf("?");
}
printf("\n");
}
return 0;
}
[UVa] 913 - Joana and the Odd Numbers
The problem is actually inside the generation of the last number in the given line. I followed the method described in the Algorithmist page of it.
To get the number of numbers in a particular line "i" you can use 2(i)-1. So you can easily obtain the number of numbers in the line that you are given to process. But you have to obtain the number of numbers before that line too. As we know that can be obtained as SUM[2(i)-1] with the limits i=1 to N-1. With the acquired result you just add 2(n)-1 and voila. But this is much simpler, with the limit changed to i=1 to N. So we get N(N+1)-N. Which actually yields to N^2. As we know, the last number is also odd so we obtain it using 2(N^2)-1, putting the equation in the braces.
Now what do we need is, judging the 2(N^2)-1 as LAST, we need, LAST-4 + LAST-2 + LAST.
Simplified 3*LAST-6. And you have the answer.
To get the number of numbers in a particular line "i" you can use 2(i)-1. So you can easily obtain the number of numbers in the line that you are given to process. But you have to obtain the number of numbers before that line too. As we know that can be obtained as SUM[2(i)-1] with the limits i=1 to N-1. With the acquired result you just add 2(n)-1 and voila. But this is much simpler, with the limit changed to i=1 to N. So we get N(N+1)-N. Which actually yields to N^2. As we know, the last number is also odd so we obtain it using 2(N^2)-1, putting the equation in the braces.
Now what do we need is, judging the 2(N^2)-1 as LAST, we need, LAST-4 + LAST-2 + LAST.
Simplified 3*LAST-6. And you have the answer.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long int n;
while (scanf("%lld",&n)==1) {
n++; /*Having an offset problem without this, a crazy workaround*/
n=ceil(n/2); /*You have to go backwards to find the line you gotta work on*/
printf("%lld\n",3*(2*n*n-1)-6);
}
return 0;
}
[UVa] 900 - Brick Wall Patterns
A simple sequence related problem. The sequence that it maintains is Fibonacci, with the fib[0] as 1. Other things are just as they always were. Here's the code:
#include <iostream>
using namespace std;
long long int fib[52]={1};
int main() {
int q, i;
fib[0]=1;
fib[1]=1;
for (i=2 ; i<53 ; i++) {
fib[i]=fib[i-1]+fib[i-2];
}
while (scanf("%d",&q)==1 && q) {
printf("%lld\n",fib[q]);
}
return 0;
}
[UVa] 443 - Humble Numbers
This solution uses a simple DP. Keeps a mark on the numbers that are generating the smooths. Then checks for the highest and sets it is the next. A slight modification will solve the 136th Problem, namely ugly numbers.
#include <iostream>
#define LIMIT 5842
#define INTH (long long)1e100
int main() {
long long num[5]={2,3,5,7}, deg[5]={0};
long long ugly[LIMIT]={1}, i, j, cur;
char numq[10], print[10]; int numenq;
for (i=0 ; i<=LIMIT ; i++) ugly[i]=1;
for (i=0 ; i<4 ; i++) deg[i]=0;
for (i=1 ; i<LIMIT ; i++) {
cur=INTH;
for (j=0 ; j<4 ; j++) {
if (cur>ugly[deg[j]]*num[j])
cur=ugly[deg[j]]*num[j];
}
ugly[i]=cur;
for (j=0 ; j<4 ; j++) {
if (cur == (ugly[deg[j]]*num[j]))
deg[j]++;
}
}
while (scanf("%s",numq)==1) {
numenq=atoi(numq);
if (numenq==0) break;
if (numq[strlen(numq)-1]=='1'&&numq[strlen(numq)-2]!='1') strcpy(print,"st");
else if (numq[strlen(numq)-1]=='2'&&numq[strlen(numq)-2]!='1') strcpy(print,"nd");
else if (numq[strlen(numq)-1]=='3'&&numq[strlen(numq)-2]!='1') strcpy(print,"rd");
else strcpy(print,"th");
printf("The %d%s humble number is %lld.\n",numenq,print,ugly[numenq-1]);
}
return 0;
}
Wednesday, September 01, 2010
[UVa] 156 - Anagrams
The method is simple. Sort both strings and run strcmp() on them. If the result is zero then same else not.
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct w {
char orig[100], sort[100];
} word;
word dict[1002]={0,0};
char print[1002][100];
int cmp_c(const void *a, const void *b) {
return (*(char*)a-*(char*)b);
}
int cmp_s(const void *a, const void *b) {
return (strcmp(a,b));
}
int main() {
int i, j, k, l;
int p;
for (i=0 ; scanf("%s",dict[i].orig) && strcmp(dict[i].orig,"#") ; i++) {
for (j=0 ; dict[i].sort[j]=tolower(dict[i].orig[j]) ; j++);
qsort(dict[i].sort,strlen(dict[i].sort),sizeof(char),cmp_c);
}
for (j=0, p=0, l=0 ; j<i ; j++, p=0) {
if (strlen(dict[j].orig) == 1) {
strcpy(print[l++],dict[j].orig);
continue;
}
for (k=0 ; k<i ; k++) {
if (!strcmp(dict[k].sort,dict[j].sort) && k!=j){
p=1;
break;
}
}
if (!p) strcpy(print[l++],dict[j].orig);
}
qsort(print,l,sizeof(print[0]),cmp_s);
for (k=0 ; k<l ; k++) printf("%s\n",print[k]);
return 0;
}
[UVa] 111 - History Grading
The main thing about this problem is not in the fact that you have to know some extraordinary algo thingy, it's simply LCS but with a twist. The problem statement clearly says that the input will be the ranks of the incidents.
So, what you you actually get isn't the real sequence. It's a sequence which you should use to make the sequence you want. Modify every given sequence (incl. the main one) in the following manner.
Suppose 2 1 3 5 6 4
It is 2 1 3 6 4 5
The sequence is telling you to put the positions in the directed places.
2 is 1st so 1 goes 2nd
1 is 2nd so 2 goes 1st
3 is 3rd so 3 stays 3rd
5 is 4th so 4 goes 5th
6 is 5th so 5 goes sixth
4 is 6th so 6 goes 4th
Now when the sequences are prepared, run LCS on it an voila!!
1 point for each event whose rank matches its correct rank
So, what you you actually get isn't the real sequence. It's a sequence which you should use to make the sequence you want. Modify every given sequence (incl. the main one) in the following manner.
Suppose 2 1 3 5 6 4
It is 2 1 3 6 4 5
The sequence is telling you to put the positions in the directed places.
2 is 1st so 1 goes 2nd
1 is 2nd so 2 goes 1st
3 is 3rd so 3 stays 3rd
5 is 4th so 4 goes 5th
6 is 5th so 5 goes sixth
4 is 6th so 6 goes 4th
Now when the sequences are prepared, run LCS on it an voila!!
#include "stdio.h"
int max(int a, int b) {
if (a>=b) return a;
else return b;
}
int main() {
int i, j, n_evt, q, temp;
int seq_main[22], pro[22], c[22][22];
scanf("%d",&n_evt);
for (i=0 ; i&n_evt ; i++) {
scanf("%d",&temp);
seq_main[temp-1]=i+1;
}
while (scanf("%d",&temp)==1) {
pro[temp-1]=1;
for (q=1 ; q<n_evt ; q++) {
scanf("%d",&temp);
pro[temp-1]=q+1;
}
for (i=0 ; i<=n_evt ; i++) {
c[i][0] = c[0][i] = 0;
}
for (i=1 ; i<=n_evt ; i++) {
for (j=1 ; j<=n_evt ; j++) {
if (seq_main[i-1]==pro[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
} else {
c[i][j] = max(c[i-1][j],c[i][j-1]);
}
}
}
printf("%d\n",c[n_evt][n_evt]);
i=j=q=0;
}
return 0;
}
[UVa] 102 - Ecological Bin Packing
Simple enough. Just have to check the six combinations and the answer is ready.
Here's my solution. I know it has an extremely short solution but I did this one.
#include <stdio.h>
int main()
{
char comb[6][4]={"BCG","BGC","CBG","CGB","GBC","GCB"};
long int input[9]={0}, i=1, count=0, mincount=999999999, com;
while (scanf("%ld",&input[i])==1)
{
for (i=2 ; i<=9 ; i++)
{
scanf("%ld",&input[i]);
}
for (i=0, count=0 ; i<6 ; i++)
{
if (comb[i][0]=='B')
{
if (comb[i][1]=='C')
{
count=input[4]+input[7]+input[3]+input[9]+input[2]+input[5];
} else
{
count=input[4]+input[7]+input[2]+input[8]+input[3]+input[6];
}
} else if (comb[i][0]=='C')
{
if (comb[i][1]=='B')
{
count=input[6]+input[9]+input[1]+input[7]+input[2]+input[5];
} else
{
count=input[6]+input[9]+input[2]+input[8]+input[1]+input[4];
}
} else if (comb[i][0]=='G')
{
if (comb[i][1]=='B')
{
count=input[5]+input[8]+input[1]+input[7]+input[3]+input[6];
} else
{
count=input[5]+input[8]+input[3]+input[9]+input[1]+input[4];
}
}
if (count<mincount)
{
mincount=count;
com=i;
count=0;
}
}
printf("%s %ld\n",comb[com],mincount);
i=1;
mincount=999999999;
}
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... -
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... -
Install MinGW GCC Port on Windows. 1. Just go to this address [ http://sourceforge.net/projects/mingw/files/Installer/mingw-get-inst/ ]...