return 0;at the end of the main program can be omitted.The range of integer types is implementation defined, the C++ standard only guarantees guarantees that ana (signed)
inthas 16 bitcan hold values from -32767 to 32767, which which is too small small for your numbers. Many compilers defineintas a 32-bit integer, butinteger, but you can uselongto be on the safe side, or use fixed-size types likeint32_t.
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long numDays;
inFile >> numDays;
for (long i = 1; i <= numDays; i++) {
long numAnts;
inFile >> numAnts;
long divisorCount = numberOfDivisors(numAnts);
if (divisorCount <>= lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence startedNo rightlonger heredecreasing.
isDescending = true;false;
} else decreasingSequencesif +=(!isDescending) 1;{
}
// A decreasing subsequence }started elseright {here.
// NoisDescending longer= decreasing.true;
isDescendingdecreasingSequences =+= false;1;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
return 0;at the end of the main program can be omitted.The C++ standard only guarantees that an
inthas 16 bit, which is too small for your numbers. Many compilers defineintas a 32-bit integer, but you can uselongto be on the safe side.
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long numDays;
inFile >> numDays;
for (long i = 1; i <= numDays; i++) {
long numAnts;
inFile >> numAnts;
long divisorCount = numberOfDivisors(numAnts);
if (divisorCount < lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
} else {
// No longer decreasing.
isDescending = false;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
return 0;at the end of the main program can be omitted.The range of integer types is implementation defined, the C++ standard only guarantees that a (signed)
intcan hold values from -32767 to 32767, which is too small for your numbers. Many compilers defineintas a 32-bit integer, but you can uselongto be on the safe side, or use fixed-size types likeint32_t.
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long numDays;
inFile >> numDays;
for (long i = 1; i <= numDays; i++) {
long numAnts;
inFile >> numAnts;
long divisorCount = numberOfDivisors(numAnts);
if (divisorCount >= lastDivisorCount) {
// No longer decreasing.
isDescending = false;
} else if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long inputLength;numDays;
inFile >> inputLength;numDays;
for (long i = 1; i <= inputLength;numDays; i++) {
long num; // Current numbernumAnts;
inFile >> num;numAnts;
long divisorCount = numberOfDivisors(numnumAnts);
if (divisorCount < lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
} else {
// No longer decreasing.
isDescending = false;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
As a further improvement you can pre-compute the prime numbers with a sieving method. Note that it sufficient to pre-compute the primes in the range \$ 2 \ldots \sqrt{N} \$ where \$ N = 10^9 \$ is the upper bound for the given input. That should help to stay within the given memory limit of 64 MB.
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long inputLength;
inFile >> inputLength;
for (long i = 1; i <= inputLength; i++) {
long num; // Current number
inFile >> num;
long divisorCount = numberOfDivisors(num);
if (divisorCount < lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
} else {
// No longer decreasing.
isDescending = false;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
As a further improvement you can pre-compute the prime numbers with a sieving method. Note that it sufficient to pre-compute the primes in the range \$ 2 \ldots \sqrt{N} \$ where \$ N = 10^9 \$ is the upper bound for the given input.
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long numDays;
inFile >> numDays;
for (long i = 1; i <= numDays; i++) {
long numAnts;
inFile >> numAnts;
long divisorCount = numberOfDivisors(numAnts);
if (divisorCount < lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
} else {
// No longer decreasing.
isDescending = false;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
As a further improvement you can pre-compute the prime numbers with a sieving method. Note that it sufficient to pre-compute the primes in the range \$ 2 \ldots \sqrt{N} \$ where \$ N = 10^9 \$ is the upper bound for the given input. That should help to stay within the given memory limit of 64 MB.
Some general remarks:
Don't use
namespace std;, see for example Why is "using namespace std;" considered bad practice?.Define variables at the narrowest possible scope. In particular, avoid global variables.
Use better variable names. It is unclear what each variable in
int n,i,v[100001],nr,j,s;
stands for.
return 0;at the end of the main program can be omitted.The C++ standard only guarantees that an
inthas 16 bit, which is too small for your numbers. Many compilers defineintas a 32-bit integer, but you can uselongto be on the safe side.
With respect to readability, I recommend to leave more (horizontal) space, e.g. around operators and parentheses.
There are two places with identical code to count the divisors of a number. This should be done in a separate function.
Your code uses a nested loop where the inner loop updates the index of the outer loop. That is difficult to understand and error-prone. And it is not necessary: Instead of starting a nested loop when the start of a decreasing subsequence is found, set a flag instead and continue with the main loop.
You store all numbers from the input file in an array, which is not necessary: each loop iteration only needs the previous number to decide if the subsequence is (still) decreasing. It suffices to store the previously processed number in a variable.
Summarizing the suggestions so far, the code could look like this:
#include <fstream>
#include <cmath>
long numberOfDivisors(long n) {
long count = 0;
for (long j = 2; j <= sqrt(n); j++) {
if (n % j == 0) {
count++;
if (j != n/j)
count++;
}
}
return count;
}
int main()
{
std::ifstream inFile("furnici.in");
std::ofstream outFile("furnici.out");
long decreasingSequences = 0;
bool isDescending = false;
long lastDivisorCount = 0;
long inputLength;
inFile >> inputLength;
for (long i = 1; i <= inputLength; i++) {
long num; // Current number
inFile >> num;
long divisorCount = numberOfDivisors(num);
if (divisorCount < lastDivisorCount) {
if (!isDescending) {
// A decreasing subsequence started right here.
isDescending = true;
decreasingSequences += 1;
}
} else {
// No longer decreasing.
isDescending = false;
}
lastDivisorCount = divisorCount;
}
outFile << decreasingSequences;
}
Now you can start to improve the performance, and the prime candidate is
of course the numberOfDivisors() function.
An efficient method (and I'm repeating arguments from Getting the divisors count of an integer now) is to use the prime factorization: If $$ n = p_1^{e_1} ,円 p_2^{e_2} \cdots p_k^{e_k} $$ is the factorization of \$ n \$ into prime numbers \$ p_i \$ with exponents \$ e_i \$, then $$ \sigma_0(n) = (e_1+1)(e_2+1) \cdots (e_k+1) $$ is the number of divisors of \$ n \$, see for example Wikipedia: Divisor function. Example: $$ 720 = 2^4 \cdot 3^2 \cdot 5^1 \Longrightarrow \sigma_0(720) = (4+1)(2+1)(1+1) = 30 ,円 . $$
Here is a possible implementation in C:
long numberOfDivisors(long n){
long numDivisors = 1;
long factor = 2; // Candidate for prime factor of `n`
// If `n` is not a prime number then it must have one factor
// which is <= `sqrt(n)`, so we try these first:
while (factor * factor <= n) {
if (n % factor == 0) {
// `factor` is a prime factor of `n`, determine the exponent:
long exponent = 0;
do {
n /= factor;
exponent++;
} while (n % factor == 0);
// `factor^exponent` is one term in the prime factorization of n,
// this contributes as factor `exponent + 1`:
numDivisors *= exponent + 1;
}
// Next possible prime factor:
factor = factor == 2 ? 3 : factor + 2;
}
// Now `n` is either 1 or a prime number. In the latter case,
// it contributes a factor 2:
if (n > 1) {
numDivisors *= 2;
}
return numDivisors;
}
As a further improvement you can pre-compute the prime numbers with a sieving method. Note that it sufficient to pre-compute the primes in the range \$ 2 \ldots \sqrt{N} \$ where \$ N = 10^9 \$ is the upper bound for the given input.