Recull de Problemes d'Algorísmia i Programació del GCED

Reculls de solucions en Python dels problemes de les assignatures AP1, AP2 i AP3 del grau de Ciència i Enginyeria de Dades (UPC).

Podeu trobar el llistat de problemes i el seu estat de resolució al final del README

Estructura

• AP1: Comencem · Bucles · Funcions · Recorreguts i Cerques · Recursivitat · Consolidació · Llistes · Matrius i Estructures · Exàmens
• AP2: Piles · Cues de Prioritat · Conjunts · Diccionaris · Dividir i vèncer · Grafs · Arbres · Exàmens
• AP3: Exhaustive search · Dynamic programming · Greedy algorithms · Exàmens

Com contribuir?

• Fes una PR afegint els problemes al repositori. El teu problema serà fàcilment acceptat si:
  • El nom del fitxer comença per l'id del problema de jutge, un bon nom per exemple seria: P11655 - Equal sums II.py
  • El teu problema no apareix a la llista, apareix en algun altre llenguatge o l'has solucionat de forma diferent o més entenedora.
  • El teu problema té una puntuació AC (Accepted, verd, etc.) al jutge.

Ús i raó de l'existència del repositori

Aquest repositori està pensat per complementar l'aprenentatge, no està pensat per substituïr res. També per reforçar l'estudi des de casa. És part del projecte "Apunts Dades" de l'Associació d'Estudiants de Dades. Entregar codi d'aquest repositori com a propi és plagi segons la normativa de la UPC.

Per qualsevol dubte, contacteu amb: roberto.nsoni@aed.cat

Llistat de problemes

AP1

Comencem

• P68688 - Hello world!
• P36795 - Tortuga - Quadrat (1)
• P87353 - Tortuga - Quadrat (2)
• P57548 - Sum of two integer numbers
• P41221 - Sum of three integer numbers
• P37469 - Time decomposition (1)
• P56118 - Maximum of two integer numbers
• P90615 - Maximum of three integer numbers
• P15613 - Temperatures
• P33134 - Tortuga - Formes
• P34279 - Add one second
• P61634 - Leap years
• P51126 - Intervals (1)
• P56559 - Intervals (2)
• P89265 - Intervals (3)

Bucles

• P37500 - First numbers
• P59875 - Top to bottom
• P97156 - Numbers in an interval
• P31170 - Multiplication table
• P55622 - Number of digits (1)
• P50327 - Reversed number
• P28754 - Reversed number in binary
• P67723 - Greatest common divisor
• P25108 - Tortuga - Espiral
• P76755 - Tortuga - Quadrícula
• P72484 - Rhombus
• P30959 - Tots els divisors primers

Funcions, accions i tipus

• P57846 - Maximum of two integer numbers
• P73231 - Maximum of four integer numbers
• P40166 - Factorial
• P88790 - Iterative greatest common divisor
• P57852 - Greatest common divisor of four
• P55722 - Iterative number of digits
• P77686 - Palindromic numbers
• P95401 - Function for leap years
• P36936 - És primer?
• P95972 - Sum of divisors
• P18680 - Factor més petit
• P24683 - Semiprimalitat
• P18777 - Day of the week
• P45598 - L'endemà
• P60801 - Factors primers
• P85158 - Missatge
• P48022 - Tortuga - Rellotge

Recorreguts i Cerques

• P37760 - Trigonometry
• P39057 - Computing areas
• P33839 - Sum of digits
• P61061 - Product of digits
• P78142 - Average
• P12454 - Life expectancy
• P96767 - Polynomial evaluation (1)
• P72986 - Polynomial evaluation (2)
• P23001 - Consecutive repeated words
• P89872 - Second maximum word
• P80660 - The sequence of Collatz
• P59539 - Harmonic numbers (1)
• P58153 - Harmonic numbers (2)
• P89078 - First position
• P39225 - I-th (1)
• P27411 - I-th (2)
• P65103 - I-th (3)
• P48713 - Primality
• P50095 - Next prime number
• P90620 - Pica d'Estats
• P36430 - Fermat's last theorem (1)
• P18203 - Fermat's last theorem (2)
• P94857 - Fermat's last theorem (3)

Recursivitat

• P26108 - Factorial recursiu
• P42523 - Recursive greatest common divisor
• P96965 - Reduction of digits
• P35537 - Increasing numbers
• P22467 - Perfect primes
• P56549 - Changes of base
• P43557 - Perfect primes (hard version)
• P62467 - Bars (1)
• P79860 - Bars (2)
• P10694 - Bars (3)
• P85288 - Towers of Hanoi
• P20006 - Prefixed expression (1)
• P35656 - Expressió prefixada (2)
• P45102 - Completely parenthesed expression
• P50324 - Arbres Fractals
• P23290 - Cercles de Koch
• P10620 - L'amenaça fractal

