Problem 2: List of Books, (K Narayan Kumar / R Shreevatsa, CMI)
This is another problem about Indraneel's library. His library has one long shelf. His books are numbered and he identifies the books by their number. Each book has a distinct number.
He has lost many books, since many of his friends borrow his books and never bother to return them. He does not want to lose any more books and has decided to keep a record of all books that he lends to his friends. To make the task of borrowing a book a little difficult, he has given the following instructions to his friends: when they borrow a book, they must record in a register its position from the left among the books currently on the shelf.
Suppose there are 5 books in the library and they are arranged as follows:
26 1 42 15 3
If someone walks in and borrows the book 42, then he will record 3 in the register because this book is the third from the left on the shelf. Now the shelf looks like this:
26 1 15 3
If the next person borrow the book 3, he writes down 4 in the register since this is currently the fourth book from the left on the shelf, and so on.
Indraneel knows the initial arrangement of the books in his library at the time that he introduced the register system. After a while he examines his register and would like to know which books have been borrowed. Your task is to write a program to help Indraneel solve this problem.
Input format
The first line of the input contains a single integer M indicating the number of books in Indraneel's library. The next line contains M distinct positive integers describing the sequence in which the books are arranged on the library shelf. The third line of input contains a single integer N indicating the number of entries in the register. This, in turn, is followed by N lines (lines 4 to N+3), each containing one positive integer. The integer on line 3+i indicates the position from left of the book ith book borrowed. (You may assume that the number on line 3+i is at most M-i+1.)
Output format
N lines with one positive integer on each line. The number on line i is the book borrowed by the ith borrower.
Test Data:
You may assume that 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
5
26 1 42 15 3
2
3
4
Sample Output
42
3
CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style:
Here's my solution :-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include <iostream>
usingnamespace std;
int main(){
int i,j,n,m,li[1000001],judge[4001],jc=0,tmp,tc=0;
cin>>m;
for (i=1;i<=m;i++) cin>>li[i];
cin>>n;
for (i=1;i<=n;i++) {
cin>>tmp;
tc++;
for (j=0;j<jc;j++) {
if (tmp>=judge[j]) tc++;
}
cout<<li[(tmp+tc-1)]<<endl;
judge[jc]=li[(tmp+tc-1)];
jc++;
tc=0;
}
}
It is working correctly in the given example , but gives me message "Wrong Answer" when i submit it .
Can anybody help me ?
Thnx for help in advance .
hmmmm... yes ne555 , i think you pointed out correctly .
coder777 , yeah your code is definatly neat and working , but it is fetching only 60% marks , just same as my one of codes i made previously ! :( can you improve it , as value of m can be very large indeed , thus it is exceeding time limit !
So can anybody tell me a better algorithm ??
Hey thanks a lot coder777 , as i read this program i felt that it was perfect , but i don't know why it is giving 0 points and telling "Wrong Answer" !!!!
Even i am in delemma ?!?
Thanks a lot coder777 for extending a helping hand !
Actually coder777 , i really couldn't understand what are you actually doing , so i couldn't debug it :) , instead i was trying and here's the code what i have brought to :-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
#include<iostream>
usingnamespace std;
int main() {
int i,j,n,booklist[100],m,borrowed[4000],tc;
cin>>m;
for (i=1;i<=m;i++) cin>>booklist[i];
cin>>n;
for (i=1;i<=n;i++) {
cin>>borrowed[i];
tc=0;
for (j=1;j<i;j++) {
if (borrowed[j]<=borrowed[i]) tc++;
}
cout<<booklist[(borrowed[i]+tc)];
}
}
Though this is giving wrong answer still , i am trying to do it !
And realy thankyou for your efforts :)
The problem is that the output should appear after the input is done. Therefore 'tc' has to be an array with the same size like 'borrowed' and you need a second loop after the borrowed loop.
The idea is: Since I can't move the books I move the index to the books. So whenever the user borrows a book the index must be incremented as long as a book left of the current book is borrowed.
Imagine that the user enters 1 three times. The first time he enters 1 he means the first book.
The second time he enteres 1 he means the second book and so forth.
The second time the amount of books are already borrowed left of the current book is 1 and so add 1 to the entered index.
If he enters 1 the third time 2 books are already borrowed left of the current. That means to get the index where the book really is you need to add 2 to the entered index.
You need to hold those corrected index in an array to show the borrowed books. And you need to hold the index entered in an array to find the index left of the currently entered index.
Hope that makes it a bit clearer.
I can show you some code, but it's up to you to make it running
Yes , it made me clear .
First of all 'tc' need not be needed , we can can print the book taken any time , as the compiler checks our program by taking all given output in a file and comparing with result file , thus we can print out book taken as we take input !!! (u can take this fact for granted , i have tried on previous problems !) .
And yes , the idea you explained me , is exactly the same as mine from the starting !!!
And once again thanks coder777 !!!
Yeah , you correctly pointed me that , it was really a silly mistake !
And also that at the time of declaration , i need to increase array size , but still even after correcting these mistakes , don't know how it is saying "Wrong Answer" and i have really lost hope for getting correct answer !
I have started believing that the checking program is wrong !!! for i have tried writing the code , testing it many many many times , but still getting same message .
#include<iostream>
usingnamespace std;
int main() {
int i,j,n,booklist[100],m,borrowed[4000],tc;
cin>>m;
for (i=1;i<=m;i++) cin>>booklist[i];
cin>>n;
for (i=1;i<=n;i++) {
cin>>borrowed[i];
tc=0;
for (j=1;j<i;j++) {
if (borrowed[j]<=borrowed[i]) tc++; // the left books
if (borrowed[j]>borrowed[i]) borrowed[j]--; // the right books
}
cout<<booklist[(borrowed[i]+tc)] << endl;
}
}
So test it with as many books as possible. Combinations are: single/multiple books. Book(s) for right/middle/left right/left right/middle ...
please tell me if that finally works, since I want to see it finished