Please click for the link here
Click here on these to view
TEST-31
1)
Gridland Metro
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
int r;
int c1;
int c2;
} train;
int cmpfunc (const void * a, const void * b)
{
train * p1 = (train*)a;
train * p2 = (train*)b;
if(p1->r != p2->r)
return (p1->r - p2->r);
else if(p1->c1 != p2->c1)
return (p1->c1 - p2->c1);
else
return (p1->c2 - p2->c2);
}
train tr[1000];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,m,k;
scanf("%d %d %d", &n, &m, &k);
for(int i=0; i<k; i++)
{
int r, c1,c2;
scanf("%d %d %d", &r, &c1, &c2);
tr[i].r=r;
tr[i].c1 = c1;
tr[i].c2 = c2;
}
if(k==0)
{
long long retval = (long long)n*m;
printf("%lld", retval);
return 0;
}
qsort(tr, k, sizeof(train), cmpfunc);
long long int ttotal = 0;
int r = tr[0].r;
int start = tr[0].c1;
int end = tr[0].c2;
long long int rtotal = end-start +1;
for(int i=1; i<k; i++)
{
if(tr[i].r != r)
{
//printf("r %d, rtotal %d\n", r, rtotal);
ttotal += rtotal;
r = tr[i].r;
start = tr[i].c1;
end = tr[i].c2;
rtotal = end-start+1;
}
else
{
if(tr[i].c1 <=end)
{
if(tr[i].c2 > end)
{
rtotal += tr[i].c2-end;
end = tr[i].c2;
}
}
else
{
start = tr[i].c1;
end = tr[i].c2;
rtotal += end-start+1;
}
}
}
ttotal += rtotal;
long long retval = (long long)m*n - ttotal;
printf("%lld\n", retval);
return 0;
}
2)
Sherlock and Divisors
#include<stdio.h>
#include<math.h>
int main()
{
long int t,i,n;
scanf("%ld",&t);
while(t--)
{
scanf("%ld",&n);
long int s=sqrt(n),c=0;
for(i=1;i<=s;i++)
{
if(n%i==0)
{
if(i%2==0)
c++;
if(i*i!=n && (n/i)%2==0)
c++;
}
}
printf("%ld\n",c);
}
return 0;
}
3)
In python
import math
def modexp_lr(a, b, n):
r = 1
for bit in reversed(_bits_of_n(b)):
r = r * r % n
if bit == 1:
r = r * a % n
return r
def _bits_of_n(n):
bits = []
while n:
bits.append(n % 2)
n /= 2
return bits
def p_factors(num, num_c, p_to_test, prime_factors):
while num_c % 2 == 0:
num_c /= 2
if 2 in prime_factors:
prime_factors[2] += 1
else:
prime_factors[2] = 1
for x in xrange(3, int(math.sqrt(num_c))+1,2):
while num_c % x == 0:
if x in prime_factors:
prime_factors[x] += 1
else:
prime_factors[x] = 1
num_c /= x
if num_c > 2:
prime_factors[num_c] = 1
p_to_test = [(num-1)/x for x in prime_factors]
return p_to_test, prime_factors
def main():
num = input()
num_c = num-1
p_to_test = []
prime_factors = {}
p_to_test,prime_factors = p_factors(num, num_c, p_to_test, prime_factors)
num_of_p_roots = 1
for key,value in prime_factors.iteritems():
num_of_p_roots *= (((key ** value)/key) * ((key-1)))
for x in xrange(2, num):
flag = 0
for y in p_to_test:
if modexp_lr(x,y,num) != 1:
flag += 1
if flag == len(p_to_test):
print x, num_of_p_roots
break
main()
4)
Minimum Multiple
import Data.List (sort, groupBy)
import Data.Function (on)
import Data.Monoid
import Control.Monad
primes :: [Integer]
data Factorization = Factorization [(Integer,Integer)]
deriving Show
instance Monoid Factorization where
mempty = Factorization []
mappend (Factorization x) (Factorization y) = Factorization $ maxImpl x y
prod (Factorization x) (Factorization y) = Factorization $ prodImpl x y
showF (Factorization x) = show $ f $ map g x
where
f [] = 1
f (x:xs) = ((f xs) * x) `mod` _P
g (p,e)
| e == 0 = 1
| e `mod` 2 == 0 = pr2
| otherwise = (pr2 * p) `mod` _P
where
pr2 = (ped2 * ped2) `mod` _P
ped2 = g (p, e `div` 2)
maxImpl [] x = x
maxImpl x [] = x
maxImpl (xh:xt) (yh:yt)
| fst xh < fst yh = xh:(maxImpl xt (yh:yt))
| fst xh > fst yh = yh:(maxImpl (xh:xt) yt)
| otherwise = (fst xh, max (snd xh) (snd yh)):(maxImpl xt yt)
prodImpl [] x = x
prodImpl x [] = x
prodImpl (xh:xt) (yh:yt)
| fst xh < fst yh = xh:(prodImpl xt (yh:yt))
| fst xh > fst yh = yh:(prodImpl (xh:xt) yt)
| otherwise = (fst xh, snd xh + snd yh):(prodImpl xt yt)
primes = 2:3:(filter isPrime [5..])
where
isPrime p = all ((/= 0) . (p `mod` )) $ takeWhile ((<= p).(^2)) primes
factorize = Factorization .
map (\x -> (fst $ head x, sum $ map snd x)) . groupBy ((==) `on` fst) . fact'
where
fact' n
| n < 1 = error "_"
| n == 1 = []
| (p:_) <- factors = (p, 1):(fact' (n `div` p))
| otherwise = [(n,1)]
where
factors = filter ((== 0) . (n `mod`)) $ takeWhile ((<= n).(^2)) primes
data Tree a
= Tree (Tree a) a (Tree a)
| Leave a
| Nil
deriving (Show)
create :: (Monoid a) => Int -> [a] -> Tree a
create len vs
| len == 0 = Nil
| len == 1 = Leave (head vs)
| otherwise = Tree t1 ((query m 0 m t1) `mappend` (query (len-m) 0 (len-m) t2)) t2
where
t1 = create m vs1
t2 = create (len - m) vs2
(vs1,vs2) = splitAt m vs
m = len `div` 2
update :: (Monoid a) => Int -> Int -> (a -> a) -> Tree a -> Tree a
update len idx f (Tree l a u)
| idx < m = Tree l' (((query m 0 m l') `mappend` (query (len-m) 0 (len-m) u))) u
| idx >= m = Tree l (((query m 0 m l) `mappend` (query (len-m) 0 (len-m) u'))) u'
where
u' = (update (len - m) (idx-m) f u)
l' = (update m idx f l)
m = len `div` 2
update _ _ f (Leave x) = Leave (f x)
update _ _ _ Nil = error "should not happen"
query :: (Monoid a) => Int -> Int -> Int -> Tree a -> a
query len beg end (Tree l a u)
| end <= beg = mempty
| beg == 0, end == len = a
| otherwise = lq `mappend` rq
where
rq = if end > m then (query (len - m) (max 0 $ beg - m) (end - m) u) else mempty
lq = if beg < m then (query m beg (min end m) l) else mempty
m = len `div` 2
query _ _ _ (Leave x) = x
query _ _ _ (Nil) = mempty
_P :: Integer
_P = 10^9 + 7
main =
do _ <- getLine
as <- getLine
let a = map (factorize . read) $ words as
atree0 = create al a
al = length a
k <- readLn
let fun atree _ =
do s <- getLine
case s of
('U':' ':u) ->
let [i,v] = (map read $ words u); v' = factorize v in
return (update al (fromIntegral i) (prod v') atree)
('Q':' ':q) -> let [l,r] = (map read $ words q) in
do -- putStrLn $ show atree
putStrLn $ showF $ query al l (r+1) atree
return atree
foldM_ fun atree0 [1..k]
