Problemset 4

[Adrian_Kosowski]

Problemset 4 is now over. You are most welcome to post any remarks or questions concerning the problems, as well as short descriptions of your accepted solutions.

If you would like to share your CTQUINE Christmas trees, please alter a few random characters of the tree before publishing (so as not to spoil the fun for those solving the problem in the SPOJ problemset ). A small growing gallery would really be fun.

[sparr0]

I, for one, would dearly love to see any of the C(++) christmas trees, even a very large one.

[Simon_Gog]

Problem: SANTA

I solved the problem with several ideas. My first approach was to cluster
the homes of the children with a quadtree and remove greedily the regions where the amount of space required for the presents are smaller equal than S.
This results in a score of 280.
Then i tried to improved the tour lenght of the clusters with the TSP heuristic
of Christophides. I haven't tried 2-opt cause of O(n^2) complexity.
I also tried to cluster the children with a knapsack heuristic and then construct tours with Chritophides algorithm. But even a combination of this approaches lead to only 288 points.
I'm curious about approaches that lead to scores greater than 350 points.

[Egor_Kulikov]

Problem: SANTA
I'm curious about approaches that lead to scores greater than 350 points.

At first we need to sort vertices in some way (by x coordinate or by dist from the start)
Then we find from current vertice most closer vertice from the next 500
After all we try to transposit all consiqutive pairs

[Simon_Gog]

Hello sparr0,

this is my very large C christmas tree. It's not a beauty and i've shorten and altered the code by 4 lines.

     ;
     ;
    ;;;
     ;
    ;;;
   ;;;;;
     ;
    ;;;
   ;;;;;
f="%c%s%c,";
#define _ printf
char*x[]={
"     ;",
"     ;",
"    ;;;",
"     ;",
"    ;;;",
"   happy",
"     ;",
"    ;;;",
"   ;xmas",
"f=%c%s%c;",
"#define _ printf",
"char*x[]={",
"},z=0;main(){int n;",
"for(n=0;n<9;n++)puts(x[n]);",
"_(x[9],34,f,34);puts(&z);",
"puts(x[10]);puts(x[11]);",
"for(n=12;n<20;n++)",
"puts(x[n]);exit(42);}",
},z=0;main(){int n;
for(n=0;n<9;n++)puts(x[n]);
_(x[9],34,f,34);puts(&z);
puts(x[10]);puts(x[11]);
for(n=12;n<20;n++)
puts(x[n]);exit(0);}

[overwise]

Changed some variable occurences (exchanging one letter with an other). It probably would not be too hard to restore the original solution, but who would want to cheat?

          i
          ,
         u,_
          [
         999
        ],m,f
          ,
         q;;
        main(
       ){char*
          w
         =_,
        *c=r(
       );for(i
      --;;){for
          (
         ;(u
        =*c++
       )==32;)
      ;for(i++;
     i>2*w-f;i=2
          )
         {if
        (f)*f
       ++=92;*
      w++=10;if
     (i++==q)i=1
    ,q++;for(j=12
          -
         +i;
        --j;)
       *f++=32
      ;}if(!f&&
     u==63)c=r()
    ,f=1,u=34;if(
   f&!u){*w++=34;*
          w
         ++=
        59;*w
       ++=125;
      puts(_+0)
     ;return-0;}
    *w++=u;}}r(){
   return"i,u,_[9\
  99],j,f,q;;main(\
          \
         ){\
        char\
       *f=_,*\
      t=r();fo\
     r(w--;;){f\
    or(;(i=*c++)\
   ==32;);for(i++\
  ;f>2*j-f;i=2){if\
 (f)*w++=92;*w++=10\
          \
         ;i\
        f(w+\
       +==q)i\
      =1,p++;f\
     or(j=12-+i\
    ;--i;)*h++=3\
   2;}if(!f&&u==6\
  3)c=r(),f=1,g=34\
 ;if(f&!u){*w++=34;\
*w++=59;*e++=125;put\
          \
         s(\
        _+0)\
       ;retur\
      n-0;}*e+\
     +=u;}}r(){\
    return?;};";}

[/code]

[overwise]

