Solution technique of 10684- The jckpot

Problem Description
source: https://uva.onlinejudge.org/external/106/10684.html

Solving Technique:

This is a maximum subarray summation related problem. We have to find the maximum subarray from a one-dimensional array and sum-up all values of sub array then we will get the patterns of consecutive wins that will give maximum benefit and elaborate a win-win strategy.

Using Kadane’s algorithm we can solve in O(n) time.


Kadane’s Algorithm:

Algorithm of 12608 - Garbage Collection

Problem Description Link
Algorithm

This is a simple problem this problem you can solve easily . To solve this problem you must remember 3 conditions.

Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either

1. is full or
2. cannot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
3. there are no more pick up points left

Algorithm of 12405 - Scarecrow

Problem Description Link
Algorithm:
This is a easy problem just you get a string
scan each character until length of string
if character is '.' then replace the next character by '#'  and
increase the counter value and set position=position+2;
some input/output:

Algorithm of 11933 - Splitting Numbers

Problem Description Link
Algorithm:

This is a simple problem the operation of splitting a binary number n into two numbers a(n), b(n) .

you need to convert decimal to binary format for a given number and from that binary format create two numbers

a(n) and b(n). To build first value a(n) need to choice 1^st  1  ,3^rd  1, 5^th  1,..... so on same position of original binary format other position fii by the value 0.

To build second value b(n) need to choice 2^nd  1  ,4^th  1, 6^th  1,..... so on same position of original binary format other position fill by the value 0.

for example

Algorithm of 11407 - Squares

Problem Description Link
Algorithm:

This is a simple problem  to solve this problem you can pre generate the number of minimum terms for all integer from 1 to 10000 and get input and check from array how many  term needed and print the value.

Process:

 For any positive integer N , N = a12 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.

For example you know minimum term of 1,2,3,4 and based on this value calculate others  5 to 10000 value term

1

2

3

1

2

3

4

2

1

2

1                    2                        3              4                              5              6              7                              8              9              10

For 5

S=sqrt(5)=2

Way    2²+1²=5 so 2 term

And  1²+2²=5 so 2 term

Min value=2

So

Algorithm of 11526 - H(n)

Problem Description Link
Algorithm
The problem is not difficult but we need to consider the problem of time limit exceeded, e.g. we are computing n/n, n/n-1, .....there are so many ones and twos,... these can be computed in one step. We can observe the number of 1, 2, 3.....the number of j is n/j - n/(j+1).  so when the number is small and many, we use the n/j - n/(j+1) method. for numbers big and few, just use the original method. We can set the break point at sqrt(n). Do not repeat the values around sqrt(n). Try to avoid division by 0 and sqrt of negative numbers.

Example:
if n=5 series is 5/1 + 5/2 + 5/3 + 5/4 + 5/5
    then sqrt(5)=2 need loop two times
    5/1-5/2=3 means 1 get 3 times, so SUM=3*1=3
    5/2-5/3=1 means 2 get 1 times, so SUM=3+2*1=5
    so last 4 (3+1) steps complete from the series ,so now we nedd calculate first 1 step

Algorithm of 10127 - Ones

Problem Description Link
Algorithm

This is a very simple but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two things can be happened.

1) If your data type is even long double (in C it is the highest data type), it can not hold the sequence and because of overflow you will get WA.
2) If your data type is string then you will get "time limit exceeded". To avoid these problems we need to follow a trick here.

The Algorithm

input (it will be the input of the problem) 
dividend=1
one=1 (in this variable finally we get how many one will be in the sequence)

Algorithm of 713 - Adding Reversed Numbers

Problem Description Link
Algorithm
This is the simple string related problem. You can solve easily using your defined string adding function. you need first
reverse the string that you entered and add two string. after adding print the result reveser order. You must
 Omit any leading zeros in the output.
You no need reverse the inputs if you adding atart from left most. but you nee create same length two string by insert 0.
For Example:
a=4358
b=754
length not same so create same length add 0 in b at right most
b=7540
 now add
a=4358
b=7540
-----------
r=1998 this is the result

if a=305 and b= 794

add
 a=305
 b=794
---------------
r= 0001 so you need avoid all leftmost 0 s, so 1 is the result.

Algorithm of 847 - A Multiplication Game

Problem Description Link
Algorithm
It is a quite hard to find this rule to solve this problem... however if Stan and Ollie plays perfect game, then Stan will always try to multiply p with 9 and Ollie will always try to multiply p with 2... and so on, so just simulate the process  (i.e. for n, you multiply by 9, then multiply by 2, then multiply by 9... etc until p>= n), then check whose turn can make p becomes greater or equal to p and output the winner name.

Algorithm of 401 - Palindromes

Problem Description Link
Algorithm:
This is a simple problem to solve this problem you need to read carefully.
However you can follow this technique to solve this problem.
1. At first you need 3 array for input string , reverse string and mirror string.
2. get input string
3. put value in reverse string array from input string . Last value of input string insert into
    first value of reverse string and so on.
4. put value in mirror string from input string reverse order
    when insert character in follow condition
    if input string character is E then insert 3 and vise versa
    if input string character is L then insert J and vise versa
    if input string character is S then insert 2 and vise versa
    if input string character is Z then insert 5 and vise versa
5. Check reverse string with input string if same put a falg rf=1;
6. for mirror check
    Check mirror string with input string character by character
    if get B,C,D,F,G,K,N,P,Q,R,4,6,7,9 in input string then this sting not mirror string
    otherwise it is mirror so flag mp=1;
