|
Titlul: 1045 Covor Scris de: Paul-Dan Baltescu din Mai 10, 2010, 08:00:30 Aici puteti discuta despre problema Covor (http://infoarena.ro/problema/covor).
Titlul: Răspuns: 1045 Covor Scris de: Cristian Lambru din Iunie 22, 2011, 21:40:29 Salut la toata lumea.
Am o rezolvare in O(N^2) pe care cred ca o pot si demonstra prin inductie, cu toate acestea iau 0 puncte. Imi puteti spune va rog daca afirmatia mea e corecta? Recursivitatea este asa: - Daca pe pozitia A[ i ][ j ] este 0 si pe A[ i-1 ][ j ] == 0 si A[ i ][ j-1 ] == 0 ( adica si sus si la stanga sa fie 0 ) recursivitatea este A[ i ][ j ] = A[ i-1 ][ j ] + A[ i ][ j-1 ] + 1 - A[ i-1 ][ j-1 ] - Daca A[ i-1 ][ j ] ( cea de deasupra ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de la stanga - Daca A[ i ][ j-1 ] (cea de la dreapta ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de deasupra Este corecta aceasta rezolvare? Eu am testat aceasta rezolvare pe mai multe teste, chiar am si verificat cu o solutie brute force, si toate imi dau corect. De ex pentru testul : Cod: 18 Da 1250 ? Va rog frumos sa ma ajutati. Multumesc! Titlul: Răspuns: 1045 Covor Scris de: Dragos-Alin Rotaru din Iunie 22, 2011, 22:15:11 Si mie imi da tot 1250 :)
Titlul: Răspuns: 1045 Covor Scris de: Cristian Lambru din Iunie 22, 2011, 22:18:30 Multumesc frumos pentru raspuns.
Mi-ai putea da si mie sursa prin PM te rog frumos? Din moment ce eu nu mai am idei de rezolvare mi-ar fi de mare ajutor. Multumesc. L.E. : Recurenta intr-un fel sau altul era gresita! Titlul: Răspuns: 1045 Covor Scris de: Paul-Dan Baltescu din Iunie 23, 2011, 11:50:16 Ce inseamna matricea A? Nu putem sa ne dam seama daca recurenta e corecta fara sa stim ce vrei sa calculezi. :)
Titlul: Răspuns: 1045 Covor Scris de: Marian Iacob din Aprilie 10, 2014, 12:19:47 care va fi raspunsul pentru
2 00 00 |