012 Ridicare la putere in timp logaritmic

[•alexandru92]

O mica/mare nelamurire.. compilez in MinGW o sursa.. primesc valori aiurea.. se comporta ciudat ..( o functie care intra pe o ramura de return 1 returneaza 0 sau valori aiurea sau nush ) .. si am observat ca daca schimb long long-urile in long-uri sau ma rog ... atunci merge.. insa sursa este de 100 de puncte ( noroc ca am incercat sa o trmit sa vad ). Deci nu merge long long-u in MinGW altfel nu imi pot explica, pt ca atunci cand declar long cele 2-3 variabile.. merge brici .. chiar nu inteleg.. de ce sa nu mearga long long-u? eroare nu da.. prin urmare? care-i faza? ms anticipat, chiar astept un raspuns ca  sursa e ultima trimisa ( nu cred c-o sa fie mare activitate la problema asta deci o gasiti usor  )

Am vazut ca lucrezi in "c" .
Inlocuieste %lld cu %I64d .

[•blasterz]

O mica/mare nelamurire.. compilez in MinGW o sursa.. primesc valori aiurea.. se comporta ciudat ..( o functie care intra pe o ramura de return 1 returneaza 0 sau valori aiurea sau nush ) .. si am observat ca daca schimb long long-urile in long-uri sau ma rog ... atunci merge.. insa sursa este de 100 de puncte ( noroc ca am incercat sa o trmit sa vad ). Deci nu merge long long-u in MinGW altfel nu imi pot explica, pt ca atunci cand declar long cele 2-3 variabile.. merge brici .. chiar nu inteleg.. de ce sa nu mearga long long-u? eroare nu da.. prin urmare? care-i faza? ms anticipat, chiar astept un raspuns ca  sursa e ultima trimisa ( nu cred c-o sa fie mare activitate la problema asta deci o gasiti usor  )

Am vazut ca lucrezi in "c" .
Inlocuieste %lld cu %I64d .

Bravo Alexandru!... E printre putinele posturi bune ale tale!...Incearca sa postezi mai rar... dar sa fie la fel ca asta, si o sa-ti creasca karma!.
Ai un + de la mine!

Eu am incercat L64D si l64d si nu mergeau (stiam eu ca e ceva de genul)

[•toni2007]

Eu recomand afisarea cu streamuri, pt ca este standard, si va merge la fel pe orice compilator. Daca lucrezi in c, si totusi vrei sa iti mearga si pe mingw si pe linux acelasi cod, fa asa:

Cod:

long long x = 3390198353949LL;

#ifdef __MINGW32__
    printf("%I64d\n", x);
#else
    printf("%lld\n", x);
#endif

Sunt define-uri din care preprocesorul va alege unul din ele in functie de compilator.

[•brainwashed20]

as putea cu acest algoritm sa ridic o permutare sigma la puterea k?

[•Florian]

Da. Si iese N * log(K), unde N e ordinul permutarii.

[•caen1]

Eu am luat 100 de puncte la problema asta folosind

Cod:

if(e == 1) return n; // daca avem n^e, iar e = 1, returneaza n

. Apoi am vrut sa rezolv problema paritate folosind functia mea de exponentiere rapida in loc de pow-ul din math.h pe care il foloseam inainte. Insa luam Memory Limit Exceeded pe toate testele, iar la mine pe calculator Segmentation Fault. Dupa multe schimbari la cod, am modificat linia scrisa mai sus in

Cod:

if(!e) return 1; // daca avem n^e, iar e = 0, returneaza 1

si a mers. Imi poate explica cineva care ar fi diferenta dintre cele doua versiuni (in afara de cea evidenta ca una se opreste la 1, iar cealalta la 0)? Multumesc!

[•devilkind]

 E posibil la un moment sa sari peste e=1 si sa ajungi direct la e=0. E cam greu sa imi dau seama de ce se intampla acest lucru fara codul functiei, ca sa vad cum faci impartirea sa iti pot da un exemplu.

[•caen1]

Codul care nu functiona la problema paritate este acesta

Cod:

#include <stdio.h>
#include <string.h>

#define IN "paritate.in"
#define OUT "paritate.out"
#define M 60000
#define N M * 8

static char sir[N];
static char text[M];

static int baza_doi(int); /* Conversie in baza 2 */
static int exp1(int, int); /* Exponentiere rapida */

