Jump to content
pwseo

[Solved] Wrong Answer no "3n+1 problem" (UVA)

Recommended Posts

pwseo

Olá pessoal,

Estes dias deu-me para me registar no UVA e peguei no exercício para resolver, o 3n+1.

Fiz a submissão do seguinte código, mas dá-me Wrong Answer, apesar de já o ter testado com vários inputs... Que me estará a escapar?

program tnpo;

function cycle(n: longint): longint;
begin
   cycle := 1;
   while n > 1 do begin
      inc(cycle);
      if odd(n) then
         n := 3 * n + 1
      else
         n := n div 2;
   end;
end;

function max(a: array of longword): longword;
var
   i: integer;
begin
   max := 0;
   for i := 0 to pred(length(a)) do
      if a[i] > max then
         max := a[i];
end;

var
   i, j, k, l: longword;
   m, n: longword;
   r: array of longword;

begin
   while not eof do begin
      readln(i, j);
      l := abs(j - i) + 1;
      setlength(r, l);
      if i < j then begin
         m := i;
         n := j;
      end else begin
         m := j;
         n := i;
      end;
      for k := m to n do
         r[k - m] := cycle(k);
      writeln(i, ' ', j, ' ', max(r));
   end;
end.

Com este input:

1 10
100 200
201 210
900 1000
1000 900
999999 999990

recebo este output (que está correcto):

1 10 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259

Nota: Sim, fiz em Pascal. Não me apetecia fazer em C.. e pronto, há que variar.

Share this post


Link to post
Share on other sites
thoga31

Não sei como funciona o tester do UVA, mas experimenta declarar as variáveis antes das funções. Nunca se sabe... :P


Knowledge is free!

Share this post


Link to post
Share on other sites
pwseo

O problema não é esse, pois ele compila correctamente o programa... E aqui também compila e corre como detalhei acima, por isso não percebo qual é o erro...

Share this post


Link to post
Share on other sites
thoga31

Mistério. Não faço a mais pequena ideia de qual seja o problema. Não vejo falhas, já testei com "tudo e todos", e tudo deu certo... :huh:


Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

Nao sei responder ... mas faco-te umas perguntas extra :P

Podes fazer um setlength com um milhao de longwords?

Dentro do ciclo nao devias gerir a memoria?

O max® funciona para "arrays" redimensioandos?


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pwseo

pmg, eu tinha testado com inputs extremamente grandes (de 1000000) mas agora apercebo-me que pode ter havido algum overflow wrap-around. Vou investigar após o jantar e dps acrescento info.

obgd pela sugestão.

PS.: aquele setlength podia muito bem ser repensado, de facto.

Share this post


Link to post
Share on other sites
pwseo

Afinal os problemas relacionavam-se com o tipo de inteiros que estava a utilizar.

Na função cycle é preciso um inteiro de 64bits, e na função max a variável i tem que ser longword, claro...

Aproveitei e fiz memoization de alguns resultados da cycle, para execução mais rápida, e optimizei também algumas partes da cycle.

program solution;

function cycle(n: qword; var lookup: array of integer): integer;
begin
  if (n < 1000000) and (lookup[pred(n)] <> 0) then
    cycle := lookup[pred(n)]
  else begin
    if odd(n) then
      cycle := 2 + cycle((3 * n + 1) shr 1, lookup)
    else
      cycle := 1 + cycle(n shr 1, lookup);
    
    if (n < 1000000) then
      lookup[pred(n)] := cycle;
  end;
end;

function max(a: array of integer; b, e: longword): integer;
var
  i: longword;
begin
  max := 0;
  for i := pred(b) to pred(e) do
    if a[i] > max then
      max := a[i];
end;

var
  i, j, k, m, n: longword;
  lookup: array [0..999999] of integer;

begin
  lookup[0] := 1;
  while not eof do begin
    readln(i, j);
    if i < j then begin
      m := i;
      n := j;
    end else begin
      m := j;
      n := i;
    end;
    for k := m to n do
      cycle(k, lookup);
    writeln(i, ' ', j, ' ', max(lookup, m, n));
  end;
end.

Share this post


Link to post
Share on other sites
mogers

se pretenderes aprender algoritmos e estruturas de dados, resolvendo uns problemas, recomendo vivamente a usaco - http://train.usaco.org

tem textos a explicar os algoritmos e dp problemas sobre os temas


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
pwseo

se pretenderes aprender algoritmos e estruturas de dados, resolvendo uns problemas, recomendo vivamente a usaco - http://train.usaco.org

tem textos a explicar os algoritmos e dp problemas sobre os temas

Pois, também me inscrevi lá e estou a ir para a secção 1.2, mas o site tem estado off nos últimos dias :\

Foi por isso que fui ao UVA :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.