And some BF. Changed only two characters, but that should be hard enough to find... eg

                    -
                    >
                   >++
                    +
                   >>+
                  +>>+>
                    >
                   +>>
                  +++>>
                 ++>>>>+
                    +
                   >>+
                  ++>>>
                 >>>+++>
                >>>>>>>>>
                    >
                   >>>
                  >>>>>
                 >>>>>>>
                >>>>>>>>>
               >>>>>>>+++>
                    >
                   ++>
                  >>>++
                 +>>+++>
                >>>+++>>+
               +>>+>>+>>+>
              >+>>+>>+>>+>>
                    +
                   >>+
                  >>+>>
                 +>>+>>+
                >>+>>+>>+
               >>>>>>+>>+>
              >+>>+>>+>>+>>
             +>>+>>+>>+>>+++
                    >
                   >++
                  >>>>+
                 +>>+>>+
                ++>>+>>++
               +>>+>>+++>>
              +>>+++>>>>>>+
             >>+>>+>>+>>+>>+
            >>+>>+>>+++>>>>+>
                    >
                   +++
                  >>>>+
                 +>>+>>+
                ++>>+++>>
               ++>>>>++>>+
              >>+++>>+>>+++
             >>+>>+++>>+>>++
            +>>>>>>+>>+>>+>>+
           >>+>>+>>+>>+>>+++>>
                    >
                   >+>
                  >+++>
                 >+>>+++
                >>+>>+++>
               >+++>>++>>>
              >++>>+>>+++>>
             +>>+++>>+>>+++>
            >+>>+++>>>>>>+>>+
           >>+>>+>>+>>+>>+>>+>
          >+++>>>>+>>+++>>+>>++
                    +
                   >>+
                  ++>>+
                 +>>>>++
                >>+>>+++>
               >+>>+++>>+>
              >+++>>+>>+++>
             >>>>>+>>+>>+>>+
            >>+>>+>>+>>+>>+++
           >>>>+>>+++>>+>>+++>
          >+++>>++>>>>++>>+>>++
         +>>+>>+++>>+>>+++>>+>>+
                    +
                   +>>
                  >>>>+
                 >>+>>+>
                >+>>+>>+>
               >+>>+>>+++>
              >>>+>>+++>>++
             +>>++>>>>++>>++
            +>>>>>>+++>>>>>>>
           >>>>>>>>>>>>>>>>>>>
          >>>>>>>>>>>>>>>>>>>>>
         >>>>>>>>>>>>>>>>>>>>>>>
        >>>>>>>>>>>>>>>>>>>>>>>>>
                    >
                   >>>
                  >>>>>
                 >>+>>++
                +>>+>>+++
               >>+++>>++>>
              +>>+>>+>>+>>>
             >>>>>>>>>>>>>>>
            >>>>>>>>>>>>>>>>>
           >>>>>>>>>>>>>>>>>>>
          >>>>>>>>>>>>+>>+++>>+
         >>+++>>>>++>>+++>>>>+>>
        +>>+>>+>>+>>+>>>>++>>+++>
       >>>+>>+>>+++>>++>>+>>+>>>>>
                    >
                   +>>
                  +++>>
                 >>++>>+
                ++>>>>+>>
               +>>+++>>++>
              >+>>+++>>+>>+
             ++>>>>>>+>>+>>>
            >>>+>>+>>>>++>>++
           +>>>>+>>+>>+++>>++>
          >>>++>>+++>>>>+>>+>>+
         >>+>>+++>>++>>+>>+++>>>
        >>>+>>+>>>>++>>+++>>>>+>>
       +++>>+++>>++>>>>++>>+>>+>>>
      >>>+>>+++>>+>>+++>>>>+++>>+>>
                    +
                   >>+
                  ++>>>
                 >+>>+++
                >>>>>>>>>
               >>>>>>>>>>>
              >>>>>>>>>>>>>
             >>>>>>>>>>>>>>>
            >>>>>>>>>>>>>>>>>
           >>>>>>>>>>>>>>>>>>>
          >>>>>>>>>>>>>>>>>>>>>
         >>>>>>>>>>>>>>>>>>>>>>>
        >>+>>+>>+>>+>>+>>+>>+++>>
       ++>>+>>+++>>+>>+++>>>>>>>>>
      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
     >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
                    >
                   >>>
                  >>>>>
                 >>>>+++
                >>++>>>>+
               +>>+++>>>>>
              >>>+>>+++>>+>
             >+++>>>>>>+++>>
            ++>>>>++>>+++>>>>
           +>>+>>+>>+>>+>>+>>+
          >>+>>+>>+>>+>>+>>>>>>
         +++>>++>>+>>+>>>>>>+>>+
        ++>>>>++>>+++>>>>+>>+>>++
       +>>++>>+>>+++>>+>>+++>>>>>>
      +>>+>>>>>>+>>+>>>>++>>+++>>>>
     >>>>+>>+++>>>>++>>+++>>>>+>>+++
    >>+++>>++>>+>>+>>+>>+>>+++>>>>>>+
                    +
                   >>+
                  >>+++
                 >>+>>++
                +>>+>>+++
               >>>>++>>+>>
              +++>>+>>+++>>
             >>>>>>>>+>>+++>
            >+>>+++>>+>>+++>>
           +++>>>>+>>+>>+>>+>>
          +>>+>>+>>+>>+>>+>>+>>
         +>>+>>+>>+>>+>>+>>+>>+>
        >+>>+>>+++>>>>>>+>>+++>>>
       >>>+>>+++>>+>>+++>>+>>+++>>
      >>>>+>>+++>>+>>+++>>+>>+++>>+
     >>+++>>+>>+++>>>>>>>>>>>>>>+>>+
    ++>>+>>+++>>>>>>+>>+++>>+>>+++>>>
   >>>>>>>>>>>>>>>+>>+++>>+>>+++>>>>>>
                    >
                   >>>
                  +>>++
                 +>>+>>+
                ++>>>>>>>
               >>>>>>>>>>>
              +>>+++>>+>>++
             +>>>>>>>>>>+++>
            >++>>+>>+++>>+>>+
           ++>>+++>>>>+>>+++>>
          +>>+++>>+++>>++>>>>>>
         +>>+>>+++>>++>>+>>+>>+>
        >+>>>>++>>+++>>>>+>>+>>++
       +>>++>>>>++>>+>>+++>>>>>>+>
      >+++>>>>>>+>>+++>>>>>>+>>+++>
     >>>>>+++>>++>>+>>+>>+>>+>>+>>+>
    >+>>+>>>>>>+>>+++>>+>>+++>>+>>+++
   >>+>>+++>>>>++>>+++>>>>+++>>>>+>>++
  +>>>>>>+>>+++>>>>>>>>>>>>>>>>>>+>>+++
                    >
                   >>>
                  >>+>>
                 +++>>>>
                >>>>>>+>>
               +++>>>>>>+>
              >+++>>>>>>>>>
             >>>>>>>>>+>>+++
            >>>>>>+>>+++>>>>>
           >>>>>+>>+++>>>>>>++
          +>>++>>+>>+>>+>>+>>+>
         >+>>+>>+>>+>>+>>+>>+>>+
        >>+>>+>>+>>+>>+>>>>>>+>>+
       ++>>+>>+++>>+>>+++>>+>>+++>
      >+>>+++>>+>>+++>>+>>+++>>+>>+
     ++>>+>>+++>>>>++>>+++>>>>+>>+>>
    +++>>++>>+>>+++>>+>>+++>>+>>+++>>
   >>>>+++>>++>>+>>+>>+>>+>>>>>>+>>+++
  >>+>>+++>>>>++>>+++>>>>+>>+>>+++>>>>+
 >>+++>>>>++>>+>>+++>>+>>+++>>+++>>++>>+
                    >
                   >+>
                  >>>>>
                 +>>+++>
                >>>++>>++
               +>>>>+>>+>>
              +++>>++>>+>>+
             ++>>>>>>+>>+>>+
            >>+>>>>>>+>>+++>>
           >>++>>+++>>>>+++>>>
          >>>>>+>>+>>+>>+>><<+[
         [->+<<+>]<[->+<]>>->[<[
        ->>+<<]+>>>]<[->>>>>>>>>+
       <<<<<<<<<]+>++>+>++++>+>++>
      +>++++>+>[[->>+>+<<<<]+>+>+>+
     >-]<[-<<]<+]>>[>>]++>>++++>>++>
    >++++>>+>>+++>>>>>+>>>+>+><<<<<<<
   <<<[>>>++>>->>>-[<<]>[->+[-<+<+>>]<
  [->+<]+<<<-<<[-]+>>+[-]++++++++++++++
 ++++++>>]<<<+++++++++++++++++++++++++++
+++++>[<.>>+<-]>[-<+>]<<[-]<[-<+<+>>]<[->
                    +
                   <]<
                  [-<<<
                 [->>+++
                +++++++++
               ++++<<]>>++
              +++++++++++++
             +++++++++++.[-]
            >[<<<<+>>>>-]>>[<
           <<<+>>>>-]>>[<<<<+>
          >>>-]>>>[<<<<+>>>>-]>
         ->[<<<<+>>>>-]<<<<<+<<<
        <<<<<][.]++++++++++.[-]<]

