## 12318 - Digital Roulette

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

Moderator: Board moderators

Amoeba
New poster
Posts: 6
Joined: Tue Sep 20, 2011 4:01 pm

### 12318 - Digital Roulette

I think. my logic is correct.

but i got a WA.

is there mistake in my code?

here my code.

Code: Select all

#include "stdio.h"
#include "memory.h"
#include "algorithm"
#include "math.h"

#define MAX 100001

using namespace std;

int main()
{
int  poly[11];
int  answer[MAX];
int  size, loop, degree, cnt;
long long temp;

while(1)
{
scanf("%d %d", &size, &loop);

if(size == 0 && loop == 0)
break;

scanf("%d", &degree);

cnt = 1;
memset(answer, -1, sizeof(answer));
memset(poly, 0, sizeof(poly));

for(int i=0; i<=degree; i++)
scanf("%d", &poly[i]);

for(int i=0; i<=loop; i++)
{
answer[i] = poly[0];
temp = i;

for(int j=1; j<=degree; j++)
{
if(poly[j] != 0)
{
temp = pow((long double)i, j);
temp %= (size+1);
poly[j] %= (size+1);
answer[i] += poly[j] * temp;

if(answer[i] > size)
answer[i] %= size+1;
}
}
}

sort(answer, answer+loop+1);

for(int i=0; i<loop; i++)
{
if(answer[i] != answer[i+1])
cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
ps.is there mistake related number range in my code?

help me plz.

seidan
New poster
Posts: 1
Joined: Thu Oct 27, 2011 7:34 pm

### Re: 12318 - Digital Roulette

the last result of the examples is 10 and in your code is 11??

Sorry for my english

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### Re: 12318 - Digital Roulette

do not use pow() method for calculating x^k
make a pow method

Code: Select all

long pow(long x, int k)
----if k==0 then return 1
----powval = x%(N+1)
----for i=1 to k-1
------powval *= x
------powval  %= (N+1)
I think now the problem is very easy
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Amoeba
New poster
Posts: 6
Joined: Tue Sep 20, 2011 4:01 pm

### Re: 12318 - Digital Roulette

I had changed pow method many times

but i still got a WA

Code: Select all

#include "stdio.h"
#include "memory.h"
#include "algorithm"

#define MAX 100001

using namespace std;

long long power(long long x, int k, int size)
{
long long powval;

if( k==0)
return 1;
powval = x%(size+1);

for( int i=1; i<= k-1; i++)
{
powval *= x;
powval  %= (size+1);
}
return powval;

/*x %= (size+1);

if(k == 0)
return 1;
else if((k%2) == 0)
return power(x*x, k/2, size);
else
return x*power(x*x, (k-1)/2, size);*/
}

int main()
{
int  poly[11];
int answer[MAX];
int loop, degree, cnt, size;
long long temp;

while(1)
{
scanf("%d %d", &size, &loop);

if(size == 0 && loop == 0)
break;

scanf("%d", &degree);

cnt = 1;
memset(answer, -1, sizeof(answer));
memset(poly, 0, sizeof(poly));

for(int i=0; i<=degree; i++)
scanf("%d", &poly[i]);

for(int i=0; i<=loop; i++)
{
answer[i] = poly[0];
temp = i;

for(int j=1; j<=degree; j++)
{
if(poly[j] != 0)
{
temp = power(i, j, size);
answer[i] = temp * poly[j];

if(answer[i] > size)
answer[i] %= size+1;
}
}
}

sort(answer, answer+loop+1);

for(int i=0; i<loop; i++)
if(answer[i] != answer[i+1])
cnt++;

printf("%d\n", cnt);
}
return 0;
}
i dno't know where is mistake T T

help me.

Amoeba
New poster
Posts: 6
Joined: Tue Sep 20, 2011 4:01 pm

### Re: 12318 - Digital Roulette

one more question

shuld i use long long or long long int? behalf of int??

Amoeba
New poster
Posts: 6
Joined: Tue Sep 20, 2011 4:01 pm

### Re: 12318 - Digital Roulette

Now I got a AC.

thx^^

I changed pow method.

Have a nice day~