Very Easy Josephus's problem. Look it on geek for geeks

For the classic Josephus problem, there exists two classic algorithms.
The algorithm A has time complexity O(lgn) and comes from <discrete mathematics>.
/* Algorithm A */
int solve(int N/*The magic number 1999*/, int m/*length of the text*/)
{
    long long z = 1;
    while (z < (N - 1LL/*int may overflow here*/) * m + 1)
    {
        z = (z * N + N - 2) / (N - 1);
    }
    return m * N - z;
}

The algorithm B is the classic O(n) algorithm.
int solve(int N/*The magic number 1999*/, int m/*length of the text*/)
{
    int z = 0;
    for (int k = 2; k <= m; ++k)
    {
        z = (z + N) % k;
    }
    return z;
}

In my submissions, algorithm A costs 0.015s, and algorithm B costs 0.001s.
Maybe arithmetic operations for "long long" is a little too slow?

This code in Java:

int v = 0;
int n = 1998;
while (buffer.length() > 1) {
    v += n;
    v %= buffer.length();
    buffer.deleteCharAt(v);
}

Got AC in 0.109 time

First of all make sure that you are not reading newlines and carriage return symbols. Input can be read like:

    char c;
    int scanfRez;
    do {
        scanfRez = scanf("%c", &c);
        if (scanfRez != EOF && c != '\n' && c != '\r') {
            chs[chCount++] = c;
        }
    }while(scanfRez != EOF);

I was getting WA7 with this input reading:

    char c;
    int scanfRez;
    do {
        scanfRez = scanf("%c", &c);
        if (c != '\n' && c != '\r') {
            chs[chCount++] = c;
        }
    }while(scanfRez != EOF);

If you get WA3 make sure that you are processing sequence correctly with given sequence length > N. For example:
let N = 11, input sequence = "abcdefghijkl" (without quotes) then letters should be removed in this order:
k 1
j 2
l 3
b 4
e 5
i 6
g 7
h 8
d 9
a 10
c 11
f 12

It does not matter if you put newline at the end of output.

Can someone provide more tests?
I am using scanner.nextLine() to read
line.charAt(pos) == '?' to compare in java and also Josephus allgorithm:
jos[1] = 1;
for (int i = 2; i < max_n; i++) {
    jos[i] = (jos[i - 1] + 1998) % i + 1;
}
My code is so small that I don't even know where is the bug

I just use two lines in my code.

pos=(pos+N-1)%question.length();
question.erase(pos,1);

and I got AC...

though it is a bit slow.
But still unbelievable.

For those who are stuck at this point.

The filtered (thus 0x0a and 0x0d removed) first testcase is:

"a ?" (w/o quotes)

I wonder if it's true that the first test matches the sample. My program writes 'Yes' just like in the sample.
But it gets WA1 ??

I have two different solutions and each of them gives me WA3 :(
First - naive, here it is:
-----------------------------------
read(s);
l:=length(s);
n:=1999;
if l < n then
          if n mod l <> 0 then
                           A:=n mod l
                          else
                           A:=l
         else
          A:=n;
while l <> 1 do
 begin
   delete(s,A,1);
   n1:=n-(l-A);
   dec(l);
   if l < n1 then
          if n1 mod l <> 0 then
                            A:=n1 mod l
                           else
                            A:=l
         else
          A:=n1;
 end;
case s[1] of
 '?': writeln('Yes');
 ' ': writeln('No');
 else writeln('No comments');
end;
readln;
end.
-----------------------------------

And the next one is recursive solution inspired by Josephus problem formula:
-----------------------------------
function Jo(l: longint): longint;
begin
  if l = 1 then
            Jo:=0
           else
            Jo:=(Jo(l-1)+n) mod l;
end;

begin
read(s);
l:=length(s);
n:=1999;
case s[Jo(l)+1] of
 '?': writeln('Yes');
 ' ': writeln('No');
 else writeln('No comments');
end;
readln;
end.
-----------------------------------

Please, help me with some tests information or tell me about my stupid bugs :)
Maybe I miss some cases?


Edited by author 12.09.2011 00:58

i've wa at Test#7 twice.

At first,my program outputed "No comments.".
Second,my program outputed "NO comments".

the firdt test is wrong, my AC program gives "No comments"
pls fixed that and change statement

do not forget about {$H+} after debuging ;^)

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n=1999;
    string s;
    int pl[100000], br=0, j=0, symb;
    while(getline(cin,s,'ç'))
    {
                             for(int i=0; i<s.size(); i++)
                             {
                                     if(s[i]=='\n'){ s.erase(i,1);}
                             }
                             symb=0;
                             for(;;)
                             {
                                    if(s.size()==1) {
                                                    if(s[0]=='?'){ cout << "Yes" << endl; return 0;}
                                                    else if(s[0]==' ') { cout << "No" << endl; return 0;}
                                                    else { cout << "No comments" << endl; return 0;}
                                                    }
                                    symb=symb+(n-1);
                                    symb=symb%s.size();
                                    s.erase(symb,1);
                             }
    }
    return 0;
}

Edited by author 07.03.2009 01:46

Edited by author 07.03.2009 01:46

I solved this problem as a Josephus Problem. Everything is ok as long as test8. I can't unterstand why WA8.

If you think it helps I will give you my code in Pascal.

What's wrong with this one i tested dozens of times and #3 always give me WA. Even hint says that question will consist of 14 characters when actually there is more than 20.

I've tried to solve this problem using lists and with the Josephus algorithm and both approaches had WA7, it seems I can't read the input properly. I've tried different approaches here, too:

1.
while not eof do
begin
read(s[i]);
if (ord(s[i])=13) or (ord(s[i])=10) then dec(i);
inc(i);
end;

2.
repeat
  readln(ss);
  for i:=len+1 to len+length(ss) do s[i]:=ss[i-len];
  len:=len+length(ss);
until eof;

And many others, but I always get WA7. What's that test?!

Finally made it (party) =P for 0.156    268 KB

Could anybody tell me how should I read the input in "c"?