10194 - Football (aka Soccer)

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

10194 - Football (aka Soccer)

Post by naushad » Mon Jul 15, 2002 1:11 pm

my big program :( 10194 giving un time error!! :cry: plz go through my code. and help if u can :o
regards,
naushad:-)

/* @JUDGE_ID: 16916** 10194 C++ "Naushad's Programming" */

/* "@BEGIN_OF_SOURCE_CODE" */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int strcmpti(char str1[], char str2[])
{
int i;
int len1 = strlen(str1);
int len2 = strlen(str2);
if(len1>len2)
{
for(i=0;i<len1;i++)
{
if(toupper(str1)>toupper(str2))
return 1;
else if(toupper(str1)<toupper(str2))
return -1;
else return 0;

}
}
else if(len2>len1)
{
for(i=0;i<len2;i++)
{
if(toupper(str2)>toupper(str1))
return 1;
else if(toupper(str2)<toupper(str1))
return -1;
else return 0;

}
}
else return 0;

}
struct TE
{
char Tname[31];
int Point;
int Win;
int Loss;
int Ties;
int Gdiff;
int Mgoal;
int Kgoal;
int Lply;
};
int compare(const void *a,const void *b)
{
int t;
t = ((TE*)b)->Point - ((TE*)a)->Point;
if(t!=0)return t;
t = ((TE*)b)->Win - ((TE*)a)->Win;
if(t!=0)return t;
t = ((TE*)b)->Gdiff - ((TE*)a)->Gdiff;
if(t!=0)return t;
t = ((TE*)b)->Mgoal - ((TE*)a)->Mgoal;
if(t!=0)return t;
t = ((TE*)a)->Lply - ((TE*)b)->Lply;
if(t!=0)return t;
t = strcmpti(((TE*)b)->Tname,((TE*)a)->Tname);
if(t!=0)return t;
}
int i;
struct TE Fifa[31];
void main()
{
int N;
char Ginfo[1000];
while(scanf("%d",&N)!=EOF)
{
while(N--)
{
char tour[100];
fflush(stdin);
gets(tour);
int T,dummy;
scanf("%d",&T);
dummy = T;
for(i=0;i<T;i++)
{
Fifa.Point=0;
Fifa.Win=0;
Fifa[i].Gdiff=0;
Fifa[i].Mgoal=0;
Fifa[i].Kgoal=0;
Fifa[i].Lply=0;
Fifa[i].Loss=0;
Fifa[i].Ties=0;
}
i=0;
fflush(stdin);
while(i!=dummy)
{
gets(Fifa[i++].Tname);
}
int G, kak;
scanf("%d",&G);
dummy = G;
while(dummy--)
{
char T1[31], T2[31];
int Tgo1, Tgo2;
fflush(stdin);
gets(Ginfo);
int len = strlen(Ginfo);
for(i=0;i<len;i++)
{
if(Ginfo[i]==' ')
Ginfo[i] = '@';
}

for(i=0;i<len;i++)
{
if(Ginfo[i]=='#')
Ginfo[i] = ' ';
}
char goru[30];
sscanf(Ginfo,"%s %s %s",&T1,&goru,&T2);
len = strlen(T1);
for(i=0;i<len;i++)
{
if(T1[i]=='@')
T1[i] = ' ';
}
len = strlen(T2);
for(i=0;i<len;i++)
{
if(T2[i]=='@')
T2[i] = ' ';
}
sscanf(goru,"%d@%d",&Tgo1,&Tgo2);
for(i=0;i<T;i++)
{
kak = strcmp(T1,Fifa[i].Tname);
if((!kak))
{
Fifa[i].Mgoal += Tgo1;
Fifa[i].Kgoal += Tgo2;
if(Tgo1>Tgo2)
{
Fifa[i].Point += 3;
Fifa[i].Win++;
Fifa[i].Lply++;
}
else if(Tgo1<Tgo2)
{
Fifa[i].Point += 0;
Fifa[i].Lply++;
Fifa[i].Loss++;
}
else
{
Fifa[i].Point += 1;
Fifa[i].Lply++;
Fifa[i].Ties++;
}
break;
}
}

for(i=0;i<T;i++)
{
kak = strcmp(T2,Fifa[i].Tname);
if(!(kak))
{
Fifa[i].Mgoal += Tgo2;
Fifa[i].Kgoal += Tgo1;
if(Tgo2>Tgo1)
{
Fifa[i].Point += 3;
Fifa[i].Win++;
Fifa[i].Lply++;
}
else if(Tgo2<Tgo1)
{
Fifa[i].Point += 0;
Fifa[i].Lply++;
Fifa[i].Loss++;
}
else
{
Fifa[i].Point += 1;
Fifa[i].Lply++;
Fifa[i].Ties++;
}
break;
}
}

}
for(i=0;i<T;i++)
Fifa[i].Gdiff = Fifa[i].Mgoal - Fifa[i].Kgoal;

printf("%s\n",tour);
fflush(stdin);
qsort((void*) Fifa, T, sizeof(Fifa[0]), compare);

for(i=0;i<T;i++)
{
printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n",i+1,
Fifa[i].Tname, Fifa[i].Point,Fifa[i].Lply,Fifa[i].Win,Fifa[i].Ties,Fifa[i].Loss,
Fifa[i].Gdiff,Fifa[i].Mgoal,Fifa[i].Kgoal);
}
}
}
}
/*"@END_OF_SOURCE_CODE" */

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Silly Mistake

