Pagini recente » Dreptunghiuri | cuvinte6 | Profil AndreiRS | Joculet | Diferente pentru monthly-2014/runda-2/solutii intre reviziile 8 si 12
Nu exista diferente intre titluri.
Diferente intre continut:
* Penultima cifră a sa este impară, iar ultima cifră este $2$ sau $6$
* Penultima cifră a sa este pară, iar ultima cifră este $4$ sau $8$
Având în vedere că trebuie să eliminăm exact $K$ cifre şi că ne interesează ultimele $2$ cifre ale numărului rămas, ne vom concentra doar asupra ultimelor $K+2$ cifre ale numărului. Vom proceda în felul următor. Vom seta penultima cifră a numărului. Să presupunem ca am setat cifra de pe poziţia $i$ şi că numărul nostru are în total $C$ cifre. Dacă această cifră este impară, ne interesează numărul de apariţii ale cifrelor $2$ şi $6$, aflate în dreapta ei. Pentru ca cifra de pe poziţia $i$ şi cifrele de după să fie ultimele cifre din număr, va trebui şă ştergem exact $C-i+1$ cifre. Deci, vom avea de şters înca $K-(C-i+1)$ cifre din primele $i-1$. Avem exact combinări de $i-1$ luate câte $K-(C-i+1)$ modalităţi de a face acest lucru. Vom înmulţi acest număr cu numărul de apariţii ale cifrelor $2$ şi $6$ aflate în dreapta cifrei alese. Vom proceda analog şi la setarea unei cifre pare.
Având în vedere că trebuie să eliminăm exact $K$ cifre şi că ne interesează ultimele $2$ cifre ale numărului rămas, ne vom concentra doar asupra ultimelor $K+2$ cifre ale numărului. Vom proceda în felul următor. Vom seta penultima cifră a numărului. Să presupunem ca am setat cifra de pe poziţia $i$ şi că numărul nostru are în total $C$ cifre. Dacă această cifră este impară, ne interesează numărul de apariţii ale cifrelor $2$ şi $6$, aflate în dreapta ei. Pentru ca cifra de pe poziţia $i$ şi cifrele de după să fie ultimele cifre din număr, va trebui şă ştergem exact $C-i-1$ cifre. Deci, vom avea de şters înca $K-(C-i-1)$ cifre din primele $i-1$. Avem exact combinări de $i-1$ luate câte $K-(C-i-1)$ modalităţi de a face acest lucru. Vom înmulţi acest număr cu numărul de apariţii ale cifrelor $2$ şi $6$ aflate în dreapta cifrei alese şi vom actualiza răspunsul. Vom proceda analog şi la setarea unei cifre pare.
h1. 'Dreapta':problema/dreapta
Pentru inceput trebuie observat orice punct din interiorul unui poligon are urmatoarea proprietate:
Pentru inceput trebuie observat ca orice punct din interiorul unui poligon are urmatoarea proprietate:
* Exista cel putin o dreapta care trece prin acel punct astfel incat daca se taie dreapta in doua semidrepte (cu capatul semidreptelor in punctul respectiv), ambele semidrepte intersecteaza poligonul intr-un numar impar de laturi.
Folosind aceasta observatie ne putem gandi la abordare de genul urmator:
Folosind aceasta observatie ne putem gandi la o abordare de genul urmator:
* Calculam punctele de intersectie ale dreptei pe care se afla toate punctele din query-uri cu laturile poligonului
* Sortam punctele de intersectie dupa $x$ si daca sunt egale dupa $y$
Diferente intre securitate:
Topicul de forum nu a fost schimbat.