Aula 1. Introdução à programação competitiva

Prévia do material em texto

Introdução à programação competitiva
Professor Tomás O. Junco Vázquez
O que é ACM-ICPC?
• Concurso Internacional Universitário de
Programação, organizado pela ACM.
• Competição anual de programação de computadores
entre equipas que representan as instituições de
Ensino Superior.
• Surgiu nos Estados Unidos em 1970.
• Patrocinadores do evento: Apple (1989), AT&T (1990-
1993), Microsoft (1994-1997), IBM (1998-).
• Espectáculo de balões de helio de diferentes cores.
O que é ACM-ICPC?
O que é ACM-ICPC?
Principais metas:
• Incentivar o desenvolvimento e reconhecimento de
habilidades profissionais.
• Proporcionar um espaço onde os estudiantes e
professores podem intercambiar culturas,
experiências e conhecimentos.
• Garantir uma plataforma para orientar e incentivar a
atenção da indústria, academia e o público que possa
olhar as próximas gerações de profissionais da
Informática.
• Site oficial: https://icpc.baylor.edu/
O que é ACM-ICPC?
O ACM-ICPC é um dos eventos académicos mais
antigos e grandes em termos de participação e
prestígio a nível do mundo.
O que é ACM-ICPC?
Níveis de competição em cada ciclo:
1. Concursos Locais. A nível de instituições.
2. Concursos Nacionais. A nível de país.
3. Concursos Regionais. Realizam-se a entre Outubro
e Dezembro de cada ano.
4. Final Mundial. Realizar-se a no primeiro semestre 
do ano seguinte depois dos Concursos Regionais.
CAMPEÕES MUNDIAIS 2004 (NRU-ITMO, RUSSIA) e VLADIMIR PUTIN.
CAMPEÕES MUNDIAIS 2009 (NRU-ITMO, RUSSIA) e DMITRY MEDVEDEV.
CAMPEÕES MUNDIAIS 2011 (ZHEJIANG UNIVERSITY, CHINA).
CAMPEÕES MUNDIAIS 2013 (NRU-ITMO, RUSSIA).
CAMPEÕES MUNDIAIS 2014 (ST. PETERSBURG STATE UNIVERSITY, RUSSIA).
CAMPEÕES MUNDIAIS 2015 (NRU-ITMO, RUSIA).
CAMPEÕES MUNDIAIS 2016 (ST. PETERSBURG STATE UNIVERSITY, RUSSIA).
CAMPEÕES MUNDIAIS 2017 (ST. PETERSBURG ITMO UNIVERSITY, RUSSIA).
Habilidades ACM-ICPC
• Resolução de problemas.
• Disciplina.
• Lógica e gênio.
• Matemáticas.
• Linguagens de programação.
• Idioma Inglês.
• Trabalho em equipa.
Habilidades Profissionais
• Resolução de problemas.
• Disciplina.
• Lógica e gênio.
• Matemáticas.
• Linguagens de programação.
• Idioma Inglês.
• Trabalho em equipa.
Motivações para participar
• Diversão, exercitar a mente e intercâmbio cultural.
Programar é divertido.
• Aumenta o prestígio, visibilidade e o reconhecimento
internacional da instituição e do país.
• Participar e obter prémios nos distintos níveis da
competição de programação mais antiga e prestigiosa
do mundo.
Motivações para participar
• Melhorar habilidades em programação e algoritmos
eficientes na resolução de problemas, com idioma
inglês, matemática e trabalho em equipa.
• Intercambiar experiências e conhecimentos com
pessoas de outras regiões do mundo.
• Obter 1 ano de membro grátis na ACM (acesso a
vários recursos e materiais de alto valor científico,
etc.).
Motivações para participar
• Muitas empresas no ramo tecnológico estão
observando os resultados do evento e dos
participantes em geral.
• Muitos dos participantes, vencedores ou não,
recebem ofertas laborais das empresas; e podem
exibir em seu currículo vital a participação no evento
como um resultado.
• 6 até 12 problemas redigidos em idioma Inglês e de
variadas complexidades.
• Correção automática das soluções. Enfoque de "Tudo
ou Nada" em cada intento de solução.
• Qualificação por quantidade de problemas resolvidos
e tempo total acumulado (inclui penalização pelo
cada envio não certo).
• Duração: 4 a 5 horas. Linguagens: C, C++, Java,
Python.
Detalhes da competição
• Cada equipa está integrada com três estudantes e 
um treinador da mesma universidade.
• Para o ciclo 2017-2018 cada estudante debe ter 
nascido depois de 1994, ou ter iniciado o Ensino 
Superior depois de 2013.
• A composição das equipas é invariavel do principio 
ao fim.
• Cada equipa dispõe de um computador com sistema 
GNU/Linux y outras ferramentas livres. 
• Podem trazer a competição bibliografías não digital. 
Detalhes da competição
Júris on-line
São aplicativos web desenhados para meios
geralmente académicos, que incluem problemas
de diferentes matérias para ser resolvidos
mediante técnicas de programação e, o mais
importante, avaliam automaticamente as soluções
dadas pelos usuarios.
Júris on-line para o treinamento
• http://coj.uci.cu/
• http://codeforces.com/
• http://www.spoj.com/
• http://acm.timus.ru/
• http://acm.sgu.ru/
• https://www.codechef.com/
Exemplo de problema de um júri on-line 
A+B Problem
Time Limit: 1000MS Memory Limit: 10000K
Description
Calculate a+b
Input
Two integer a,b (0 <= a,b <= 10)
Output
Output a+b
Sample Input
1 2
Sample Output
3
Usuario do
júri on-line
Compilador 
Seleccionado
Componente 
de Execução
Componente 
de Julgado
Saída
Esperada
Dados de 
Prova
Descrição
Problema
Solução do usuario
Executável
Saída do usuario
Funcionamento dos júris on-line
Esquema geral de trabalho
Nosso programa
• Algoritmos
• Conhecimento de 
múltiplas matérias
• Técnicas de programação
• Estruturas de dados
• Memória
• Tempo de execução
ENTRADA DOS DADOS
.in
SAÍDA DO PROGRAMA
.out
Sytem.out.println(“Entre o valor de a:”);
…
Sytem.out.println(“A soma é: ” + (a + b));
Esquema geral de trabalho
• Também não é preciso verificar as condições da secção Input.
• Em caso de múltiplas entradas, também não é preciso ler
todas as entradas de uma vez. Podem ser processadas pouco a
pouco.
• Em Java não pode incluir a linha package <nome>;
if(a >= 0 && a <= 10 && b >= 0 && b <= 10){
}
❖Classe Scanner
Scanner in = new Scanner(System.in);
int a = in.nextInt();
❖Classe BufferedReader
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.valueOf(in.readLine());
A principal diferença entre estas duas formas de leitura é quanto a
tempo, com a classe Scanner a leitura é mais lenta.
Entrada dos datos (Java)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
long b = in.nextLong();
double c = in.nextDouble();
float d = in.nextFloat();
String cad1 = in.next();
String line = in.nextLine();
}
}
Entrada dos datos (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.valueOf(in.readLine());
long b = Long.parseLong(in.readLine());
double c = Double.parseDouble(in.readLine());
float d = Float.parseFloat(in.readLine());
String cad1 = in.readLine().split(" ")[0];
String line = in.readLine();
}
}
Entrada dos datos (Java)
❖função scanf()
int a;
scanf("%d", &a);
❖cin
int a;
cin >> a; 
A principal diferença entre estas duas formas de leitura é quanto a
tempo, com cin a leitura é mais lenta.
Entrada dos datos (C++)
#include <cstdio>
int main(){
int a;
long long b;
double c;
float d;
char cad1[100], line[200];
scanf("%d", &a);
scanf("%lld", &b);
scanf("%lf", &c);
scanf("%f", &d);
scanf("%s", cad1);
gets(line);
return 0;
}
Entrada dos datos (C++)
#include <cstdio>
int main(){
int a;
long long b;
double c;
float d;
char cad1[100], line[200];
scanf("%d%lld%lf%f%s", &a, &b, &c, &d, cad1);
gets(line);
return 0;
}
Entrada dos datos (C++)
#include <iostream>
using namespacestd;
int main(){
int a;
long long b;
double c;
float d;
char cad1[100], line[200];
cin >> a >> b >> c >> d >> cad1;
cin.getline(line, 200);
return 0;
}
Entrada dos datos (C++)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String cad = in.next();
//do something
}
}
}
Leitura até fim de ficheiro (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
while(in.ready()){
String cad = in.readLine();
//do something
}
}
}
Leitura até fim de ficheiro (Java)
#include <cstdio>
int main(){
int n;
while(scanf("%d", &n) != EOF){
//do something
}
return 0;
}
Leitura até fim de ficheiro (C++)
#include <iostream>
using namespace std;
int main(){
int n;
while(!cin.eof()){
cin >> n;
//do something
}
return 0;
}
Leitura até fim de ficheiro (C++)
❖System.out.print("ACM-ICPC 2017");
System.out.println();
❖System.out.printf("%s %d\n", "ACM-ICPC", 2017);
❖PrintWriter
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 1 << 16), false);
out.println("ACM-ICPC 2017");
out.flush(); out.close();
A principal diferença entre estas duas formas de saída é quanto a
tempo, com a classe PrintWriter a saída é mais rápida.
Saída (Java)
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
public class Main{
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 1 << 16), false);
out.println("ACM-ICPC 2017");
out.flush();
out.close();
}
}
Saída (Java)
❖função printf()
int a;
printf("%d", a);
❖cout
int a;
cout << a; 
A principal diferença entre estas duas formas de saída é quanto a
tempo, com cout a saída é mais lenta.
Saída (C++)
#include <cstdio>
int main(){
int a; long long b;
double c; float d;
char cad1[100], line[200];
//ENTRADA DOS DADOS
printf("%d\n", a);
printf("%lld\n", b);
printf("%lf\n", c);
printf ("%f\n", d);
printf("%s\n", cad1);
puts(line);
return 0;
}
Saída (C++)
#include <cstdio>
int main(){
int a; long long b;
double c; float d;
char cad1[100], line[200];
//ENTRADA DOS DADOS
printf("%d\n%lld\n%lf\n%f\n%s\n", a, b, c, d, cad1);
puts(line);
return 0;
}
Saída (C++)
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int a; long long b;
double c; float d;
char cad1[100], line[200];
//ENTRADA DOS DADOS
cout << a << endl << b << endl << c << endl << d << endl << cad1 << endl;
cout.write(line, strlen(line));
return 0;
}
Saída (C++)
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Scanner;
public class Main{
public static void main(String[] args) throws IOException{
System.setIn(new FileInputStream("entrada.txt")); 
System.setOut(new PrintStream(new FileOutputStream("saida.txt"))); 
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
System.out.println(a + b);
}
}
Ler/Escrever desde/para um ficheiro em Java
#include <cstdio>
int main(){
int a, b;
freopen("entrada.txt", "r", stdin);
freopen("saida.txt", "w", stdout);
scanf("%d%d", &a, &b);
printf("%d", a + b);
return 0;
}
Ler/Escrever desde/para um ficheiro em C++
Introdução à programação competitiva
Professor Tomás O. Junco Vázquez