TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Názory ke článku Google Code Jam 2008 - cvičení
10. 8. 2008
Jakube, nic moc. Pricitam to Vasemu zvyku psat tak, aby chapali i idioti :)
10. 8. 2008
luky: O zvyku nic nevim, ale me se zda prave naivni popis uloh vhodny pro prilakani lidi, kteri nikdy neresili programovaci ulohy :) Pekny clanek.
Reagoval na komentář od uživatele dejvik : Mám na to stejný názor. Zdejší obsah nemusí být jen pro pokročilé čtenáře.
12. 8. 2008
Tak treba ten problem s vajicky neni moc dobre popsany a na uvedenem odkazu jsem zadani nenasel:(
Podle toho zadani zde vubec nevim, proc mam nektera vajicka, kdyz je stejne nemuzu rozbit, a kdyby ten problem byl takovy, jak je tu popsano, tak bych postupoval binarnim pulenim a pocet pater budovy by byl 2^pocet vajicek
Doporučoval bych pro příště psát takové články ve stylu Matematického koutku tady na programujte, kdy je srozumitelně zadaná nějaká úloha, není předem prozrazeno řešení a zájemci odevzdávají svá řešení v úkolech. Správné řešení je pak prozrazeno v dalším díle.
Co se týče těchto úloh, zaujala mě ta vajíčka. Koukal jsem na originální zadání a oproti tvému řešení jsem nejdřív zkusil vymyslet ten algoritmus házení vajíček, protože bez něj nelze úlohu řešit. Jako nejefektivnější se mi pro tyto účely jeví metoda půlení intervalu (binární půlení). A když víme, jak funguje, stačí jednoduchá matematika základní školy ke spočítání správného řešení.
Moje řešení v Pythonu (dle originálního zadání, pro zde uvedené zadání stačí pouze fce Fmax):
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
def Fmax(D, B):
"""
Vrací maximální počet pater budovy.
D = celkový počet vajíček
B = počet vajíček které můžeme rozbít
"""
# zde je třeba si uvědomit, že v případě, kdy dojde k rozbití
# maximálního počtu vajíček (když se nerozbíjí pouze v prvním
# patře) stačí celkem (D) jen o jedno vajíčko více, než je počet
# k rozbití (B)
if D > B+1:
D = B+1
# omezení z původního zadání, kdy pro řešení >= 2^32 je výsledek
# vždy -1
if D >= 33:
return -1
else:
# a tohle je řešení :-)
return 2**D - 1
def Dmin(F):
"""
Vrací minimální počet vajíček potřebných pro řešení.
F = zadaný počet pater
"""
return int(math.log(F + 1, 2))
def Bmin(F):
"""
Vrací minimální počet vajíček které můžeme rozbít.
F = zadaný počet pater
"""
return Dmin(F) - 1
# teď už těmi funkcemi stačí jen prohnat testovací data
Reagoval na komentář od uživatele Architekt :
Články oproti soutěži vycházejí se značným zpožděním, takže si je zájemci mohou vyřešit nezávisle a s články následně jen porovnat. Psát článek jenom jako přesný překlad zadání by mě nebavilo.
Úloha se zjevně dá řešit i bez znalosti algoritmu, jak dokazuje můj postup.
Půlení intervalu je pro tuto úlohu nedostačující postup. Stačí si představit řešení např. pro celkem 3 vejce, z nichž se 2 dají rozbít. Optimální postup je tento:
[seznam]Začnu ve třetím patře. Když se vejce rozbije, jdu do prvního, jinak do pátého.[/seznam]
[seznam]Když se rozbije v prvním, jsem hotov, jinak jdu do druhého.[/seznam]
[seznam]Když se vejce rozbije v pátém, jdu do čtvrtého, jinak do šestého.[/seznam]
Výsledek je tedy ten, že se dá prozkoumat šest pater. Algoritmus se od půlení intervalů zásadně liší.
Pokud stále nevěříte, tak své výsledky zkuste poslat a uvidíte, že jsou špatně. Např. pro 20 vajec, z nichž lze 5 rozbít, se dá prozkoumat 21699 pater, i když váš algoritmus tvrdí 63.
Reagoval na komentář od uživatele Architekt :
Tak beru zpět co jsem napsal. Koukal jsem na řešení na netu a zjistil jsem že v závislosti na rozdílu mezi D a B je možné začít házet ne v půlce, ale v nižších patrech (a stejně tak přizpůsobit i další hody) a pak se dá prozkoumat vyšší barák.
Reagoval na komentář od uživatele Architekt :
Jak by jen pro zajímavost vypadal algoritmus pro 20 vajec, z nichž lze 5 rozbít:
[seznam]Začnu v 5036. patře. Když se vejce rozbije, jdu do 988. patra, jinak do 9084.[/seznam]
[seznam]...[/seznam]
[seznam]Když se vejce rozbije v prvním patře, jsem hotov. Když se nerozbije v 21698. patře, jdu do 21699.[/seznam]