[adixt_sof]

Przyznam się, że jedynie zerknąłem na twój kod i mogłem coś przeoczyć / nie ogarnąć, ale oto jak ci podpowiem

1.Nie tablicuj rozwiązania. Tj działaj zasadą wczytujesz test, wypisujesz odpowiedź, wczytujesz, wypisujesz itp. Zauważ skoro korzystasz z ideone, że to kiedy twój program wypisuje odpowiedź nie ma wpływu na okienko, w którym pojawia się wyjście, podobnie spojowej sprawdzarce zwisa i powiewa, kiedy i czy w ogóle wczytałeś dane - byleś zrobił poprawny output i byle program szybko się skończył. Tablica zaś spowalnia program (przepisywanie jej) i zużywa niepotrzebnie pamięć.

2. Wczytywać , tworzyć tablice można także z doubli, czyli zamiast wczytać inta i zrobić doubla, który jest mu równy możesz po prostu wczytać doubla, a zamiast tworzyć inta, którego wypiszesz możesz zrobić to samo z doublem. Marnujesz w ten sposób czas i pamięć na dodatkowe zmienne.

3. Round() jest posrany(robi błędy). Polecam ogarnąć bibliotekę cstdio oraz scanf/printf. Z początku mogą wydawać się dzikie jednak jak się przyzwyczaisz to z czasem zauważysz (szczególnie na spoju), że są szybsze. Poza tym możesz za ich pomocą wypisywać double z poprawnym przybliżeniem. Wypisanie doubla o nazwie "spagetti" z przybliżeniem do trzech miejsc po przecinku będzie wyglądało tak :
printf("%.3lf", spagetti);

