ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1048. Superlong Sums

Please find a solution that's uglier than mine >=)
Posted by cearny (Adrian Cearnau) 21 Mar 2003 22:12
2.133 Seconds
704K of Memory Used

Tell me I ain't single-minded :) This is by far the ugliest solution
I've used to solve a problem at Timus by now. No brain, but lots
of copy & paste muscle :)
====================================================================

#include <stdio.h>

struct five {
  unsigned int a: 5;
  unsigned int b: 5;
  unsigned int c: 5;
  unsigned int d: 5;
  unsigned int e: 5;
  unsigned int f: 5;
};

struct five *sum;
long l;

int main() {
  long i, j, k;

  sum = (struct five*)malloc( 200001 * sizeof( struct five ) );

  scanf( "%ld", &l );

  if( l % 6 == 1 ) {
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].a = j + k;
  } else if( l % 6 == 2 ) {
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].b = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].a = j + k;
  } else if( l % 6 == 3 ) {
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].c = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].b = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].a = j + k;
  } else if( l % 6 == 4 ) {
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].d = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].c = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].b = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].a = j + k;
  } else if( l % 6 == 5 ) {
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].e = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].d = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].c = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].b = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ l / 6 ].a = j + k;
  }

  for( i = l / 6 - 1; i > - 1; i-- ) {
    scanf( "%ld %ld", &j, &k );
    sum[ i ].f = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ i ].e = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ i ].d = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ i ].c = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ i ].b = j + k;
    scanf( "%ld %ld", &j, &k );
    sum[ i ].a = j + k;
  }

  for( i = 0, j = 0; i < l / 6; i++ ) {
    sum[ i ].a += j; j = sum[ i ].a / 10; sum[ i ].a %= 10;
    sum[ i ].b += j; j = sum[ i ].b / 10; sum[ i ].b %= 10;
    sum[ i ].c += j; j = sum[ i ].c / 10; sum[ i ].c %= 10;
    sum[ i ].d += j; j = sum[ i ].d / 10; sum[ i ].d %= 10;
    sum[ i ].e += j; j = sum[ i ].e / 10; sum[ i ].e %= 10;
    sum[ i ].f += j; j = sum[ i ].f / 10; sum[ i ].f %= 10;
  }
  if( l % 6 || j ) {
    k = 0;

    if( j ) k++; sum[ i ].a += j; j = sum[ i ].a / 10; sum[ i ].a %=
10;
    if( j ) k++; sum[ i ].b += j; j = sum[ i ].b / 10; sum[ i ].b %=
10;
    if( j ) k++; sum[ i ].c += j; j = sum[ i ].c / 10; sum[ i ].c %=
10;
    if( j ) k++; sum[ i ].d += j; j = sum[ i ].d / 10; sum[ i ].d %=
10;
    if( j ) k++; sum[ i ].e += j; j = sum[ i ].e / 10; sum[ i ].e %=
10;
    if( j ) k++; sum[ i ].f += j; j = sum[ i ].f / 10; sum[ i ].f %=
10;

    if( k + 6 * ( l / 6 ) > 6 * ( l / 6 ) + l % 6 ) l++; j = 1;
  }

  if( l % 6 || j ) {
    i = l < 6 ? 0 : ( l / 6 );
    if( sum[ i ].f ) printf( "%d", sum[ i ].f );

    if( l % 6 >= 5
Sursa belea
Posted by Tiberiu Danet 22 Mar 2003 00:01
Uite, Cerno, ceva mai simplu. De pe vremea cand eram in Pascal.

var n,i,j,secv:longint;
    bufx,bufy,x,y:integer;
begin
     read(n);
     read(bufx,bufy);
     for i:=2 to n do
     begin
          read(x,y);
          if (x+y>=10) then
          begin
               write(bufx+bufy+1);
               for j:=1 to secv do write(0);
               secv:=0;
               bufx:=x-10; bufy:=y;
          end
          else if (x+y<9) then
          begin
               write(bufx+bufy);
               for j:=1 to secv do write(9);
               secv:=0;
               bufx:=x;bufy:=y;
          end
          else if (x+y=9) then
               inc(secv);
     end;
     write(bufx+bufy);
     for j:=1 to secv do write(9);
end.
u rule ~nt~
Posted by foxX 12 Apr 2003 19:42
> 2.133 Seconds
> 704K of Memory Used
>
> Tell me I ain't single-minded :) This is by far the ugliest solution
> I've used to solve a problem at Timus by now. No brain, but lots
> of copy & paste muscle :)
> ====================================================================
>
> #include <stdio.h>
>
> struct five {
>   unsigned int a: 5;
>   unsigned int b: 5;
>   unsigned int c: 5;
>   unsigned int d: 5;
>   unsigned int e: 5;
>   unsigned int f: 5;
> };
>
> struct five *sum;
> long l;
>
> int main() {
>   long i, j, k;
>
>   sum = (struct five*)malloc( 200001 * sizeof( struct five ) );
>
>   scanf( "%ld", &l );
>
>   if( l % 6 == 1 ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].a = j + k;
>   } else if( l % 6 == 2 ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].b = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].a = j + k;
>   } else if( l % 6 == 3 ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].c = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].b = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].a = j + k;
>   } else if( l % 6 == 4 ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].d = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].c = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].b = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].a = j + k;
>   } else if( l % 6 == 5 ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].e = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].d = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].c = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].b = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ l / 6 ].a = j + k;
>   }
>
>   for( i = l / 6 - 1; i > - 1; i-- ) {
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].f = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].e = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].d = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].c = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].b = j + k;
>     scanf( "%ld %ld", &j, &k );
>     sum[ i ].a = j + k;
>   }
>
>   for( i = 0, j = 0; i < l / 6; i++ ) {
>     sum[ i ].a += j; j = sum[ i ].a / 10; sum[ i ].a %= 10;
>     sum[ i ].b += j; j = sum[ i ].b / 10; sum[ i ].b %= 10;
>     sum[ i ].c += j; j = sum[ i ].c / 10; sum[ i ].c %= 10;
>     sum[ i ].d += j; j = sum[ i ].d / 10; sum[ i ].d %= 10;
>     sum[ i ].e += j; j = sum[ i ].e / 10; sum[ i ].e %= 10;
>     sum[
Problem with data structure
Posted by Eduard Munteanu 27 Jun 2005 04:42
> struct five {
> unsigned int a: 5;
> unsigned int b: 5;
> unsigned int c: 5;
> unsigned int d: 5;
> unsigned int e: 5;
> unsigned int f: 5;
> };

You've got a problem with the way you defined the structure.  There are 6 x 5 bits in that structure, summing up to 30 bits. Most likely, the compiler will pad up to 32 bits, so you get 4 byte, which will waste 2 bits per 6 digits. I recommend using a similar structure with a size of 40 bits (8 x 5 bits) instead. Also, you should use unsigned short integers, which I think it will prevent the compiler from padding up to the next word (up to 48 bits). Or to be very sure no padding occurs, the structure needs to have a size equal to a multiple of 5 and 16 (a word's size), preferably the smallest common multiple, which would mean 80 bits.

Yet worse, I don't think it's wise to use bit fields. The best way is to allocate the memory and use an int pointer (16 bits wide) to extract and inject the required 5 bits into memory.

That's enough about saving bits for now. I'll post my solution soon.

---
Eduard Gabriel Munteanu

Edited by author 27.06.2005 04:47

© 2000–2024 Timus Online Judge Team. All rights reserved.