10295 - Hay Points

[Rivaldo]

It says the dollars value are real numbers, so how to output them?

[gvcormac]

Good question. I think it is a typo in the question. The input is integer.

[Eduard]

I'm getting WA for this problem.My algo is right and I can pass simple input.I'm sorting words than use binary search to find word in dictionary.
I whant to know, are there many inputs ending with eof or just one test?
Thanks.

[nymo]

hi, i am stuck with this problem(10295)... i have some inquiries ...

a dollar value (a real number between 0 and 1,000,000)

Code: Select all

Does that mean that point is a floating point number ?
Then how come the sample output is without decimal point...
(Is it because the sample input produces result without fractions !!!)

SECONDLY, 
what is the size of the array to take per input line ?
[I use some 10000000 bytes char array and gets RE :(]

Please clarify ... thanks.

[/quote]

[Solaris]

dear nymo (boss)

1. I have got AC using normal 32 bit integer as the dollar value

2. Instead of taking one line, I have taken one word of the dictionery at a time by simply using scanf("%s", str)

hope this helps

[nymo]

scanf("%s", str) is well enough to get ACC. THANKS SOLARIS , i am honored to be your friend. Thanks again.

[Darko]

I am trying to solve this one using Java. Should I give up? I see some people got it...

Is the length of the input line the only "tricky" input?

Darko

[athlon19831]

10295 WA ( I need some Sample Input!!!)

[Darko]

Man... I guess I learned a few tricks in the meantime, but this is plain silly:
AC

Code: Select all

st = new StringTokenizer(readLine());
			String s = st.nextToken();
			int val = parseInt(st.nextToken());
			list.put(s, new Integer(val));

WA

Code: Select all

st = new StringTokenizer(readLine());
			list.put(st.nextToken(), new Integer(parseInt(st.nextToken())));

[bidol]

visit here...



http://www.geocities.com/acmbeganer/p10295io.htm

[hamedv]

I Got Compile Error Many Times

ACed

[mf]

Online judge usually sends compiler's error messages to your email. Here's what I got for your code:

05837124_24.c:8: ANSI C++ forbids data member `word' with same name as enclosing class
05837124_24.c:10: confused by earlier errors, bailing out

[hamedv]

Thanx Got AC

[Jirico]

Hi, I'm getting runtime error with my Hay Points problem (10295)
I really appreciate any help.
Here is the code:

Code: Select all

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

typedef struct no
{
    char pala[16];
    long value;    
}dictionary;

void Particiona(dictionary tabela[], unsigned inf, unsigned sup, unsigned *posPivo );
void Quick(dictionary tabela[], unsigned  inf, unsigned  sup);
void QuickSort(dictionary tabela[], unsigned  nElem);
int EncontraIndice(char palavra[], dictionary tabela[], int tam);


int main()
{
    
    dictionary words[1000];
    char aux[16];
    char palavra[16];
    long aux2;
    long score;
    int help;
    int numberWords;
    int numberJobs;
    int i = 0;    
   
    scanf("%d %d", &numberWords, &numberJobs);
    
    
    while(i < numberWords)
    {
            scanf("%s %ld", words[i].pala, &words[i].value);
            i++;
            
            
    }
    if(strcmp(words[0].pala, words[1].pala) < 0 )
{
       strcpy(aux, words[1].pala);
       aux2 = words[1].value;              
      strcpy(words[1].pala, words[0].pala);
      words[1].value = words[0].value;
      strcpy(words[0].pala, aux); 
      words[0].value = aux2;
} 
 
    QuickSort(words, numberWords);

       i = 0;
   
   
   while(i < numberJobs)
    {
           score = 0;
            while(1)
            {
                 
               scanf("%s", palavra);
               
               if(!strcmp(palavra,"."))
               {
                         break;
               }
              
              help = EncontraIndice(palavra, words, numberWords);
             
               if(help == -1)
               {
               continue;
               }
               else{
               
              score = score + words[help].value;
               
               
              
               
               }
                                  
            } 
            printf("%ld\n", score);
            i++;
    }
    
    

    

    return(0);
}

void  Particiona(dictionary tabela[], unsigned inf, unsigned sup, unsigned *posPivo )
{
   char	pivo[16];  
   long vpivo;
   unsigned	sobe, desce;
   char aux[16];
   int vaux;

   strcpy(pivo,tabela[inf].pala); 
   vpivo = tabela[inf].value;
   sobe = inf;  
   desce = sup; 

   while (sobe < desce) {
      while (strcmp(tabela[sobe].pala, pivo) <= 0 && sobe < sup)   
         sobe++;        

      while (strcmp(tabela[desce].pala, pivo) > 0) 
         desce--;   	

      if (sobe < desce) { 
         strcpy(aux, tabela[desce].pala);
         vaux = tabela[desce].value;
         strcpy(tabela[desce].pala, tabela[sobe].pala);
         tabela[desce].value =  tabela[sobe].value;
         strcpy(tabela[sobe].pala,  aux);
         tabela[sobe].value = vaux;
      }
   }
		
   strcpy(tabela[inf].pala, tabela[desce].pala);
   tabela[inf].value = tabela[desce].value;
   strcpy(tabela[desce].pala, pivo);
   tabela[desce].value = vpivo;

   *posPivo = desce; 
}





void Quick(dictionary tabela[], unsigned  inf, unsigned  sup)
{
   unsigned  posPivo;

   if (inf >= sup) 
      return; 

   Particiona(tabela, inf, sup, &posPivo);  
   Quick(tabela, inf, posPivo-1); 
   Quick(tabela, posPivo+1, sup); 
}

void QuickSort(dictionary tabela[], unsigned  nElem)
{
   	   
   Quick(tabela, 0, nElem-1);
}



int EncontraIndice(char palavra[], dictionary chaves[], int tam)
{
    int limiteInf, limiteSup, metade;

    limiteInf = 0;
    limiteSup = tam - 1;
 

    while(limiteInf <= limiteSup) {
         
        metade = (limiteInf + limiteSup)/2;
         
        if (!strcmp(chaves[metade].pala,  palavra))
        {
                                
            return metade;
            
            }
        if (strcmp(palavra, chaves[metade].pala) < 0)
            limiteSup = metade - 1;
        else
            limiteInf = metade + 1;
    }

    return -1;
}

[Jirico]

I'm getting Runtime Error
Any help is appreciated.
I'm just wondering where is the error, on my computer it runs fine.

Here is the code:

Code: Select all

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

typedef struct no
{
    char pala[16];
    long value;    
}dictionary;

void Particiona(dictionary tabela[], unsigned inf, unsigned sup, unsigned *posPivo );
void Quick(dictionary tabela[], unsigned  inf, unsigned  sup);
void QuickSort(dictionary tabela[], unsigned  nElem);
int EncontraIndice(char palavra[], dictionary tabela[], int tam);


int main()
{
    
    dictionary words[1000];
    char aux[16];
    char palavra[16];
    long aux2;
    long score;
    int help;
    int numberWords;
    int numberJobs;
    int i = 0;    
   
    scanf("%d %d", &numberWords, &numberJobs);
    
    
    while(i < numberWords)
    {
            scanf("%s %ld", words[i].pala, &words[i].value);
            i++;
            
            
    }
    if(strcmp(words[0].pala, words[1].pala) < 0 )
{
       strcpy(aux, words[1].pala);
       aux2 = words[1].value;              
      strcpy(words[1].pala, words[0].pala);
      words[1].value = words[0].value;
      strcpy(words[0].pala, aux); 
      words[0].value = aux2;
} 
 
    QuickSort(words, numberWords);

       i = 0;
   
   
   while(i < numberJobs)
    {
           score = 0;
            while(1)
            {
                 
               scanf("%s", palavra);
               
               if(!strcmp(palavra,"."))
               {
                         break;
               }
              
              help = EncontraIndice(palavra, words, numberWords);
             
               if(help == -1)
               {
               continue;
               }
               else{
               
              score = score + words[help].value;
               
               
              
               
               }
                                  
            } 
            printf("%ld\n", score);
            i++;
    }
    
    

    

    return(0);
}

void  Particiona(dictionary tabela[], unsigned inf, unsigned sup, unsigned *posPivo )
{
   char	pivo[16];  
   long vpivo;
   unsigned	sobe, desce;
   char aux[16];
   int vaux;

   strcpy(pivo,tabela[inf].pala); 
   vpivo = tabela[inf].value;
   sobe = inf;  
   desce = sup; 

   while (sobe < desce) {
      while (strcmp(tabela[sobe].pala, pivo) <= 0 && sobe < sup)   
         sobe++;        

      while (strcmp(tabela[desce].pala, pivo) > 0) 
         desce--;   	

      if (sobe < desce) { 
         strcpy(aux, tabela[desce].pala);
         vaux = tabela[desce].value;
         strcpy(tabela[desce].pala, tabela[sobe].pala);
         tabela[desce].value =  tabela[sobe].value;
         strcpy(tabela[sobe].pala,  aux);
         tabela[sobe].value = vaux;
      }
   }
		
   strcpy(tabela[inf].pala, tabela[desce].pala);
   tabela[inf].value = tabela[desce].value;
   strcpy(tabela[desce].pala, pivo);
   tabela[desce].value = vpivo;

   *posPivo = desce; 
}





void Quick(dictionary tabela[], unsigned  inf, unsigned  sup)
{
   unsigned  posPivo;

   if (inf >= sup) 
      return; 

   Particiona(tabela, inf, sup, &posPivo);  
   Quick(tabela, inf, posPivo-1); 
   Quick(tabela, posPivo+1, sup); 
}

void QuickSort(dictionary tabela[], unsigned  nElem)
{
   	   
   Quick(tabela, 0, nElem-1);
}



int EncontraIndice(char palavra[], dictionary chaves[], int tam)
{
    int limiteInf, limiteSup, metade;

    limiteInf = 0;
    limiteSup = tam - 1;
 

    while(limiteInf <= limiteSup) {
         
        metade = (limiteInf + limiteSup)/2;
         
        if (!strcmp(chaves[metade].pala,  palavra))
        {
                                
            return metade;
            
            }
        if (strcmp(palavra, chaves[metade].pala) < 0)
            limiteSup = metade - 1;
        else
            limiteInf = metade + 1;
    }

    return -1;
}