CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • February CookOff
    • February Long Contest
    • January CookOff
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
    • Event Calendar
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Ranks
    • Tutorials
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » Manthan 2010 » Decryption

Decryption

Problem code: CF01

  • All Submissions

All submissions for this problem are available.

Aliens are planning to attack on Earth. Scientists at ISRO got a breakthrough when they were able to intercept the message being transferred in between aliens, but the problem is that aliens are using a technique for encrypting the message. Codefest team of IT-BHU were able to hack into the systems of aliens and decipher the method, the aliens were using for encryption but a method for decryption has not been found yet. You are required to decrypt the message.

The method used for encryption is explained below:
Consider a string of N alphabets for example encrypt (N=7). The string is treated as if the last character wraps around back to the first. Next consider a set S of N different strings, in which each string is formed by cyclic rotation of the alphabets of the original string. So for the string encrypt, S = {encrypt, ncrypte, crypten, ryptenc, yptencr, ptencry, tencryp}

The next step is to perform a lexicographical sort in decreasing order on the set of above strings. So S becomes {yptencr, tencryp, ryptenc, ptencry, ncrypte, encrypt, crypten}

Now, the encyrpted string of N alphabets is formed taking the last character from the above sorted strings. For given example, the encrypted string is rpcyetn. They also send the position of the first character of the encrypted string so that the message can be decrypted i.e. 5 for the given example.

Input

There is a single integer T<=200 on the first line of input which denotes the number of test cases to follow. Each of the next T lines, contains a string made up of k alphabets (a-z characters only) followed by an integer N, separated by a blankspace. 1<=N<=k<=3000.

Output

Output consists of T lines, each containing the decrypted string.

Example

Input:
3
rpcyetn 5
rathe 5
aabb 2
Output:
encrypt
earth
baba

Date: 2010-03-26
Time limit: 1s
Source limit: 50000
Languages: C C++ 4.0.0-8 C++ 4.3.2


  • Submit

Comments

  • Login or Register to post a comment.

The 3rd test case is

ahmed_aly_tc @ 28 Mar 2010 06:06 PM

The 3rd test case is wrong.

aabb 2
the first char of the output should be a

Yes. The output for third

manthan @ 28 Mar 2010 06:13 PM
Yes. The output for third case is:
abab

i m not able to submit it

calc_saransh @ 28 Mar 2010 06:53 PM

i m not able to submit it says... restricted area

@Saransh: have you registered

manthan @ 28 Mar 2010 07:00 PM
@Saransh: have you registered your team for this contest. If yes, login with the team login credentials

i am not able to submit a

technocoders @ 28 Mar 2010 07:00 PM

i am not able to submit a java solution

@coders_ntu : Only C/CPP

manthan @ 28 Mar 2010 07:03 PM

@coders_ntu : Only C/CPP codes are allowed for the contest.

// firstapp.cpp : Defines the

digcon9 @ 28 Mar 2010 07:16 PM

// firstapp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <string.h>
#include <stdlib.h>

char buf[3000];
char buf1[3000];

int posit(char t[], int len, char a){
int i;
for(i = 0; i < len; i++){
if(t[i] == a) return i;
}
//This case shouldn't occur
return -1;
}

char* match(int pos, int len){
char tmp[3000];
int cnt = 0;
int index = 0;
tmp[index++] = buf[pos];
while(cnt++ < len){
pos = posit(buf, len, buf1[pos]);                   
tmp[index++] = buf[pos];
}
tmp[index - 1] = 0;
return tmp;
}

int cmp(const void* arg1, const void* arg2){
char a = *(char*)arg1;
char b = *(char*)arg2;
return a < b ? 1 : (a == b) ? 0 : -1;
}

int main(){
int n = 0, i, pos, len;
scanf("%dn", &n);
for(i = 0; i < n; i++){
scanf("%s %d", buf, &pos);
len = strlen(buf);
strncpy(buf1, buf, len);
qsort((void*)buf1, len, sizeof(char), cmp);   
printf("%sn", match(pos - 1, strlen(buf)));
}

return 0;
}

sorry!

digcon9 @ 28 Mar 2010 07:17 PM

sorry!

Why can't I submit?

digcon9 @ 28 Mar 2010 07:18 PM

Why can't I submit?

FDHDFYTF;R57UTFUTIK8I

maverickers @ 28 Mar 2010 07:22 PM

FDHDFYTF;R57UTFUTIK8I

@digcon9: Have you registered

manthan @ 28 Mar 2010 07:22 PM

@digcon9: Have you registered your team for this contest. If yes, login with the team login credentials

