Another boring problem 0/ 100

Aiuto
1

Salve. Sto provando a risolvere “Another boring problem”, ma credo ci sia un problema riguardante le operazioni che faccio col modulo. Qualcuno sa come aiutarmi?

// NOTE: it is recommended to use this even if you don't understand the following code.

#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

// input data
int N, Q;
vector<int> A;

int main() {
    //  uncomment the following lines if you want to read/write from files
    //  ifstream cin("input.txt");
    //  ofstream cout("output.txt");

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;

            int ans = A[x] % 1000000007;

            cout << ans << endl;
        } else {
            int x, y, b, c;
            cin >> x >> y >> b >> c;
            for(int j = x; j <= y; j++) {
            	int newA = (b*int(pow(j, c))) % 1000000007;
            	if (newA > A[j]) A[j] = newA;
			}
            // insert your code here
        }
    }

    return 0;
}
2

Ciao, ci sono due problemi principali nel tuo codice:

  • il risultato della funzione pow può essere maggiore di 2^{32} (e persino maggiore di 2^{64}), per cui quando lo converti ad intero, ottieni un valore sbagliato;
  • quando aggiorni i valori nell’array A, non consideri che questi valori sono rappresentati modulo 10^9+7, ad esempio il tuo programma considera 1000000042 minore di 42.
3

ma cosa si potrebbe fare per non andare in integer overflow? qualsiasi tipo di variabile non supporta numeri cosi grandi.

4

Nota che non ti serve avere il valore preciso di ogni elemento ma ti basta avere una rappresentazione che ti permetta di eseguire le operazioni descritte nel testo. Puoi ad esempio sfruttare il fatto che ogni elemento A_i può essere descritto come una coppia di numeri (b, c) tali che A_i = b \cdot i^c,

5

ma il valore di b * i^c bisogna saperlo per verificare se sia maggiore o no del precedente valore di Ai,
come richiesto da problema: max(Ai, b * i^c);

6

Non necessariamente, ti basta solo trovare un modo per sapere se b_1 \cdot i^{c_1} sia minore di b_2 \cdot i^{c_2} senza effettivamente calcolare i due numeri.

1 Mi Piace