Page 3 of 3
Posted: Sun Jan 14, 2007 12:35 pm
by EonStrife
I need help too...
I tried with test case Sanny provided, and the outputs are correct, however, I still got WA. Can anybody help me ? Thanks.
Code: Select all
#include <iostream>
#include <sstream>
#include <cmath>
#include <stack>
const long binaryMask[20] = {
1, // 0 2^0
2, // 1 2^1
4, // 2 2^2
8, // 3 2^3
16, // 4 2^4
32, // 5 2^5
64, // 6 2^6
128, // 7 2^7
256, // 8 2^8
512, // 9 2^9
1024, // 10 2^10
2048, // 11 2^11
4096, // 12 2^12
8192, // 13 2^13
16384, // 14 2^14
32768, // 15 2^15
65536, // 16 2^16
131072, // 17 2^17
262144, // 18 2^18
524288, // 19 2^19
};
int n;
using namespace std;
class Matrix
{
public:
Matrix();
~Matrix();
void initMatrix(bool flag);
unsigned long Cells[40][64];
// Matrix operator+(Matrix &rhs);
// Matrix operator*(Matrix &rhs);
};
struct Variant
{
Matrix Multiplier;
Matrix Adder;
bool flag;
};
Matrix sigmaMatrix;
Matrix aMatrix;
Matrix powerMatrix[20];
Matrix globalTempMatrix[21];
Matrix::Matrix(){}
Matrix::~Matrix(){}
void Matrix::initMatrix(bool flag)
{
for(int i=0;i<n; i++)
for(int j=0;j<n; j++)
Cells[i][j]=0;
if(flag==true)
for(int i=0;i<n;i++)
Cells[i][i]=1;
}
Matrix operator %(const Matrix &lhs, const int &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
C.Cells[j][kk]=lhs.Cells[j][kk]%rhs;
return C;
}
Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
int j, kk, l;
Matrix C;
C.initMatrix(false);
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
for(l=0;l<n;l++)
C.Cells[j][kk]+=lhs.Cells[j][l]*rhs.Cells[l][kk];
}
return C%10;
}
Matrix operator +(const Matrix &lhs, const Matrix &rhs)
{
int j, kk;
Matrix C;
for(j=0;j<n;j++)
for(kk=0;kk<n;kk++)
{
C.Cells[j][kk]=lhs.Cells[j][kk]+rhs.Cells[j][kk];
}
return C;
}
Matrix MatrixPower(unsigned long power)
{
Matrix temp;
unsigned long i;
temp.initMatrix(true);
for(i=0; i<20; i++)
{
if(power&binaryMask[i])
{
temp = temp * powerMatrix[i];
}
}
return temp;
}
Matrix hitung(unsigned long power, unsigned long no)
{
stack<Variant>myTree;
Variant temp;
Matrix localSigma=aMatrix;
unsigned long tempPower=power;
while(tempPower!=1)
{
// if(tempPower==1)
// {
// temp.Multiplier=aMatrix;
// temp.flag=false;
// myTree.push(temp);
// }
if(tempPower%2==0)
{
temp.Multiplier=MatrixPower(tempPower/2);
temp.flag=true;
myTree.push(temp);
}
else
{
tempPower--;
temp.Multiplier=MatrixPower(tempPower/2);
temp.Adder=MatrixPower(tempPower+1);
temp.flag=false;
myTree.push(temp);
}
tempPower/=2;
}
tempPower=1;
while(!myTree.empty())
{
temp=myTree.top();
if(temp.flag)
{
localSigma=localSigma+(temp.Multiplier*localSigma);
}
else
{
localSigma=localSigma+(temp.Multiplier*localSigma)+temp.Adder;
}
myTree.pop();
}
return localSigma;
//
// if(power==1)
// {
// return aMatrix;
// }
// else if(power%2==0)
// {
// globalTempMatrix[no]=hitung(power/2, no+1);
// return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no]);
// }
// else
// {
// power--;
// globalTempMatrix[no]=hitung(power/2, no+1);
// return globalTempMatrix[no]+(MatrixPower(power/2)*globalTempMatrix[no])+MatrixPower(power+1);
// }
}
int main()
{
unsigned long k;
int i, j, kk;
n=1;
while(n!=0)
{
cin >> n >> k;
if(n!=0)
{
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
cin >> aMatrix.Cells[i][j];
}
powerMatrix[0]=aMatrix;
for(i=1;i<20;i++)
powerMatrix[i]=powerMatrix[i-1]*powerMatrix[i-1];
sigmaMatrix=hitung(k, 0);
for(j=0;j<n;j++)
{
for(kk=0; kk<n; kk++)
cout << sigmaMatrix.Cells[j][kk]%10 << " ";
cout << endl;
}
cout << endl;
}
}
}
Posted: Wed Jan 17, 2007 1:57 am
by EonStrife
Anybody ?
Posted: Fri Jan 19, 2007 1:05 am
by A1
Sanny wrote:Ok now it is time to post the code i think. I've spent many hours with it. This program gets WA in ~.027 seconds.
Code: Select all
..
..
Dummy(n);
sort(v.begin(),v.end());
rep(i,v.size()) Pow(v[i]);
sort(vs.begin(),vs.end());
rep(i,vs.size()) find_sum(vs[i]);
..
maybe reassigning in map is doing trouble!! So change the part of ur code like above and get AC again
btw: u may be like to remove ur code also..
Posted: Tue Feb 13, 2007 1:54 am
by EonStrife
Any help for me ? I already posted my source code (check two posts above)
Thanks.
Posted: Thu Feb 15, 2007 1:06 am
by lord_burgos
EonStrife wrote:Any help for me ? I already posted my source code (check two posts above)
Thanks.
after read get of mod
scanf("%d", &A[x][y]);
A[x][y] %= 10;
because 10000000 x 10000000 > int
sorry for my english
Compilation Error
Posted: Sat Jan 19, 2008 9:15 pm
by mukeshtiwari
Could some one please help me why this code is giving compilation error. The code is working fine on my pc.
Code: Select all
#include<stdio.h>
#include<stdlib.h>
int n,**I,MOD=10;
int **alloc(int n)
{
int **a,i;
a=malloc(n*sizeof(int *));
for(i=0;i<n;i++)
a[i]=malloc(n*sizeof(int));
return a;
}
int **mul(int **res1,int **res2)
{
int **D,i,j,k;
D=alloc(n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
D[i][j]=0;
for( k=0;k<n;k++)
D[i][j]=(D[i][j]+(res1[i][k]*res2[k][j])%MOD)%MOD;
}
return D;
}
void cpy(int **a,int **b)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=b[i][j];
}
void sum(int **t1,int **t2)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
t1[i][j]=(t1[i][j]+t2[i][j])%MOD;
}
int **pow_(int** A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **res;
res=pow_(A,n_pow/2);
res=mul(res,res);
if(n_pow%2)
res=mul(res,A);
return res;
}
int **geom(int **A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **result=geom(A,n_pow/2);
int **t=pow_(A,n_pow/2);
sum(t,I);
result=mul(result,t);
if(n_pow%2)
{
int **v=pow_(A,n_pow);
sum(result,v);
}
return result;
}
int main()
{
int k,w=0,i,j;
int **A;
while(scanf("%d",&n) && n!=0)
{
scanf("%d",&k);
A=alloc(n);
I=alloc(n);
if(w)
printf("\n");
w=1;
for( i=0;i<n;i++)
{
for( j=0;j<n;j++)
{
scanf("%d",&A[i][j]);
A[i][j]=A[i][j]%10;
I[i][j]=0;
}
I[i][i]=1;
}
int** v;
v=geom(A,k);
for( i=0;i<n;i++)
for( j=0;j<n;j++)
printf("%d%c",v[i][j],(j==n-1)?'\n':' ');
}
}
Posted: Sun Jan 20, 2008 1:14 am
by mf
p.cc: In function `int** alloc(int)':
p.cc:7: error: invalid conversion from `void*' to `int**'
p.cc:9: error: invalid conversion from `void*' to `int*'
Posted: Sun Jan 20, 2008 8:17 am
by mukeshtiwari
Thank you
It was quite helpful but don't know why it was not giving compiler error on my pc.
Posted: Tue Jan 22, 2008 9:11 am
by mukeshtiwari
Could someone please tell me why judge is giving WA for this problem.Its giving all output correct for inputs given on board.If someone can point out error it will be very much thankful.
Code: Select all
//kindly compile with g++
#include<cstdio>
#include<cstdlib>
int n,**I,MOD=10;
int **alloc(int n)
{
int **a,i;
a=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
a[i]=(int *)malloc(n*sizeof(int));
return a;
}
int **mul(int **res1,int **res2)
{
int **D,i,j,k;
D=alloc(n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
D[i][j]=0;
for( k=0;k<n;k++)
D[i][j]=(D[i][j]+(res1[i][k]*res2[k][j])%MOD)%MOD;
}
return D;
}
void cpy(int **a,int **b)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=b[i][j];
}
void sum(int **t1,int **t2)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
t1[i][j]=(t1[i][j]+t2[i][j])%MOD;
}
int **pow_(int** A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **res;
res=pow_(A,n_pow/2);
res=mul(res,res);
if(n_pow%2)
res=mul(res,A);
return res;
}
int **geom(int **A,int n_pow)
{
if(n_pow==1)
{
int **Temp=alloc(n);
cpy(Temp,A);
return Temp;
}
int **result=geom(A,n_pow/2);
int **t=pow_(A,n_pow/2);
sum(t,I);
result=mul(result,t);
if(n_pow%2)
{
int **v=pow_(A,n_pow);
sum(result,v);
}
return result;
}
int main()
{
int k,w=0,i,j;
int **A;
while(scanf("%d",&n) && n!=0)
{
scanf("%d",&k);
A=alloc(n);
I=alloc(n);
if(w)
printf("\n");
w=1;
for( i=0;i<n;i++)
{
for( j=0;j<n;j++)
{
scanf("%d",&A[i][j]);
A[i][j]=A[i][j]%10;
I[i][j]=0;
}
I[i][i]=1;
}
int** v;
v=geom(A,k);
for( i=0;i<n;i++)
for( j=0;j<n;j++)
printf("%d%c",v[i][j],(j==n-1)?'\n':' ');
}
}
Posted: Sat Jan 26, 2008 12:19 pm
by mukeshtiwari
no reply
Posted: Mon Mar 03, 2008 12:37 am
by jurajz
I don't read your code in parts of computation with matrices, but i think, I found, where may be a problem. Variable w is initially set on 0, after first test case is set on 1. This cause, that before each case except the first you write a blank line. But problem description says, that there have to be blank line after each test case. But you don't write a blank line after last test case. In old system, that was PE, now missing a blank line is WA. Try to correct it, maybe this is reason of your WA
Re: 11149 - Power of Matrix
Posted: Tue Sep 29, 2009 4:26 pm
by manhattan
somebody could tell me what's wrong with my program?
tks,
Code: Select all
#include <iomanip>
#include <iostream>
using namespace std;
const int maximo = 40;
int n, k;
struct MATRIZ {
int matriz[maximo][maximo];
MATRIZ() {
memset(matriz,0,sizeof(matriz));
}
}A, E;
void inicializa() {
memset(E.matriz,0,sizeof(E.matriz));
for(int i=0;i<maximo;i++) E.matriz[i][i] = 1;
}
void entrada() {
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>A.matriz[i][j];
}
MATRIZ soma(const MATRIZ &A, const MATRIZ &B) {
MATRIZ c;
for (int i=0;i<maximo;i++)
for (int j=0;j<maximo;j++)
c.matriz[i][j] = (A.matriz[i][j]+B.matriz[i][j])%10;
return c;
}
MATRIZ multiplica(const MATRIZ &A,const MATRIZ &B) {
MATRIZ C;
int tmp;
for(int i=0;i<maximo;i++)
for(int j=0;j<maximo;j++) {
tmp=0;
for(int k=0;k<maximo;k++) {
tmp += A.matriz[i][k]*B.matriz[k][j];
}
C.matriz[i][j] = tmp%10;
}
return C;
}
MATRIZ potencia(const MATRIZ B, int e){
if(e==0) {
MATRIZ I;
for(int i=0;i<maximo;i++) I.matriz[i][i]=1;
return I;
} else {
MATRIZ res = potencia(B,e/2);
res = multiplica(res,res);
if(e % 2) res = multiplica(res,B);
return res;
}
}
void imprime(const MATRIZ &B, int count) {
for(int i=0;i<count;i++) {
for(int j=0;j<count;j++) {
cout<<B.matriz[i][j]<<" ";
}
cout<<endl;
}
}
MATRIZ resolve(int k) {
if (k==0) return E;
if (k==1) return A;
if (k & 0x1){
return soma(A,multiplica(A,resolve(k-1)));
} else {
MATRIZ C = resolve(k>>1);
return soma(C, multiplica(potencia(A,k>>1),C));
}
}
int main() {
inicializa();
int controle[1][20];
int numero = 0,contador=0;
bool acabou = false;
cin>>n>>k;
if(n==0) acabou = true;
while (!acabou) {
controle[0][numero] = k;
controle[1][numero] = n;
entrada();
cin>>n>>k;
if(n==0) acabou = true;
numero++;
}
while(contador<numero) {
cout<<endl;
imprime(resolve(controle[0][contador]),controle[1][contador]);
contador++;
}
return 0;
}
Re: 11149 - Power of Matrix
Posted: Thu Feb 27, 2014 9:37 am
by Repon kumar Roy
The code has bug in multipling matrices . Check the mod every step..