Jump to content
mogers

Google Code Jam 2011

Recommended Posts

mogers

Começa já no próximo fim de semana o Google Code Jam 2011. Este concurso pode abrir muitas portas em termos profissionais. Quem vai concorrer? :(

Google Code Jam 2011

Do you enjoy solving tough problems and grappling with technical challenges? Then enter Google Code Jam!

Google Code Jam is a programming competition in which professional and student programmers are asked to solve increasingly complex algorithmic challenges in a limited amount of time. The contest is all-inclusive: Google Code Jam lets you compete in the programming language and development environment of your choice.

The competition consists of four online rounds, starting on May 6th and culminating in the world finals at Google's office in Tokyo, Japan.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

Eu inscrevi-me e a umas horas de começar ainda não sei se vou participar, pois infelizmente calhou no fim-de-semana do Enterro em Aveiro, ahaha. Mas como ainda não tenho o convite para o enterro, logo ainda não sei se vou, estava aqui a ver como é que isto funcionava...

Primeiro, nunca tinha usado o PHP na consola, mas isso não foi grave e percebi rapidamente...

Mas, agora as minhas dúvidas (visto que o meu inglês é 0)...

O que são aqueles ficheiros para se fazer download?

Qual a diferença entre o pequeno e o grande?

O que se envia é só um ficheiro com o resultado? Se sim, então não é preciso enviar o código-fonte? Se não, como se envia o código-fonte?

Share this post


Link to post
Share on other sites
mogers

a ronda dura 24h, tens tempo a menos k te esqueças dela como eu no ano passado x)

o resto tá tudo em http://code.google.com/codejam/faq.html


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
pedrosorio

Boas,

Eu inscrevi-me e a umas horas de começar ainda não sei se vou participar, pois infelizmente calhou no fim-de-semana do Enterro em Aveiro, ahaha. Mas como ainda não tenho o convite para o enterro, logo ainda não sei se vou, estava aqui a ver como é que isto funcionava...

Primeiro, nunca tinha usado o PHP na consola, mas isso não foi grave e percebi rapidamente...

Mas, agora as minhas dúvidas (visto que o meu inglês é 0)...

O que são aqueles ficheiros para se fazer download?

Qual a diferença entre o pequeno e o grande?

O que se envia é só um ficheiro com o resultado? Se sim, então não é preciso enviar o código-fonte? Se não, como se envia o código-fonte?

Se o teu inglês é 0, torna-se complicado porque toda a competição é em inglês. O chrome com tradutor automático de páginas não te safa? Em relação às tuas perguntas:

- Os ficheiros contêm inputs. O teu programa deve ler o ficheiro de input e produzir um ficheiro de output com o formato que eles indicam. A partir do momento em que fazes download do ficheiro de input um relógio começa a contar e tens 4/8 minutos para submeter o output correspondente ao ficheiro pequeno/grande. Se não o fizeres conta como uma submissão errada.

- Para além da diferença que indiquei acima, no input pequeno, quando fazes a submissão ele diz-te se está correcto ou errado. Se estiver certo, tens o problema resolvido. Se estiver errado, tens 4 minutos de penalização e tens que fazer download de outro ficheiro para tentar resolver.

-No caso do grande, fazes download uma vez do input e podes submeter quantas vezes quiseres dentro dos 8 minutos, e quando acaba esse tempo, esse problema grande fica fechado mas nunca te dizem se está certo ou errado até ao fim do concurso. As pontuações do caso pequeno e grande para cada problema são independentes e o grande vale sempre mais.

-Quer no pequeno quer no grande, se tiveres um erro no formato (o teu output não começa por "Case #1:", por exemplo), és avisado e não tens penalização nenhuma.  O que significa que no caso do input pequeno podes tentar resolver esse mesmo ficheiro de input dentro do tempo que restar e não precisas de fazer download de outro.

- Envias o ficheiro com o resultado e envias o ficheiro com o código-fonte, mas julgo que nas páginas de treino não tens essa opção disponível, só durante o próprio concurso.

Se participares, boa sorte =)


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

Eu uso o Google para traduzir lool.

Não tinha percebido era para que serviam os ficheiros de que se faziam download, pois só têm uma linha  com números e espaços, e por exemplo:

Problem

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input

The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

One line containing the value C, the amount of credit you have at the store.

One line containing the value I, the number of items in the store.

One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.

Each test case will have exactly one solution.

Output

For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Eu fiz este código, talvez não sejas a melhor solução, mas experimentei com os dados do "Sample" e funciona, mas comigo a meter os dados à mão, pensei que fosse assim. Agora com os ficheiros, a minha questão é: o programa tem de estar preparado para ler os dados do ficheiro e não como se fosse o utilizador a inseri-los? E, para além disso, no exercício diz "uma linha para, uma linha para,..." então os ficheiros não deviam vir com linhas? Assim para além de ter de ler do ficheiro, ainda tenho de separar os dados para "convverter" para linhas? Ou estou a fazer uma grande confusão e não é nada disso?

Desculpem a minha ignorância, :cheesygrin:

Share this post


Link to post
Share on other sites
pedrosorio

Input

The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

One line containing the value C, the amount of credit you have at the store.

One line containing the value I, the number of items in the store.

One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.

Each test case will have exactly one solution.

Tradução:

A primeira linha do input dá o número de casos, N. N casos de teste seguem-se. Para cada caso de teste existirá:

Uma linha contendo o valor C, o crédito que tens na loja.

Uma linha contendo o valor I, o número de items na loja.

