wpc113

Shade Of Mine

Was haben die sich denn dabei gedacht? Oder gibt es da tatsächlich einen Trick?

ein

if(sum<0) { sum=-sum; sign=1; }
if(sum >= 1000) return 4 + sign;
else if(sum >= 100) return 3 + sign;
else if(sum >= 10) return 2 + sign;
else return 1 + sign;

fällt doch unter lookup, oder?
Zumindest wurden schon Leute wegen sowas disqualifiziert.

Irgendwie vewirrt mich das wpc - egal wieviel ich nachdenke, ich komme nur auf 1 Lösung. Oder habe ich ein riesen Brett vorm Kopf??

http://www.geocities.com/acmesofties/wpcq.htm

volkard

lol.

Geo

Und der Virus ist immernoch auf der WPC-Seite.

ERROR

int wpc113(int *arr, int n)
{
  int sum= 0;

  for (--n; n>-1;--n)
    sum+= arr[n];

  return (sum<0)+((sum%1000==sum)?
    ((sum%100==sum)?
    ((sum%10==sum)? 1:2) :3) :4);
}

nicht großartig anders ...

SideWinder

Berechnen lässt sich die Zahl auch ohne if, allerdings müsst ihr dann (je nach dem wie ihr programmiert) eine oder zwei Funktionen aus der math.h nachprogrammieren.

Ist wahrscheinlich weit nicht so schlecht, aber wenn diese Methode verboten sein soll.

MfG SideWinder

Shade Of Mine

btw:

statt

for (--n; n>-1;--n)
    sum+= arr[n];

kann man auch

while(n--)
  sum+=arr[n];

schreiben.

Das finde ich einfacher zu verstehen...

ERROR

"wenn ich mich nicht ganz täusche fehlt dann aber noch was ... es gibt kein arr[10] ;-)"
EDIT: arg habe was übersehen ... stimmt schon!
wird ja erst geguckt was n ist und dann decrementiert *kopfschüttel*
bin echt total raus .. (wenn ich jemals drin war

edit: ej kann heut echt nicht schreiben ...

ps: deine ist viel schneller als meine!
der %-operator braucht viel zu viel zeit!

EDIT: im durchschnitt sollte dies hier schneller sein als deins(weniger vergleiche max. 2 = min. 2 für das zählen)!!
steht den varianten von dir gegen über:
min. 1
vielleicht 2
max. 3

if(sum<0) { sum=-sum; sign=1; }

  if(sum < 100)
  {
    if(sum <10) return 1 + sign;
    else return 2 + sign;
  }
  else
  {
    if(sum<1000) return 3 + sign;
    else return 4 + sign;
  }

oder??

cu

volkard

ERROR schrieb:

EDIT: im durchschnitt sollte dies hier schneller sein als deins(weniger vergleiche max. 2 = min. 2 für das zählen)!!

fast alle zahlen liegen über 1000. nur dieser fall ist zu optimieren, würde ich sagen.

Geo

Wohl eher so:

if(sum>0) {

    if(sum < 100) 
    { 
      if(sum <10) return 1; 
      else return 2; 
    } 
    else 
    { 
      if(sum<1000) return 3; 
      else return 4; 
    }
  }
  else
  {
    if(sum > -100) 
    { 
      if(sum > -10) return 2; 
      else return 3; 
    } 
    else 
    { 
      if(sum > -1000) return 4; 
      else return 5; 
    }
  }

(die elses kann man natürlich weglassen, ist aber so übersichtlicher)

stahl

ihr wisst aber immernoch nicht ob eure varianten "legal" sind, oder?

Please ensure that your code does not handle more than 10 input cases by table lookup or such techniques.

ganz 10 fälle wären es ja nicht.. aber ne ähnliche technik vielleicht, hms..

int wpc113(int *arr, int n)
{
  int sum = 0;
  int c = 0;

  while(n--)
    sum += *arr++;

  if (sum < 0) {
    sum = -sum;
    c = 1;
  }

  do {
    sum /= 10;
    c++;
  } while (sum);

  return c;
}

ich würds sonst so machen
alerdings is das doch deutlich langsamer

Christoph

volkard schrieb:

fast alle zahlen liegen über 1000. nur dieser fall ist zu optimieren, würde ich sagen.

Wie kommst du darauf?
Im Array stehen Zufallszahlen von -MAX_INT bis +MAX_INT. IMHO ist es zwar wahrscheinlicher, dass der Betrag der Summe über 1000 liegt ist als unter 1000. Allerdings bei weitem nicht so wahrscheinlich, dass man von "fast allen zahlen" sprechen kann.

SideWinder

Anzahl der Zahlen zwischen

1000 und 3000 = 2001
100 und 999 = 1000
10 und 99 = 100
0 und 9 = 10

Das heißt die Chance, dass eine Zahl über 1000 ist, ist immerhin 2001:1110 = 1,8:1

Wenn das kein ausschlagkräftiges Argument ist die Funktion für Zahlen über 1000 zu optimieren was dann?

MfG SideWinder

Christoph

cd9000 schrieb:

IMHO ist es zwar wahrscheinlicher, dass der Betrag der Summe über 1000 liegt ist als unter 1000. Allerdings bei weitem nicht so wahrscheinlich, dass man von "fast allen zahlen" sprechen kann.

~2:1 fällt nach meinem Verständnis nicht unter "fast alle Zahlen".

Christoph

SideWinder schrieb:

Anzahl der Zahlen zwischen
[...]
100 und 999 = 1000
10 und 99 = 100

Sicher?

SideWinder

Ja du weißt ja, dass volkard immer übertreibt. Aber er zeigt dafür ordentlich auf in welche Richtung optimiert werden muss

Zu dem Quote: Ja sicher wenn du zwischen nicht als ]100,999[ sondern so wie ich als [100,999] siehst.

MfG SideWinder

Christoph

Also im Intervall [0;999] sind wohl 1000 Zahlen.
Im Intervall [100;999] werden dann 100 Zahlen weniger sein, oder?

SideWinder

cd9000 schrieb:

Also im Intervall [0;999] sind wohl 1000 Zahlen.
Im Intervall [100;999] werden dann 100 Zahlen weniger sein, oder?

Ich neige halt auch dazu zu übertreiben :p

MfG SideWinder

volkard

SideWinder schrieb:

Ja du weißt ja, dass volkard immer übertreibt.

danke.
aber diese übertreibung war ein versehen. ich dachte, die zahlen gingen bis 10000 und nicht nur bis 3000.
fraglich bei den softies ist immer, welche testwerte sie nehmen. werden sie wirklich gleichverteilt sein?

SideWinder

War in keiner Weise negativ gemeint

Stimmt, machen die tatsächlich ein rand()? Oder fügen die jeweils 2 Werte einer Dezimalgruppe ein.

Wie meinte TV Kaiser? Wir werden es erleben...

MfG SideWinder

ERROR

jo klar nicht drann gedacht, aber was bedeutet folgendes eigentlich genau?

The sum of the numbers would not exceed 3000 in magnitude.

Die Summe der Zahlen würd 3000 nicht in der Größe übersteigen.

aber da ist doch eigentlich nicht ausgeschlossen, dass wir zahlen kleiner als zb -3000 haben .... ergo könnten doch auch zahlen von:

-1323412 rauskommen? ... oder wo ist da die einschränkung?

danke + cu