Błąd NZEC przy zadaniu PA05_POT ze SPOJa.

0

Cześć. Ostatnio w wolnych chwilach rozwiązuje sobie łatwe zadania ze SPOJa i natrafiłem na problem z zadaniem: http://pl.spoj.com/problems/PA05_POT/ - jeżeli wykonam taki kod, to wiadomo rozwiązanie przekroczy czas wykonania:

program pa05_pot;

{$MODE DELPHI}

uses
  SysUtils;

function Potega(Podst, Wykl : Integer) : Longint;
var
  I, Res : Longint;
begin
  Res := 1;
  for i := 1 to Wykl do
    Res := Res * Podst;
  Result := Res;
end;

var
  S : string;
  P, W, N, X : integer;
begin
  Readln(N);
  while N > 0 do
  begin
    Readln(S);
    X := Pos(' ', S);
    P := StrToInt(Copy(S, 1, X - 1));
    W := StrToInt(Copy(S, X + 1, 10));
    S := IntToStr(Potega(P, W));
    Writeln(Copy(S, Length(S), 1));
    N := N - 1;
  end;
end.

Dla takiego kodu zaś jak poniżej mam NZEC. Stąd pytanie jak można to rozwiązać. Noga jestem z matmy jak wiecie, ale myślałem że skoro ludzie postują na forach rozwiązania w C++ gdzie używają funkcji Pow, to chyba nic szybszego od takiej funkcji tutaj zastosować nie można. To jak zrobić to zadanie w FPC. Bo to taka durna błahostka wydaje się, a utknąłem niestety. Z góry dziękuję za podpowiedzi.

program pa05_pot;

{$MODE DELPHI}

uses
  Math, SysUtils;

function MyPower(P, W : integer) : integer;
begin
  Result := Round(Power(P, W));
end;

var
  S : string;
  P, W, N, X : integer;
begin
  Readln(N);
  while N > 0 do
  begin
    Readln(S);
    X := Pos(' ', S);
    P := StrToInt(Copy(S, 1, X - 1));
    W := StrToInt(Copy(S, X + 1, 10));
    S := IntToStr(MyPower(P, W));
    Writeln(Copy(S, Length(S), 1));
    N := N - 1;
  end;
end.
0

Teoretycznie powinno być coś na kształt tego:

{$MODE DELPHI}
 uses SysUtils;
 
var A,B,V,N:Cardinal;
begin
  ReadLn(N);
  while N>0 do
  begin
    Readln(A,B);
    A:=(A)mod(10); // tego brakowało mu do szczęścia
    V:=1;
    while B>0 do
    begin
      if ((B)and(1))<>0 then V:=(V*A)mod(10);
      A:=(A*A)mod(10);
      B:=(B)shr(1);
    end;
    WriteLn(V);
    Dec(N);
  end;
end.

ale nie wiedzieć czemu pisze że niepoprawna odpowiedź.

4

No to mój potworek:

program PA05_POT;
var
  IloscPrzypadkow,
  i                : Integer;
  a, b             : LongInt;

begin
  Readln(IloscPrzypadkow);
  for i := 1 to IloscPrzypadkow do
  begin
    readln(a,b);

    if (a mod 10 = 0) or (a mod 10 = 1) or (a mod 10 = 5) or (a mod 10 = 6) then Writeln(a mod 10)

    else if (a mod 10 = 4) and (b mod 2 = 0) then Writeln('6')
    else if (a mod 10 = 4) and (b mod 2 = 1) then Writeln('4')

    else if (a mod 10 = 9) and (b mod 2 = 0) then Writeln('1')
    else if (a mod 10 = 9) and (b mod 2 = 1) then Writeln('9')

    else if (a mod 10 = 2) and (b mod 4 = 1) then Writeln('2')
    else if (a mod 10 = 2) and (b mod 4 = 2) then Writeln('4')
    else if (a mod 10 = 2) and (b mod 4 = 3) then Writeln('8')
    else if (a mod 10 = 2) and (b mod 4 = 4) then Writeln('6')

    else if (a mod 10 = 3) and (b mod 4 = 1) then Writeln('3')
    else if (a mod 10 = 3) and (b mod 4 = 2) then Writeln('9')
    else if (a mod 10 = 3) and (b mod 4 = 3) then Writeln('7')
    else if (a mod 10 = 3) and (b mod 4 = 4) then Writeln('1')

    else if (a mod 10 = 7) and (b mod 4 = 1) then Writeln('7')
    else if (a mod 10 = 7) and (b mod 4 = 2) then Writeln('9')
    else if (a mod 10 = 7) and (b mod 4 = 3) then Writeln('3')
    else if (a mod 10 = 7) and (b mod 4 = 4) then Writeln('1')

    else if (a mod 10 = 8) and (b mod 4 = 1) then Writeln('8')
    else if (a mod 10 = 8) and (b mod 4 = 2) then Writeln('4')
    else if (a mod 10 = 8) and (b mod 4 = 3) then Writeln('2')
    else if (a mod 10 = 8) and (b mod 4 = 4) then Writeln('6')
  end;
