Salve ragazzi, sto avendo difficoltà a portare un codice python in c++ :(, sia per via della mia scarsa conoscenza del c++ stesso sia per il fatto che in python tante funzioni sono già incluse nelle librerie permettendo di lavorare più ad alto livello, mentre da quel che mi è sembrato di capire in c++ no. Btw questo è il codice:
#!/usr/bin/env python3
import sys
from itertools import combinations_with_replacement, permutations
from math import factorial as fac
# se preferisci leggere e scrivere da file
# ti basta decommentare le seguenti due righe:
#sys.stdin = open('input.txt','r')
#sys.stdout = open('output.txt', 'w')
def controllino(l):
new_list = []
for element in l:
if element not in new_list:
new_list += [element]
n = new_list
l = n.copy()
for element in l:
for i in range(len(element)-1):
if element[i] == element[i+1]:
n.remove(element)
break
return n
def solve(t):
N,M = map(int,input().split())
elementi = ['3','6','9']
resti = []
n = []
for i in range(1,N+1):
a = (list(combinations_with_replacement(elementi,i)))
for j in a:
for e in list(permutations(j)):
n += [e]
n = controllino(n)
for i in n:
a = ''
for j in i:
a+=str(j)
resti += [int(a)%M]
print(f"Case #{t}: {max(resti)}")
T = int(input().strip())
for t in range(1, T+1):
solve(t)
sys.stdout.close()
Scrivere le funzioni che ho importato da itertools sarebbe complicato. Sarebbe utile qualche suggerimento sia per scrivere queste funzioni che riguardano la combinatoria (combinations_with_replacement mi restituisce una lista di tuple dove ogni tupla è una combinazione senza ripetizioni, mentre permutations mi restituisce una lista di tuple dove ogni tupla è una permutazione), sia per trovare una soluzione a questo problema di invio delle soluzioni (a me piacerebbe lavorare in python e non in c++, quindi mi specializzerei in quello), grazie
P.S Da quel che mi sembra di capire la piattaforma di somministrazione porta il codice python in c++ autonomamente (fallendo gran parte delle volte per via della diversa natura dei due linguaggi) e poi lo compila. Non sarebbe meglio introdurre direttamente un interprete python?
ciao, partendo dal presupposto che, essendo python un linguaggio di livello più alto del C++, è anche sensibilmente più lento, cosa che emerge per esempio nelle OIS (olimpiadi di informatica a squadre) dove sì, ti permettono di sottoporre in python ma dicono anche esplicitamente che non è possibile fullare tutti i problemi utilizzandolo perchè non è veloce a sufficenza. Se questo non fosse ancora sufficiente a convincerti del fatto che nella programmazione competitiva c++ è estremamente più potente ti porto anche due ragioni molto più persuasive: alle OII (olimpiadi italiane informatica) non è possibile sottoporre codice in python ma unicamente in c++ e stessa cosa alle IOI (international olympiad in informatics).
Detto questo capisco che possa risultare complicato o scomodo per te al momento passare da python a c++, come è normale che sia abbassando il livello del linguaggio ma tieni anche presente che i problem setter pensano i problemi per essere risolti in c++ e non in python perciò sicuramente (nella maggior parte dei casi lol) esiste un modo comodo per fare tutto in c++ perchè il problema è pensato per quello.
Non sono qua ad insultare python che è un linguaggio validissimo, ma purtroppo nella programmazione competitiva al momento utilizzarlo è uno svantaggio sensibile per le ragioni che ti ho raccontato sopra, perciò ti consiglio caldamente di, per quanto riguarda le gare di competitive programming, prediligere c++ in quanto imparando a conoscerlo bene è comunque molto comodo per la soluzione di questi problemi.
Comunque la piattaforma di valutazione non transpila il Python a C++ (sarebbe un task alquanto arduo), viene utilizzato già un interprete Python. In ogni caso può essere utile cambiare un po’ metodo e scrivere direttamente in C++ piuttosto che cercare di riscrivere a mano da Python e C++.
Sapevo che il c++ fosse più efficiente (anche se non pensavo fino al punto da non riuscire a fullare dei problemi), ma non tutte le altre cose . Potresti per caso consigliarmi qualche dispensa utile a conoscere il c++ orientato alla programmazione competitiva?
P.S.: Non voglio rusharla eh, ma quanto tempo potrebbe volerci per masterare adeguatamente il c++ (fino a raggiungere il livello che ho ora in python)? Btw grazie dell’aiuto
Grazie, non ci avevo fatto caso. Alla fine però dal terzo subtask in poi o il codice ci impiega più di 1 sec o eccede i memory limits, ora provo un pò ad ottimizzare anche se penso che a breve dovrò spostarmi al c++
certo! sicuramente una piattaforma che propone un ottimo percorso è https://usaco.guide/, che ha diverse raccolte di nozioni e problemi per esercitarsi su tutti i livelli, inoltre ti consiglierei di iscriverti a https://codeforces.com/ che è una piattaforma che, oltre a contenere problemi consigliati da usaco guide, organizza molti contest, delle sorta di mini-gare che accadono molto spesso quindi ti permettono di provare a svolgere problemi come in gara senza dovere aspettare necessariamente le OII oppure OIS o altro. Infine un’altra ottima piattaforma per svolgere problemi è senza dubbio CSES - CSES Problem Set - Tasks che contiene molti bei problemi. (ovviamente dato per scontato l’utilizzo di training)
ah e per spiegazioni dettagliate e affidabili di algoritmi io mi affido a https://cp-algorithms.com/
per quanto riguarda masterare il c++, inizialmente sarà certamente una sofferenza, ma penso che (essendomi permessa di stalkerarti su training) tu sia più che in tempo per cambiare linguaggio senza troppi problemi. Soprattutto ricorda che alla fine è importante sapere implementare, certo, ma prima di tutto sapere risolvere proprio concettualmente problemi è fondamentale e l’implementazione viene dopo.
Grazie mille di tutto :), piano piano mi guardo tutto e mi metto a studiare.
Il fatto è che io python lo utilizzo da un paio d’annetti prima della scoperta delle oii, quindi mi ero abbastanza abituato a scrivere senza dover dichiarare il tipo delle variabili o dei contenuti di liste, tuple o dizionari, ah e ovviamente senza preoccuparmi minimamente della memoria . Ma se studiare c++ è ciò che serve, mi metterò l’anima in pace e comincierò a lavorare
Piccolo aggiornamento: ho provato a scrivere la soluzione di cabala in c++, ma mi da 10 su 100
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <math.h>
#define pb push_back
using namespace std;
// funzione ricorsiva che porta un numero n da base 10 a base 3
// E ritorna quel numero con tutte le cifre multiple di 3
vector<int> GeneraNumero(vector<int> sol, int n){
int r = n%3;
int d = n/3;
sol.pb(r);
if(d==0){
vector<int> v;
for(int i=0; i<sol.size(); i++){
v.pb((sol[i]+1)*3);
}
return v;
}
return GeneraNumero(sol,d);
}
// funzione che prende in input il vettore comb che rappresenta le cifre
// del numero, ed m succesivamente restituisce il resto tra il numero rappresentato
// da comb e m
int calcolaResto(vector<int> comb, int m){
// verifica che il numero sia valido
for(int i=0; i<comb.size()-1; i++){
if(comb[i]==comb[i+1]) return -1;
}
int r = 0;
for(int i=0; i<comb.size(); i++){
r += comb[i]*pow(10,i);
}
return r%m;
}
// funzione solve
int solve(int N,int M){
int n = 0;
for(int i=0; i<N; i++){
n+=2*pow(3,i); // restituisce il massimo valore rappresentabile da un numero di N cifre in base 3
}
int r = 0;
for(int i=0; i<=n; i++){
vector<int> v = GeneraNumero({},i); // genera tutti i numeri da 0 a n (max numero rappresntabile) in base 3
r = max(r,calcolaResto(v,M)); // calcola il resto di quel numero in base M
}
return r; // ritorna il resto massimo
}
int main(){
fstream fr,fw;
fr.open("input.txt",ios::in); // apre i due file input.txt e output.txt
fw.open("output.txt",ios::out);
int N,M,T;
fr >> T;
for(int t=0; t<T; t++){
fr >> N >> M;
fw << solve(N,M) << " "; // per ogni valore di N e M nel file chiama solve e scrive la soluzione in output.txt
}
fr.close(); // chiude i file
fw.close();
return 0;
}
Il codice è questo. Per generare i numeri validi ho pensato di usare i numeri in base 3 (che possono avere come cifre quindi 0,1 e 2, potendo far corrispondere ad ogni cifra o 3 o 6 o 9 [(cifra+1)*3]). Quindi mi genera tutti i numeri in base 3 da 0 fino al numero massimo di N cifre rappresentabile in base 3. Una volta ottenuto il numero verifico che questo non abbia cifre consecutive uguali e poi calcolo il resto per M, e trovo il resto massimo. Mi fallisce tutti i test case però tranne i primi 2 d’esempio, il 2 e il 4, e all’ultimo subtask ci mette anche più di un secondo. Dov’è l’errore nel codice? Grazie
GeneraNumero crea i numeri al contrario (probabilmente non è quello che volevi fare, ma non è un grosso problema). Se provi a stampare i valori che provi ti accorgerai che ne mancano molti, poiché usando i numeri in base 3, è ambiguo se i leading 0s siano “3” oppure cifre vuote di un numero con meno di N cifre. Ricordati che in C++ gli interi hanno una dimensione: se hai a che fare con valori più grandi di 2 miliardi, devi usare i long long per evitare overflow. Evita di usare std::pow, poiché lavora con i float che hanno enormi problemi di precisione, se devi calcolare potenze, fallo a mano con un for.
Per quanto riguarda i TLE, stai controllando O(3^N) numeri, che è un miglioramento rispetto alla soluzione naive che ne controlla O(10^N) ma comunque è troppo lenta (in generale considera che con \approx10^8 operazioni al secondo sei al limite, e questa soluzione che ha complessità O(3^NN) ne fa quasi 10^{10}.
Se eviti di generare i numeri con due cifre uguali consecutive puoi ridurre ulteriormente la complessità a O(2^NN), che passa agevolmente.
In GeneraNumero i numeri sono generati “al contrario” poiché in calcolaResto vengono “riassemblati” giusti
Riguardo i leading 0 GeneraNumero viene chiamata la prima volta su un vettore vuoto che man mano assume la dimensione del numero di cifre che ha il numero che rappresenta (scusa per la confusione ) quindi quali sarebbero i leading 0?
Ho scritto una funzione “int potenza” per calcolare le potenze ma continua a non passare sempre gli stessi test case
Hai ragione , ora ho capito. Ora come ora mi viene in mente di portare il numero in stringa e calcolarmi le permutazioni della stringa, così da poter avere che ne so un “002” diverso da un “2” cosa impossibile con gli interi. Vedo un pò come implentarla e la complessità dell’algoritmo ;).
Questa è l’implementazione, e non mi da problemi con i test case apparte per i TLE. Per gli N <= 7 ci mette meno di 0,3s, ma per gli N>7 ci mette molto più di un secondo. Con la mia logica mi è molto difficile far si che le funzioni permNumero e GeneraNumero non generino di base numeri con cifre consecutive uguali e che non generino numeri già generati, poiché next_permutation mi genera già la permutazione successiva senza controlli… . Penso che questo sia l’ultimo problema dopodiché il codice dovrebbe andare bene, il problema è l’implementazione
#include <iostream>
#include <fstream>
#include <set>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#define pb push_back
using namespace std;
bool controllino(vector<int> n){
for(int i=0; i<n.size()-1; i++){
if(n[i]==n[i+1]) return false;
}
return true;
}
int potenza(int base,int esponente){
int p = 1;
for(int i=0; i<esponente; i++){
p *= base;
}
return p;
}
vector<vector<int>> permNumero(vector<int> n){
vector<vector<int>> sol;
do{
if(controllino(n)){
sol.pb(n);
}
}while(next_permutation(n.begin(),n.end()));
return sol;
}
// funzione ricorsiva che porta un numero n da base 10 a base 3
vector<int> GeneraNumero(vector<int> sol, int n){
int r = n%3;
int d = n/3;
sol.pb(r);
if(d==0){
vector<int> v;
for(int i=0; i<sol.size(); i++){
v.pb((sol[i]+1)*3);
}
return v;
}
return GeneraNumero(sol,d);
}
// funzione che prende in input il vettore comb che rappresenta le cifre
// del numero, ed m succesivamente restituisce il resto tra il numero rappresentato
// da comb e m
int calcolaResto(vector<vector<int>> ci, int m){
int f = 0;
set<vector<int>> co(ci.begin(),ci.end());
for(auto j=co.begin(); j!=co.end();j++){
bool term = 1;
vector<int> comb = *j;
// verifica che il numero sia valido
int r = 0;
for(int i=0; i<comb.size(); i++){
r += comb[i]*potenza(10,i);
}
f = max(f,r%m);
if (f == m-1) return f;
}
return f;
}
// funzione solve
int solve(int N,int M){
int n = 0;
for(int i=0; i<N; i++){
n+=2*potenza(3,i); // restituisce il massimo valore rappresentabile da un numero di N cifre in base 3
}
int r = 0;
for(int i=0; i<=n; i++){
vector<int> v = GeneraNumero({},i);
vector<vector<int>> comb = permNumero(v); // genera tutti i numeri da 0 a n (max numero rappresntabile) in base 3
r = max(r,calcolaResto(comb,M));
if(r==M-1) return r;// calcola il resto di quel numero in base M
}
return r%M; // ritorna il resto massimo
}
int main(){
fstream fr,fw;
fr.open("input.txt",ios::in); // apre i due file input.txt e output.txt
fw.open("output.txt",ios::out);
int N,M,T;
fr >> T;
for(int t=0; t<T; t++){
fr >> N >> M;
fw << solve(N,M) << " "; // per ogni valore di N e M nel file chiama solve e scrive la soluzione in output.txt
}
fr.close(); // chiude i file
fw.close();
return 0;
}
Questo programma sta diventando molto in fretta molto più lungo e complesso di quanto sia realmente necessario. Come vedi provare a portare alcuni schemi funzionali del Python in C++ è molto complicato e anche abbastanza inutile. In C++ si scrive codice più a basso livello e più imperativo, con il vantaggio che la complessità del programma risulta di solito molto più evidente dal sorgente. Ti consiglio di provare a scrivere da 0 una soluzione in C++ senza partire da quella in Python, cercando di trovare il modo più semplice di implementare le cose. In particolare per questo problema potrebbe essere comodo creare una funzione ricorsiva per generare tutti i numeri che ti interessano.
In verità tipo ieri avevo pensato ad una soluzione del genere. Sicuramente sarebbe molto meno complessa sia a livello computazionale che di implentazione, poi la mia testardaggine mi ha detto di tirare diritto sull’idea iniziale . Ormai però sta veramente diventando too much, mi sa che ritorno sui miei passi e vi aggiorno con la soluzione
Hai ragione, mi sono dimenticato di levarla quando ho finito di debuggare. Comunque ora 100/100 :). Grazie a tutti coloro che hanno commentato sotto questo thread <3
. Potresti per caso consigliarmi qualche dispensa utile a conoscere il c++ orientato alla programmazione competitiva?
) quindi quali sarebbero i leading 0?
. Penso che questo sia l’ultimo problema dopodiché il codice dovrebbe andare bene, il problema è l’implementazione