Prefab: subtask falliti


#1

Prefab è un problema semplicissimo, ne prendo atto, e anzi sono il primissimo a dirlo. Peccato che nonostante la mia sfacciataggine e presunzione non riesca a ottenere 100/100.

http://paste.ubuntu.com/23549997/

Falliscono i subtask 14 e 15


Prefab: testcase 12
#2

Ciao,

La tua soluzione è corretta, ma non hai considerato un caso.

Questa riga è valida solo se il lato maggiore del tetto è più grande del lato maggiore della casa (ovvero a sporgere è il lato maggiore del tetto):

return ((X - A) / 2 + (X - A) % 2) * Y;

Ma se invece a sporgere fosse il lato minore del tetto?


#3

Grazie, provo subito ad aggiungere questo caso


#4

Ragazzi avrei bisogno di un chiarimento…
Avevo scritto questo codice per i casi in cui ci fosse un solo lato che va fuori (X > A o Y > B).

if (X > A && Y <= B) { return (Y * ((X-A+1) / 2)); } else if (Y > B && X <= A) { return (X * ((Y-B+1) / 2)); }

Io non avevo messo i “+1”, che però nella soluzione corretta ci sono.
Non riesco a capire a cosa servono perché nell’esempio non è necessario (il risultato è sempre 40), qualche idea?


#5

In realtà il “+1” a prescindere è sbagliato quanto la sua assenza.

Mettiamo che A e B sono 20 e 30, mentre X e Y sono 23 e 30 (supponendo sempre che A < B e X < Y, si scambiano in caso contrario): la presenza di un numero dispari comporta che la divisione per 2 provochi un troncamento, e quindi ti darebbe come risultato, senza aggiungere 1, (23 - 20)/2 * 30, ovvero 30, ma in realtà è 60 perché devi sempre prendere, tra 2 eccedenze, quella maggiore (e le misure sono sempre intere), di conseguenza avresti dovuto arrotondare quel 23 al prossimo numero pari.

Prova a modificare quel “+1” con “+qualcosachetiserve%2”


#6

Il +1 serve per arrotondare per eccesso il risultato della divisione per 2, per ottenere l’area della sezione più grande in caso di lunghezza in eccesso dispari.
(N + 1) / 2 = ceil(N / 2)
Se N è pari il risultato sarà N / 2 perchè il ,5 risultante dal +1 verrebbe ignorato, se N è dispari il risultato sarà N / 2 + 0.5, arrotondando per eccesso il ,5.

Dario


#7

ciao,

penso che il testcase #12 sia scorretto. Ho provato 3 soluzioni fatte indipendentemente (una fatta da me in Pascal, una fatta da Cip666 in C++ e la soluzione ufficiale scaricata dal sito OIS) e tutte falliscono.
Ho ottenuto 100/100 con una soluzione che considero scorretta, cioè nel caso in cui Y <= A < X e B<Y si considera uno solo dei due orientamenti possibili, mentre penso si debba provarli entrambi.

Qualcuno può controllare? :slight_smile:


#8

A me la soluzione ufficiale da 100
https://pastebin.com/QG9GQHCX


#9

grazie!
non conoscevo questa soluzione, ma conferma la mia idea che il testcase 12 sia sbagliato.
A meno che non abbia capito male il problema, s’intende.
Infatti secondo me la soluzione ufficiale che mi hai indicato è errata. Infatti essa, se l’input è:
2 6 4 8
da come risultato 20 (ovvero la differenza tra le aree, ottenuta orientando il blocco superiore in modo da ricoprire completamente quello inferiore).
Invece (se ho interpretato bene il testo del problema :slight_smile: ) il risultato corretto è 12, ottenuto disponendo i due blocchi “a croce”, cosa che in questo caso è possibile in quanto 6>4, mentre la soluzione ufficiale non prova questa possibilità


#10

Hai ragione il risultato corretto è 12.

Comunque credo di essermi confuso, credo che questa fosse la mia implementazione non la soluzione ufficiale. :blush:


#11

ah ok. :smile:
Comunque, poco importa in realtà la soluzione ufficiale, il problema vero è che il testcase secondo me è scorretto:

  • la soluzione, che calcola un risultato errato per l’istanza “2 6 4 8” prende 100/100

  • due soluzioni che calcolano il risultato corretto per “2 6 4 8” prendono 60/100

:face_with_raised_eyebrow:


#12

Anche con la mia soluzione succede la stessa cosa, l’unico modo per ottenere 100 è stato quello di sottoporre la soluzione “sbagliata” che considera un solo orientamento. Btw, Cip666 è la versione malefica di Cip999 o è solo un typo? :grinning:


#13

:smiley: l’Anti-Cip :smiley:
comunque malefico o meno, è sempre lui ed è una garanzia


#14

Anche la mia soluzione sbaglia solo il test case 12 e prende 60/100 inoltre con l’input “2 6 4 8” da come risultato 12.