I've registerd at itbhu, but

digcon9 @ 28 Mar 2010 07:25 PM

I've registerd at itbhu, but not at codechef. Is there any solution to such problem?

i have looged in with my team

3fools @ 28 Mar 2010 07:27 PM

i have looged in with my team 3fools but on submitting it shows internal error occured.........

@digcon9: No, you can not

manthan @ 28 Mar 2010 07:34 PM

@digcon9: No, you can not particiapte in the contest. Registration at codechef was compulsary as mentioned in the rules section of the event at Codefest ans Codechef website.

You can still try out the problems and get to know new things when the solutions are released.

@titan: have you registered

manthan @ 28 Mar 2010 07:40 PM

@titan: have you registered your team for this contest i.e. MANTH10 at Codechef? If not, then you can not participate.

yes i have registered my

3fools @ 28 Mar 2010 07:46 PM

yes i have registered my teamat codechef

team handle "3fools" disply team name "titan"

kindly look into the problem..........

@titan: Kindly, try

manthan @ 28 Mar 2010 07:53 PM

@titan: Kindly, try submitting the code again

forgot my team name... not

cinash @ 28 Mar 2010 07:55 PM

forgot my team name... not able to submit.. pls help...

@Cinash: Search your team at

manthan @ 28 Mar 2010 07:58 PM

@Cinash: Search your team at http://www.codechef.com/teams/list/MANTH10/

my team name is same as the

cinash @ 28 Mar 2010 08:03 PM

my team name is same as the codechef username... where do i login with my team name?

@codefest again the same

3fools @ 28 Mar 2010 08:05 PM

@codefest again the same problem persists................it says internal error occured on submitting the solution ........

plzzz help............

when i submit the solution,

define @ 28 Mar 2010 08:07 PM

when i submit the solution, this error is displayed. "contest_problem_id field is required." ... why so ???

what must i do ???

Current ranking is available

manthan @ 28 Mar 2010 08:09 PM

Current ranking is available at http://www.codechef.com/teams/list/MANTH10/

@titan: Does the same problem

manthan @ 28 Mar 2010 08:12 PM

@titan: Does the same problem occur when you try to submit codes for other problem also?

 

@define:Try submitting the code for some other problem. Let me know of the outcome.

yes the same problem exists

3fools @ 28 Mar 2010 08:18 PM

yes the same problem exists while submitting the slution of other problems.......................

I hv registered my team at

nice coder @ 28 Mar 2010 08:21 PM

I hv registered my team at codefest... but i m not able to register it on codechef... plz hekp me..

I hv registered my team at

nice coder @ 28 Mar 2010 08:21 PM

I hv registered my team at codefest... but i m not able to register it on codechef... plz help me...

"contest_problem_id field

define @ 28 Mar 2010 08:35 PM

"contest_problem_id field is required." ... the same error display occurs everytime ...

however i see that my solutions were submitted ...:) so as long as it is submitted ... no problemo ...

Those who need

nice coder @ 28 Mar 2010 08:38 PM

Those who need solution...

 

#include<iostream>

using namespace std;

 

 

void merge_sort(char x[], int end, int start) {

int j = 0;

const int size = start - end + 1;

int mid = 0;

int mrg1 = 0;

int mrg2 = 0;

char executing[3000];

 

if(end == start)

return;

 

mid = (end + start) / 2;

 

merge_sort(x, end, mid);

merge_sort(x, mid + 1, start);

 

for(j = 0; j < size; j++)

executing[j] = x[end + j];

 

mrg1 = 0;

mrg2 = mid - end + 1;

 

for(j = 0; j < size; j++) {

if(mrg2 <= start - end)

if(mrg1 <= mid - end)

if(executing[mrg1] < executing[mrg2])

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

else

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

}

}

 

 

 

int main()

{

int t;

cin>>t;

cin.ignore('n',10);

char str[3000],str1[3000],result[3000];

int end,pos;

while(t--)

{

cin.getline(str,3000);

end=cin.gcount();

pos=int(str[end-2]-48)-1;

end-=3;

for(int i=0;i<end;i++){

str1[i]=str[i];

}

merge_sort(str1, 0, end-1);

for(int i=0;i<end;i++){

result[i]=str[pos];

str[pos]='@';

for(int j=0;j<end;j++){

if(str[j]==str1[pos]){

pos=j;

break;

}

}

}

result[end]='';

cout<<result<<endl;

}

return 0;

}

which compiler r u using??? y

cinash_team @ 28 Mar 2010 08:38 PM

which compiler r u using??? y is iostream.h giving compilation error?

