Competitive programming – Introdução – Anatomia de um problema
Competitive programming – Introdução – Anatomia de um problema
0 0
slides
Repositório contendo todos as apresentações dos treinamentos e da maratona de programaçãoOn Github maratonato / slides
Competitive programming
Created by Herinson Rodrigues
Conteúdo
- Introdução
- Anatomia de um problema
- Rotinas de I/O
- Onde treinar
Introdução
Fato: "ACM-ICPC é uma competição de programação disputada"
O que veremos pela frente?
"Dado um conjunto de problemas bastante conhecidos em Ciência da Computação, seu trabalho é resolvê-los o mais rápido que você puder!"
Como assim?
- Os problemas já estão resolvidos
- Pelo menos os problem setters já resolveram os problemas
Anatomia de um problema
O problema
Bullshit!
Informações relevantes!
Entrada e saída
Restrições e exemplo de I/O
O que isso significa?
- Seu programa deve produzir a mesma saída que o problem setter produziu utilizando uma entrada secreta
- Seu programa deve resolver o problema dentre um limite de tempo
Rotinas de I/O
1) O número de casos de testes é dado na primeira linha da entrada
int TC, a, b;
scanf("%d", &TC);
while (TC--) {
scanf("%d %d", &a, &b);
printf("%d\n", a + b);
}
Exemplo
2) Múltiplos casos de testes terminam com um valor especial de entrada (geralmente zeros)
int a, b;
while (scanf("%d %d", &a, &b), (a || b))
printf("%d\n", a + b);
Exemplo 2
3) Múltiplos casos de testes terminam com EOF (fim de arquivo)
int a, b;
while (scanf("%d %d", &a, &b) == 2)
printf("%d\n", a + b);
int a, b;
while (scanf("%d %d", &a, &b) != EOF)
printf("%d\n", a + b);
Exemplos 3
Onde treinar
Onde treinar
Estrutura de dados em c++ e java
Created by Herinson Rodrigues
Estrutura de dados
Uma estrutura de dados é um meio de armazenar e organizar dados (não os da imagem!). Estes dados podem ser tipos de dados primitivos e tipos de dados abstratos
Embora uma estrutura de dados não consiga resolver um problema por ela mesma, é fundamental saber escolher a estrutura adequada para cada tipo de problema
No processo de design de um algoritmo, é importante levar em conta:
- inserções
- buscas
- exclusões
- queries
- modificações
Tipos primitivos de dados
C++ boolean char int float double void — — Java bool char int float double — byte shortLimites dos dados primitivos
Todos os tipos de dados primitivos possuem um intervalo de representação numérica
Quer dizer que só usar int pra tudo não funciona?
Não! Familiarize-se com esses limites:
- $2^{10} = 1,024 ≈ 10^3, 2^{20} = 1,048,576 ≈ 10^6$
- Inteiros de 32 bits com sinal (int) e inteiros de 64 bits com sinal (long long) possuem limites superiores de $2^{31}-1 ≈ 2*10^9$ e $2^{63}-1 ≈ 9*10^{18}$, respectivamente
- Ou seja, é seguro usá-los para números de até 9 dígitos (para o int) e de até 18 dígitos (para o long long)
- Para valores $\geq 2^{64}$, utilize a técnica Big Integer (próximas aulas)
Para pensar...
Um número natural é um inteiro não-negativo $(0, 1, 2, 3, 4, 5,...)$. A sua tarefa neste problema é calcular a soma dos números naturais que estão presentes em um determinado intervalo $[A, B]$ inclusive. Por exemplo, a soma dos números naturais no intervalo $[2, 5]$ é $14 = (2+3+4+5)$.
Cada caso de teste contém dois inteiros $A$ e $B$ $(1 \leq A \leq B \leq 10^9)$, representando o limite inferior e o superior respectivamente.
Exemplo de Entrada Exemplo de Saída1 10000 1 5 10 20
500500 15 165
O quão grande é o número $1$$0^{9}$?
Que tipo de dado seria ideal para representar as variáveis A e B?
Solução em C
#include <stdio.h>
int main() {
long long n1, n2;
scanf("%lld %lld", &n1, &n2);
long long sum = ((n2-n1+1) * (n2+n1))/2;
printf("%lld\n", sum);
return 0;
}