10420 - List of Conquests

[Per]

There is no guarantee that there is at most 80 countries.

[Ghust_omega]

Hi!! Per thanks for you answer, i change the value to 800 and still WA , i change the compare about strcmp to < 0, ichange the size of country to 800 and the array to the frecuencies to 800 and nothing still WA please Help

[Per]

There is no guarantee that there is at most 800 countries, either.

[Ghust_omega]

Thanks Per for your answer, and that case what size can be the array please Help me, or better how many countries are??

[Dominik Michniewski]

Ghust_omega, just try to create any dynamic data structure. Not always static tables are enough

Best regards
DM

[Per]

Though in this case, they are.

The input consists of at most 2000 lines.

[Ghust_omega]

HI Per and Dominik thanks for yours answers I will rewrite my code with linked list with order plus frecuency of country but now i wonder how long is the name of a country
??
to Per and Dominik Keep posting!!
Thanks in advance

[CodeMaker]

Hi, anyone who needs helps in this problem can check this out....nothing much but may help u.

I was getting WA for whole night(u know how it feels ) and in the morning i just got AC ....

Here is some I/O...u can test it...[c]15
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
Bangladesh Hasan
Bangladesh Bijon Khaled Jaman
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
India Saiket podder
India Partha Sarker
Bangladesh Hasan Ahmed
Bangladesh Bijon Khaled Jaman
Australia Anil
Bangladesh Shoikot
Barma Asma
Bangladesh Saiket[/c]

Output:
Australia 1
Bangladesh 6
Barma 1
India 2

[Ali Arman Tamal]

Hello Everyone !

I think codemaker is wrong. I solved the code without considering any duplicate women name and still got AC.

My output for the codemaker's input is

Australia 1
Bangladesh 11
Barma 1
India 2

Since the judge doesn't seem to give any duplicate name, so considering duplicate or not considering will lead to the same answer !!

And Ghust Omega, if you still haven't got AC, watch this:

1. There will not be more than 201 different countries. My AC code couldn't handle more than 201 different countries.

2. You can use array of structure like this:


struct data
{
char name[80];
int freq;
};

struct data country[201];

and later use it for other operation

Hope it helps!!

[Sedefcho]

Hello, Ali Arman Tamal !

Yes, you are right. I got ACC having same output as yours
for CodeMaker's input.

Seems like the tests the Judge has really don't contain
duplicate women names.

[Sedefcho]

By the way, if they put decent tests for this problem we will
get WA. I think the better approach is to take into consideration
duplicate women names.

[smilitude]

Sir John Leparro (104-20) has died on the march 20th of the year 2006 with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before being crashed by an ongoing heavy truck, he ran for 0.014 seconds on the streets of downtown of UVa. His last wish was someone will tell his innocent relatives about why he had an invalid memory reference problem!

We mourn for Sir John Leparro, but right now, invalid memory reference is bugging us very much! Instead of a proper hashing, all the program did is a proper crashing~!

Code: Select all

/*
 * 10420 List of Conquests
 * submission 1 RE
 * coded at 1004pm march 20, 2006
 *
 */ 


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define PRIME 3001
#define MULTIPLIER 37
#define NHASH PRIME

typedef struct Country Country;
struct Country {
    char name[76];
    int count;
    int next;
};

Country country[3001];
int extra=2003;

void init() {
    for(int i=0;i<=PRIME;i++) {
        strcpy(country[i].name,"");
        country[i].count=0;
        country[i].next=-1;
    }
}        

void print() {
    for(int i=0;i<=PRIME;i++) {
        if(strcmp(country[i].name,"")!=0) {
            printf("%s %d\n",country[i].name,country[i].count);
        }
    }
}

int compare(const void *va, const void *vb) {
    Country *a,*b;
    a=(Country *)va;
    b=(Country *)vb;
    
    return strcmp(a->name,b->name);
}                

unsigned int hash(char *str) {
    unsigned int h=0;
    int len=strlen(str);
   
    for(int i=0;i<len;i++) 
        h=MULTIPLIER*h + str[i];
    return h % NHASH;
}

void add(char *str) {
    int h=hash(str);
    if(!strcmp(country[h].name,"")) {
        strcpy(country[h].name,str);
        country[h].count++;
    }else if(!strcmp(country[h].name,str)) {
        country[h].count++;
    }else {
        while(country[h].next!=-1) {
            h=country[h].next;
            if(!strcmp(country[h].name,str)) {
                country[h].count++;
                h=-1;
                break;
            }
        }
        if(h!=-1) {
            country[h].next=++extra;
            strcpy(country[extra].name,str);
            country[extra].count++;
        }
    }
}            
         
int main() {
    char line[100];
    char word[76];
    int n;
    int i,j;
    
    while(scanf("%d",&n)==1) {
        init();
        gets(line);
        for(i=0;i<n;i++) {
            gets(line);
            j=0;
            while(line[j]!=' ') {
                word[j]=line[j];
                j++;
            }
            word[j]='\0';
            add(word);
        }
    qsort(country,PRIME,sizeof(country[0]),compare);
    print();
    }
    
    
}                
            
            
    

[Roby]

Hmmm.. may be the array size is to small for the judge input... I've solved it with Binary Search Tree method, may be this method can help you out of this problem...

[stubbscroll]

Volume CIV (104) is the correct thread for this problem.

[little joey]

I moved this thread to the correct forum. Please Mr. Smilitude, problems 104xx belong in volume 104, which is CIV in Roman numerals
I moved your other thread too.