N.B: in this problem O and 0(zero) are same.
7. for print check
    if(rp==0 && mp==0)
            printf("%s -- is not a palindrome.\n\n",input);
        else if(rp==1 && mp==0)
            printf("%s -- is a regular palindrome.\n\n",input);
        else if(rp==0 && mp==1)
            printf("%s -- is a mirrored string.\n\n",input);
        else if(rp==1 && mp==1)
            printf("%s -- is a mirrored palindrome.\n\n",input);

Algorithm of 10189 - Minesweeper

Problem Description Link
Algorithm:
In this problem if you compare with "." and increase the adjacent value it is more time consume and get garbage value when row=0 or row=n
 in this case no have 8 adjacent value.
 so you can compare with "*" and generate another 2D value array that contain only value.
 if get "*" in input array then increase the all adjacent value and store that value in value array.
After generating the all value check from input array if character is "*" then print the "*" otherwise print from value array for this position.

Algorithm of 10533 - Digit Primes

Problem Description Link

Algorithm:

This is a simple prime related problem
if a number is a prime then check that if sum of prime digit also prime then this digit is called digit prime
For example the prime number 41 is a digit prime because 4+1=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8 is not a prime number.
But to solve this problem if you follow ittarative way then you may got TLE.
so you must generate prime and digit-prime before goe input.
and follow this technique.
1.pre calculate number of digit primes from 1 to 1000000
2. when you get t1 & t2 , number of digit primes t2 subtract number of digit primes t1-1
3. if t1 = 10, t2 = 100 . Number of digit primes at 10 is 4 and number of digit primes at 100 is 14
so dprime[100] - dprime[10-1] = 14 - 4 = 10
4. print the difference.

Algorithm of 406 - Prime Cuts

Problem Description Link

Algorithm:

This is a prime related problem . In this problem you need to   generate the  prime number from 1 to N.

Where 1 also a prime number in this problem .

After generate the all prime number from 1 to N count the prime numbers check.

 I f prime numbers are even then print the center (c*2) primes  .

I f prime numbers are odd then print the center (c*2-1) primes  .

If center (c*2) for even or (c*2-1) for odd excite the list of all prime numbers then print all prime from 1 to N

For example.

Algorithm of 12043 - Dvisor

Problem Description Link

Algorithm:

In this problem if you use more loop in main program to determine the number of divisor and sum of divisor may be you get time limit exit .
so before test case you must generate two array for divisor and sum_of_divisor and and finally use a loop l
i=a to b and check that if any value i mod k is zero then add div+=divisor[i] and sum+=sum_of_divisor[i];
To generate divisor[] and sum_of_divisor[] you can use siv method
that method is bellow :
at first you must set each element 1 in divisor[] and sum_of_divisor[] after then

Algorithm of 11995 - I Can Guess the Data Structure!

Problem Description Link

Algorithm:

for this problem n=number of line x=element  you can use STL stack , queue, priority_queue
and when get 1 insert data each STL and increase  value for each STL variable(i.e s, q,p)
when get 2 chaeck
    1. for stack check stack not empty and stack top element = x 
        if condition true the pop from stack.
    2. for que  check queue not empty and queue front = x
        if condition true the pop from queue.
    3. for priority queue check priority_queue not empty and  priority_queue top=x
        if condition true the pop from priority_queue.
for each pop increase value that data(ie. s for stack pop ..)

Algorithm of 11936 - The Lazy Lumberjacks

Problem Description Link

Algorithm:

This is a geometric problem . you  can solve this problem easily . you can follow this stapes
1. At first you need three value for three sides (ie. a, b, c)
     N.B.: three sides can formed a triangle if and only if third side is greater than summation of    other two side   .
     where third side is largest value among three sides value .(i.e.:  5, 9, 6 where third side is 9).
2. if possible formed a triangle then you need print
     OK
3. Otherwise print
         Wrong!!

Algorithm of 11876 - N + NOD (N)

Problem Description Link

Algorithm:

To solve this problem you should generate divisor and NOD sequence before get input otherwise you may get time limit exit
NOD value sequence generate by this produce :
Nodvalue[i]=Nodvalue[i-1]+dividor[Nodvalue[i-1]];

when you get input just find the index of value A and B
and difference of index B and A is O/P.
you can use binarry search for find speedy  index of A and B .

Algorithm of 11799 - Horror Dash

Problem Description Link

Algorithm:

In this problem you are to find out the minimum speed
that the clown must maintain so as not to get caught
even if they keep on running forever.

so if you can find the maximum speed then it is the
minimum speed to continue the race
so
1. get input t(test case)
2. get input n(number of students)
3. speed of each students (speed)
    if(speed>max)
        max=speed;
4. print the max.

Algorithm of 11743 - Credit Check

Problem Description Link

Algorithm:

This is a simple you just see the following example
For example, using the number 5181 2710 9900 0012:

   1.  Double the appropriate digits (5181 2710 9900 0012) to obtain the values:(5*2) 10,  (8*2)16,  (2*2)4, (1*2) 2, (9*2) 18, (0*2) 0, (0*2) 0, (1*2)2.
   2.  (10)->(1+0) , (16)->(1+6), 4, 2, (18)->(1+8), 0, 0, 2
    Add up the digits of these values to get (1+0) + (1+6) + 4 + 2 + (1+8) + 0 + 0 + 2 = 25. The sum of the undoubled digits is 1+1+7+0+9+0+0+2 = 20, so the total is 20+25=45.
   3.  45 does not end in a 0, so this credit card number is invalid.

Algorithm of 11727 - Cost Cutting

Problem Description Link

ALgorithm:

This problem determine the medium salary that not lowest or highest.
let a, b and c are salaries and avg is medium salary that
we determine.
1. get input testcase
2. get input a, b, c
3.
           if((b>a and b<c)||(b<a and b>c))
                avg=b;
            else if((c>a and c<b)||(c<a and c>b))
                avg=c;
            else
                avg=a;
4.print the avg.