Uma linha contendo uma lista de I inteiros separados por espaços. Cada inteiro P indica o preço de um item na loja.

Cada caso de teste terá uma solução.

Se leres o problema, e depois vires os exemplos que eles dão em baixo de input e output, é fácil  perceber o formato.

Sim, é suposto o teu programa ler o ficheiro e fazer output para um ficheiro. Normalmente o que se faz é ler do standard input e escrever para o standard output, e na linha de comandos usar "< e >" para redireccionar o input e output. Por exemplo, se o teu programa for o ficheiro "programa" e o input for "A.in" e quiseres fazer  output  para o ficheiro "A.out", farias na linha de comandos:

programa < A.in > A.out


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

Eu percebi o exercício ;)

Mas, como no exercício não diz que tens de guardar num ficheiro, eu fiz como já mostrei acima. Mas, depois para guardar num ficheiro o resultado para depois enviar eu faço "php exercicio.php > resultado.txt" e em vez de mostrar na tela o resultado, grava-o no ficheiro.

Mas a minha dúvida continua, pois no exercício diz "uma linha contendo o valor C, uma linha contendo o valor I, etc", mas nos ficheiros que se faz download só vem uma linha com os dados todos. É isto que não estou a perceber.

Share this post


Link to post
Share on other sites
pedrosorio

Boas,

Eu percebi o exercício ;)

Mas, como no exercício não diz que tens de guardar num ficheiro, eu fiz como já mostrei acima. Mas, depois para guardar num ficheiro o resultado para depois enviar eu faço "php exercicio.php > resultado.txt" e em vez de mostrar na tela o resultado, grava-o no ficheiro.

Mas a minha dúvida continua, pois no exercício diz "uma linha contendo o valor C, uma linha contendo o valor I, etc", mas nos ficheiros que se faz download só vem uma linha com os dados todos. É isto que não estou a perceber.

Isso não corresponde à minha experiência. Podes indicar-me qual é o problema que estás a resolver? Se calhar o ficheiro vem com terminação de linha \n e tu estás a ler isso num editor de windows que não interpreta \n como fim de linha?


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

OH ! O problema era mesmo esse, é que nem me lembrei disso. Eu fiz o download e como vem com um formato desconhecido, estava a abrir com o Bloco de Notas e nem me lembrei desse pequeno grande pormenor.

A minha dúvida era mesmo essa, enfim...

Já agora, mas devemos guardar o resultado num ficheiro via código ou podemos fazer como eu já referi acima!?

E, já agora obrigado pela paciência  ;)

Share this post


Link to post
Share on other sites
pedrosorio

Acho que é mais lógico fazeres o output para o standard output e depois redireccionares como disseste acima para um ficheiro qualquer. O mesmo se passa com o standard input.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Warrior

Eliminei o código colocado, o desafio ainda não terminou.

Vamos ver se não me esqueço de participar, quero uma t-shirt!

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

O código era de um dos exercícios para praticar e não do desafio que está a decorrer agora.

Acabei de chegar, mas dei uma vista de olhos e a vontade para pensar a estas horas não é muita lool.

Já agora, já alguém fez algum ? ;)

Share this post


Link to post
Share on other sites
mogers

eu fiz os 3 primeiros, o D é do estilo que me trama sempre x)

o C é fácil, mas foi dificil provar a mim mesmo que a solução funcionava


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Acordei agora, fiz o B e vou almoçar.

Sou capaz de fazer também o C para ficar seguro, já que só são precisos 25 pontos. (digo isto sem ter lido o enunciado, porque só depois é que vamos ver)

Share this post


Link to post
Share on other sites
Warrior

Resolvi agora o C, e honestamente ainda estou um bocadinho impressionado em relação à solução.

Um grande apreço ao autor deste problema, muito bom.

Share this post


Link to post
Share on other sites
Lfscoutinho

Boas,

Eu vou lá agora tentar, mas ontem dei uma vista de olhos e não percebi nada daquilo, por isso... lool

Share this post


Link to post
Share on other sites
mogers

Nesta área o inglês é fundamental, eu penso que deverias investir seriamente nisso


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Pedro Ribeiro

Eu também já "piquei o ponto" (A, B e C) mas não sei se vou ter tempo de pensar sequer no D. Vamos ver. Isto de ser pai complica as coisas ;)

Share this post


Link to post
Share on other sites
pedrosorio

Eu fui lá meia hora depois do concurso começar a arrependi-me porque estava num daqueles momentos de cérebro zombie, e demorei 2h30 a resolver o A,B,C (sendo que o A e sobretudo o B que são directos foram os que me deram mais trabalho xD).

O C concordo,  é um problema muito bom de facto (btw, a minha solução tem mais palha que não devia estar lá porque só percebi completamente a simplicidade fantástica da solução pouco depois de submeter, mas penso que está correcto, felizmente).

Em relação ao D, o enunciado é muito engraçado, e a solução também ;)


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Tharis

Fiz os 3 primeiros. Tive 1 wrong try no A e no C. No C, a wrong try é mesmo parva. Corri o programa e verifiquei os primeiros casos do input com o output. E parecia que estavam errados porque pensei que o N era ele próprio um caso aka não percebi que aquele número sozinho naquela linha indicava o tamanho do input para aquele caso. Resultado: debug de algo sem bugs. FAIL -.-'

A wrong try do A foi um típico erro estúpido de não fazer limpar a memória que vamos reutilizar. :x

Amei o problema C. Muito fixe mesmo! ;)

Agora estou a pensar se vale a pena pensar no D. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.