Friday, January 31, 2014

codechef ROWCOLOP - "row and column operations" solution

codechef ROWCOLOP - "row and column operations" :  http://www.codechef.com/problems/ROWCOLOP/
codechef ROWCOLOP - "row and column operations" editorial :  http://discuss.codechef.com/questions/6643/rowcolop-editorial

codechef ROWCOLOP - "row and column operations" draft : http://ideone.com/sJiw9Z
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int n, q, r[314160], c[314160], max[314160], ans, b, d;
char s[10];
ans=0;
memset(r, 0, sizeof(r));
memset(c, 0, sizeof(c));
memset(max, 0, sizeof(max));
scanf("%d%d", &n, &q);
for(int i=0; i<q; i++) {
scanf("%s%d%d", s, &b, &d);
if(s[0]=='R') c[b-1]+=d;
else r[b-1]+=d;
}
for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(r[i]+c[j]>max[i]) {
max[i]=r[i]+c[j];
if(max[i]>ans) ans=max[i];
}
printf("%d", ans);
return 0;
}

codechef ROWCOLOP - "row and column operations" solution :  http://ideone.com/GRdwpH

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int n, q, r[314160], c[314160], mc, mr, b, d;
char s[10];
memset(r, 0, sizeof(r));
memset(c, 0, sizeof(c));
mc=-1;
mr=-1;
scanf("%d%d", &n, &q);
for(int i=0; i<q; i++) {
scanf("%s%d%d", s, &b, &d); 
if(s[0]=='R') c[b-1]+=d;
else r[b-1]+=d;
}
for(int i=0; i<n; i++) if(r[i]>mr) mr=r[i];
for(int i=0; i<n; i++) if(c[i]>mc) mc=c[i];
printf("%d\n", mc+mr);
return 0;
}

note: 2-d array with that large number is impossible. so instead lets have two 1-d array, for columns and rows. when "rowadd" we increase our column array's row index indicated at "rowadd". we apply the same to our row array. by doing so, we now know exact amount of our imaginary array[i][j] by looking at our column array r[i] and row array c[j]. so, maximum number of array[][] will be also, max r[] + max c[]. my draft gives TLE, i posted my draft so that by looking at my draft you can easily get the point.

codechef DIRECTI - "reversing directions" solution

codechef DIRECTI - "reversing directions" : http://www.codechef.com/problems/DIRECTI

codechef DIRECTI - "reversing directions" solution :  http://ideone.com/Pwnt6i

#include<stdio.h>
#include <string.h>

int main()
{
    char tem,a[60][60];
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
              scanf("%d",&n);
              scanf("%c",&tem);
              for(i=0;i<n;i++)
                              gets(a[i]);
              /*for(i=0;i<n;i++)
                              puts(a[i]);
              */printf("Begin");
              if(a[n-1][0]=='R')
                                for(j=5;j<strlen(a[n-1]);j++)
                                                             printf("%c",a[n-1][j]);
              else if(a[n-1][0]=='L')
                                for(j=4;j<strlen(a[n-1]);j++)
                                                             printf("%c",a[n-1][j]);
              printf("\n");
              for(i=(n-2);i>=0;i--)
              {
                        if(a[i+1][0]=='R') 
                        {
                                           printf("Left");
                                           if(a[i][0]=='L')
                                                           j=4;
                                           else
                                               j=5;                   
                                           for(;j<strlen(a[i]);j++)
                                                                        printf("%c",a[i][j]);
                                           printf("\n");
                        }          
                        else if(a[i+1][0]=='L') 
                        {
                                           printf("Right");
                                           if(a[i][0]=='L')
                                                           j=4;
                                           else
                                               j=5;                   
                                           for(;j<strlen(a[i]);j++)
                                                                        printf("%c",a[i][j]);
                                           printf("\n");
                        }
              }
              printf("\n");
    }
    scanf("%c%c",&tem,&tem);
    return 0;
}

note: i was damn tired of gets(). later, i learned from stackoverflow that gets() function was officially deprecated. so i switched to c from c++, and tried my chance there, still no. so i glanced other AC codes, and mine was almost same with the above code, but still runtime error. since i dont know how to read whole line other than gets(), i just copy pasted at the end :(

codechef ATTIC - "attic crossing" solution

codechef ATTIC - "attic crossing" : http://www.codechef.com/problems/ATTIC
codechef ATTIC - "attic crossing" editorial : http://discuss.codechef.com/questions/15030/attic-editorial

codechef ATTIC - "attic crossing" solution :  http://ideone.com/MSO5OR

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, day, max, step;
char s[1000009];
scanf("%d", &t);
while(t--) {
day=0;
max=0;
step=0;
scanf("%s", s);
for(int i=0; i<strlen(s); i++) {
if(s[i]=='#') day=0;
else day++;
if(day>max && s[i+1]=='#') {
max=day;
step++;
}
}
printf("%d\n", step);
}
return 0;
}

Tuesday, January 28, 2014

codechef LUCKY5 - "lucky long" solution

codechef LUCKY5 - "lucky long" : http://www.codechef.com/problems/LUCKY5

