Friday 15 November 2013

Regionals 2000 :: Europe - Central (UVALive 2158 + HDU 1124 + POJ 1401 + ZOJ 2022 + SPOJ FCTRL)

Problem: Factorial
Tutorial: Trailing Zeros of a Factorial
You are given an integer N, you have to print how many Trailing Zeros N Factorial has.

lets be familiar with the term Factorial. Factorial of a number N is the product of all positive integer less than or equal to N.
Example: 5! = 5*4*3*2*1= 120

Trailing Zeros of a number is the total Zeros the number ends with.
Example: Trailing Zero of 120 is 1,
            Trailing Zero of 153 is 0,
            Trailing Zero of 50300 is 2.

A number will have a trailing zero if the number has 10 as a factor. that means the number should have 2 and 5 as a factor. if we have a pair of 2 & 5, then we can say that it has a trailing zero. so, trailing zero of a number is the minimum of factors of 2 & 5.
wait..
almost all even number has a multiple number of factor 2.
Example: 6! = 6*5*4*3*2*1. has 2 as factors in 2, 4, 6. but there is only one factor of 5 in number 5.
In the factorial of any number, the number of 2′s as factors will always exceed the number of 5′s as factors. that means, there is enough 2's to be paired with 5's.

now, the problem became easier, the total number of 5's as a factor in an integer is the number of trailing zero of that integer. we just need to count the number of 5's as factor of an integer.

if a number is multiple of 5, then it should have at least one 5's as a factor.
if a number is multiple of 25 (5*5), then it should have at least two 5's as a factor.
if a number is multiple of 125 (5*5*5), then it should have at least three 5's as a factor.
and so on...
lets be clear with an example:
the factorial of number 132 has 132/5^1=26 numbers multiple of 5.
132! has 132/5^2=5 (25, 50, 75, 100, 125) numbers multiple of 5^2
132! has 132/5^3=1 (125) numbers multiple of 5^3.
so factorial of 132 has a total 26+5+1=32 factor of 5's.

we are done, number of Trailing Zeros of 132! is 32.
a little simplification for code to avoid pow function is:
Trailing Zero of 132! = 132/5 + (132/5)/5 + ((132/5)/5)/5 = 26 + 5 +1.

Code





Tuesday 12 November 2013

Regionals 2006 :: Africa/Middle East - Arab and North Africa. Being Smarty! (UVALive 3755)

Problem: Being Smarty!
You are given two integer (R and N) and two string in a single line. you have to separate the integers and strings.  a string made of upper- or lower-case letters, digits, and/or spaces. A string may be surrounded by double quotes,  If a property contains spaces, the surrounding double quotes are mandatory. first N row contains 1st string, 2nd N rows contains 2nd string, 3rd N rows contains 1st row and so on.
You have to print string of Rth row. if there is any upper case character in that string, print that character in lower case.

Category: Adhoc, IO handling.

Idea: first take the integers, then remove extra spaces, if 1st character of the 1st string is ", then insert the remaining string until another " found to 1st string. do the same for 2nd string. if there is no ", task is easier for you.
you can determine which string you have to print by the following condition.
((r-1)/n)%2, if 0, 1st string, otherwise 2nd stirng

code:


Monday 11 November 2013

Regionals 2012 :: Asia - Dhaka. Wedding of Sultan (UVA 12582 + UVALive 6201)

Problem: Wedding of Sultan
You are given a path for an connected undirected graph with no cycle. The path is written by a man in the way: if he enter or leave the node he will write it down. When he comes to a node he looks for another connected to it which he has not traversed yet. If he finds such node, he follows that one. Otherwise, he go back. You have to find degree of each node.

Category: basic data structure [stack]

Idea: use stack to push the nodes in path one by one. if two consecutive node are equal, that means, this is the end of that node. now increase the degree of that node by one, and also increase its parent degree by one.
You are done.

Code