Post by shahriar_manzoor » Mon Jul 15, 2002 1:50 pm

Hello Naushad,
I guess you have made a silly mistake. Tournament names can have at most 100 characters. So the array used to read it should have 101 characters. As computer memory does not cost anything, why don't you take more than enough length to read it. Ofcourse, your program may have other mistakes.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10194 WA

Post by dwyak » Fri Sep 13, 2002 9:57 am

Who can tell me if there is any trick?
I can't find any mistakes in my program.

[cpp]#include <fstream.h>
#include <strstream.h>
#include <string.h>
#include <stdlib.h>

//ifstream fin("10194.txt");
#define fin cin
#define endl '\n'

class team {
public:
char name[50];
int point, game, win, tie, lose, gd, gs, ga;
};

const int MAX = 1000;

char line[MAX], name[MAX];
team t[100];
int tot, g[100][100][2];

int getid(char name[]) {
int i;
for (i = 1; i <= tot; i++)
if (strcmp(t.name, name) == 0)
return i;
return 0;
}

int cmp(const void* e1, const void* e2) {
const team* t1 = (const team*)e1;
const team* t2 = (const team*)e2;
if (t1->point != t2->point) return t2->point - t1->point;
if (t1->win != t2->win) return t2->win - t1->win;
if (t1->gd != t2->gd) return t2->gd - t1->gd;
if (t1->gs != t2->gs) return t2->gs - t1->gs;
if (t1->game != t2->game) return t1->game - t2->game;
return strcmp(t1->name, t2->name);
}

main() {
int cases, pcase;
fin >> cases; fin.getline(line, MAX);
for (pcase = 0; pcase < cases; pcase++) {
if (pcase) cout << endl;
fin.getline(line, MAX);
cout << line << endl;

int i;
memset(t, 0, sizeof(t));
fin >> tot; fin.getline(line, MAX);
for (i = 1; i <= tot; i++)
fin.getline(t.name, MAX);

memset(g, 0, sizeof(g));
int game;
fin >> game; fin.getline(line, MAX);
for (i = 0; i < game; i++) {
fin.getline(line, MAX);
istrstream is(line);

int id1, id2, g1, g2;
char tmp;
is.getline(name, MAX, '#'); id1 = getid(name);
is >> g1 >> tmp >> g2 >> tmp;
is.getline(name, MAX); id2 = getid(name);


t[id1].game++, t[id2].game++;
if (g1 > g2) {
t[id1].point += 3;
t[id1].win++, t[id2].lose++;
} else if (g1 == g2) {
t[id1].point++, t[id2].point++;
t[id1].tie++, t[id2].tie++;
} else {
t[id2].point += 3;
t[id1].lose++, t[id2].win++;
}
t[id1].gd += g1 - g2, t[id1].gs += g1, t[id1].ga += g2;
t[id2].gd += g2 - g1, t[id2].gs += g2, t[id2].ga += g1;
}

qsort(&t[1], tot, sizeof(t[0]), cmp);

for (i = 1; i <= tot; i++)
cout << i << ") " << t.name << ' ' << t.point << "p, " << t.game << "g ("
<< t.win << '-' << t.tie << '-' << t.lose << "), " << t.gd << "gd ("
<< t.gs << '-' << t[i].ga << ')' << endl;
}

return 0;
}[/cpp][/cpp]
Wenyuan Dai, Shanghai Jiaotong University.