codechef LUCKY5 - "lucky long" solution :  http://ideone.com/O9tKEU

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, cnt;
char s[1000000];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
cnt=0;
for(int i=0; i<strlen(s); i++) if(s[i]!='4' && s[i]!='7') cnt++;
printf("%d\n", cnt);
}
return 0;
}

codechef RIGHTRI - "chef and the right triangles" solution

codechef RIGHTRI - "chef and the right triangles" : http://www.codechef.com/problems/RIGHTRI
codechef RIGHTRI - "chef and the right triangles" editorial :  http://discuss.codechef.com/questions/21667/rightri-editorial

codechef RIGHTRI - "chef and the right triangles" solution :  http://ideone.com/y4pOmO

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
int n, x1, y1, x2, y2, x3, y3, cnt;
scanf("%d", &n); 
cnt=0;
while(n--) {
scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
if (((y2-y1)*(y3-y2))==-((x2-x1)*(x3-x2)))
cnt++;
else if (((y1-y2)*(y3-y1))==-((x1-x2)*(x3-x1)))
cnt++;
else if (((y3-y1)*(y2-y3))==-((x3-x1)*(x2-x3)))
cnt++;
}
printf("%d", cnt);
return 0;
}

note: when angle is right, it means that two lines are perpendicular, which means that one angle is 90 degree, so how we know whether any two lines are perpendicular or not, by calculating their slope:  http://www.mathsisfun.com/gradient.html

UVa 12646 - Zero or One solution

UVa 12646 - Zero or One: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4375

UVa 12646 - Zero or One solution: http://ideone.com/fuhEML

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
int a, b, c;
while(scanf("%d%d%d", &a, &b, &c)==3) {
if(a!=b && a!=c) printf("A");
else if(b!=a && b!=c) printf("B");
else if(c!=a && c!=b) printf("C");
else printf("*");
printf("\n");
}
return 0;
}

note: it is my 1st prob solution ever on UVa. 

Monday, January 27, 2014

codechef TAVISUAL - "the ball and cups" solution

codechef TAVISUAL - "the ball and cups" : http://www.codechef.com/problems/TAVISUAL
codechef TAVISUAL - "the ball and cups" editorial: http://discuss.codechef.com/questions/7694/tavisual-editorial

codechef TAVISUAL - "the ball and cups" solution: http://ideone.com/rUl3RJ

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
int t, n, c, q, l, r, temp;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &c, &q);
for(int i=0; i<q; i++) {
scanf("%d%d", &l, &r);
if(c>=l && c<=r) {
temp=c-l;
c=r-temp;
}
}
printf("%d\n", c);
}
return 0;
}

note: place where cup stays(c), will change if only it falls between left and right changes(if(c>=l && c<=r)). after change cup's new position will be the the difference it had with left change before the change occurs(temp=c-l; c=r-temp;)

Sunday, January 26, 2014

codechef KNIGHTMV - "correctness of knight move" solution

codechef KNIGHTMV - "correctness of knight move": http://www.codechef.com/problems/KNIGHTMV
codechef KNIGHTMV - "correctness of knight move" editorial :  http://discuss.codechef.com/questions/4132/knightmv-editorial

