11051 - Dihedral groups

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

11051 - Dihedral groups

Post by shihabrc »

Hi all,

I'm getting WA in this problem. Can some1 give me some I/O.

-Thanx in advance
Shihab
CSE,BUET

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: Getting WA in 11051. I/O required

Post by Martin Macko »

shihabrc wrote:I'm getting WA in this problem. Can some1 give me some I/O.

Code: Select all

882
m216
346
r303
362
r420 r413 r577 r805 r94 r777 r168 r763 r666 r700 r730 r357
82
r715 r707 r680 r156 r476 r817 r692 r436 m531 r415 r657 r732 r416 m401 r406 r293
993
r840 r477 r570 r79 r935 r1000 r942
906
r823 r788 r41 r366
630
r742 r244 r971 r667 r429 r751
695
r981 m407 r856 r630 r415 r935 r973 r601 m423 r622 m883 r100 m39 r137
151
r177 r789 r641 r17 r25 r39
849
r610 m14 r236 r698 r227 r371 r678 r109 m970 r135
44
r105 r748 r371 r439 m149 r503 r80 r149 r208 r279 r343
426
m75 r87 m867 r687 m598 r451 r221 r929 m288 m235 r169 r849 r109 r306 r138 r253
402
m773 r349 m391 m245 m913 r81 m538 r624 r88 r506
496
m118 m768 r271 r818 r62 r542 r105 r59 r477 r166 r164 r278 r178 r931 r652 r1000 m627 r375 r490
872
m838 r313 r548 m642 r694 r934 r213 m348 r575 r776
568
r698 m245 r603 r319 r637 r589 m449 m23 m512 r249 r278 r7 r555 m255 r510 r809 r391 m334 m491
631
r160 r779 m746 r403 r870 m406 r816 r123 m345
795
m414 r765 r970 r150 m750 m939 r429 r574 m871 m486 r978 m238
728
r164 r441 r204 r132 r10 r418 m562 r682 r132 r921 r987 m680 r882 r67
347
m183 m71 r885 m180 r946 r469 r700 r585 m234 r194
114

746
r356 r110 r1 r142 r229 r509 r189 r480
998

75
m682 r13 r853 r773 r738 r77 r302 m866 r449 r540 r922
166

597
m300 r273 r652 r988 r573 r575 r464 r469 m109 r78 r128 r685 r203 m67 r420 r316 r877 r571 m893
912
r749 r513 r486 r104 r455 r920 r60 r600 r561 r309 m875 r52 r563 r984 m531 r624
675
r194 m821 r837 r183 m208 r711 r207 r177 m955 r491 m507 r979 r861
215
r491 r972 r720 r686
546
r663 r813 r138 r348 r886 r69
0
My AC's output:

Code: Select all

m1 r43 m1
m1 r46 m1
m1 r40 m1
m1 r122 m1
r206
r24
r10
r27
m1 r332 m1
r13 m1
m1 r49
r146
m1 r122
m1 r307 m1
m1 r261
m1 r4
r270
m1 r56 m1
m1 r38 m1

m1 r222 m1

r17

m1 r289
r134
r105 m1
r74
r187

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc »

Thanx 4 ur I/Os. Got AC now.
Shihab
CSE,BUET

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david »

I am getting TLE just by reading the input. I read a line and successively use sscanf with the appropiate pointer within the string; I have successfully used this method on many other occasions. Does anyone know where the problem lies?

Here goes my code:

Code: Select all

/* 11051 dihedral groups */
#include <algorithm>
#include <cstdio>
#include <cassert>
using namespace std;

char cad[1000000];

int main() {
  long long n, m, r;
  for (;;) {
    gets(cad);
    if (feof(stdin)) break;
    sscanf(cad, "%lli", &n);
    if (n == 0) break;
    
    m = r = 0;
    gets(cad);

    char *p = cad;
    while (*p) {
      long long veces; int leidos;
      char letra;
      assert(sscanf(p, " %c%lli%n", &letra, &veces, &leidos) == 2);
      p += leidos;
      
      if (letra == 'r') r = (r + veces) % n;
      else if (veces & 1) { m = 1 - m; r = (n - r) % n; }
    }    
 
    if (r) {
      if (m) {
        if (r <= n - r) printf("m1 r%lli\n", r);
        else printf("r%lli m1\n", n - r);
      } else {
        if (r <= 2 + n - r) printf("r%lli\n", r);
        else printf("m1 r%lli m1\n", n - r);
      }
    } else if (m) puts("m1");
    else puts("");
  }
  return 0;
}

Edit: I have changed the code above so as to use an sstream and it was accepted in 0.4 seconds. But I still have no idea as to why this causes so great an speedup, and would be grateful if someone explained the reason; this seems rather mysterious to me.

joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa »

I not found problem in my implementation, however I'he got WA.
My code works for all tests cases above.

Somebody can help me ?

Code: Select all

I've got AC now.
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

pothiknobi
New poster
Posts: 2
Joined: Fri Oct 20, 2006 4:56 pm

!!! STRANGE !!! WA in 11051

Post by pothiknobi »

The following is an AC-ed code for the problem 11051...

Code: Select all

//Problem Solved

But the following code gets WA !!!

Code: Select all

//Problem Solved
the ONLY change in the second code is the line where I declare two character arrays 'op_str' and 'tmp' is made active. How can this result into a WA.. is it me seeing things or is it some kind of restriction of C/C++ that I dont know about ?? Can someone please clarify what can be the reason??

Sorry for putting an AC code in the board.. But I really wanted to know the reason.
Last edited by pothiknobi on Sat Oct 21, 2006 11:20 am, edited 1 time in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

The restriction is that undefined behaviour (such as resulting from overwriting some random memory after incorrect use of scanf) is bad. The code might work, in might not work, it might crash.

Read the manual and compile with all warnings on (-Wall -W -Wshadow etc.) to avoid similar errors in future.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

pothiknobi
New poster
Posts: 2
Joined: Fri Oct 20, 2006 4:56 pm

Post by pothiknobi »

I now understand the problem ... the problem is in the while(scanf()) part .. I have to put the character in some temporary variable ... (actually that %c portion was just to take the next newline character and as I dont need it I did not store it either)

Thanks to Mr. Duleba :)

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Actually, scanf("%d%*c", &an_int_which_original_name_I_forgot_and_cannot_lookup_after_you_removed_the_code) will do the trick (again, you can find really amazing things in the manual :-) )
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Post Reply

Return to “Volume 110 (11000-11099)”