Consolidació (1)

• P43850 - Uncle Ernie the Magician
• P26492 - Balanced numbers
• P76024 - Sum of fractions
• P42672 - Mixing in base 2
• P74859 - I-th (4)
• P84735 - Smallest multiple
• P54911 - Parells consecutius
• P20262 - Maximum sums
• P39308 - Divisors in order
• P21895 - Strobogrammatic numbers
• P56412 - Funció per als nombres xupiguais
• P68777 - Patró recursiu

Llistes

• P14130 - Equal to the last one
• P67268 - Reverse of sequences
• P71310 - Scalar product
• P50497 - Is it a palindrome?
• P87920 - Equal to the sum of the rest (II)
• P94464 - Dígit més freqüent
• P89124 - Sieve of Eratosthenes
• P53322 - Paraulògic
• P63414 - Counting frequences
• P78548 - Reversing words (1)
• P99133 - Reversing words (2)
• P81966 - Dichotomic search
• P29094 - Position of the maximum
• P81073 - Selection sort
• P98179 - Insertion into a sorted table
• P41412 - Insertion sort
• P70093 - Array merge
• P16072 - Array intersection
• P52205 - Mergesort

Matrius i Estructures

• P28318 - Rows and columns
• P27498 - Transposed matrix
• P61473 - Symmetric matrix
• P26374 - Sum of square matrices
• P37390 - Product of square matrices
• P88905 - Products of matrices
• P16893 - Is it the solution of a Sudoku?
• P44243 - Spirals
• P99555 - Magic squares
• P71711 - Zig-zag
• P87801 - Word search puzzle
• P69476 - Pel·licules (1)
• P28398 - Països i províncies (1) en Python
• P28251 - Països i províncies (2) en Python
• P12284 - Most frequent words
• P33147 - Ordenant rectangles

Generació exhaustiva

• P12828 - Zeros and ones (1)
• P45965 - Zeros and ones (2)
• P69348 - From one to en (1)
• P24674 - Permutations of words

Consolidació (2)

• P36671 - Genetic code
• P65538 - Mode
• P30170 - Repeated words
• P35941 - The Gold-Bug
• P26100 - Game of life (1)
• P27283 - Game of the life (2)
• P12284 - Most frequent words
• P66257 - The most frequent element
• P94464 - Dígit més freqüent
• P18931 - Patró recursiu
• P42922 - Funció per als nombres prims
• P96912 - Prefixos i sufixos
• P41101 - Cicle més llarg
• P12834 - Propagació d'un virus
• P30034 - Nombres complementaris
• P71839 - Vectors quasi-ordenats
• P75290 - Patró recursiu
• P34911 - Simulació d'un ecosistema
• P50250 - Caselles segures
• P99926 - Conjugació
• P42272 - Escriure nombres en lletres
• P19724 - El campanar de la Torrassa
• P98577 - El campanar de la Torrassa strikes back
• P67171 - The return of el campanar de la Torrassa

Exàmens

Examen parcial de prova

• P72200 - Quadrats curiosos
• P56412 - Funció per als nombres xupiguais
• P54911 - Parells consecutius
• P35656 - Expressió prefixada (2)

Parcial 2017

• P85916 - Més zeros o uns?
• P91406 - Mesures topogràfiques
• P42181 - Expressió booleana completament parentitzada
• P66244 - Concatenació composta

Final 2018

• P33147 - Ordenant rectangles
• P89612 - L'alfil rebotador
• P43307 - Nombre de divisors
• P51435 - Cool permutations

Recuperació 2018

• P57540 - Triplets monos
• P53047 - El taxista dislèxic
• P89318 - Forbidden words
• P65201 - Carambole (1)

Parcial 2018

• P87198 - Easy octagons
• P37257 - Function for three equal consecutive digits
• P39308 - Divisors in order
• P68777 - Patró recursiu

Final 2019

• P61061 - Product of digits
• P67731 - Jaccard index
• P77893 - Subsquares in a matrix
• P66705 - Sorting words

Recuperació 2019

• P29054 - Narcissistic numbers
• P87024 - Patró recursiu 2
• P45836 - Min-Max Matrix
• P40710 - Petrol stations

Parcial 2019

• P62355 - Bases and bars
• P78721 - A badly placed word
• P16814 - Subsèrie de Fibonacci
• P70064 - Nombres semiprimers

Final 2020