end.

Zaakceptowano
Czas: 0.0

3

@babubabu, pomysł genialny, zaś realizacja pomysłu bardzo słaba, patrz:

const str:String='0161656161012345678901496569410187456329';
var A,B,N:Cardinal;
begin
  ReadLn(N);
  while N>0 do
  begin
    Readln(A,B);
    WriteLn(str[10*(B mod 4)+(A mod 10)+1]);
    Dec(N);
  end;
end.
0

Dziękuję @_13th_Dragon. Rozwiązanie idealne, w życiu bym na nie sam nie wpadł. Ponieważ jestem mózg niematematyczny i nie potrafię tak kombinować. Muszę z tym żyć ;) Zresztą jak googlowałęm na necie to widziałłem rozwiązanie tego zadania w C++ gdzie ktoś używał sobie chyba zmiennych o nazwie Major i Minor i kombinował coś na wzór drabinki if'ów jak @babubabu, ale coś i tak nie było do końca dobrze. Bo podany kod się w jego wydaniu nie kompilował.

A przy okazji żeby nie zakładać nowego wątku. Można prosić jakąś podpowiedź - naprowadzenie na rozwiązanie zadania: http://pl.spoj.com/problems/PRZEDSZK/ - aż mi głupio, ale nie mogę nic wymyśleć. Zrobiłem kod - potworka operującego na tablicach, ktory podaje liczby dla ktorych reszty z dzielenie to zero. I działa na przykładowym zestawie, ale już jak wpisałem ilość dzieci odpowiednio 5 i 32, to zwrócił zero - domyślną wartość funkcji i przez to za pewne nie przechodzi. A na pewno rozwiązanie jest banalne, tylko przez swój humanistyczny umysł ciężej mi na to wpaść. Chyba po to na studiach informatycznych, których nie mam tłucze się ludziom matme do łbów i torturują nią ich, chyba po to żeby ogarniali takie zadania pod kątem SPOJa ;)

1

I działa na przykładowym zestawie, ale już jak wpisałem ilość dzieci odpowiednio 5 i 32, to zwrócił zero

Błędne dane zestawu, ponieważ:

W pierwszym i jedynym wierszu zestawu danych znajdują się dwie liczby całkowite a i b (10<=a,b<=30)

czyli grupy muszą mieć minimum 10 osób, ale nie więcej niż 30;

A na pewno rozwiązanie jest banalne, tylko przez swój humanistyczny umysł ciężej mi na to wpaść.

Na moje zezowate oko - po wczytaniu zestawu (dwóch liczb z jednej linii) szybciej będzie wyliczyć NWW, skoro Pani Agnieszka musi rozdać wszystkie cukierki;

Spróbuj tego, na pewno będzie szybsze niż tablice (nie używaj ich, rób to w locie po linijce) i reszta z dzielenia;


EDIT:

Zarejestrowałem się z ciekawości i wypróbowałem takiego leniwego dziada - działa elegancko:

program Project1;

{$APPTYPE CONSOLE}

  function CalcCandyAmount(AFirstGroup, ASecondGroup: Cardinal): Cardinal;
  var
    intFirstGroup, intSecondGroup: Cardinal;
  begin
    intFirstGroup := AFirstGroup;
    intSecondGroup := ASecondGroup;

    while intFirstGroup <> intSecondGroup do
      if intFirstGroup > intSecondGroup then
        Inc(intSecondGroup, ASecondGroup)
      else
        Inc(intFirstGroup, AFirstGroup);

    CalcCandyAmount := intFirstGroup;
  end;

var
  intSetsCnt, intFirstGroup, intSecondGroup, I: Integer;
begin
  ReadLn(intSetsCnt);

  for I := 1 to intSetsCnt do
  begin
    Read(intFirstGroup);
    Read(intSecondGroup);
    WriteLn(CalcCandyAmount(intFirstGroup, intSecondGroup));
  end;
