This is one of the prob. listed in OPC,can anyone pls pinpoint my error and rectify it, I'd be thankful to u.
Problem 1: 0/1 Tiles, (K Narayan Kumar, CMI)
To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.
To amuse herself, Lavanya has decided to pick a number N and try and construct as many binary sequences of length N as possible using her collection of tiles. For example if N = 1, she can only make the sequence 1. For N=2, she can make 11 and 00. For N=4, there are 5 possiblities: 0011, 0000, 1001, 1100 and 1111.
Lavanya would like you to write a program to compute the number of arrangements possible with N tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.
Input format
A single line with a single integer N.
Output format
A single integer indicating the number of binary sequences of length N, modulo 15746, that Lavanya can make using her tiles.
Test data
You may assume that N ≤ 1000000.
Example
Here is a sample input and output corresponding to the example discussed above.
Sample input
4
Sample output
5
CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style: ioi
My solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int n;
cin>>n;
int k=floor(n/2);
int a[(n+1)];
int b[(k+1)];
a[0]=1;
int i;
for(i=1;i<=n;i++)
{
a[i]=i*a[(i-1)];
}
int s=0;
for(i=0;i<=k;i++)
{
b[i]=(a[(n-i)]/(a[i]*a[(n-i-i)]));
s=s+b[i];
}
int m;
m=s%15746;
cout<<m;
}
|