• P50324 - Arbres Fractals
• P62377 - Successió de Farey
• P99349 - Ordenació de paraules
• P96219 - Els socis

Recuperació 2020

• P87801 - Word search puzzle
• P71701 - Peaceful kings
• P71311 - Become a professional bio-scientist

Parcial 2020

• P81519 - Dibuixant paràboles
• P89700 - Seqüències similars
• P19666 - Base més petita amb el mateix nombre de dígits
• P23290 - Cercles de Koch

Final 2021

• P40706 - Suma de nombres llargs
• P66083 - Una sola escala
• P33354 - Vectors harmoniosos
• P10620 - L'amenaça fractal

Recuperació 2021

• P73242 - X marks the spot
• P20006 - Prefixed expression (1)
• P76554 - Covering with intervals
• P92844 - Bounding rectangle

Parcial 2021

• P39308 - Divisors in order
• P68136 - Nombres creixents-decreixents
• P40353 - Triangle de Sierpiński

Final 2022

• P80928 - Histogrames
• P49287 - Paraules supercreixents
• P44556 - Sous desorbitats

Recuperació 2022

• P67363 - Average and median
• P42181 - Expressió booleana completament parentitzada
• P87801 - Word search puzzle

Parcial Nov 2022

• P24335 - Les fractals del poder
• P91691 - L'enèsim euro
• P98817 - Primers Bessons

Final Gen 2023

• P77360 - Matrius amb marc nul
• P46295 - Soptyfive Wrapped
• P20410 - Nombre de permutacions emparellades

Recuperació 2023

• P24335 - Les fractals del poder
• P16893 - Is it the solution of a Sudoku?
• P14213 - Primer nombre de Hamming

Parcial 2023

• P90689 - La roda del temps
• P39415 - El tresor
• P78422 - Números d-espaiats

Final 2024

• P69316 - Matriu de Haskel
• P20476 - Contant Parells
• P63795 - Triple dobles

Recuperació 2024

• P79387 - Transformation to odd digits
• P66664 - Frequencies on a board
• P72099 - Combinacions afitades

Final 2025

• P45681 - Wall-E
• P26915 - El Coleccionista de Letras Únicas
• P26317 - Enquestes UPC

AP2

Piles

• P52023 - Reverse Polish notation
• P69643 - Checking parenthesis
• P62390 - Simulating recursion (1)
• P34441 - Simulating recursion (2)

Cues de Prioritat

• P59282 - Statistical measures
• P50709 - Collection of numbers
• P62266 - Huffman codes

Conjunts

• P53386 - Paraules en un text
• P92616 - Funcions amb conjunts
• P99649 - Quin falta? (2)
• P93409 - Producte cartesià
• P11754 - Els amics dels meus amics són els meus amics

Diccionaris

• P69288 - Recompte de paraules en un text (1)
• P10730 - Recompte de paraules en un text (2)
• P12284 - Most frequent words
• P40902 - Casino
• P64031 - Chess tournament
• P35117 - Chess club
• P80928 - Histogrames

Dividir i vèncer

• P23800 - A gas station too far
• P80595 - How many inversions?
• P76893 - Superposition of two rectilinear skylines
• P48675 - Superposition of many rectilinear skylines
• P70827 - Closest pair
• P72545 - Select from two sorted arrays

Grafs

• P56483 - Graphs (1)
• P37001 - Graphs (2)
• P88760 - Zamburguesas
• P70690 - Treasures in a map (1)
• P60796 - Treasures in a map (2)
• P90766 - Treasures in a map (3)
• P39846 - Treasures in a map (4)
• P43164 - Treasures in a map (5)
• P14952 - Topological sort
• P43859 - Weighted shortest path (1)
• P13994 - Weighted shortest path (2)
• P68936 - Weighted shortest path (5)
• P12887 - Minimum spanning trees
• P90865 - Strongly connected components
• P17957 - Electrical grids
• P29033 - Two colors
• P10047 - Troba el camí (1)
• P68428 - Puzzle de 8
• P59791 - Pancakes
• P16062 - Pouring water

Arbres

• P98436 - Trees - Recursive traversal
• P61120 - Trees - Height
• P37445 - Trees - Width
• P92765 - Trees - Searching in a binary search tree
• P92776 - Trees - Inserting in a binary search tree
• P21036 - Trees - Printing a tree

Exàmens

Parcial 2018

• P62390 - Simulating recursion (1)
• P86160 - Suma dels k més petits

Final 2018

• P51499 - Christmas raffle
• P27258 - Monstres en un mapa
• P68644 - Push negations

Recuperació 2018

• P80094 - Honest politicians
• P96413 - Erdős number (2)
• P21036 - Trees - Printing a tree

