Wrong Answer

Ο Troy έφτιαξε το παρακάτω πρόβλημα (με τίτλο WA) για ένα διαγωνισμό προγραμματισμού:

Υπάρχει ένα παιχνίδι με ~N~ επίπεδα αριθμημένα από το ~1~ έως το ~N~. Υπάρχουν δύο χαρακτήρες, και οι δύο είναι αρχικά στο επίπεδο ~1~. Για ~i~ ~<~ ~j~, κοστίζει ~A_{i,j}~ νομίσματα για να κινηθεί ένας χαρακτήρας από το επίπεδο ~i~ στο επίπεδο ~j~. Δεν επιτρέπεται να μετακινήσουμε έναν χαρακτήρα από το επίπεδο ~i~ στο επίπεδο ~j~ αν ~i~ ~>~ ~j~. Για να κερδίσετε το παιχνίδι, κάθε επίπεδο (εκτός από το επίπεδο ~1~) πρέπει να το έχει επισκεφθεί ακριβώς ένας χαραχτήρας. Ποιός είναι ο ελάχιστος αριθμός νομισμάτων που χρειάζετε για να κερδίσετε;

Ο JP είναι ένας διαγωνιζόμενος και υπέβαλε την παρακάτω λύση σε Python.

def Solve(N, A):
  # A[i][j] is cost of moving from level i to level j
  # N is the number of levels
  x, y, sx, sy = 1, 1, 0, 0 # Initialize x and y to 1, sx and sy to 0
  for i in range(2, N + 1): #loop from 2 to N
    if sx + A[x][i] < sy + A[y][i]:
      sx += A[x][i]
      x = i
    else:
      sy += A[y][i]
      y = i
  return sx + sy

Ο Troy είναι σίγουρος πως η λύση του JP είναι λάθος. Ας υποθέσουμε ότι για μια είσοδο στο WA, η λύση του JP επιστρέφει ~X~ αλλά ο ελάχιστος αριθμός κερμάτων που χρειάζονται είναι ~Y~. Για να δείξετε πόσο λάθος είναι η λύση του JP, βοηθήστε τον Troy να βρει μία είσοδο ~N~ και ~A_{i,j}~ έτσι ώστε το ~X/Y~ να μεγιστοποιείται.

Είσοδος

Δεν υπάρχει είσοδος

Έξοδος

Εκτυπώστε μία είσοδο στο WA με την ακόλουθη μορφή:

Στην πρώτη γραμμή, εκτυπώστε έναν ακέραιο ~N~ (~2~ ~\le~ ~N~ ~\le~ ~100~). Έπειτα εκτυπώστε ~N~ - ~1~ γραμμές και η ~i~-οστη γραμμή θα πρέπει να περιέχει ~N~ - ~i~ ακέραιους ~A_{i, i+1}~, ..., ~A_{i, N}~ (~1~ ~\le~ ~A_{i, j}~ ~\le~ ~100~).

Αν η έξοδός σας δεν είναι στη σωστή μορφή, θα θεωρηθεί λανθασμένη και θα λάβετε ~0~ βαθμούς.

Αλλιώς, υποθέστε ότι για τη δική σας είσοδο, η λύση του JP επιστρέφει ~X~ αλλά ο ελάχιστος αριθμός νομισμάτων που απαιτείται είναι ~Y~. Τότε θα λάβετε ~\lceil~min(~25~, ~X~/~4Y~)~\rceil~ βαθμούς όπου ~\lceil~~Z~~\rceil~ είναι ο μικρότερος ακέραιος που δεν είναι μεγαλύτερος του ~Z~.

Παράδειγμα

output

5
1 2 3 4
10 9 8
7 6
5

Επεξήγηση του παραδείγματος

Ο βέλτιστος τρόπος για να κερδίσετε το παιχνίδι είναι ο ένας χαρακτήρας να επισκεφθεί το επίπεδο ~2~ και ο άλλος χαρακτήρας να επισκεφθεί τα επίπεδα ~3~, ~4~ και ~5~. Αυτό κοστίζει (~1~) + (~2~ + ~7~ + ~5~) = ~15~ νομίσματα. Η λύση του JP επιστρέφει ~18~. Οπότε, ~X~/~4Y~ = ~18~/(~4~x~15~) = ~0.3~, άρα αυτή η έξοδος θα λάβει ~\lceil~~0.3~~\rceil~ = ~1~ βαθμό.