119 - Greedy Gift Givers

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

Moderator: Board moderators

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 119 Why WA??

Post by Scarecrow » Thu Jan 26, 2012 10:44 pm

thnx brianfry713 for the help :)
Do or do not. There is no try.

at5anpo3
New poster
Posts: 7
Joined: Sun Apr 29, 2012 6:46 pm

Re: 119 Why WA??

Post by at5anpo3 » Sat May 05, 2012 6:39 pm

the example with Fat and Dude is wrong.

as per text "All names are lower-case letters". Therefore, it should be fat and dude.

Best Regards,
at5anpo3

1971
New poster
Posts: 1
Joined: Sun Jun 16, 2013 3:03 am

Re: 119 Why WA??

Post by 1971 » Sun Jun 16, 2013 3:08 am

I've passed all sample test cases provided here, but still getting WA. Anybody's help will be appreciated:

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char giver[11][15];
int n;

int search_index(char* name){
    int i,j;

    //printf("%s\n\n",name); //

    for(i=0; i<n;i++)
        if(!strcmp(name,giver[i]))
            return i;
        //double even triple check this function --later


}

int main()
{
   // freopen("input.txt","r",stdin);//

    char name[15];
    int money[11],tc=0;

    int m,i,j,d,rem,res,giver_id,taker_id;

    while(scanf("%d",&n)!=EOF){
            tc++;

        memset(giver,'\0',sizeof(giver));
        for(i=0; i<n; i++)
            money[i]=0;

        for(i=0; i<n; i++)
            scanf(" %s",giver[i]);

        for(i=0; i<n;i++){
            memset(name,'\0',sizeof(name));
            scanf(" %s %d %d",name,&m,&d);
            giver_id = search_index(name);

            if(d>0){
            rem = m%d;
            res = (m-rem)/d;



            money[giver_id]-=m-rem;

            for(j=0; j<d; j++){
                scanf(" %s",name);
                taker_id = search_index(name);
                //cout<<taker_id<<endl;
                money[taker_id]+=res;
            }

            //money[giver_id]+=rem;
            }

        }

        if(tc>1)
            printf("\n");

        for(i=0; i<n;i++){
            printf("%s %d\n",giver[i],money[i]);
        }
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 119 Why WA??

Post by brianfry713 » Tue Jun 18, 2013 12:40 am

That is AC code.
Check input and AC output for thousands of problems on uDebug!

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 119 Why WA??

Post by Shihab » Thu Nov 14, 2013 1:38 pm

Getting RTE ! please help

Code: Select all

#include<map>
#include<cstdio>
#include<iostream>

using namespace std;

int main()
{
    int NumOfMembers,i,j,Money,Persons;
    map<string,int>mp;
    string Names[10],Name;
    while(scanf("%d",&NumOfMembers)!=EOF)
    {
        mp.clear();
        i=1;
        while(i<=NumOfMembers)
        {
            cin>>Names[i];
            i++;
        }
        i=1;
        while(i<=NumOfMembers)
        {
            cin>>Name>>Money>>Persons;
            if(Persons!=0)
            {
                mp[Name]+=Money*(-1) + (Money%Persons);
                for(j=1; j<=Persons; j++)
                {
                    cin>>Name;
                    mp[Name]+=Money/Persons;
                }

            }

            i++;
        }

        for(i=1; i<=NumOfMembers; i++)
        {
            cout<<Names[i]<<" "<<mp[Names[i]]<<"\n";
        }
        printf("\n");
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 119 Why WA??

Post by brianfry713 » Thu Nov 14, 2013 10:27 pm

Try a test case with 10 people.
Check input and AC output for thousands of problems on uDebug!

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 119 Why WA??

Post by Shihab » Thu Nov 21, 2013 12:30 pm

Still WA

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 119 Why WA??

Post by brianfry713 » Thu Nov 21, 2013 8:33 pm

The code you posted is throwing a RE on this input:

Code: Select all

10
a b c d e f g h i j
a 0 0
b 0 0
c 0 0
d 0 0
e 0 0
f 0 0
g 0 0
h 0 0
i 0 0
j 0 0
Post your updated code if you want more help.
Check input and AC output for thousands of problems on uDebug!

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 119 Why WA??

Post by Shihab » Sun Nov 24, 2013 1:30 pm

I got AC.
But i don't understand why my code didn't work when i used
EOF

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 119 Why WA??

Post by brianfry713 » Mon Nov 25, 2013 11:49 pm

If Names is an array of size 10 don't try to write to Names[10]
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 119 Why WA??

Post by uDebug » Mon Dec 16, 2013 1:51 pm

While solving this problem, I found the input by Jan to be very useful and I'm grateful for this. However, while working this out on paper, the names that were used were confusing - largely since they looked like they were just a combination of random letters. So, I went ahead and used the same input but changed the names up to be more meaningful. This way, if you're working this out step by step, it (hopefully) makes more sense. I've also included gtcoder's input - albeit a bit modified for improved readability.

Input:

Code: Select all

10
bob anne lee juanita omar shawanda lavanya park xianyu yvette
lavanya 1805 1 yvette
bob 1350 6 anne juanita xianyu yvette juanita omar
omar 756 4 lavanya lavanya anne xianyu
omar 439 1 juanita
park 1538 5 lee yvette anne juanita shawanda
yvette 1658 4 bob park lavanya juanita
lavanya 1021 4 omar lee bob yvette
park 1573 2 lee lavanya
bob 1161 3 shawanda park shawanda
omar 31 6 bob bob anne lavanya bob park
8
anne ganesh wahida shizuka maria catherine kiran leo
wahida 886 1 ganesh
catherine 142 5 anne ganesh kiran wahida shizuka
catherine 1699 3 maria maria shizuka
anne 600 1 shizuka
catherine 1861 4 ganesh leo leo wahida
ganesh 182 1 anne
wahida 617 3 anne maria ganesh
wahida 1721 5 anne ganesh anne maria ganesh
2
fanny disha
fanny 1000 0
disha 100 1 fanny
AC Output:

Code: Select all

bob -1827
anne 726
lee 1348
juanita 1610
omar -745
shawanda 1081
lavanya -1242
park -2301
xianyu 414
yvette 936

anne 503
ganesh 2090
wahida -2728
shizuka 1194
maria 1681
catherine -3698
kiran 28
leo 930

fanny 100
disha -100
Last edited by uDebug on Fri Jun 13, 2014 7:05 am, edited 1 time in total.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 119 Why WA??

Post by mostruash » Thu Jun 12, 2014 5:44 pm

I'm unfortunately getting Runtime Error. Tried all test cases available on the boards.

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cstring>
#include <sstream>

#define CLEAR(arr) (memset(arr, 0, sizeof(arr)))
#define BUFF 250

using namespace std;

map<string, int> index_of;
string names[10];
int money[10] = { 0 };
char buff[250];

int main() {

    int n;
    bool first = true;
    int result;
    while((result = scanf("%d", &n)) == 1) {
        if(first) first = false;
        else printf("\n");
        
        CLEAR(money);
        CLEAR(names);
        index_of.clear();
        
        for(int i = 0; i < n; i++) {
            string name;
            cin >> name;
            index_of[name] = i;
            names[i] = name;
        }
        
        cin.getline(buff, BUFF);
        
        for(int i = 0; i < n; i++) {
            cin.getline(buff, BUFF);
            stringstream ss;
            ss << buff;
            
            string giver_name;
            int amount;
            int num_of_ppl;
            ss >> giver_name >> amount >> num_of_ppl;
            int giver = index_of[giver_name];
            
            for(int j = 0; j < num_of_ppl; j++) {
                string taker_name;
                ss >> taker_name;
                int taker = index_of[taker_name];
                int share = amount / num_of_ppl;
                money[taker] += share;
                money[giver] -= share;
            }
        }
        
        for(int i = 0; i < n; i++) {
            printf("%s %d\n", names[i].c_str(), money[i]);
        }
    }
    
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 119 Why WA??

Post by brianfry713 » Thu Jun 12, 2014 7:53 pm

Your code is throwing a seg fault on the sample input. Delete line 28: CLEAR(names);
Check input and AC output for thousands of problems on uDebug!

mostruash
New poster
Posts: 8
Joined: Thu May 22, 2014 7:06 pm

Re: 119 Why WA??

Post by mostruash » Thu Jun 12, 2014 7:55 pm

Huh... Not on my compiler (llvm latest version). Thank you brianfry713.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 119 Why WA??

Post by lbv » Thu Jun 12, 2014 10:29 pm

mostruash wrote:I'm unfortunately getting Runtime Error. Tried all test cases available on the boards.
Using memset to fill with zeros a variable like "string names[10]" doesn't make much sense and is likely to end in memory corruption. string is an opaque data structure and its internals depend on your C++ standard libary.

On a side note, I receive a segfault when I compile it with both g++ and clang++. What compiler do you use?

Post Reply

Return to “Volume 1 (100-199)”