codechef KNIGHTMV - "correctness of knight move" solution :  http://ideone.com/hPy4KW

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
int t, flag;
char s[15];
scanf("%d", &t);
getchar();
while(t--) {
flag=0;
gets(s);
if(s[0]<'a' || s[0]>'h' || s[1]<'1' || s[1]>'8' || s[2]!='-' || s[3]<'a' || s[3]>'h' || s[4]<'1' || s[4]>'8' || strlen(s)!=5) {
cout<<"Error"<<endl;
}
else {
if(s[0]>s[3]) {
if(s[1]>s[4]) {
if(s[0]-s[3]==1 && s[1]-s[4]==2) flag=1;
else if(s[0]-s[3]==2 && s[1]-s[4]==1) flag=1;
}
else {
if(s[0]-s[3]==1 && s[4]-s[1]==2) flag=1;
else if(s[0]-s[3]==2 && s[4]-s[1]==1) flag=1;
}
}
else {
if(s[1]>s[4]) {
if(s[3]-s[0]==1 && s[1]-s[4]==2) flag=1;
else if(s[3]-s[0]==2 && s[1]-s[4]==1) flag=1;
}
else {
if(s[3]-s[0]==1 && s[4]-s[1]==2) flag=1;
else if(s[3]-s[0]==2 && s[4]-s[1]==1) flag=1;
}
}
if(flag==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}

note: pay attn to difference between <cstdio> and <stdio.h>, i damn used and tried many times gets(), etc with <cstdio>, verdict was always WA, but i changed it to <stdio.h>, AC :)

also, imho many use of && in if condition brings prob may be, i dont know :( my code did not work on that

c/c++ getchar() in detail

c/c++ getchar() in detail :  http://rabbit.eng.miami.edu/class/een218/getchar.html


Using Getchar

The getchar() function is another part of the old C library. It is the most basic input function there is, and is very useful in building your own more complex input operations when the provided cin ones aren't up to the job. To use getchar(), your program must #include <stdio.h>

getchar() has no parameters. Every time you call it, it reads the next character of input and returns it to you. The function returns an int, being the ASCII code of the relevant character, but you can assign the result to a char variable if you want.


Press ENTER to continue

Here's a simple example: The "press ENTER to continue" operation that is used when a program produces a lot of output, and the reader needs to be given a chance to read it. The function should print "press ENTER to continue", then wait until ENTER actually is pressed, ignoring all other keypresses. Very simple.
         void PressEnterToContinue(void)
         { printf("Press ENTER to continue: ");
           char c=getchar();
           while (c != '\n')
             c=getchar(); }
Except of course, things are never quite that simple, even in this case. What if there is no more input? The user might type control-D (or on windows control-Z) to signify End Of File, or the user might have redirected the program's input channel so that it is receiving from a file, and that file could just end.

        If either of those things happens, this program will just continue to run for ever. Getchar really does strictly obey its rules. It always gives you the next input character. If it hasn't been typed yet, then of course it waits, but if the input file has ended, there is nothing to wait for. It gives you the special value EOF, over and over again. Any program that enters a loop waiting for some particular input should be designed to survive unexpected end of files.

        Fortunately, that is very easy. Just stop the loop if c is EOF:
         void PressEnterToContinue(void)
         { printf("Press ENTER to continue: ");
           char c=getchar();
           while (c != '\n' && c != EOF)
             c=getchar(); }
Personally, I don't like even that little bit of repeated code, where a character has to be read once before the loop is entered, and then again inside the loop. It makes it too easy to make mistakes when the program is modified in the future to meet slightly different requirements. I would probably prefer something like this:
         void PressEnterToContinue(void)
         { printf("Press ENTER to continue: ");
           while (true)
           { char c=getchar();
             if (c=='\n' || c==EOF) break; } }

A word about EOF

The value of EOF is always defined to be -1. That works well because all ASCII codes are positive, so it can't possibly clash with any real character's representation. Unfortunately, C and C++ have a very strange feature that can cause trouble. It is not defined what the range of possible values for a char variable must be. On some systems it is -128 to +127, which is fine; but on other systems it is 0 to +255, which is fine for normal ASCII values, but not so hot for EOF's -1.

Generally it is best to store getchar()'s result in an int guaranteeing that EOF is properly handled.

So the final version might be this:
         void PressEnterToContinue(void)
         { printf("Press ENTER to continue: ");
           while (true)
           { int c=getchar();
             if (c=='\n' || c==EOF) break; } }
You might reasonably think that using a signed char to receive the result of getchar() would be even better. It should be. But things are not always as they should be in C++. The ReadLine function (next) explains what is wrong.



Reading a Whole Line

C++'s cin functions like to skip white space before they do anything (although that can be changed with an input stream manipulator), and generally stop reading as soon as they find a second patch of white-space. It is quite aggravating when you want to read a whole line. Using getchar it is extremely easy.

Start with an empty string, and enter a loop. Each time round the loop, read a single character. If it is the newline character (or EOF), then exit from the loop. Otherwise just add the new character to the end of the string. When the loop is finished, you've got the whole line of input, totally unmolested, in the string.
         string ReadLine(void)
         { string s = "";
           while (true)
           { char c = getchar();
             if (c=='\n' || c==EOF) break;
             s=s+c; }
           return s; }
And that really is it this time.

Except for one thing. We have the problem of not knowing whether EOF (which is -1) is going to be properly representable on any given system. The majority of C++ systems these days seem to allow negative char values, so it will normally work out fine. But platform-independence is a good thing. It would be nice if we could safely run the same program on all computers. What if we come across a computer that makes char variables unsigned by default?

The natural thing to try is to make the variable c be explicitly declared as signed, so we would have signed char c = getchar(); That should be the perfect solution. But it doesn't work. Absurdly, C++ knows how to add a normal char to the end of a string, but not how to add a signed char to the end of a string. You'd get a compilation error.

Another thing to try would be declaring c as an int, which would also get an error. The only things that C++ knows how to add to the ends of strings are plain chars and other strings.

Usually the best solution is to save the result of getchar() in an int variable, and use a Type Cast to convert it to a char just as it is being added to the end of the string. The fully correct version would look like this:
         string ReadLine(void)
         { string s = "";
           while (true)
           { int c = getchar();
             if (c=='\n' || c==EOF) break;
             s=s+(char)c; }
           return s; }
And really, every use of getchar() should be handled in the same way. Always keep its result in an int.

What would go wrong?

On a computer that has unsigned char variables by default, what could the problem be? It is the result of C's and C++'s rules for mixed-type operations. When we read past the end of the input file, and the value -1 (EOF) is stored in an unsigned charvariable, it takes on the value of 255 (that's the way negatives work in binary). The value of EOF is assumed to be an int, so when testing for EOF, we have c==EOF, the test actually performed is 255==-1, which is of course false. So EndOfFile conditions would never be detected.



Reading a Comma-Delimited List

An almost identical function can be used to read strings that don't necessarily occupy whole lines, but are not delimitted (begun and ended) with spaces. A common alternative is to use commas or colons as the delimiter, especially when dealing with real names that could have spaces in them.

The need is for a function that will read a string, stopping when it reaches a colon (or any other character you designate) OR the end of the line. It makes sense to have the delimiter character as a parameter:
         char terminator = 0;

         string ReadDelimitedString(char marker)
         { string s = "";
           while (true)
           { int c = getchar();
             if (c==marker || c=='\n' || c==EOF) break;
             s=s+(char)c; }
           terminator=c;
           return s; }
What is the global variable terminator for? Well, after reading a string that may have beed terminated by a colon or may have been terminated by the end of the line, perhaps you want to know what the terminator actually was. Perhaps you care how many strings are on each line. Perhaps each line contains colon-separated strings describing one object or person. After calling ReadDelimitedString just look at that global variable, if terminator=='\n' then you know that you have finished a whole line of input.



Reading a Squashed Number

C++'s cin is fine for reading properly delimited numbers. If we have a date written as three separate integers (year, month, date), for example 2004 2 12, the basic cin >> operations will read all three perfectly.

Very often, we like to leave out unnecessary characters in files to reduce their size and make other processing easier. Dates are very often written still as three numbers, but with no spaces, so the above example date would be 20040212. Even though we know that it consists of a four digit number followed immediately by two two digit numbers, there is nothing that can be done with it using cin's normal operations. You would have to read the whole thing as a string, perform substring operations to extract the three parts, then convert each of those three substrings to ints separately (another thing C++ isn't too good at!).

Wouldn't it be nice if we had a function that would read an int of a particular known number of digits, and not require spaces around it? That's very easy using getchar:
         int ReadInt(int size)
         { int value=0;
           for (int i=0; i<size; i+=1)
           { char c=getchar();
             if (c==' ') c='0';
             value=value*10+c-'0'; }
           return value; }
A nice simple little function, but it may need to have a few things explained.

Why don't we bother with reading c as an int? We could, but there is no need. When we are never going to compare c with EOF, no problems can arise.

What is that "if (c==' ') c='0';" line? It isn't necessarily necessary, but it may be that when the month or day number only requires one digit, it could be typed with a space instead of the (logically unnecessary) zero, so just treating spaces as zeros keeps it working properly.

What is that "value=value*10+c-'0';" line? That is the one that does the conversion from just a bunch of characters into a single int. If value contains what we've read so far, that kind of operation is necessary to keep it updated. Consider reading the number1234: at some point you will already have read the 12 and understood it as twelve. When you read the next character 3, the whole thing read so far is 123, so value should be one hundred and twenty three. Given twelve and three, how do you get to one hundred and twenty three? Multiply by ten and add. That's what is happening.

Except for the -'0': That is to handle the ASCII coding. The character '0' is not the same thing as the integer value zero. Characters are represented by their ASCII codes. The code for '0' is 48, the code for '1' is 49, the code for '2' is 50, the code for'3' is 51, the code for '9' is 57, but you don't need to remember that. Just knowing that the follow a logical pattern starting with '0' is enough. To convert an ASCII code to the correct int, just subtract the ASCII code for zero. Take three as an example:'3'-'0' = 51-48 = 3. Its always the same.

So, using that nice little function, we can read compressed dates very easily:

        { int year=ReadInt(4);
          int month=ReadInt(2);
          int day=ReadInt(4);




Whenever an input situation is too much for cin to handle, getchar is there to rescue us. There's nothing it can't do.

As with printf, you should not use getchar and cin in the same program: two different systems both fighting over control and processing of what you type can lead to errors.









Saturday, January 25, 2014

codechef NOCODING - "code crazy minions" solution

codechef NOCODING - "code crazy minions" : http://www.codechef.com/problems/NOCODING
codechef NOCODING - "code crazy minions" editorial :  http://discuss.codechef.com/questions/2098/nocoding-editorial

codechef NOCODING - "code crazy minions" solution : http://ideone.com/xhzG43

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, a;
char s[1005];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
a=2;
for(int i=1; i<strlen(s); i++) {
a += (s[i]-s[i-1]+26)%26 + 1;
}
if(a<=strlen(s)*11) printf("YES\n");
else printf("NO\n");
}
return 0;
}

note: "a" is the total cost. a=2, because we load and print 1st letter(char s[0]). start move cost from second letter(s[1]) to last letter (s[n-1]). and every move between letters cost (s[i]-s[i-1]+26)mod 26, because it is cyclical motion of the alphabet. and add 1 for every cycle, because loading or printing, whatsoever costs 1. 

codechef LUCKYSTR - "little elephant and strings" solution

codechef LUCKYSTR - "little elephant and strings" : http://www.codechef.com/problems/LUCKYSTR

codechef LUCKYSTR - "little elephant and strings" solution: http://ideone.com/DtYOZ7

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int k, n, flag;
char f[55][55], s[55];
scanf("%d%d", &k, &n); 
for(int i=0; i<k; i++) scanf("%s", f[i]);
for(int i=0; i<n; i++) {
scanf("%s", s);
flag=0;
if(strlen(s)>=47) printf("Good\n");
else {
for(int j=0; j<k; j++) {
if(strstr(s, f[j])) {
flag=1;
break;
}
}
if(flag) printf("Good\n");
else printf("Bad\n");
}
}
}