adler
New poster
Posts: 1
Joined: Mon Nov 04, 2002 5:43 am

Post by adler » Mon Nov 04, 2002 5:49 am

You must treat the team names case insensitivly:

"Notice that should the tie-breaker be the lexographic order, it must be done case insenstive"

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Mon Dec 09, 2002 4:39 pm

That's the problem!
I got AC now.
Thank you very much:)

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10194

Post by Dominik Michniewski » Mon Feb 10, 2003 1:19 pm

This problem drives me crazy :( only WA and WA
Could anyone give me some special inputs for this problem ?

I create array of teams, read desciptions of played matches and assign some data to teams by names (case sensitive). After that I use standard qsort() to sort data (if I compare names, I'm doing it case insensitive) and display it ?

Is possible to get input like this:
1
4
A
B
a
b
1
A#0@1#a

?

Thanks for help
Dominik Michniewski
Last edited by Dominik Michniewski on Mon Sep 29, 2003 9:20 am, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Wed Feb 12, 2003 12:42 pm

I don't remember any special cases in the problem. So my only help is to give you the output for your input:

Code: Select all

Tour Name
1) a  3p, 1g (1-0-0), 1gd (1-0)
2) A  0p, 0g (0-0-0), 0gd (0-0)
3) B  0p, 0g (0-0-0), 0gd (0-0)
4) b  0p, 0g (0-0-0), 0gd (0-0)
By the way you forgot to write "Tour Name" in the second line of input.

Good luck.
Andrey.

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Feb 12, 2003 5:06 pm

but it's not very important to this test case ;-)))

Thanks for help, but I got the same result and got WA :((

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

stefan_buettcher
New poster
Posts: 2
Joined: Fri Feb 14, 2003 11:20 pm

Post by stefan_buettcher » Fri Jun 27, 2003 8:08 pm

Are you sure the above output is correct?
Shouldn't A be last because they have lost one match?

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Fri Jun 27, 2003 8:40 pm

No, this program has a "trick" :-(

For instance,
1) bRASIL 6p, 3g (2-0-1), 3gd (6-3)
2) Canada 6p, 3g (2-0-1), 3gd (6-3)
AND
1) Brazil 6p, 3g (2-0-1), 3gd (6-3)
2) cANADA 6p, 3g (2-0-1), 3gd (6-3)

So the order of the letters is A<B<...<Z<a<b<..<z

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

WA

Post by zsepi » Wed Jul 02, 2003 3:01 am

I have a feeling that i have problems with the final sorting (lexographic) - would appreciate tricky inputs and/or comments on this code fragment - thanx!
[c]struct team {
char name[L];
int points, wins, scored, against, played, ties;
}teams[MX];

int my_strcmp(char *a, char *b) {
static char ch1, ch2;

while(*a && *b) {
ch1 = tolower(*a);
ch2 = tolower(*b);
if(ch1 != ch2) break;
a++;
b++;
}
if(ch1 == ch2) return *a - *b;
else return ch1 - ch2;
}

int rank(const void *a, const void *b) { /* for qsort */
static struct team *t1, *t2;
static int x;

t1 = (struct team *)a;
t2 = (struct team *)b;
if((x = t2->points - t1->points) == 0)
if((x = t2->wins - t1->wins) == 0)
if((x = (t2->scored - t2->against) - (t1->scored - t1->against)) == 0)
if((x = t2->scored - t1->scored) == 0)
if((x = t1->played - t2->played) == 0)
x = my_strcmp(t1->name, t2->name);
return x;
}[/c]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Aug 19, 2003 3:01 pm

i have checked all the cases. but isn't there anything more tricky?my program satisfies C<canada but again why wa?
pls discuss more.
"Everything should be made simple, but not always simpler"

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Sep 01, 2003 10:25 pm

stefan_buettcher wrote:Are you sure the above output is correct?
Shouldn't A be last because they have lost one match?
I agree with you. To me, the answer to

Code: Select all

1
4
A
B
a
b
1
A#0@1#a
is

Code: Select all

Tour name
1) a 3p, 1g (1-0-0), 1gd (1-0)
2) B 0p, 0g (0-0-0), 0gd (0-0)
3) b 0p, 0g (0-0-0), 0gd (0-0)
4) A 0p, 1g (0-0-1), -1gd (0-1)
But ALAS, I'm keeping getting WA. Doing insensitive case compare (with strcasecmp), and doing 6 stable sorts. Anupam, did you solve it ? Anybody, an idea ?

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Tue Sep 02, 2003 12:19 am

