Clasa a V-a lecția 25 - 18 feb 2014

Probleme olimpiadă

Discuție probleme olimpiadă.

Jocul resturilor

• Am prezentat o soluție care nu ține cont de faptul că cifrele sînt prea multe și prefixele prea mari. Cei ce nu știau o soluție mai bună trebuia să o implementeze pe aceasta. Probabil luau 20-30p. Am aflat că Ioana Feraru a rezolvat așa și a luat 60p!
• Cineva a propus soluția corectă, cu modulo k și am explicat-o împreună.
• Partea centrală a explicației, a fost faptul că dacă avem de calculat o expresie modulo k atunci putem înlocui toate numerele din expresie cu aceleași numere modulo k și rezultatul nu se modifică.
• Am schițat o idee de demonstrație, cum ca ar trebui să demonstrăm aceasta pentru adunare și înmulțire separat, dînd ca exemplu adunarea: scriem numerele ca multipli de k plus restul și apoi facem adunarea și vedem că în ambele cazuri vom avea același rezultat.
• Am scris codul care nu ține cont de numere mari și am văzut că modificarea era banală, trebuia doar să calculăm prefixul modul k.
• Am vorbit despre cum calculăm maximul și numărul de apariții: se poate face cu vectori, cum au facut majoritatea, sau dintr-o singură parcurgere. Am scris codul pentru o singură parcurgere.
• În partea a doua am vorbit despre cum facem citirea numerelor pînă la final de linie, prin doua metode:
  • metoda 1, citire cu caractere. Ați întrebat dacă era sigur ca aveți \n la final de linie, v-am răspuns că corect așa era: la olimpiadă toate liniile se termină cu \n.
  • metoda 2, citire cu fscanf() testînd rezultatul; fscanf() întoarce numărul de variabile citite din fișier. În cazul nostru trebuia să întoarcă 1 dacă a citit ceva, 0, atlfel. Unii dintre voi știau acest lucru deși nu l-am predat. Felicitări!

Exodul marțienilor

• Am mentionat neclaritatea enuntului care spunea că n ≤ 40 de miliarde, dar numărul era scris ca 40000 000 000. Primele patru zerouri lipite m-au făcut să ma întreb dacă nu cumva era o greșeală la zerouri, mai ales că numărul era foarte mare, extrem de neobișnuit pentru clasa a 5^a, olimpiada pe sector!
• Am vorbit despre prima parte, calculul numărului de etape în care evacuăm planeta. Am discutat despre două soluții:
  • cea simplă, în care facem simulare, avem grijă să calculăm pentru fiecare etapă numerele pentru cele trei planete
  • atenție la long long, am vorbit despre cînd folosim acest tip, ce variabile din simulare ar trebui să aibă acest tip
  • am calculat numărul maxim de etape, am ajuns la concluzia că este mai mic de 300 000 și am că este un număr mic de operații, dat fiind ca aveți o secundă pentru execuție
• Am vorbit de metoda mai grea dar mai eficientă: calcul. Putem calcula numărul de etape facînd suma lui Gauss pînă la 2p; am scris ecuațiile si a rezultat că trebuie să extragem un radical ca să aproximăm p, dar ulterior trebui să testăm daca rezultatul este p sau p+1.
• Nu am detaliat cu calculăm ulterior cîți marțieni avem pe fiecare planetă la final, deoarece părea greu; ar fi trebuit să facem calcule multe și greu de urmărit.
• Am ajuns la concluzia că prima soluție, cea cu simulare, este mai sigură în condiții de olimpiadă. Felicitări celor care au reușit să ia 100p cu formule!
• Am discutat și punctul doi, determinarea mărimii navei pentru ca simularea să se termine în p etape.
• Am menționat neclaritatea enunțului, care spune că evacuarea trebuie să se termine în exact p etape; cuvîntul exact nu este necesar, dar ne poate face să ne întrebăm ce semnificație specială are. Combinat cu exemplul nefericit ales ne întrebăm dacă nu cumva trebuie să evacuăm toți marțienii. Am ajuns la concluzia că nu se poate și că luăm varianta cea mami probabilă, că transportul se face ca la primul punct, pînă ce nu mai putem umple navele catre ambele planete. Cuvîntul exact era inutil, care probabil vrea să însemne să calculăm p maxim, ceea ce oricum trebuia să facem deoarece planeta nu era considerată evacuată în caz contrar.
• Am făcut calculul sumei lui Gauss, am scris inegalitatea, suma lui Gauss ≤ n, de unde am calculat k. Formula e simplă, în final.

Temă

Tema 25 clasa a 5^a:

• Culori1 dată la ONI 2012, clasa a 5^a
• Panglica dată la ONI 2002 clasa a 5^a

Rezolvări aici [1]