EDIT : spojrzałem na mój kod (zadania do końca nie pamiętałem, a sam kod pochodzi z czasów, gdy pisałem w iostreamie) i ja tam nic nie zaokrąglam. Taka ciekawostka.

EDIT 2: drobny cytat z treści : "Uwaga: Dane wejściowe będą tak dobrane, aby wynik był liczba całkowitą."

Bardzo wartościowa odpowiedź , skorzystałem z rad zmieniony kod na ideone działa na spoju cały czas źle...

EDIT: Dodam, że nie chodzi o za wolne działanie tylko "błędna odpowiedź".

[narbej]

Może dlatego, że cytując treść zadania::

Uwaga: Dane wejściowe będą tak dobrane, aby wynik był liczba całkowitą.

Jeżeli przekształciłbyś wzór, uniknąłbyś dzielenia 1.0/a i 1.0/b - zmiennopozycyjnego, a zostałoby samo dzielenie całkowite, plus jeszcze dwa inne działania.
Działania dostosowywane są automatycznie do typów zmiennych, ewentualnie do jedenj ze zmiennych, która ma większy zakres, więc jak masz 10/3=3 - dzielenie całkowitoliczbowe
a 10.0/3 ==== 10/3.0 ~= 3.3333...
1/40 = 0 i to powoduje error
1.0/40=0.025000000000000001 - ta jedynka na końcu to skutek dzielenia zmiennopozycjnego
10/(1/40)=10/0=error
10(1.0/40)=10/0.0250.....=400.0
PS
Jak umieszczasz kod programu w tagach bbone, to potem możesz i powinieneś zmienić:
[bbone=c,945][bbone=text] na [bbone=c][/bbone]

[marthasimons]

Bardzo cenna odpowiedź, spróbuję