Parcial 2019

• P60296 - Role classification
• P63069 - Number of rotations (1)
• P55375 - Number of rotations (2)

Final 2019

• P69781 - Collatz pseudo-sequences (2)
• P34324 - Random geometric graphs

Recuperació 2019

• P14514 - Coloració de grafs
• P12459 - Grups d'amics

Parcial 2020

• P97803 - Library
• P23519 - Minimitzar el màxim de les sumes

Final 2020 (confinat)

• P24958 - Arbres Verd-Blau
• P40802 - Cheapest Routes

Recuperació 2020

• P74484 - Escriptura d'arbres en graelles
• P77353 - Number of shortest paths

Parcial 2021

• P68660 - Cargols i femelles
• P79292 - Queues of a supermarket (3)

Final 2021

• P49809 - Lowest common ancestor
• P11840 - Amistat a la xarxa

Recuperació 2021

• P38736 - Illes
• P52853 - Lowest common ancestor

Parcial 2022

• P50741 - Servidors
• P11643 - Quick sort amb llistes

Final Juny 2022

• P81478 - Xarxa social
• P63634 - Arbres lògics

Recuperació 2022

• P21259 - Merge sort amb llistes
• P30895 - Camí en un tauler

Parcial 2023

• P61669 - Generadors de Collatz
• P82248 - Selectivitat

Final 2023

• P88233 - Arbres - Mateixes fulles
• P98846 - Donacions
• P17866 - The hungry knight

Recuperació 2023

• P42342 - Arbres binaris de cerca - Elements comuns
• P60296 - Role classification
• P40479 - Painting a board

Parcial 2024

• P91890 - Pila sense duplicats
• P83009 - Quicksort iteratiu
• P72033 - Caja de Ingenieros de Datos

Final 2024

• P92501 - Medianator
• P86567 - Generador d'arbres AVL
• P45234 - Is it cyclic?

Recuperació 2024

• P33884 - Iaies al súper
• P35036 - Mediana
• P97149 - Temps de sequera

Parcial 2025

• P43272 - Els amics dels meus amics són els meus amics (2)
• P50045 - La bossa
• P62891 - Generadors de Recamán

Final 2025

• P42980 - Conjunt ordenat
• P37940 - Negative cycle detection

Parcial 2026

• P67928 - Grafs amb colors
• P50227 - Cua amb nombre màxim de duplicats
• P96604 - Filtre

Final 2026

• P35444 - Presos Agressius
• P96496 - Generador de camins en un arbre binari
• P17458 - Aparallament màxim en un graf bipartit

AP3

0. Exhaustive search

• P33748 - Subsets (2)
• P40685 - Equal sums (1)
• P11655 - Equal sums (3)
• P53046 - From one to en (2)
• P49889 - Consonants and vowels
• P37197 - Incompatible species
• P76807 - Sudoku
• P42934 - Hamiltonian cycle of minimal cost
• P98089 - Interpersonal dislikes
• P18110 - Firefighters and grannies (1)
• P46547 - Digits in optimal order
• P46634 - Maximum cost of a path (1)
• P63648 - Turning off lights
• P64493 - Optimal separation
• P39621 - Cavalls voraços

1. Dynamic programming

• P82409 - Writing parentheses
• P88567 - Adding subrectangles
• P59506 - Some sequences of bits (3)
• P88921 - Scape from the maze
• P96556 - Increasing subsequences
• P52289 - The one of the greatest common subword
• P26005 - The one of the edition distance (I)
• P54504 - Card game
• P87919 - The one of the coins
• P17438 - The game of Nim

2. Greedy algorithms

• P92166 - Peluixos gegants
• X11795 - Covering with intervals
• P40710 - Petrol stations
• P40128 - Setting the video
• P43859 - Weighted shortest path (1)
• P12887 - Minimum spanning trees

Exàmens

Q1 18-19

• P70756 - Partitions
• P68813 - Correct expressions

Q1 19-20

• X10514 - Carbó de reis
• X62901 - Investidura

Q1 20-21

• X62753 - Expressió aritmètica màxima
• X93236 - Selecció musical

Q1 21-22

• X86969 - Estalviant electricitat
• X52431 - Autòmats finits deterministes

Q1 22-23

• X88082 - Canvi mínim
• X74356 - Pintant cotxes

Q1 23-24

• X59979 - D'excursió a Sibèria
• X98001 - Cadenes d'ADN

Q1 24-25

• W29750 - Parèntesis i claus
• W52152 - Nombre cromàtic

Q1 25-26

• X23697 - Índex de poder de Banzhaf (1)
• U17233 - Índex de poder de Banzhaf (2)