I think the input for first sample should be:
1
A*X*C
*CM
not
1
XC
*CM
am I right?
created
last reply
- 24
replies
- 3.6k
views
- 14
users
- 3
links
I think the input for first sample should be:
1
A*X*C
*CM
not
1
XC
*CM
am I right?
yeah, figured out that part, intersection of all possible n is to be used. But everything done, my code now dies in TLE.I figure I am having O(n^2) complexity. Please help me out, by directing me to some better approach. Is there any DP approach or did I miss some crucial optimization step? Please help
int main(){
int no,n,i,j,kbase,kval,top,N,misVal,counter;
char tmp;
bool flag;
cin>>no;
while(no>0){
no--;
string x,y;
cin>>N;//Max length of cypher
cin>>x;//Plain text
cin>>y;//Encrypted text
int kMap[x.length()][2];
int mismatch[N+1];//As 0 is left unconsidered
//Initializing the array containing the values of n that is never possible
for(i=0;i<=N;i++)
mismatch[i]=-1;
top = -1;
for(i=0;i<x.length();i++){
//If both the values are known, we can determine the k values
if((x[i]!='*')&&(y[i]!='*')){
kval=(y[i]+26-x[i])%26;
//Chekcing for possible mismatch
for(j=top;j>=0;j--){
//Mismatch occurs
if(kMap[j][1]!=kval){
misVal=i-kMap[j][0];
mismatch[misVal]=1;
}
}
top++;
//Insert the k value and the index in the k-map
kMap[top][0]=i;
kMap[top][1]=kval;
}
}
//If a n is not possible, so is all its factors also, calculating those values
for(i=0;i<=N;i++){
if(mismatch[i]==1)
storeMisVal(misVal,N,mismatch);
}
n=-1;
char mem[x.length()];
int k[N];//Array holding cyphers.
counter=-1;
//Initialzing array to hold the plaintext
for(i=0;i<x.length();i++)
mem[i]=1;
//Detecting the value of n
for(i=N;i>0;i--){
if(mismatch[i]==-1){
n=i;
}else
continue;
counter++;
//Initializing the values of k.
for(j=0;j<N;j++)
k[j]=-1;
for(j=0;j<=top;j++){
kbase=kMap[j][0];
kbase%=n;
k[kbase]=kMap[j][1];
}
for(j=0;j<x.length();j++){
//The text is inelligible to compute, meaning for different n, the value is not unique.
if(mem[j]==0)
continue;
//If encrypted text is inelligible or plaintext is elligible,then print the plaintext as it is.
if((y[j]=='*')||(x[j]!='*')){
if(counter==0)
mem[j]=x[j];
else if(mem[j]!=x[j]){
mem[j]=0;
}
continue;
}
kbase=j%n;
if(k[kbase]==-1){
if(counter==0)
mem[j]=x[j];
else if(mem[j]!=x[j]){
mem[j]=0;
}
continue;
}
tmp=y[j]-k[kbase];
if(tmp<65){
if(counter==0)
mem[j]=(char)(tmp+26);
else if(mem[j]!=(char)(tmp+26)){
mem[j]=0;
}
}
else{
if(counter==0)
mem[j]=tmp;
else if(mem[j]!=tmp){
mem[j]=0;
}
}
}
}
//Print the generated plaintext, for those values with conflicting for different n, original plaintext letter is used.
for(i=0;i<x.length();i++){
if(mem[i]!=0)
cout<<mem[i];
else
cout<<x[i];
}
cout<<endl;
}
}
//Function to store the value and all their factors as well in the mismatch array.
int storeMisVal(int val,int max,int mismatch[]){
int i;
if(val<=max)
mismatch[val]=1;
for(i=val-1;i>0;i--){
if(val%i==0){
if(mismatch[i]!=1)
storeMisVal(i,max,mismatch);
}
}
}
Sorry friend, don't know why but I can't find any result..
https://www.spoj.pl/forum/search.php?keywords=CRYPT049
please see
Nie wiem co dokładnie pokazuje "menedżer zadań" w Windows i co dokładnie sprawdzasz, ale prosta analiza kodu wskazuje, że nie może to być pamięć alokowana przez proces.
windows.microsoft.com/pl-pl/wind ... =windows-7
Ja pod Linuxem sprawdzam zużycie pamięci używając valgrind-a
==29479== Memcheck, a memory error detector
==29479== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==29479== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==29479== Command: ./a.out
==29479==
1
1000000000 1000000000
==29479== Warning: set address range perms: large range [0x395a5040, 0x127c57840) (undefined)
0
==29479== Warning: set address range perms: large range [0x395a5030, 0x127c57850) (noaccess)
==29479==
==29479== HEAP SUMMARY:
==29479== in use at exit: 24 bytes in 5 blocks
==29479== total heap usage: 7 allocs, 2 frees, 4,000,000,032 bytes allocated
==29479==
Tak jak się można spodziewać dla wejścia z b=10^9 Twój program alokuje ~4GB pamięci i stąd na spoj-u przekracza limit.
Proponuje zapoznaj się z narzędziami, które pokazują zużycie/alokacje pamięci pod Windows. Znalazłem taki wątek:
stackoverflow.com/questions/4134 ... or-windows2
Poddaję się. To już kolejny wariant który testuje. Szybciej i krócej nie potrafie. Spoj wskazuję błąd.
[bbone=CPP,2663]
using namespace std;
int ostatnia(int liczba)
{
int wynik=0;
wynik = liczba % 10; // pobiera cyfrę
liczba = liczba / 10; // obcina liczbę o wybraną cyfrę
return(wynik);
}
int main()
{
int ile,b;
int liczba,potega;
double wynik;
cin>>ile;
for(int i=0;i<ile;i++)
{
cin>>liczba>>potega;
b=ostatnia(liczba);
wynik=pow(b,potega);
cout<<ostatnia(wynik)<<endl;
}
return 0;
}
[/bbone]