Type the Question

Saturday, February 16, 2019

Question Name:RHEZO & PRIME PROBLEMS

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
 
bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;
 
    return true;
}
 
int biggestPrime(int n) {
    for (int i = n; i > 1; i--)
        if (isPrime(i))
            return i;
 
    return -1;
}
 
int main() {
    int n;
    cin >> n;
 
    int bi = biggestPrime(n);
    if (bi == -1) {
        cout << 0;
        return 0;
    }
 
    int arr[n + 1];
    arr[0] = 0;
 
    for (int i = 1; i <= n; i++) {
        int vv;
        cin >> vv;
        arr[i] = arr[i-1] + vv;
    }
 
    int max = 0;
    for (int i = bi; i <= n; i++) {
        int ccc = arr[i] - arr[i - bi];
        max = max > ccc ? max : ccc;
    }
 
    cout << max;
 
}
  • Problem Description
    Rhezo and his friend Vanya love problem solving. They have a problem set containing N problems, with points assigned to each. Rhezo wants to solve problems in such a way that he gets the maximum number of points.

    Rhezo has a weird habit of solving only prime number of consecutive problems, that is, if he solves X consecutive problems from the problem set, then X should be prime.

    Vanya has already solved all problems from the problem set and he wonders how much maximum points Rhezo can get. Vanya can answer this, but can you?

    Input:

    First line contains a single integer N, denoting the number of problems in the problem set. Next line contains N space separated integers denoting the points assigned to the problems.

    Output:

    Print a single integer, the maximum points Rhezo can get.

    Constraints:

    1<= N<=5000
    1<= Points of Problems <=10^5

    Hints: For example
    Sample Input:
    4
    8 1 3 7

    Sample Output:
    12

    Rhezo will solve problems 1, 2 and 3, and will get 12 points. Note that, he cannot solve all the problems because then he will solve
    4 (non-prime) consecutive problems.
  • Test Case 1
    Input (stdin)4
    8 1 3 7
    Expected Output12
  • Test Case 2
    Input (stdin)7
    5 6 3 8 9 1 2
    Expected Output34

No comments:

Post a Comment

Question Name:TOWER OF HANOI

#include < bits / stdc ++. h > #define lli long long using namespace std ; lli dp [ 202 ]; int main () { int t , n ; ...