Προς το περιεχόμενο
  • 0
Xvipes

Facebook Πρόβλημα(όχι δεν είμαι σε λάθος section :P )

Ερώτηση

Αν πάτε ποτέ στο careers στο Facebook και μετά στο New grads and university students (κάτω κάτω) σε ένα σημείο στο κάτω μέρος της σελίδας λέει Solve a Facebook Programming Challenge.

Το πρόγραμμα που δίνουν σαν τεστ στο κανονικό πρόβλημα είναι το παρακάτω.
 

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

·         A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.

·         At anypoint of time, the decreasing radius property of all the pegs must be maintained.


Constraints:
1<= N<=8
3<= K<=5


Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.


Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

 

2 3

1 1

2 2

Sample Output #00:

 

3

1 3

1 2

3 2



Sample Input #01:

6 4

4 2 4 3 1 1

1 1 1 1 1 1

Sample Output #01:

5

3 1

4 3

4 1

2 1

3 1

NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"

 

 

 

 

λίγο που το googlara είδα ότι μοιάζει με το Tower of Hanoi.
 

Ξέρει ή μπορεί να μου πει κανείς που θα βρω την λύση του παραπάνω προβλήματος κατά προτίμηση σε Java?

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

4 απαντήσεις σε αυτή την ερώτηση

Προτεινόμενες αναρτήσεις

  • 0

Ψάξε στο google για υλοποιησεις του Hanoi. Αν ειναι αυτο.... δεν διαβασα καθολου το προβλημα.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Φανταζομαι πως οποιος κατσει και βρει τη λυση, θα την στειλει στο facebook για να παρει credit αντι να απαντησει εδω..... Σε ενθαρρυνω να την προσπαθησεις μονος σου.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Φανταζομαι πως οποιος κατσει και βρει τη λυση, θα την στειλει στο facebook για να παρει credit αντι να απαντησει εδω..... Σε ενθαρρυνω να την προσπαθησεις μονος σου.

 

Όπως έγραψα και στην αρχή, δεν είναι το κανονικό ερώτημα αλλά ένα sample test.

 

If you want to get a feel for how the system works before starting the timer, please try our sample test

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Τα προβληματα δεν ειναι παντα ιδια, αλλα ολα ειναι στο ιδιο context.

 

99% Δυναμικος προγραμματισμος + 1% parsing

ή

29% computation + 60% Δυναμικος προγραμματισμος + 1% parsing

 

Τετοια μπαινουν και σε διαγωνισμους προγραμματισμου (πχ google code jam ή facebook hacker cup).

  • Like 1

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
×
×
  • Δημιουργία νέου...

Χρήσιμες πληροφορίες

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.