Thread: anyone know the solution?

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    14

    anyone know the solution?

    Emily is a teacher. She likes to give candies to her students on days near festivals. She would like to give the candies to the students in order.

    She decides to distribute the candies to them one by one, with a rule that if student A is teased by B, A can receive candy before B. But this is a troublesome and time consuming task as she is very busy.

    You are asked to help Emily by writing a program to find the order of students that satisfies the rule.

    Input

    The first line of the input file contains an integer N (2 £ N £ 100), the number of students. The students are numbered as 1 to N. The following N lines describe each student being teased by whom. In the Kth line of those N lines, the first integer M (0 £ M < N) contains the number of students who tease student K, and the next M integers are the student numbers who tease student K.

    Output

    The output file should contain the sequence of student numbers separated by a space that Emily can distribute the candies with the rule satisfied. If there is more than one solution, you are only required to output anyone of them. If there is no solution, output "No Solution".

    Sample Input 1


    5
    2 2 3
    1 3
    1 5
    1 2
    0

    Sample Output 1

    1 4 2 3 5



    Sample Input 2

    5
    2 2 3
    1 3
    1 4
    1 2
    0

    Sample Output 2

    No Solution




    do anyone know how to solve this problem?

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    I assume you can figure out input and output okay.

    Here's a hint for you. This problem uses a datastructure that represents a graph.

  3. #3
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    Here's another hint for you: Read This

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > do anyone know how to solve this problem?

    This is a little story about four people named Everyone, Someone, Anyone, and Noone.

    There was an important job to be done and Everyone was sure that Someone would do it.

    Anyone could have done it, but Noone did it.

    Someone got angry about that because it was Everyone's job.

    Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

    It ended up that Everyone blamed Someone when Noone did what Anyone could have done
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    Quote Originally Posted by Salem
    > do anyone know how to solve this problem?

    This is a little story about four people named Everyone, Someone, Anyone, and Noone.

    There was an important job to be done and Everyone was sure that Someone would do it.

    Anyone could have done it, but Noone did it.

    Someone got angry about that because it was Everyone's job.

    Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

    It ended up that Everyone blamed Someone when Noone did what Anyone could have done
    I haven't heard that one before.

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    Quote Originally Posted by cwr
    Here's another hint for you: Read This
    this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    Quote Originally Posted by Rashakil Fol
    I assume you can figure out input and output okay.

    Here's a hint for you. This problem uses a datastructure that represents a graph.
    do you mean using array?let me try first

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by heeroyung
    this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.
    Then actually study it. Asking if any of us know how to solve it doesn't help you at all.

  9. #9
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    Quote Originally Posted by Thantos
    Then actually study it. Asking if any of us know how to solve it doesn't help you at all.
    i have already think this problem for two days. i don't think it's wrong to ask for some hints.

  10. #10
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Are you familiar with graphs?

    Topological sort.

  11. #11
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    Topological sort
    what's the meaning of this word?

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > what's the meaning of this word?
    Oh please tell me you've heard of google....
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by heeroyung
    i have already think this problem for two days. i don't think it's wrong to ask for some hints.
    Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.

  14. #14
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    Quote Originally Posted by Thantos
    Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.
    No need to say sorry. That's normal.

    This question require us to find a correct order of students. This can be done by making an array, e.g.
    Code:
    student[5]={1,2,3,4,5}
    , and then do swapping.if student 4 is teased by 1.the final array should be like that:{4,2,3,1,5}. The hardest problem is there may have some contradiction. e.g. student 4 is teased by 1 but student 1 is also teased by student 4! this come to another output--no solution. yesterday i thought one method---use array to store each student, and the following space store the number of students who tease this student. but i don't think this is a good method because the file size may be very large and the running time may be very long. so i hope to hear some opinions from you.

    (if you still don't trust me, you can ask me to explain. since my english standard is very low, i hope you can understand what i am saying above.)

  15. #15
    Registered User
    Join Date
    Sep 2005
    Posts
    14
    no one help me..................

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. K&R solution?
    By deadhippo in forum C Programming
    Replies: 12
    Last Post: 05-09-2008, 06:36 AM
  2. 'Solution' and 'Project' usage in VC++
    By C+/- in forum C++ Programming
    Replies: 2
    Last Post: 01-13-2007, 09:50 AM
  3. My Unix/Linux SECURITY SOLUTION - pls read
    By bjdea1 in forum Linux Programming
    Replies: 3
    Last Post: 04-11-2004, 09:28 PM
  4. Solution - Israel and Palestine?
    By Vber in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 03-19-2003, 08:27 AM
  5. Speed Challenge, my solution:
    By RoD in forum C++ Programming
    Replies: 11
    Last Post: 03-17-2003, 09:12 PM