Alcuni di voi potrebbero aver notato delle piccole modifiche alla piattaforma di allenamento negli ultimi giorni, e in particolare un nuovo indicatore che elenca i linguaggi di programmazione permessi in ogni problema. Questo era per arrivare a supportare anche Java, cosa che da oggi è completa.
Non tutti i problemi lo supportano: se un task utilizza i grader, i linguaggi supportati rimangono gli stessi di prima (C++ per la maggior parte dei problemi, e in alcuni casi anche C/Pascal). Tutti gli altri task, e in particolare quelli delle olimpiadi a squadre, possono ora essere risolti anche in Java.
Se deciderete di provare a risolvere un problema in Java, dovrete chiamare la classe che contiene il vostro codice come il nome breve del problema. Ad esempio, per risolvere easy1 (Trova il massimo), dovrete fare qualcosa del genere:
public class easy1 {
public static void main(String args[]) {
// codice complicatissimo
}
}
Trovate il nome breve del problema come parte dell’URL, e in ogni caso avrete un suggerimento col nome corretto da usare quando selezionate il linguaggio:
Piccola correzione: per alcuni dei problemi delle OIS non va incluso il prefisso ois_ nel nome della classe. Il nome suggerito quando mandate una soluzione è quello corretto.
Ho provato a risolvere un problema (cabala) con Java. I test falliscono sempre con l’indicazione “Execution failed because the return code was nonzero”. Visto che Java non è citato nel testo (che risale al 2015) ma c’è comunque il file sorgente con lo scheletro, cosa occorre modificare per riuscire a far girare i test?
Grazie, ha funzionato. In cabala occorrerebbe anche rivedere negli allegati il tipo dei parametri passati alla funzione “occulta” da scrivere perché sono errati sia nella versione C che in quella Java (M deve essere, rispettivamente, long long e long).
Non penso, anzi, secondo me la funzione occulta sarebbe potuta tranquillamente essere dichiarata con return type int, siccome deve ritornare il valore di C mod M (sapendo che M sta perfettamente in un int).
Comunque, per confermare la teoria (M sta in un int ed è \leq 10^9), ho provato a eseguire questi test:
#include <cassert>
#include <fstream>
#include <limits>
using namespace std;
int main() {
assert(numeric_limits<int>::max() > 1000000000); // se 10^9 fosse meno della dimensione massima di un int, questo fallirebbe
ifstream fin("input.txt");
ofstream fout("output.txt");
int T;
fin >> T;
for (int t = 0; t < T; t++) {
long long N, M;
fin >> N >> M;
assert(M == (int)M); // se ci fosse integer overflow, questo fallirebbe
assert(M <= 1000000000); // se M fosse > 10^9, questo fallirebbe
assert(2 <= M); // se M fosse < 2, questo fallirebbe
}
}
Siccome nessuno è fallito (assert(false) provoca “Execution killed”) allora direi che M può essere messo in un int.
Non conosco i dettagli del problema, ma vedo che la funzione ritorna un long long. Probabilmente per calcolare l’output hai bisogno di lavorare con i long long, anche se in input ti arriva un int. Ad esempio, se volessi calcolare x^2 per x \le 10^9, ti servirebbe qualcosa di questo tipo per convertire x in long long prima di usarlo:
long long calcola(int x) {
return x * 1LL * x;
}
O in alternativa
long long calcola(int _x) {
long long x = _x;
return x * x;
}
Dipende dalla tua implementazione. Sicuramente, il numero C può causare integer overflow (con N \leq 18 cifre)… Però il problema richiede di trovare il valore C mod M, e siccome M è un int, allora anche C mod M sarà int.
La funzione attraverso cui risolvo il problema ritorna un int e il mio codice da 100/100. Anche se questi sono dettagli dell’implementazione, per risolvere il problema la funzione potrebbe essere tranquillamente dichiarata così:
int occulta(int N, int M);
Queste sono le mie congetture, spero sia tutto corretto. Buona serata!
Pseudo-codice da 100/100 (con int)
funzione risolvi(cifre rimanenti, numero considerato, ultima cifra, M):
nuovo modulo = numero considerato % M
se cifre rimanenti == 0, ritorna nuovo modulo
per ogni cifra in [3, 6, 9]:
se ultima cifra != cifra:
nuovo modulo = massimo(nuovo modulo, risolvi(rimanenti - 1, partenza * 10 + cifra, cifra, M))
ritorna nuovo modulo
In questo modo, la funzione ritornerà solo int. N.B. il numero considerato deve essere long long (ma si potrebbe trovare un modo per non usarlo, forse).
L’hai provata in C11/gcc? A me fornisce 30/100, cambiando in long numero_considerato, nuovo_modulo e valore di ritorno restituisce 100/100.
Il perché mi è assolutamente oscuro, dato che concordo con te sulla sufficienza degli int.
Certamente, numero_considerato può avere al più N = 18 cifre (chiaramente, quindi, non entra in un int). Io riesco a prendere 100/100 usando int sia in C che in C++ (con codice leggermente diverso per C++, ma ovviamente funzionerebbe anche quello di C).
Per capire meglio la tua situazione, potresti provare a mandare l’implementazione?