#include<iostream> using

nice coder @ 28 Mar 2010 08:39 PM
#include<iostream>
using namespace std;
void merge_sort(char x[], int end, int start) {
int j = 0;
const int size = start - end + 1;
int mid = 0;
int mrg1 = 0;
int mrg2 = 0;
char executing[3000];
if(end == start)
return;
mid = (end + start) / 2;
merge_sort(x, end, mid);
merge_sort(x, mid + 1, start);
for(j = 0; j < size; j++)
executing[j] = x[end + j];
mrg1 = 0;
mrg2 = mid - end + 1;
for(j = 0; j < size; j++) {
if(mrg2 <= start - end)
if(mrg1 <= mid - end)
if(executing[mrg1] < executing[mrg2])
x[j + end] = executing[mrg2++];
else
x[j + end] = executing[mrg1++];
else
x[j + end] = executing[mrg2++];
else
x[j + end] = executing[mrg1++];
}
}
int main()
{
int t;
cin>>t;
cin.ignore('n',10);
char str[3000],str1[3000],result[3000];
int end,pos;
while(t--)
{
cin.getline(str,3000);
end=cin.gcount();
pos=int(str[end-2]-48)-1;
end-=3;
for(int i=0;i<end;i++){
str1[i]=str[i];
}
merge_sort(str1, 0, end-1);
for(int i=0;i<end;i++){
result[i]=str[pos];
str[pos]='@';
for(int j=0;j<end;j++){
if(str[j]==str1[pos]){
pos=j;
break;
}
}
}
result[end]='';
cout<<result<<endl;
}
return 0;
}

#include<iostream> using

nice coder @ 28 Mar 2010 08:40 PM

#include<iostream>

using namespace std;

 

 

void merge_sort(char x[], int end, int start) {

int j = 0;

const int size = start - end + 1;

int mid = 0;

int mrg1 = 0;

int mrg2 = 0;

char executing[3000];

 

if(end == start)

return;

 

mid = (end + start) / 2;

 

merge_sort(x, end, mid);

merge_sort(x, mid + 1, start);

 

for(j = 0; j < size; j++)

executing[j] = x[end + j];

 

mrg1 = 0;

mrg2 = mid - end + 1;

 

for(j = 0; j < size; j++) {

if(mrg2 <= start - end)

if(mrg1 <= mid - end)

if(executing[mrg1] < executing[mrg2])

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

else

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

}

}

 

 

 

int main()

{

int t;

cin>>t;

cin.ignore('n',10);

char str[3000],str1[3000],result[3000];

int end,pos;

while(t--)

{

cin.getline(str,3000);

end=cin.gcount();

pos=int(str[end-2]-48)-1;

end-=3;

for(int i=0;i<end;i++){

str1[i]=str[i];

}

merge_sort(str1, 0, end-1);

for(int i=0;i<end;i++){

result[i]=str[pos];

str[pos]='@';

for(int j=0;j<end;j++){

if(str[j]==str1[pos]){

pos=j;

break;

}

}

}

result[end]=NULL;

cout<<result<<endl;

}

return 0;

}

Copy and paste the solution

nice coder @ 28 Mar 2010 08:42 PM

Copy and paste the solution in ur source file...

I logged into my account + I

Debanjan @ 28 Mar 2010 08:47 PM

I logged into my account + I have registerd my team,how to login to my team,how to login from my team account ? Am i need to login in both ?

@nice coder: It was required

manthan @ 28 Mar 2010 08:49 PM

@nice coder: It was required for you to register both at Codefest and Codechef to participate in the contest.

@Debanjan: Login on codechef

manthan @ 28 Mar 2010 08:52 PM

@Debanjan: Login on codechef website with your team handle and password.

I have registered with the

Debanjan @ 28 Mar 2010 08:56 PM

I have registered with the team name CodersOfPhoenix but I forgot my password,what to do ?

@CodeFest But u must had

nice coder @ 28 Mar 2010 08:57 PM