note: i was damn tired of coding bugs, when i was trying to solve this problem. add to that previous days i had failed to solve "arrange" and "equation" problems at codechef. but then i came up with "strstr" function in <cstring> header : http://en.cppreference.com/w/cpp/string/byte/strstr

Thursday, January 23, 2014

check whether if site is down or not

check whether if site is down or not

all night long i could not get into ideone, so i googled "ideone is down" and i came up with is it down right now dot com: http://www.isitdownrightnow.com/
if the site is up, follow the troubleshooting instructions:

If the site is UP but you cant access the page, try one of the below solutions:
Browser Related Problems
Force a full refresh for the site. This can be achieved by pressing CTRL + F5 keys at the same time on your favourite browser (Firefox, Chrome, Explorer, etc.)
Clear the temporary cache and cookies on your browser to make sure that you have the most recent version of the web page. For instructions choose your browser :   
Fix DNS Problems
A Domain Name System (DNS) allows a site IP address (192.168.x.x) to be identified with words (*.com) in order to be remembered more easily, like a phonebook for websites. This service is usually provided by your ISP.
Clear your local DNS cache to make sure that you grab the most recent cache that your ISP has. For Windows - (Start > Command Prompt > type "ipconfig /flushdns" and hit enter). For details choose your operating system :   
If you can access a website at office or from a 3G network yet it's not working on your computer, it is a good idea to use an alternative DNS service other than your ISPs.OpenDNS or Google Public DNS are both excellent and free public DNS services.
Check our help page for step-by-step instructions on how to change your DNS.

