runtah

UVa 11296 Counting Solutions

UVa 11296 Counting Solutions

Method:
First design a bruteforce solution with small input in mind. It should be able to compute answers for 100 101 etc. Now sequentially examine all the answers youll find a pattern. The solution to every i-th even number is the sum of all numbers till i+1. It also applies to all odd numbers. Such as 2, 1st even number, so result is 1+2, till 2nd number And for 3, 1st odd number, its the same. Just find the i using i = (n/2) and use i*(i+1)/2 formula for the result.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

typedef long long lint;

lint res[1000010];

int main ( void ) {
 
 lint i, j, k, n, cnt, ser;
 res[0] = 1LL;
 res[1] = 1LL;
 
 for (i=2, ser=2LL ; i<=1000001LL ; i+=2, ser++) {
 res[i] = (res[i-1]+ser);
 res[i+1] = res[i];
 }
 
 
 while ( cin >> n ) {
 cout << res[n] << endl;
 }

 return 0;
}

Go to link download