Afişează mesaje
|
Pagini: 1 [2] 3 4 ... 40
|
27
|
infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2018 / Răspuns: Smooth2
|
: Martie 11, 2018, 10:16:07
|
De fiecare dată se analizează caracterele care apar în ÎNTREG ȘIRUL cel puțin o dată. Deci caracterul "b" trebuie luat în considerare pentru toate prefixele. Șirul plin de "a" este ok fiindcă "a" este singurul caracter care apare în șir, deci diferenta e tot timpul 0.
Am modificat enunțul ca să fie mai clar, deși cred că era formulat ok și înainte.
|
|
|
35
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 416 Log
|
: Noiembrie 14, 2017, 12:00:47
|
Prima nelamurire e acoperita de enunt: "Factorii expresiei initiale sau ai oricareia dintre expresiile rezultate pe parcursul evaluarii NU pot fi comutati intre ei." Iar in general cand un enunt iti explica ce operatii poti face este subinteles ca nu poti face altele decat cele mentionate. Trebuie sa limitezi termenul de "simplificare" la ce iti spune enuntul despre el, daca vii cu alte presupuneri, ai iesit cel mai probabil din intentiile autorului.
|
|
|
49
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 493 Cezar
|
: Septembrie 17, 2017, 18:22:18
|
N-am rezolvat problema asta si n-am stat mult sa verific acum, sper ca nu vorbesc prostii.
Cred ca e corect ce faci. Daca presupunem ca alegem intai muchiile gratuite, centrul poate fi orice nod care are o muchie gratuita incidenta cu el (deci ai K + 1 variante la fel de bune). Atunci vrei sa demonstrezi doar ca exista intotdeauna o alegere optima a muchiilor gratuite care atinge si centrul "greedy" (sa-l numim centroid) descris de tine. Iar asta pare adevarat. Presupunand prin absurd ca setul optim de muchii nu atinge centroidul, atunci stergand una dintre muchiile cele mai indepartate de centroid si adaugand una noua "in directia" centroidului, costul nu poate sa creasca, fiindca muchia nou aleasa este utilizata de mai multi senatori decat cea veche (altfel centroidul n-ar fi fost centroid).
|
|
|
|