Tuesday, January 21, 2014

codechef LEBOMBS - "little elephant and bombs" solution

codechef LEBOMBS - "little elephant and bombs": http://www.codechef.com/problems/LEBOMBS

codechef LEBOMBS - "little elephant and bombs" solution: http://ideone.com/640R3v

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, n, cnt, a[1005];
char c[1005];
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
cnt=0;
memset(a, 0, sizeof(a));
scanf("%s", c);
for(int i=0; i<strlen(c); i++) {
if(c[i]=='0' && i==0) a[i]=0;
else if(c[i]=='1' && i==0) a[i]=a[i+1]=1;
else if(c[i]=='1' && i==n-1) a[i-1]=a[i]=1;
else if(c[i]=='1') a[i-1]=a[i]=a[i+1]=1;
}
for(int i=0; i<n; i++) if(a[i]==0) cnt++;
printf("%d\n", cnt);
}
return 0;
}

Monday, January 20, 2014

codechef HELLO - "hello hello" solution

codechef HELLO - "hello hello" : http://www.codechef.com/problems/HELLO

codechef HELLO - "hello hello" solution: http://ideone.com/RnU22b

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
int t, u, n, m, c, no;
double r, d, a, b;
scanf("%d", &t);
while(t--) {
scanf("%lf%d%d", &d, &u, &n);
no=0;
b=d*u;
for(int i=0; i<n; i++) {
scanf("%d%lf%d", &m, &r, &c);
a=u*r+c/(double)m; 
if(a<b) { b=a; no=i+1; }
}
printf("%d\n", no);
}
return 0;
}

note: the minimum plan(a) that is lesser than actual monthly plan(b) would be helpful for chef, which is a<b, and print out that index(no)

codechef TOTR - "tourist translations" solution

codechef TOTR - "tourist translations" :  http://www.codechef.com/problems/TOTR

codechef TOTR - "tourist translations" solution: http://ideone.com/FwN23v

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, m1[30];
char m[30], s[105];
scanf("%d%s", &t, m);
for(int i=0; i<strlen(m); i++) m1[i]=m[i]-'a';
for(int i=0; i<t; i++) {
scanf("%s", s);
for(int j=0; j<strlen(s); j++) {
if(s[j]>='A' && s[j]<='Z') {
printf("%c", m1[s[j]-65]+65);
}
else if(s[j]>='a' && s[j]<='z') {
printf("%c", m1[s[j]-97]+97);
}
else if(s[j]=='_') printf(" ");
else printf("%c", s[j]);
}
printf("\n");
}
return 0;
}

note: imho, here is only imp thing is just char conversions, look at the ascii table to understand the logic behind number 65 for capital letters and 97 for lowercase letters

Sunday, January 19, 2014

codechef LELEMON - "little elephant and lemonade" solution

codechef LELEMON - "little elephant and lemonade" : http://www.codechef.com/problems/LELEMON

codechef LELEMON - "little elephant and lemonade" solution:  http://ideone.com/Mh6hGf

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);}

int main() {
int t, n, m, p[105], c[105], cnt, tot, a, b;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
tot=0;
memset(p, 0 ,sizeof(p));
for(int i=0; i<m; i++) { scanf("%d", &a); p[a]++; }
for(int i=0; i<n; i++) {
scanf("%d", &b); 
memset(c, 0, sizeof(c));
cnt=0;
for(int j=0; j<b; j++) scanf("%d", &c[j]);
qsort(c, b, sizeof(int), cmp);
for(int k=0; k<p[i]; k++) { cnt += c[b-1-k]; if((b-1-k)==0) break; }
tot += cnt;
}
printf("%d\n", tot);
}
return 0;
}

codechef MAXDIFF - "maximum weight difference" solution

codechef MAXDIFF - "maximum weight difference": http://www.codechef.com/problems/MAXDIFF