end.
Czas wykonania Wykorzystana pamięć
0.00 232k
Ale że mają FPC 2.6.0 to już wstyd - dwa razy kompilacja przerwana, bo Error: Identifier not found "Result" we funkcji... Pierwszy raz wrzucałem coś na SPOJa, więc nie wiedziałem dokładnie jak powinien program wyglądać (chodzi o ramy).
1

Moja propozycja:

program PRZEDSZK;
var
  a, b, NWD, NWW, n, i , j, tmpNr, tmpA, tmpB : LongInt;

begin
  Readln(n);
  for i := 1 to n do
  begin
    Readln(a,b);
    tmpA := a;
    tmpB := b;
    repeat
      if a < b then
      begin
        tmpNr := a;
        a := b;
        b := tmpNr;
      end;
      a := a mod b;
    until a mod b = 0;
    NWD := b;
    b := tmpB;
    a := tmpA;
    NWW := (a * b) div NWD;
    Writeln(NWW);
  end;
end.

pewnie @furious programming lepszą dowalił ale moja działa.

Rezultat: ZAAKCEPTOWANO
Czas: 0.00
MEM: 232k

poprawienie znaczników <code class="delphi"> - fp

0

Dziękuję @furious programming: proste, acz geniealne. Sposób bardziej dla mnie przejrzysty, niż "mod'zenie" ;) Ale każdy zatwierdzony jest dobry. I fakt mają tam badzo stare FPC, co nie zmienia faktu, że należy pamiętać o magicznym {$MODE DELPHI} na początku. Jeśli mamy zamiar używać rzutowań czy Result i pewnie jeszcze innych rzeczy, który domyślnie FPC wcale nie rozpoznaje. Akurat to dla mnie nie stanowi problemu. Jednak według mnie - jeśli była by taka możliwość - to powinni zaktualizować FPC do możliwie najnowszego. Poza tym niestety sprawdzanie i kompilacja kodów trwa tam według mnie za długo.

0

Proste, ale nieoptymalne... Na szybko takiego dziada wymyśliłem, ale można zrobić to szybciej, skoro swoim rozwiązaniem zamykam stawkę;

Zmodyfikowałem kod do prostszej wersji:

program CNDS;
var
  C, F, S, FF, SS, I: Integer;
begin
  ReadLn(C);

  for I := 1 to C do
  begin
    Read(F);
    Read(S);

    FF := F;
    SS := S;

    while FF <> SS do
      if FF > SS then
        Inc(SS, S)
      else
        Inc(FF, F);

    WriteLn(FF);
  end;
end.

czyli pozbyłem się funkcji i skróciłem identyfikatory, ale niewiele to pomogło (moje NWW jest po prostu powolne); Trzeba inaczej kombinować jeśli chce się być wysoko w rankingu; Może chociaż okaże się najkrótsze - nie wiem :]

Jednak według mnie - jeśli była by taka możliwość - to powinni zaktualizować FPC do możliwie najnowszego. poza tym niestety sprawdzanie i kompilacja kodów trwa tam według mnie za długo.

Nie dziw się:

<quote>Your submission will be judged on the Pyramid Cluster (Intel Pentium III 733 MHz)</Quote>
:D

0

Tak można jeszcze spróbować odnośnie największego wspólnego dzielnika.

var a,b,k,r : longword;

begin
  readln(a,b);
  if (a = 0) or (b = 0) then writeln(a or b)
  else
  begin
    k := 0;
    while ((a or b) and 1) = 0 do
    begin
      a := a shr 1;
      b := b shr 1;
      inc(k);
    end;
    repeat
      if a = 0 then
      begin
        a := b;
        break;
      end;
      while (a and 1) = 0 do 
        a := a shr 1;
      while (b and 1) = 0 do 
        b := b shr 1;
      if a < b then
      begin
        r := (b - a) shr 1;
        b := a;
        a := r;
      end
      else 
        a := (a - b) shr 1;
    until b = 0;
    if k > 0 then 
      a := a shl k;
    writeln(a);
  end;
end.
0

Ależ lubicie kombinować i utrudniać sobie życie !!

var N,A,B,V,R:Integer;
begin
  ReadLn(N);
  while N>0 do
  begin
    ReadLn(A,B);
    V:=A*B;
    while B>0 do
    begin
      R:=(A)mod(B);
      A:=B;
      B:=R;
    end;
    WriteLn((V)div(A));
    Dec(N);
  end;
end.

1 użytkowników online, w tym zalogowanych: 0, gości: 1