230 - Borrowers

[pete]

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

[RuiFerreira]

for me too!

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


Thanks!

[bobi1978]

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?

[angga888]

Hi bobi1978,

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

Hope it helps.
angga888

[DD]

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.

[Neto_o]

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.

[uDebug]

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

[BlackBeard]

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

[brianfry713]

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.

[BlackBeard]

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

[madca03]

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;
  }
}