codechef MAXDIFF - "maximum weight difference" solution: http://ideone.com/n63XxB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);}

int main() {
int t, n, k, w[105], tot, cnt1, cnt2;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
cnt1=cnt2=tot=0;
for(int i=0; i<n; i++) {
scanf("%d", &w[i]);
tot += w[i];
}
qsort(w, n, sizeof(int), cmp);
for(int i=0; i<k; i++) cnt1 += w[i];
for(int i=n-1; i>n-k-1; i--) cnt2 += w[i];
cnt1=abs(cnt1);
cnt2=abs(cnt2);
//cout<<tot<<endl;
if(abs(cnt1-(tot-cnt1))>abs(cnt2-(tot-cnt2))) printf("%d\n", abs(cnt1-(tot-cnt1)));
else (printf("%d\n", abs(cnt2-(tot-cnt2))));
}
return 0;
}

Wednesday, January 15, 2014

codechef LAPIN - "lapindromes" solution

codechef LAPIN - "lapindromes": http://www.codechef.com/problems/LAPIN/

codechef LAPIN - "lapindromes" solution: http://ideone.com/YnIfzK

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, a[30], b[30], n, flag;
char s[1005];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
for(int i=0; i<30; i++) a[i]=b[i]=0;
n=strlen(s); 
for(int i=0; i<n/2; i++) {
a[s[i]-'a']++;
b[s[n-1-i]-'a']++;
}
flag=memcmp(a, b, sizeof(a));
if(flag==0) printf("YES\n");
else printf("NO\n");
}
return 0;
}

note: use memcmp instead of cmomparing every index of array solely, memcmp is a bit faster imho

codechef PLZLYKME - "please like me" solution

codechef PLZLYKME - "please like me": http://www.codechef.com/problems/PLZLYKME

codechef PLZLYKME - "please like me" solution: http://ideone.com/tN7fUo

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
int t;
long long l, d, s, c;
scanf("%d", &t);
while(t--) {
scanf("%lld %lld %lld %lld", &l ,&d, &s, &c);
for(int i=1; i<d; i++) { s+=s*c; if(s>=l) break; }
if(s>=l) printf("ALIVE AND KICKING\n");
else printf("DEAD AND ROTTING\n");
}
return 0;
}

codechef SPCANDY - "splitting candies" solution

codechef SPCANDY - "splitting candies": http://www.codechef.com/problems/SPCANDY

codechef SPCANDY - "splitting candies" solution: http://ideone.com/19BYF0

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
int t;
long long n, k;
scanf("%d", &t);
while(t--) {
scanf("%lld", &n); 
scanf("%lld", &k);
if(k==0) printf("0 %lld\n", n);
else printf("%lld %lld\n", n/k, n%k);
}
return 0;
}

note: just pay attention to k, whether if it is 0 or not

codechef ALEXNUMB - "magic pairs" solution

codechef ALEXNUMB - "magic pairs":http://www.codechef.com/problems/ALEXNUMB

codechef ALEXNUMB - "magic pairs" solution: http://ideone.com/K6W4bu

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
long long int t, n, a;
scanf("%lld", &t);
while(t--) {
scanf("%lld", &n); 
for(int i=0; i<n; i++) scanf("%lld", &a); 
printf("%lld\n", n*(n-1)/2);
}
return 0;
}

codechef JOHNY - "uncle johny" solution

codechef JOHNY - "uncle johny" : http://www.codechef.com/problems/JOHNY

codechef JOHNY - "uncle johny" solution:  http://ideone.com/7HpaqN

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);}

int main() {
int t, k, n, a[105], ans;
scanf("%d", &t);
while(t--) {
scanf("%d", &k);
for(int i=0; i<k; i++) scanf("%d", &a[i]);
scanf("%d", &n); 
ans=a[n-1];
qsort(a, k, sizeof(int), cmp);
for(int i=0; i<k; i++) if(ans==a[i]) printf("%d\n", i+1);
}
return 0;
}

codechef ERROR - "chef and feedback" solution

codechef ERROR - "chef and feedback": http://www.codechef.com/problems/ERROR

codechef ERROR - "chef and feedback" solution: http://ideone.com/h7ahmj

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, flag, n;
char c[100000];
scanf("%d", &t);
while(t--) {
scanf("%s", c); 
flag=0; n=strlen(c);
for(int i=0; i<n-2; i++) {
if(c[i]=='1' && c[i+1]=='0' && c[i+2]=='1') { printf("Good\n"); flag=1; break; }
else if(c[i]=='0' && c[i+1]=='1' && c[i+2]=='0') { printf("Good\n"); flag=1; break; }
}
if(flag==0) printf("Bad\n");
}
return 0;
}

Sunday, January 12, 2014

codechef COMMUTE - "the morning commute" solution

codechef COMMUTE - "the morning commute": http://www.codechef.com/problems/COMMUTE

editorial: http://discuss.codechef.com/problems/COMMUTE

codechef COMMUTE - "the morning commute" solution: http://ideone.com/pHohIL

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
int t, n, x, l, f, a;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%d %d %d", &x, &l, &f);
if(i==0) a=x+l;
else {
if(a<=x) {
a=x; a += l;
}
else {
while(a>x) x += f;
a=x; a += l;
}
}
}
printf("%d\n", a);
}
return 0;
}