int main(void) {

    long len, i;
    int b_par, j, unu;
    char ok = 1, paritate;

    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);

    fgets(sir, N, stdin);
    len = strlen(sir);

    for(i = 0; i < len >> 3; ++i) {

        b_par = i << 3;
        if(sir[b_par] == '1') paritate = 1;
        else paritate = 0;

        for(j = 1, unu = 0; j < 8; ++j) {

            if(sir[b_par + j] == '1') ++unu;
        }

        if(unu % 2 == paritate) text[i] = baza_doi(b_par);
        else ok = 0, text[i] = 0;
    }

    if(ok) {

        printf("DA\n");
        for(i = 0; i < len >> 3; ++i) printf("%c", text[i]);
    } else {

        printf("NU\n");
        for(i = 0; i < len >> 3; ++i) if(!text[i]) printf("%ld ", i);
    }

    return 0;
}

int baza_doi(int start) {

    int j, rez = 0;

    for(j = 7; j > 0; --j) if(sir[start + j] == '1') rez += exp1(2, 7 - j);

    return rez;
}

int exp1(int n, int e) {

    int rez;

    if(e == 1) return n;

    rez = exp1(n, e >> 1);
    rez *= rez;
    if(e & 1) rez *= n;

    return rez;
}

[•geniucos]

Imi poate spune si mie cineva cum se face Nice Patterns Strike Back ca nu imi vine nici o idee

[•visanr]

La problema aia din cate am vazut aici (http://infoarena.ro/forum/index.php?topic=2565.0) trebuie sa ridici o matrice la putere in timp logaritmic. Probabil intrebi cum ridici rapid matricea la putere, asa ca te poti folosi de "Al k-lea termen Fibonacci" din Arhiva Educationala, acolo trebuie sa faci asta.

[•reking]

Puteti sa-mi dati si mie, va rog, un exemplu de teste pentru care sursa aceasta pica???

Cod:

#include <iostream>
#include <fstream>
#define MOD 1999999973
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
int n,p;
int powmodulo ()
{
    int b=1;
    while (p)
    {
        if ((p&1))
        {
            b=((b%MOD)*(n%MOD))%MOD;
            p--;
        }
        n=((n%MOD)*(n%MOD))%MOD;
        p=(p>>1);
    }
    return b;
}
int main ()
{
    f>>n>>p;
    g<<powmodulo();
}

Chiar am incercat multe exemplu si toate imi dau bine.
Multumesc.

[•rares96cheseli]

Puteti sa-mi dati si mie, va rog, un exemplu de teste pentru care sursa aceasta pica???

Cod:

#include <iostream>
#include <fstream>
#define MOD 1999999973
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
int n,p;
int powmodulo ()
{
    int b=1;
    while (p)
    {
        if ((p&1))
        {
            b=((b%MOD)*(n%MOD))%MOD;
            p--;
        }
        n=((n%MOD)*(n%MOD))%MOD;
        p=(p>>1);
    }
    return b;
}
int main ()
{
    f>>n>>p;
    g<<powmodulo();
}

Chiar am incercat multe exemplu si toate imi dau bine.
Multumesc.

Pune variabilele si functia long long si o sa mearga 

[•reking]

Uff...si cat am mai rasucit sursa xD.
Multumesc din nou ^_^ 

[•dutzul]

http://www.infoarena.ro/job_detail/1019598

cum de ia sursa asta 100 p?? adica aici fac o(n) operatii de inmultire ,miam dat seama deaba cand am rezolvat problema al k-lea termen fibonacii, si la invers modular din arhiva tot 100 iau cu acelasi algorithm gresit.

oare compilatoru imi optimizeaza programul?? nu prea intaleg dc totusi imi ruleaza asa repede

[•PlayLikeNeverB4]

oare compilatoru imi optimizeaza programul?

Se pare ca da.

[•https]

Imi puteti explica va rog si mie solutia oficiala? Am inteles ideea astfel incat sa implementez algoritmul recursiv, dar nu inteleg cum functioneaza solutia oficiala.

[•dr_personality]

Ideea e ca n^k = n*n*...*n si asta are complexitate o(k).In sursa oficiala ei ii gasesc reprezentarea binara a lui k si scriu acel pordus sub forma mai multor produse de tipul n^(2^x),din cate poti vedea daca bitul x este 1,inmultesc produsul cu n^(2^x), iar toate aceste produse se genereaza in timp logaritmic, adica avem complexitate o(log k), ceea ce in multe probleme poate face diferenta.

[•SMerlin]

Imi poate explica cineva de ce nu imi functioneaza codul?
http://www.infoarena.ro/job_detail/1842699

[•AlexandruValeanu]

Ar trebui sa calculezi si rezultatele intermediare modulo m.

[•SMerlin]

Imi da la fel.

http://www.infoarena.ro/job_detail/1842980?action=view-source

[•AlexandruValeanu]

Unde conteaza tot nu pui modulo (eg n*n).

[•SMerlin]

Appreciated