008 Cifra

[•fluffy]

Aici puteţi discuta despre problema Cifra.

[•SergiuH]

Puteti verifica testele de iesire pt aceasta problema? pt ca eu mi-am verificat programu (pe care evaluatorul imi arunca 10 pct de mila) pana la n=10000  si e corect. Si daca merge pana la 10000 merge SIGUR si pana la 10^100.

[•domino]

Si daca merge pana la 10000 merge SIGUR si pana la 10^100.

Gresit!!! Nu prea ai cum sa sustii afirmatia asta.. plus gandeste-te ca problema a fost rezolvata de foarte multa lume de 100 de puncte.. asa ca sigur nu e de la noi.

[•SergiuH]

Nu vreau sa par nesimtit pt. ca te contrazic si nici sa deconspir ideea mea de rezolvare, dar, daca "merge" pana la 100, restul numerelor nu mai conteaza, indiferent de cat de mari sunt.

[•domino]

Nu vreau sa par nesimtit pt. ca te contrazic si nici sa deconspir ideea mea de rezolvare, dar, daca "merge" pana la 100, restul numerelor nu mai conteaza, indiferent de cat de mari sunt.

Pai poate calculezi tu gresit restul impartirii la 100 ... cine stie.. oricum, greseala e de la tine... daca e scurt codul incearca sa-l pui aici sa vedem ce are.

[•SergiuH]

Imi cer scuze ca te-am contrazis, am depistat greseala. Vectoru meu de constante nu era alocat pt 0 si cand trecea de limita, in BP imi dadea zero si mergea pe orice caz da in FP se impusca. Asta e, pe viitor voi compila sursele numa in FP.

[•danny]

Eu personal nu pot sa inteleg ce are acest program pe evaluatorul meu iau 100 puncte din 100 dar pe site imi da 0 pct.
  Va rog sa-mi explicati ce gresala are.
  Uita-ti codul:

Cod:

  var i,j,n,m,suma:longint;
    f,g:text;

function rez2(x:longint):longint;
var y,h,rez:longint;
begin
     y:=x;
     x:=x mod 10;
     if x=0 then rez:=0;
     if x=1 then rez:=1;
     if x=2 then
       begin
            h:=y mod 4;
            if h=1 then rez:=2;
            if h=2 then rez:=4;
            if h=3 then rez:=8;
            if h=0 then rez:=6;
        end;
     if x=3 then
       begin
            h:=y mod 4;
            if h=1 then rez:=3;
            if h=2 then rez:=9;
            if h=3 then rez:=7;
            if h=0 then rez:=1;
        end;
     if x=4 then
       begin
            h:=y mod 2;
            if h=1 then rez:=4;
            if h=0 then rez:=6;
        end;
     if x=5 then rez:=5;
     if x=6 then rez:=6;
     if x=7 then
       begin
            h:=y mod 4;
            if h=1 then rez:=7;
            if h=2 then rez:=9;
            if h=3 then rez:=3;
            if h=4 then rez:=1;
        end;
     if x=8 then
       begin
           h:=y mod 4;
           if h=1 then rez:=8;
           if h=2 then rez:=4;
           if h=3 then rez:=2;
           if h=0 then rez:=6;
        end;
     if x=9 then
       begin
            h:=y mod 2;
            if h=1 then rez:=9;
            if h=0 then rez:=1;
        end;
     rez2:=rez;
end;

begin
     assign(f,'cifra.out');
     rewrite(f);
     close(f);
     assign(f,'cifra.in');
     reset(f);
     readln(f,m);
     j:=0;
     while j<m do
          begin
               readln(f,n);
               inc(j);
               suma:=0;
               for i:=1 to n do
                  suma:=(suma+rez2(i)) mod 10;
               assign(g,'cifra.out');
               append(g);
               writeln(g,suma mod 10);
               close(g);
           end;
    close(f);
end.

[edited by svalentin] foloseste [*code*][*/code*] (fara *) pentru a formata o sursa corect

[•Twister]

vezi ca     1 ≤ N < 10^100 ; la tine e declarat ca fiind longint;
desi nu m-am uitat pe toata sursa ta cred ca asta ar fi problema

[•danny]

Mersi. M-am prins eu am crezut ca T<10^100

[•vially]

Va rog frumos spuneti-mi si mie de ce iau o puncte pe aceasta problema:
PPPPPPPPLLLLLLLSSSSSSSSSS