guidance: on 1st station(i=0), just add x+l, starting time and time between 1st and 2nd station. however, on following stations, if chef arrived earlier than trains departure time(a<x), then chef waits till train depart(a=x). if chef has missed the train(a>x), then wait till next train depart(x=x+f). then update time(a=x; a=a+l;). follow same approach till last station. that is all.

codechef AMSGAME1 - "subtraction game 1" solution

codechef AMSGAME1 - "subtraction game 1": http://www.codechef.com/problems/AMSGAME1

editorial: http://discuss.codechef.com/questions/10494/amsgame1-editorial

codechef AMSGAME1 - "subtraction game 1" solution: http://ideone.com/JndiG1

#include <iostream>
#include <cstdio>
using namespace std;

unsigned int gcd(unsigned int u, unsigned int v) {
if(u==v) return u;
if(u==0) return v;
if(v==0) return u;
if(~u & 1) {
if(v & 1) return gcd(u>>1, v);
else return gcd(u>>1, v>>1) <<1;
}
if(~v & 1) return gcd(u, v>>1);
if(u>v) return gcd((u-v)>>1, v);
return gcd((v-u)>>1, u);
}

int main() {
int t, n, c[1005], a, b;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(n==1) { scanf("%d", &a); printf("%d\n", a); }
if(n==2) { scanf("%d %d", &a, &b); printf("%d\n", gcd(a, b)); }
if(n>2) {
for(int i=0; i<2; i++)  {
scanf("%d %d", &a, &b); a=gcd(a, b); break;
}
for(int i=2; i<n; i++) {
scanf("%d", &b); a=gcd(a, b); 
}
printf("%d\n", a);
}
}
return 0;
}

note: i used binary gcd here. 

codechef RESQ - "arranging cup-cakes" solution

codechef RESQ - "arranging cup-cakes": http://www.codechef.com/problems/RESQ

editorial:  http://discuss.codechef.com/questions/1123/resq-editorial

codechef RESQ - "arranging cup-cakes" solution:  http://ideone.com/1v3r2t

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main() {
int t, n, a, b, r;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
a=sqrt(n); b=r=0;
for(int i=a; i>0;) {
if(n%i!=0) i--;
else {
b=n/i; r=b-i; break;
}
}
printf("%d\n", r);
}
return 0;
}

codechef RESQ - "arranging cup-cakes"guidance:

 i used 1st approach on the editorial. if you noticed, the question wants "almost" square cup-cakes, that means two divisors needs to be equal or "almost" equal(nearest possible numbers)

Saturday, January 11, 2014

codechef BUY1GET1 - "buy1-get1" solution

codechef BUY1GET1 - "buy1-get1": http://www.codechef.com/problems/BUY1GET1

codechef BUY1GET1 - "buy1-get1" solution:  http://ideone.com/59HWlx

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, n, b[205], cnt;
char s[205];
scanf("%d", &t);
while(t--) {
scanf("%s", s);
n=strlen(s); cnt=0;
for(int i=0; i<n; i++) b[i]=1;
for(int i=0; i<n-1; i++) {
if(b[i]==0) continue;
for(int j=i+1; j<n; j++) {
if(s[i]==s[j]) { b[j]=0; break; }
}
}
for(int i=0; i<n; i++) cnt += b[i];
printf("%d\n", cnt);
}
return 0;
}

codechef RRECIPE - "recipe reconstruction" solution

codechef RRECIPE - "recipe reconstruction": http://www.codechef.com/problems/RRECIPE

editorial: http://discuss.codechef.com/questions/2554/rrecipe-editorial

codechef RRECIPE - "recipe reconstruction" solution: http://ideone.com/7O3u5f

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, r, n;
char s[1000005];
scanf("%d", &t);
while(t--) {
scanf("%s", s); 
r=1; n=strlen(s);
if(n%2==0) {
for(int i=0; i<n/2; i++) {
if(s[i]=='?' && s[n-1-i]=='?') r=(r*26)%10000009;
else if(s[i]!=s[n-1-i] && s[i]!='?' && s[n-1-i]!='?') r *= 0;
else r=(r*1)%10000009;
}
}
else {
for(int i=0; i<(n-1)/2; i++) {
if(s[i]=='?' && s[n-1-i]=='?') r=(r*26)%10000009;
else if(s[i]!=s[n-1-i] && s[i]!='?' && s[n-1-i]!='?') r *= 0;
else r=(r*1)%10000009;
}
if(s[(n-1)/2]=='?') r=(r*26)%10000009;
}
printf("%d\n", r);
}
return 0;
}

Friday, January 10, 2014

codechef LEPERMUT - "little elephant and permutations" solution and guidance

codechef LEPERMUT - "little elephant and permutations": http://www.codechef.com/problems/LEPERMUT

