230 - Borrowers

All about problems in Volume 2. 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
pete
New poster
Posts: 2
Joined: Thu Mar 14, 2002 2:00 am

230 - Borrowers

Post by pete » Fri Mar 15, 2002 8:15 pm

Can you give me a set of Test Data of Problem 230? Thank you.

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

Post by RuiFerreira » Fri Feb 21, 2003 9:38 pm

for me too!

I'm getting Runtime Error... Do you have any ideia why? any tricky case?


Thanks!
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post by bobi1978 » Tue Jul 29, 2003 11:34 pm

I don't understand completely this problem.
I have two questions:

1)
Should I SORT books at the begining, or to leave them as they are in the INPUT?

2)
And after that, does it mean that each book has its OWN POSITION on the shelves, and it need to be returned on that position?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Wed Feb 25, 2004 3:49 pm

Hi bobi1978,

The answer for your questions:
1. Yes
2. Yes

Hope it helps.
angga888

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 230

Post by DD » Fri Apr 01, 2011 6:09 am

RuiFerreira wrote:for me too!



I'm getting Runtime Error... Do you have any ideia why? any tricky case?





Thanks!
Please try to describe your algorithm first, otherwise it is hard to figure it out why you got R.E.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Neto_o
New poster
Posts: 2
Joined: Wed Dec 28, 2011 9:21 pm

Re: 230

Post by Neto_o » Thu Dec 29, 2011 5:23 am

Please someone give some hard inputs and outputs from your accepted codes, I'm getting wrong answer and I don't know why...

Thanks in advance

*Edit: Nevermind, I got Accepted now, it was a very simple output mistake.

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

Re: 230

Post by uDebug » Wed Apr 30, 2014 1:45 pm

Here's some input / output that helped me during testing / debugging.

Input:

Code: Select all

"The Canterbury Tales" by Chaucer, G.
"The Canterbury Taless" by Chaucer, B.
"Algorithms" by Sedgewick, R.
"The C Programming Language" by Kernighan, B. and Ritchiee, D.
"The C Programming Languag" by Kernighan, B. and Ritchiee, D.
"The D Programming Language" by Kernighan, B. and Ritchiee, D.
"A House for Mr. Biswas" by Naipaul, V.S.
"A Congo Diary" by Naipaul, V.S.
END
BORROW "Algorithms"
BORROW "The C Programming Language"
BORROW "The C Programming Languag"
BORROW "The Canterbury Taless"
SHELVE
RETURN "Algorithms"
SHELVE
RETURN "The C Programming Languag"
SHELVE
BORROW "The C Programming Languag"
BORROW "The Canterbury Taless"
BORROW "A House for Mr. Biswas"
RETURN "The Canterbury Taless" 
SHELVE
RETURN "The C Programming Language"
RETURN "A House for Mr. Biswas"
SHELVE
END
AC Output:

Code: Select all

END
Put "Algorithms" after "A House for Mr. Biswas"
END
Put "The C Programming Languag" after "The Canterbury Tales"
END
Put "The Canterbury Taless" first
END
Put "The C Programming Language" after "The Canterbury Tales"
Put "A House for Mr. Biswas" after "A Congo Diary"
END
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 230 - Borrowers

Post by BlackBeard » Tue Dec 23, 2014 6:20 pm

I've tried all possible inputs including the one provided by v1n1t. couldn't find a bug....
Please help....
Here's my code...

Code: Select all

GOT AC
Last edited by BlackBeard on Sat Jan 03, 2015 11:00 pm, edited 1 time in total.

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

Re: 230 - Borrowers

Post by brianfry713 » Tue Dec 23, 2014 11:47 pm

You are iterating through an unordered_map and expecting them to be in order.

I solved it by using a set<pair<string, string> > for books on the shelf, a vector<pair<string, string> > for returned books, and a map<string, string> to keep track of what author wrote each book.
Initially all books are on the shelf, for each borrowed book remove it from the shelf, for each returned book push it onto the back of the returned vector.
To Shelve: sort the returned vector, then iterate through it and use lower_bound to find it's location on the shelf, insert the book there, and at the end clear the returned vector.
Check input and AC output for thousands of problems on uDebug!

BlackBeard
New poster
Posts: 18
Joined: Wed Dec 17, 2014 9:44 pm

Re: 230 - Borrowers

Post by BlackBeard » Sat Jan 03, 2015 11:01 pm

Thanks brianfry. I used vector instead of unordered_map and got ac...

madca03
New poster
Posts: 1
Joined: Tue Aug 04, 2015 12:20 pm

Re: 230 - Borrowers

Post by madca03 » Sat Aug 29, 2015 4:06 pm

Hi, I'm getting WA for this problem although I'm getting the right output from the critical input of udebug.

Code: Select all

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;

class Main {
  private static List<Book> books = new ArrayList<Book>();
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    try {
      while(sc.hasNextLine()) {
        String s = sc.nextLine();

        if (s.equals("END")) break;
        
        String[] tokens = s.split("\\s(by)\\s");
        books.add(new Book(tokens[0], tokens[1]));
      }
    } catch (Exception e) { System.out.println(e); }

    Collections.sort(books, new Comparator<Book>() {
      public int compare(Book o1, Book o2) {
        if (o1.getAuthor().compareTo(o2.getAuthor()) == 0) {
          return o1.getTitle().compareTo(o2.getTitle());
        }

        return o1.getAuthor().compareTo(o2.getAuthor());
      }
    });

    List<String> booksToReturn = new ArrayList<String>();
    List<String> booksBorrowed = new ArrayList<String>();
    try {
      while(sc.hasNextLine()) {
        String s = sc.nextLine();

        if (s.contains("BORROW")) {
          String title = s.substring((new String("BORROW")).length() + 1, s.length());
          booksBorrowed.add(title);
        } else if (s.equals("SHELVE")) {
          Collections.sort(booksToReturn, Collections.reverseOrder());

          for(String title : booksToReturn) {
            printMessage(bookIndex(title), booksBorrowed);
          }

          booksToReturn.clear();
          System.out.println("END");
          continue;
        } else if (s.contains("RETURN")) {
          String title = s.substring((new String("RETURN")).length() + 1, s.length());
          booksToReturn.add(title);
        } else if (s.equals("END")) {
          break;
        }
      }
    } catch (Exception e) { System.out.println(e); }
  }

  public static void printMessage(int index, List<String> booksBorrowed) {
    if (index == 0) {
      System.out.println("Put "
        + books.get(0).getTitle()
        + " first");
    } else {
      int i = 1;
      Book previousBook = books.get(index - i);
      
      while (booksBorrowed.contains(previousBook.getTitle())) {
        previousBook = books.get(index - (i++));
      }

      System.out.println("Put " 
        + books.get(index).getTitle()
        + " after "
        + previousBook.getTitle());
    }
  }

  public static int bookIndex(String title) {
    int index = 0;

    for(int i = 0; i < books.size(); i++) {
      if (books.get(i).getTitle().equals(title)) {
        index = i;
        break;
      }
    }

    return index;
  }
}

class Book {
  private String title;
  private String author;

  public Book(String new_title, String new_author) {
    title = new_title;
    author = new_author;
  }

  public Book() {}

  public String getTitle() {
    return title;
  }

  public void setTitle(String new_title) {
    title = new_title;
  }

  public String getAuthor() {
    return author;
  }

  public void setAuthor(String new_author) {
    author = new_author;
  }
}

Post Reply

Return to “Volume 2 (200-299)”