PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : EASY
PREREQUISITES:
Arrays, Loops
PROBLEM:
Generate the first N rows of Pascal’s triangle. Each row should be printed as an array/list. Find the sum of non-terminal elements of (12N+10)th array. Also print the no. of arrays in which only two elements do not repeat.
(Since the sum and no. can be large, compute it modulo 998,244,353.)
(Pascal’s triangle => To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1.)
QUICK EXPLANATION:
Similar to previous problem use a nested array and store the values into it (until 12N+10),
Print each row (until N) and corresponding (sum= sum of all elements - 2)
EXPLANATION:
Similar to previous problem use a nested array and store the values into it (until 12N+10),
Print each row (until N) and corresponding (sum= sum of all elements - 2)
Print the sum % 998244353 of 12N+10th row.
If you observe the Pascal’s triangle, the no. of arrays in which only two elements do not repeat will always be 0.
Because all elements repeat in Pascal’s triangle other than the first element when in the first row and Middle element in odd rows.
So just print 0.
Or use formula :
Store value 1 into an array, for multiple rows keep adding values according to the given formula to it
(To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1)
If you observe the series the sum of each row is power of 2, i.e. sum of all elements in first row = 2^0 =1
sum of row 2 i.e. [1,1] = 2 =2^1 and so on.
According to the problem statement we do not need to print the first and last elements
=> for row 1 sum =0 and for all other rows sum is 2^n - 2.
For the sum of 12N+2 th row use the same formula. (N=12N +2) .
Then finally print 0 as mentioned earlier.
SOLUTIONS:
Setter's Solution
T=int(input())
N=[int(items) for items in input().split()]
ic=0
while(ic<T):
cnt=0
t=[]
sums=0
temp=N[ic]
A=[1]
B=[1,1]
C=[]
sumar=[]
C.append(A)
sumar.append(0)
temp=(N[ic]*12)+10
if(temp>=2):
C.append(B)
sumar.append(0)
if(temp>2):
while(temp>2):
A=B[:]
B=B[:]+[1]
sums=0
for i in range(1,len(B)-1):
B[i]=A[i]+A[i-1]
sums+=B[i]
C.append(B)
sumar.append(sums%998244353)
temp-=1
for i in range(N[ic]):
print(C[i])
print(sumar[i])
print(sumar[-1])
print(cnt)
ic+=1
Tester's Solution
Same Person
Editorialist's Solution
Same Person