codechef LEPERMUT - "little elephant and permutations" solution: http://ideone.com/zSwh4P

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
int t, n, a[105], n_inv, l_inv;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
n_inv=l_inv=0;
for(int i=0; i<n; i++) scanf("%d", &a[i]);
for(int i=0; i<n-1; i++) for(int j=i+1; j<n; j++) if(a[i]>a[j]) n_inv++;
for(int i=1; i<n; i++) if(a[i-1]>a[i]) l_inv++;
if(l_inv==n_inv) printf("YES\n");
else printf("NO\n");
}
return 0;
}

codechef LEPERMUT - "little elephant and permutations" guidance:

number inverse is all inverse in the loop; however, local inverse is, as name also indicates, consecutive number inverse.


thank God, i am happy with my progression :)

codechef TIDRICE - "popular rice recipe" solution and guidance

codechef TIDRICE - "popular rice recipe": http://www.codechef.com/problems/TIDRICE

codechef TIDRICE - "popular rice recipe" solution: http://ideone.com/5XLror

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
int t, n, v[105], cnt;
char id[105][25], c;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
cnt=0;
for(int i=0; i<n; i++) {
scanf("%s %c", id[i], &c);
(c=='+') ?  v[i]=1 : v[i]=-1;
}
for(int i=n-1; i>0; i--) {
if(v[i]==0) continue;
for(int j=i-1; j>=0; j--) {
if(strcmp(id[i], id[j])==0) v[j]=0;
}
}
for(int i=0; i<n; i++) cnt += v[i];
printf("%d\n", cnt);
}
return 0;
}

codechef TIDRICE - "popular rice recipe" guidance: 

started from backwards, and looped through id array, if dublicate exist nullify dublicates vote(v[j]=0). and then count all votes and print it.

codechef BESTBATS - "top batsmen" solution and guidance

codechef BESTBATS - "top batsmen": http://www.codechef.com/problems/BESTBATS

codechef BESTBATS - "top batsmen" solution: http://ideone.com/QpJR8X


#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int fact(int a) {
return (a==1 || a==0) ? 1 : fact(a-1)*a;
}

int cmp(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}

int main() {
int t, p[12], k, k_th, in, out, tot;;
scanf("%d", &t);
while(t--) {
for(int i=0; i<11; i++) scanf("%d", &p[i]); scanf("%d", &k);
qsort(p, 11, sizeof(int), cmp); 
k_th=p[k-1]; in=out=tot=0;
for(int i=0; i<k; i++) if(k_th==p[i]) in++;
for(int i=k; i<11; i++) if(k_th==p[i]) out++;
tot=in+out;
printf("%d\n", fact(tot)/(fact(in)*fact(tot-in)));
}
return 0;
}

codechef BESTBATS - "top batsmen" guidance:

lets sort scores of players(qsort). here i sorted in decreasing order. the number of ways depends on k_th element, it doesnt matter if all elements except k are equal, the situation wont change. if k_th element has equivalents then it does affect the situation. for 1st case in given sample input, there is no equivalent of k, so only 1 way of output is possible. however, on the 2nd sample input, the k_th element=p[i]=2, and it has 4 equivalents(there exist 4 number "2" in the set). so lets calculate how many different ways there exist. assume, 2nd sample input as a set. A = {2, 5, 1, 2, 4, 1, 6, 5, 2, 2, 1}. after sorting set "A" we get, A = {6, 5, 5, 4, 2, 2, 2, 2, 1, 1, 1}. as you see, k_th element is 2, and there are 4 "2"s, and two of them is in set and other two of them is out of the set. so, lets get another set B, which has elements exactly equivalents of k. B = {2, 2, 2, 2}. and now, lets display all subsets of B so that we can see how many ways there exist for each active(in) and passive(out) equivalents.



Let's look at a set B = {1, 2, 3, 4}. 

There is one subset with no elements { } or ΓΈ. 
There are 4 subsets with 1 element: {1}, {2}. {3}, {4} 
There are 6 subsets with 2 elements: {1, 2}, {2, 3}, {3, 4}, {1, 3} ,{2, 4}, {1, 4} 
There are 4 subsets with 3 elements: {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {1, 2, 4} 
There is one subset with 4 elements, B. 

There are 16 subsets in all. 

The rule is a set with n elements has 2^n subsets.

As you have seen above, whence from four elements, two active(displayed within range of K) and two passive(excluded from K bigger elements), there exist 6 different ways of display. and "6" is actual output of 2nd sample. but what if, of four elements, not two but one was active. then there would be 4 different ways of displaying K bigger elements. what if, three of four were active, then again, 4 different ways of exhibition of K bigger elements. if all or none were active, then only 1 way. 
lets look for sets with lesser elements: 
  
or

as you have seen from above images and examples, according to its total elements and activeness(inclusiveness) of them in K range, their exhibition alter. and the change in their exhibition(subset) has relevancy, in numbers. does that relevancy look familiar. i am hearing as if you confirm. yes, you are right, they pinpoint to pascal triangles:

 1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1

assume the triangle as an array. we have to output just that exact element(here 6) of total elements(4). put total elements as row, and active elements as columns. 2 active, 4 elements, then we need 3rd element of 5th row. and that number is "6", the exact output of 2nd sample. i tried hardly to program that in c++, but i couldnt, however, i realized that i can reach to the same answer with this:
later i learned that through factorials, i can get to that element. how to do it? the image above explains everything ;)