Cod:

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <string.h>
using namespace std;
int funct(int a)
{
if(a==4)
    return 6;
else if(a==8)
{
    if(a%4==0)
    return 6;
    else return 4;
}
else if(a==2)
{
    if(a%4==0)
    return 6;
    else return 4;
}
else if(a==3)
{
    if(a%4==1)
    return 3;
    else return 7;
}
else if(a==7)
{
    if(a%4==1)
    return 7;
    else return 9;
}
else return a;
}
int main()
{
  ifstream fin("cifra.in");
  ofstream fout("cifra.out");
  int t,x,sum,i;
  char n[100],u[2];
  fin>>t;
  for(t;t>0;t--)
  {
  fin>>n;
  if(strlen(n)>=2)
  {
  u[0]=n[strlen(n)-2];
  u[1]=n[strlen(n)-1];
  }
  else u[0]=n[strlen(n)-1];
  if(u[0]=='0')
  {
  u[0]=u[1];
  u[1]='\0';
  }
  x=atoi(u);
  sum=(x/20)*4;
  x=x%20;
  for(i=1;i<=x;i++)
  {
  sum=(sum+funct(i))%10;
  }
  fout<<sum<<endl;
  }
  return 0;
}

[edited by svalentin] foloseste [*code*][*/code*] (fara *) pentru a formata o sursa corect

[•cavendish]

cel mai mut imi place partea asta:

if(a==8)

Dar serios, de ce nu folosesti un vector cu raspunsul pt 0->99, n-ar fi greu de generat si programul ar deveni mai simplu. Nu te prea pot ajuta fiindca eu am folosit precomputare si nu ifuri.

[•Cosmin]

Folositi marcatorul code cand dati paste la cod, ca altfel se duce dracului indentarea codului si nu se mai intelege nimic.

[•cavendish]

M-am jucat un pic cu sursa ta, sa generez valorile pt 0->99, ca dc merge bine pt alea merge bine pt toate. Interesant ca pt 60 obtin 12 sau ceva de genu asta. nici asa valorile programului tau nu-s la fel cu ale mele. Pana la 6 is la fel, la 7 ii 2, nu 8, pana la 14 nu-s la fel, la 14 is. Mai verifica manual si vezi ce cazuri iti scapa.

[•vially]

Merci pentru ajutor. O sa mai verific odata sa vad ce imi scapa.

[•stifmeister]

Am rezolvat problema asta in 2 moduri.

I. Am folosit, ma rog, relatii matematice acolo.... si am facut un algoritm cat de cat eficient pentru care am luat 90 de puncte.

II. Am observat ca pot sa preprocesez solutiile si sa le pun intr-o matrice de 10x10.
    Programul meu arata cam in felul urmator:

deschide fisiere

pentru i = 1 la T
   citeste o valoare
   afiseaza a[penultimacifra][ultimacifra].
sfarsit pentru

inchide fisierele


Cu toate ca al doilea program avea 10 randuri si face de cel putin vreo 10 ori mai putine operatii, am obtinut 80 de puncte. ( timpul de executie a fost depasit pentru ultimele teste).

Am tot auzit de "linia de cache" peste tot pe forum si vreau sa stiu daca asta este problema si in cazul meu. Si chiar daca nu este, vreau ceva informatii despre linia de cache si cum putem evita problemele legate de ea.

Va multumesc!!!

[u-92]

salut
am o intrebare legata de evaluatorul acestei probleme.. sigur e ok? am verificat sursa de multe ori si am verificat pt niste valori cu cineva care a luat 100 puncte si obtineam acelasi rezultat. (iau WA la toate testele.. hmm.. sau poate este un caz particular? nu cred..)

[•bogdan2412]

Incearca sa faci un brute force si compara ce da brute forceu si ce face programu tau pt 1 2 3 ...
Oricum acum am si eu o prob: am trimis exact aceeasi sursa pe care luasem 100 pct si acum iau numai 90 pct... Care e problema? :cry:
....
Ok s-a rezolvat...

[u-92]

am descoperit bugul
n-are nimic evaluatorul..

[•flo_demon]

Poi... pt. cine inca nu s-a apucat de problema... cateva hint-uri
asa de ajutor(e voie?)

1. numai ultimele 2 cifre
2. formula
3. 2 siruri constante - sume partiale
4. (((n % 10) * 10) + 2) % 4 -> 0 sau 2

si gata.. spor la treaba....

Am facut prima data prob si era la conditizie if (n % 4)...si luam 0 nu
jtiam ce greseam...si am lasao balta o vreme, daca avetzi acelasi algoritm
si nu stitzi unde atzi gresit....few...sper ca  scapatzi de o zi cu migrene

[•dausyana]

dc numai ultimele 2 cifre??...dc nu merge numai ultima cifra??...

[•cristy]

fa pentru numere mici...adica...fa un program care sa iti calculeze toate rezultatele pt n=1 pana la n=25 sa zicem...si o sa descoperi de ce numai ultimele 2 conteaza...

[•wefgef]

dc numai ultimele 2 cifre??...dc nu merge numai ultima cifra??...

ptr k restul unui numar la 4 este egal cu restul numarului format din ultimele doua cifre la 4.

does anybody remember laughter?(

led zeppelin - the song remains the same (filmul - cd2) - stairway to heaven?

[•dausyana]

aha, acum pricep.....mc wefgef...

ps: dap "Does anybody remember laughter?" este din The Song Remains the Same-filmul , Led Zeppelin...

[•greco]

E din concert... ca or fi facut si un film cu el... asta-i altceva.  

[•dausyana]

ma rog..concert...