Here's my (weird) source :
[cpp]
#include <stdio.h>
#include <strings.h>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

class team {

team() {};
team(team & t) {};
void operator=(team &t) {};

public:
string name; /* name of the team */
int points; /* number of points : 3 for a win, 1 for a tie, 0 for a loss */
int wins; /* number of matches won */
int ties;
int loss;
int gd;
int goalscored;
int goalagainst;
int gamesplayed; /* number of games played */

team(char * s) : name(s), points(0), wins(0), ties(0), loss(0), gd(0), goalscored(0), goalagainst(0), gamesplayed(0) {
};
/* updates the stats after a game has been played */
/* i : score of the team, j : score of the other one */
void game(int i, int j) {
gamesplayed++;
gd += (i - j);
goalscored += i;
goalagainst += j;
if (i>j) {
wins++;
points += 3;
} else if (i == j) {
points += 1;
ties++;
} else loss++;
}
/* prints the stats */
void print() {
printf("%s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n", name.c_str(), points, gamesplayed, wins, ties, loss, gd, goalscored, goalagainst);
}

};

map<string, team *> teams; /* map of the teams */
char tournament[200]; /* name of the current tournament */
int nbteam; /* number of teams */
int nbmatch; /* number of matchs */

template <int team::* ARG >
inline bool ascending (team * a, team * b) {
return a->*ARG < b->*ARG;
}

template <int team::* ARG >
inline bool descending (team * a, team * b) {
return a->*ARG > b->*ARG;
}

inline bool cmpnames (team * a, team * b) {
return strcasecmp(a->name.c_str(), b->name.c_str()) == -1;
}


int main()
{
int nbscenar;
char temp[200];
char a[200];
char b[200];
int na,nb;
int i;
map<string, team *>::iterator it;

for (scanf("%d\n", &nbscenar); nbscenar > 0; nbscenar--) {
teams.clear();
/* get the tournament name and output it */
gets(tournament);
scanf("%d\n", &nbteam);
/* creating the teams and adding them to the map */
for(i=0; i<nbteam; i++){
gets(temp);
teams[temp] = new team((char *)temp);
}

/* playing the games */
scanf("%d\n", &nbmatch);
for(i=0; i<nbmatch; i++){
scanf("%[^#]#%d@%d#%[^\n]\n",a,&na,&nb,b);
teams[a]->game(na,nb);
teams->game(nb,na);
}

/* using a tab to simplify stable sort */
team * tab[nbteam];
for (i=0, it = teams.begin(); it != teams.end(); it++, i++)
tab = it->second;

/* 6 stable sort */
// 1. case insensitive ascending order
sort(tab, tab+nbteam, cmpnames);
// 2. ascending number of games played
stable_sort(tab, tab+nbteam, ascending<&team::gamesplayed>);
// 3. descending goal scored
stable_sort(tab, tab+nbteam, descending<&team::goalscored>);
// 4. descending goal difference
stable_sort(tab, tab+nbteam, descending<&team::gd>);
// 5. descending wins
stable_sort(tab, tab+nbteam, descending<&team::wins>);
// 6. descending points earned
stable_sort(tab, tab+nbteam, descending<&team::points>); */

// STRANGE ! It works with the QSORT, but not with the stable_sorts just before... Anybody, an Idea ?

/* output */
puts(tournament);
for (i=0; i < nbteam; i++) {
printf("%d) ", i+1);
tab->print();
delete tab;
}
if (nbscenar > 1) putchar('\n');
}
return 0;
}
[/cpp]
I really don't understand : the code above gets WA, but when I replace the stable_sorts and the template compare function with pointer to members by a qsort with a global compare function, I get AC... So there must be an error in my stable_sorts and my template function, but I don't see wich one... Does anybody have an idea ?? I'm really mad about it... and moreover : curious :wink:

kvee119
New poster
Posts: 2
Joined: Tue Sep 16, 2003 3:37 am
Contact:

10194 - Football (aka Soccer)

Post by kvee119 » Sun Sep 21, 2003 3:39 pm

*Just a few words of mine.
*Take #6 into account: Case-insentive Lex.
So when all have the same score and names are being considered, both
a B b
a b B
are correct. Dmytro already mentioned this.
It might be a cause for stable-sort's failure.
I got AC.
Give and Get

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest