849 Taxe

[•DITzoneC]

Aici puteţi discuta despre problema Taxe.

[•funkydvd]

Problema aceasta se poate rezolva foarte usor cu o cautare binara, obtinand complexitatea O(log^2 n).

[•ciuperca]

Detaliaza te rog, si vezi ca complexitatea ta e n log ^ 2 din cate vad. Problema merge in log ^ 2. 

[•DraStiK]

Detaliaza te rog, si vezi ca complexitatea ta e n log ^ 2 din cate vad. Problema merge in log ^ 2. 

Cred ca ce vre sa spuna David este ca problema se poate rezolva cautand rezultatul intre 1 si S/4 - acest pas find de complexitate O(log N) si pentru fiecare rezultat se face o verificare - acest pas are complexitatea O(log REZ) (sau asa cred eu)

Deci final vine O (log S log REZ)

[•toni2007]

Problema aceasta se poate rezolva foarte usor cu o cautare binara, obtinand complexitatea O(log^2 n).

Ce ai rezolvat daca ne-ai spus cum se face ? Din cate stiu eu, era o regula sa nu oferi solutii complete, sau hinturi atunci cand nu-ti cere nimeni .

[•xtreme]

Pe nivelul 0 sunt 22 de oameni de rând, 20 dintre ei plătesc funcţionarilor de pe nivelul 1, ceilalţi 2 plătesc direct funcţionarului şef.
Pe nivelul 1 sunt 5 funcţionari, 4 dintre ei plătesc funcţionarului de pe nivelul 2, iar 1 plăteşte direct funcţionarului şef.
Pe nivelul 2 este un singur funcţionar care plăteşte direct funcţionarului şef.

enunt:Oamenii de rând sunt consideraţi funcţionari de nivel 0, iar funcţionarul şef este cel de pe nivelul maxim.=> ca functionarul de pe nivelul 2(nivel maxim) este functionarul sef.

Funcţionarul şef va preda statului 22*4+5*4+1*4(de la functionarul sef sau functionarul de pe nivel maxim 2...enunt:Singura persoana scutită de această taxă este funcţionarul şef)=112.

Nu vi se pare ca se contrazice enuntul cu explicatia exemplului?

iar S trebuie sa fie cel putin egal cu 4 pentru ca sa avem o solutie valida...

Care e diferenta d.p.d.v a enuntului daca pe nivelul 0 puneam 20 de functionari in loc de 22 si pe nivelul 1 puneam 7 in loc de 5?
d.p.d.v. al enuntului e corecta repartitia? dar rezultatele difera ...o repartitie da rezultat 22 si cealalta 20.

[•Bit_Master]

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta), si log-ul e ciudat (nu poti sa specifici baza logaritmului)...   (scz de off-topic daca e cazul).
Tot nu inteleg de ce e MinGW-ul asa de popular...  -> Eram sigur ca aceasta afirmatie imi va scadea karma-ul. MinGW-ul e ceva sfant aici, alaturi de C? Am mai vazut pe net unul care zicea ca C-ul nu e bun si ce probleme a avut cu el si a primit drept raspuns o ploaie de batjocuri...

______________________Mai tarziu__________________________________

Am luat 100 pe ea.
Ideea e ca nu aloci functionari pe nivele mai mari de 0 decat daca e nevoie.
Singurul caz in care cred ca ai voie sa aloci asa (fara sa ai nevoie) e daca nu sunt suficienti oameni.

Ex: ultimul omulet taran (pe nivelul 0) creeaza o noua grupa de 4 dar nu mai ai oameni ca sa creezi functionarul peste ei de nivelul 1. Atunci ultimul omulet nu mai e taran (nivelul 0) ci taran distins (nivelul 1), chiar daca nu aduna taxe de la nimeni.

[•Mishu91]

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta), si log-ul e ciudat (nu poti sa specifici baza logaritmului)...   (scz de off-topic daca e cazul).
Tot nu inteleg de ce e MinGW-ul asa de popular...  -> Eram sigur ca aceasta afirmatie imi va scadea karma-ul. MinGW-ul e ceva sfant aici, alaturi de C? Am mai vazut pe net unul care zicea ca C-ul nu e bun si ce probleme a avut cu el si a primit drept raspuns o ploaie de batjocuri...

______________________Mai tarziu__________________________________

Am luat 100 pe ea.
Ideea e ca nu aloci functionari pe nivele mai mari de 0 decat daca e nevoie.
Singurul caz in care cred ca ai voie sa aloci asa (fara sa ai nevoie) e daca nu sunt suficienti oameni.

Ex: ultimul omulet taran (pe nivelul 0) creeaza o noua grupa de 4 dar nu mai ai oameni ca sa creezi functionarul peste ei de nivelul 1. Atunci ultimul omulet nu mai e taran (nivelul 0) ci taran distins (nivelul 1), chiar daca nu aduna taxe de la nimeni.

In legatura cu log, acesta logaritmeaza in baza e, insa nu prea vad la ce ti-ar trebui o alta baza (in general se foloseste pentru evitarea lucrului cu numere mari unde este cazul).
Nu cred ca a zis nimeni ca MinGW e sfant, insa este unul dintre cele mai bune IDE-uri gratuite.
La olimpiadele scolare se folosesc C/C++ si Pascal. Daca C nu este pe placul tau poti folosi Pascal, dar acesta din urma nu se mai prea foloseste nicaieri, fiind un limbaj aproape mort.

[•blasterz]

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta)

Cod:

#include <cstdio>
#include <cmath>

int main()
{
	double x = sqrt(14);
	
	printf("%lf\n", x);
	
	return 0;
}

Mie de ce imi merge bine codul asta pe Mingw ?

[•robigi]

salut, as avea si eu o intrebare in legatura cu enuntul, adica repartizarea oamenilor de ce trebuie neaparat sa fie asa:

Pe nivelul 0 sunt 22 de oameni de rând, 20 dintre ei plătesc funcţionarilor de pe nivelul 1, ceilalţi 2 plătesc direct funcţionarului şef.
Pe nivelul 1 sunt 5 funcţionari, 4 dintre ei plătesc funcţionarului de pe nivelul 2, iar 1 plăteşte direct funcţionarului şef.
Pe nivelul 2 este un singur funcţionar care plăteşte direct funcţionarului şef.

si nu poate fi de exemplu asa:

Pe nivelul 0 sunt 23 de oameni de rând, 20 dintre ei plătesc funcţionarilor de pe nivelul 1, ceilalţi 3 plătesc direct funcţionarului şef.
Pe nivelul 1 sunt 4 funcţionari care plătesc funcţionarului de pe nivelul 2
Pe nivelul 2 este un singur funcţionar care plăteşte direct funcţionarului şef.

sau asa :


Pe nivelul 0 sunt 20 de oameni de rând care plătesc funcţionarilor de pe nivelul 1
Pe nivelul 1 sunt 7 funcţionari, 4 dintre ei plătesc funcţionarului de pe nivelul 2, iar 3 plătesc direct funcţionarului şef.
Pe nivelul 2 este un singur funcţionar care plăteşte direct funcţionarului şef.


nu inteleg care e diferenta, adica de ce prima metoda este corecta si restu nu sunt

[•wefgef]

Enuntul te poate induce in eroare, insa ceea ce se doreste este: X[k+1] = X[k] div 4, unde X[k] - numarul functionarilor de pe nivelul k.

[•cipriancx]

problema ajutatoare: cate zerouri are n! ?
principiul de rezolvare e acelasi doar ca in loc de 5 e 4.

[•Bit_Master]

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta), si log-ul e ciudat (nu poti sa specifici baza logaritmului)...   (scz de off-topic daca e cazul).
Tot nu inteleg de ce e MinGW-ul asa de popular...   -> Eram sigur ca aceasta afirmatie imi va scadea karma-ul. MinGW-ul e ceva sfant aici, alaturi de C? Am mai vazut pe net unul care zicea ca C-ul nu e bun si ce probleme a avut cu el si a primit drept raspuns o ploaie de batjocuri...

______________________Mai tarziu__________________________________

Am luat 100 pe ea.
Ideea e ca nu aloci functionari pe nivele mai mari de 0 decat daca e nevoie.
Singurul caz in care cred ca ai voie sa aloci asa (fara sa ai nevoie) e daca nu sunt suficienti oameni.

Ex: ultimul omulet taran (pe nivelul 0) creeaza o noua grupa de 4 dar nu mai ai oameni ca sa creezi functionarul peste ei de nivelul 1. Atunci ultimul omulet nu mai e taran (nivelul 0) ci taran distins (nivelul 1), chiar daca nu aduna taxe de la nimeni.

In legatura cu log, acesta logaritmeaza in baza e, insa nu prea vad la ce ti-ar trebui o alta baza (in general se foloseste pentru evitarea lucrului cu numere mari unde este cazul).
Nu cred ca a zis nimeni ca MinGW e sfant, insa este unul dintre cele mai bune IDE-uri gratuite.
La olimpiadele scolare se folosesc C/C++ si Pascal. Daca C nu este pe placul tau poti folosi Pascal, dar acesta din urma nu se mai prea foloseste nicaieri, fiind un limbaj aproape mort.

N-am nimic cu C-ul, vorbeam de MinGW. Am vazut intre timp ca functia sqrt in MinGW are probleme doar la debug. Oricum, intre timp m-am mai obisnuit cu MinGW-ul...

Partea cu C-ul am vrut sa spun ca poti fi luat in batjocura daca spui niste chestii rele despre el (pe internet), ceea ce nu mi se pare normal.

Cat despre C, am vazut intre timp ca e mult mai bun ca Pascalul. Adica urmaresti mult mai usor liniile de cod, si chiar imi place.
Ce NU imi place la el sunt functiile din bibliotecile lui. Sunt de parere ca cineva ar trebui sa faca putina ordine. In fine, asta e parerea mea.

Later Edit:

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta)

Cod:

#include <cstdio>
#include <cmath>

int main()
{
	double x = sqrt(14);
	
	printf("%lf\n", x);
	
	return 0;
}

Mie de ce imi merge bine codul asta pe Mingw ?

Pt ca functia merge, dar debug-ul e stricat. Eu la vremea aceea nu stiam asta, asa ca eu ma luam dupa debug crezand ca functia e gresita. Daca si la debug iti merge, atunci nush, merge oneori, alteori nu.

Editat de moderator : Nu posta consecutiv, modifica-ti posturile anterioare.

[•Andrei.Xwe]

Eu nu inteleg exemplul, daca avem S=112, rezulta 28 de functionari(29 cu seful).Deci, avem 1 functionar de nivel maxim(seful), de unde rezulta 4 functionari de nivelul imediat inferior,si 4*4=16 functionari pe urmatorul nivel inferior.Pana acum avem 21.Ne-ar mai trebui 64 pe nivelul de jos, dar cum nu avem atatia, adaugam un functionar langa ceilalti 4 de mai jos de sef, si automat 4 pe ultimul nivel.Deci mai avem inca 5(in total 5+21=26).Mai trebuie pusi 3 functionari, si acestia pot fi pusi pe ultimul nivel.
In concluzie, avem pe ultimul nivel 4*4+4+3=23 de oameni de rand...

[•Theodor1000]

Sunt de acord. Si dupa ce ca sqrt-ul nu merge in MinGW (am mai scris pe Infoarena ca sqrt (14) = 165 sau ceva de genul asta), si log-ul e ciudat (nu poti sa specifici baza logaritmului)...   (scz de off-topic daca e cazul).
Tot nu inteleg de ce e MinGW-ul asa de popular...  -> Eram sigur ca aceasta afirmatie imi va scadea karma-ul. MinGW-ul e ceva sfant aici, alaturi de C? Am mai vazut pe net unul care zicea ca C-ul nu e bun si ce probleme a avut cu el si a primit drept raspuns o ploaie de batjocuri...

______________________Mai tarziu__________________________________

Am luat 100 pe ea.
Ideea e ca nu aloci functionari pe nivele mai mari de 0 decat daca e nevoie.
Singurul caz in care cred ca ai voie sa aloci asa (fara sa ai nevoie) e daca nu sunt suficienti oameni.

Ex: ultimul omulet taran (pe nivelul 0) creeaza o noua grupa de 4 dar nu mai ai oameni ca sa creezi functionarul peste ei de nivelul 1. Atunci ultimul omulet nu mai e taran (nivelul 0) ci taran distins (nivelul 1), chiar daca nu aduna taxe de la nimeni.

Defapt sqrt-ul merge in mingw , dar probabil ai uitat sa incluzi cmath (#include <cmath>), altfel mingw-ul tau e prost