@CodeFest But u must had provided the option to register even during the contest is taking place... I hv made the solution but not able to submit it... :-(

@CodeFest i think my solution

nice coder @ 28 Mar 2010 08:58 PM

@CodeFest i think my solution is correct which i hv provided above...!!!!!!!!

@Debanjan: Logout and when

manthan @ 28 Mar 2010 09:01 PM

@Debanjan: Logout and when you try to login use the option of forgot password

@nice coder: Rules for

manthan @ 28 Mar 2010 09:03 PM

@nice coder: Rules for registration were clearly mentioned on codechef website. You can still try to solve the problems, this will help you to understand the solutions when they will be released.

why our team is not listed in

cro1 @ 28 Mar 2010 09:07 PM

why our team is not listed in eligible list? we registered on codefest with same name.

is there no way of submitting

3fools @ 28 Mar 2010 09:11 PM

is there no way of submitting the solution ..................................i m constantly getting internal error in system............kindly resolve it

@Musketiri : Eligible team

manthan @ 28 Mar 2010 09:23 PM

@Musketiri : Eligible team section shows invalid data. All teams registered on Codechef wenbsite and listed at http://www.codechef.com/teams/list/MANTH10/ are eligible for prizes if they form a team for Manthan at Codefest website with same team members. The team names can be different.

@titan: We are trying to resoolve your issue. Please be patient. We will let you know as soon as the problem is resolved.

is anybody dere ??? i m

3fools @ 28 Mar 2010 09:30 PM

is anybody dere ??? i m unable 2 submit a single solution..........seems like a dead end.............constantly giving internal system error why so???

@titan: please check your my

manthan @ 28 Mar 2010 09:42 PM

@titan: please check your my submissions page. Can you see your submissions on that page?

#include<iostream> using

witwiki @ 28 Mar 2010 09:50 PM

#include<iostream>
using namespace std;
 
 
void merge_sort(char x[], int end, int start) {
int j = 0;
const int size = start - end + 1;
int mid = 0;
int mrg1 = 0;
int mrg2 = 0;
char executing[3000];
 
if(end == start)
return;
 
mid = (end + start) / 2;
 
merge_sort(x, end, mid);
merge_sort(x, mid + 1, start);
 
for(j = 0; j < size; j++)
executing[j] = x[end + j];
 
mrg1 = 0;
mrg2 = mid - end + 1;
 
for(j = 0; j < size; j++) {
if(mrg2 <= start - end)
if(mrg1 <= mid - end)
if(executing[mrg1] < executing[mrg2])
x[j + end] = executing[mrg2++];
else
x[j + end] = executing[mrg1++];
else
x[j + end] = executing[mrg2++];
else
x[j + end] = executing[mrg1++];
}
}
 
 
 
int main()
{
int t;
cin>>t;
cin.ignore('n',10);
char str[3000],str1[3000],result[3000];
int end,pos;
while(t--)
{
cin.getline(str,3000);
end=cin.gcount();
pos=int(str[end-2]-48)-1;
end-=3;
for(int i=0;i<end;i++){
str1[i]=str[i];
}
merge_sort(str1, 0, end-1);
for(int i=0;i<end;i++){
result[i]=str[pos];
str[pos]='@';
for(int j=0;j<end;j++){
if(str[j]==str1[pos]){
pos=j;
break;
}
}
}
result[end]=NULL;
cout<<result<<endl;
}
return 0;
}

on clicking mysubmission page

3fools @ 28 Mar 2010 09:51 PM

on clicking mysubmission page it says page not found

what will be d output for

sankalp91 @ 28 Mar 2010 09:55 PM
what will be d output for aabbcc 6??

@Sankalp: We can only help to

manthan @ 28 Mar 2010 10:02 PM

@Sankalp: We can only help to explain the sample test cases, if required, during the contest.

@titan: Thats a really wierd problem. Codechef guys are currently working on your problem and will let you know as soon as the issue is resolved

hey, i cant submit any

origamy @ 28 Mar 2010 10:49 PM

hey, i cant submit any solution. there is no submit button for submission although i am logged in. may be this problem is because my profile name is same as my team name. what should i do now???

titan, what is the name of

. @ 28 Mar 2010 11:54 PM

titan, what is the name of your team?

I also had (well, probably still have) the same problem of not being able to submit solutions and I think the problem could be because of my team name. I entered '.' symbol as my team name (I was surprised that the system allowed me to do that) and I can't submit code or even open team profile page.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of computer programming. At CodeChef we work hard to revive the geek in you by hosting programming contests on a monthly basis. We also aim to have training sessions and events related to online programming for programmers around the world. Apart from providing a platform for programming competitions, CodeChef also has various tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our judge accepts solutions in over 35+ programming languages. Online programming was never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming competitions that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly programming contests and the shorter format Cook-off programming contests. Put yourself up for recognition and win great prizes. Prizes worth up to Rs.20,000 and $700 are up for grabs every month along with lots more CodeChef goodies.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be part of CodeChefs Forums and interact with all our programmers love helping out other programmers and share their ideas.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. Be a part of the CodeChef community through CodeChef meetups and techtalks. You can also host a programming contest for your institute on CodeChef and be a guest author on our blog.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com