Táto úloha je špeciálna. Odovzdávate program, ktorý vypíše vstup pre naše programy. Ak k nej máte nejaké otázky, napíšte nám. Kontakt nájdete pri ostatných úlohách.
Miško so Štepim chystajú nové kolo najlepšieho semináru - PRASKu. Keďže sú veľmi leniví, a už vôbec sa im nechce programovať, Miško sa rozhodol, že sa spýta veľkého jazykového modelu o pomoc. Štepi si je istý, že ten vygenerovaný program nemôže byť správny, nevie to však dokázať. Pomôžte Štepimu nájsť taký vstup, na ktorom Miškov program vygeneruje chybný výstup.
Táto úloha má $4$ podúlohy, za každú viete získať $50$ bodov.
Na vstupe je na jedinom riadku niekoľko medzerou oddelených čísel. Vypíšte druhé najväčšie číslo.
Miškov program:
vstup = [int(x) for x in input().split()]
najvacsie = 0
for i in range(len(vstup)):
if vstup[i] > najvacsie:
najvacsie = vstup[i]
druhe_najvacsie = 0
for i in range(len(vstup)):
if vstup[i] > druhe_najvacsie and vstup[i] < najvacsie:
druhe_najvacsie = vstup[i]
print(druhe_najvacsie)
Na vstupe je jediný riadok medzerou oddelených čísel. Počet čísel je $n$ a $2 \leq n \leq 50$. Hodnoty sú celé čísla v intervale $0$ až $1000$.
1 3 2 5 4
4
Na vstupe je na jedinom riadku niekoľko medzerou oddelených čísel - nadmorské výšky v krajine. Kráľa Stanka by zaujímalo, kolko pozícií v jeho kráľovstve je na vrchole kopca - teda počet takých pozicií, že najbližšia iná nadmorská výška vľavo aj vpravo je nižšia.
Miškov program:
vstup = [int(x) for x in input().split()]
vrcholy = []
odpoved = 0
for i in range(1, len(vstup)):
if vstup[i] > vstup[i-1]:
if len(vrcholy) > 0:
vrcholy.pop()
vrcholy.append(vstup[i])
elif vstup[i] < vstup[i-1]:
while len(vrcholy) > 0:
odpoved += 1
vrcholy.pop()
elif len(vrcholy) > 0:
vrcholy.append(vstup[i])
print(odpoved)
Na vstupe je jediný riadok medzerou oddelených čísel. Počet čísel je $n$ a $2 \leq n \leq 50$. Hodnoty sú celé čísla v intervale $0$ až $1000$.
1 3 4 4 2 3 1 2
3
Sú to pozície s výškou 4, 4 a 3. Pozície na kraji královstva sa nikdy nerátajú.
Medzni $n$ vedúcimi Prasku je $m$ dvojíc kamarátov. Strižo pozná všetkých svojich kamarátov a navyše aj všetkých kamarátov svojich kamarátov. Vypíšte, koľko vedúcich Strižo nepozná.
Miškov program:
n, m, strizo = map(int, input().split())
kamarati = [[] for i in range(n)]
for i in range(m):
a, b = map(int, input().split())
kamarati[a].append(b)
kamarati[b].append(a)
strizo_pozna = [False for i in range(n)]
strizo_nepozna = n
for i in range(len(kamarati[strizo])):
kamarat = kamarati[strizo][i]
if not strizo_pozna[kamarat]:
strizo_pozna[kamarat] = True
strizo_nepozna -= 1
for i in range(len(kamarati[kamarat])):
kamarat_kamarata = kamarati[kamarat][i]
if not strizo_pozna[kamarat_kamarata]:
strizo_pozna[kamarat_kamarata] = True
strizo_nepozna -= 1
print(strizo_nepozna)
Na prvom riadku vstupu sú tri čísla $n$, $m$, a $s$ - číslo Striža. $2 \leq n \leq 100$, $2 \leq m \leq 100$, $0 \leq s < n$. Nasleduje $m$ riadkov, kde každý riadok obsahuje dve čísla $u$ a $v$, ktoré znamenajú, že ľudia s tými číslami sú kamaráti. $0 \leq u \leq n$, $0 \leq v < n$.
5 4 0
0 1
0 2
1 2
3 4
2
Strižo (človek $0$) pozná človeka $1$, a človeka $2$ pozná cez človeka $1$. Ľudí $3$ a $4$ ale nepozná.
V tejto podúlohe nevieme čo presne Miškov program robí (a ani to nechceme zistiť), dôležité je, že program dokážeme spustiť.
Na vstupe je na jedinom riadku niekoľko medzerou oddelených čísel. Vypíšte zvyšok po delení ich súčtu $256$.
Miškov program:
_ = lambda __ : __import__('zlib').decompress(__import__('base64').b64decode(__[::-1]));exec((_)(b'=4M+Sv7H//33n3vW3WoPFmXvNr37068hfhbuPis3Jz+UGn231c9AeFuPmsad+S2o5EIosgU4ABi1AMggDY/EdeWNCOocuOlR5ND1QcEqtMAQvZA9gHDGNEq2uHig+hdAeQKe7UXwp9id4lJQ2wAq5PHA6nIF81sAKPfi2NW3ZevWnhqHf8p0Nqa9sdV39vMImSUD/153Y1LTwiGcMEySNSF1ivR+W7pr+OVB0Q7AYR8Nf+STbS7NXNGiSSo8jqEsMf2Ky72BoeQV78ZDkob39c4ObMizh+iHlK0xahVFRD91x8jKxS2M3iZj5kNrEoXv/ikuLnvFPGOFYdtaEmf7G82agdXdNFvP41u27dN7AKXcjNF2NlVkMwceUCzPKHsZ2bRhc/2kX3z2x06IaVJmPkz3v/VgKoVRk1uIP/ekK6k4lcK8zHgjfULBEUbs3q89fts+Ezqa8xu4PJqDTKkXG8cUjXHc9mFB/NKyWVRZDswk2+osnL0TXHIV+BT0oRtbxohWrLw+Q2oqV0kRlzjOkllLPedTMv5DujZVwf6u5LqHqWjX1j1e7CcITdAs2f65Zxl7pba8jD/lMzbEJEWW+UEIARpLttFp9fSoc2lAupVW/NZ4aYVbS35pgaKwejtF0L5QJApBQqV72dPJEP1KhI+JYUIq3/n3z2QQRBrLrfAblMDxOfYZt5U27oWu8hjUP1Bwv/lHwW9zCPn9laLLdw4BvaLOD4u0s3tOR2rIqGi8r3UXjBkPAXLxNwV8DvP1V854BHoSrNNS6MZ67Iu30EweLEgQdIA1wgJot1lReaO7TMyBPDsH5H0ZB+6ho7dgL/KtqQz+qbhjgWJU0XSdcEHG8zuNNz1n6W+M77NZsmOUoqBmuIvzoGq6RvtCm5rvw8O+Suzt8Kou4224SXoBh7ntXeiH73LHCiENCvlK5v5P/wrE1TsPv0fBtaQQfMD2cyvvZV4zBhwqAf0WPOY+jSJYVGGruAq0yXT9hXB1ckTAnjSDmthd4pxPHS7SY1dlV4JEPMtb342Y/M8UwgzXCg4LOWkALZsczGrb7UZS3j5FZCkwxqSePQ+txeHosSemy5TCr6KfO/fM8afadXqqGlLz1Pz7sREf6BUpP0UspMkX8kcY4QuLk4XiiBFqyzXcizb6l+CTnGiOw23Qr7fh47/+erDt6nldb840CAg6zkC2JfvWynSQQ5IVLLY84nTQDNltBe5oHHIhdzAkE4ZDPBdZ5Zr/1NZhU19EIFGh7xItrg/yKrVw+s8mIZazt9g9KMJ/i5RNBnsFAvP3dH2GIWTu9ULqLb6M4q9C5XrRyXgyfEjC0wjwJMvb3aYIofyRI0lo6B7sAvkdZik5mHhCZP6VFf9Mr5K74WwZLxsEmTXD+HfYxMT5q1r4vsxj82D1iUpH/pPBZ9HDs6WY3JpQ/cj76kkGzqZVes3XAaV1gcVtPFzQjn61NKuM+s6LeOF6lhzDnOpTpPAa1oy/iTnXSiTieLfxEYgy4J6RT2/onGD8pCcKE5/OE8GnFLi/QLDWN8zogF3yYZXyWEv05kHmPcnlF8djcPqgnHkv15llLo/8GU6dYJGVRvx8hFAmfZilxNKa24hC21LkY2mkkOd/ZRXZdTzzWItlFKfuozYCpQwi3GtpgANpJ3cQmPhBbsHhrdLkqKwFtpqVCXqQPK/c/HJGDv/T0F4v/9OaTu7amiRPdnDG43T+xiEzH6LCvVHqsVqJ2jKyhP3SQ8HRJ8CVhIpf2bBp9bzkVUUD3WQae56EvP/o6q72xfRpZ6Eo8oyq+ewEvqayMJy9SdJXw4VfhwAPb3u7O7Poo+o/Ds2wuf5HaDoqxJajqV5+5Yly5jQ5cwJQJgY5zkiOb26LlJRQJFf5doo/Mbg02+MxAUH+gAmgVex/+Fyl8vy6snz/g0pT9xl4z6kJqugrZiNTxqb7Tm0g4hoZV9+B6dWFx4S9L0LP4JSvC3MRe8SdP+iI6ECR5ATIaNYn2TBybh8YLj1ZKABQykYorgHr99gs7bHtrsjnadqKZh9KkgThreqAwT8IUDrZ4cQjZ8SKlMcGjrvfS7I5B0sDEiCEm7UP4ZjKFX1Zhc3iNiqkQQcPKO631f7nqeUorwr5gp8eGmLNnOqTN5OUZZgfoBRdXw6l0rMapqvnPGvHDFYwVzlfntEYr+6PiLhD5nQZ/VmHPEUhExheOmqFz7Uu8CtucaWo+Xt+xT4C2txgNjZnNwoV3YZeOUEDkQKBJDtI3O20JIEXWJ3Qn9cvrXKv8KWdZWGgUJPQxXRTmcsNdEv7ACmUm9KZzK6/XgsI6XvKH6oyuE01y4QYS7fruzi1+DgthhE6xJ2+D6c6b3ss79qcbsx+e72ho4iE93efx04EhmLmD8XCFhIBUH5N5zmAHLOKTM/WjZ1BEi2vlfAsx1MvFIIMOFY+/RS2k6qHw7xhgpzv7eEQ+lTmH7MPcGVojmq4umZ3VpcSTa5GPE3AP6yC5rC/NwVxPbowL4ZpEmyuQe9B394BFn+gY+3JyPj17dYqOV66xdr7csp1hoU7qCIYgtaclHus1+G66s5g+Ga+H7fCklTgOOmSiyK5+3ytzZ1lyXiVVKUVknf2COWCkjtM/YjRiEEBmmXZGiw44CyJQfk/XUGwfK9fwqM5DQc/b5WUfAxbqp2HePAM+7pu9xiTRD/zCKX9hmfxz6+3hjxNPPYFR8im3mdQNVkvB3SzEtKQFRhn7qZM1DMwW+rI1Aaj/YOYvqwbAp4vpmSftQqV4cADPFfKqlxyXx7p91u2dKjGLpScyLUIy5hP1guz2uiz4BG3kVnqvs3qPOze8BuZQE/CjRdpUPce5BBdIkSifDIk25JSnquj/95IpusdusIy7HeJdyYyHStSyeo5LsHm+jpQtX3Nc3Iq+P+vawJku++OLAz773tYRj0s0g/T3ueMtY/NsbdXDyYKPzaeUWfOFwNhNmhoeH5CPELN3dapRoRSXrtMDX8p/LgvEjCWCgFlJ2kjbShaKRz0kIRx5ZOnqQm7jgk3boMO3g5yujjTyeNIlMj/YpwWRD3McEu9Vh8TMYinDCnjLLOozFxU7TgQVPKiWMqg8UgszMG8kzx1YNkGtEqlZf+3rog6Ty7smQiWbQyv8N4ahYCoJdBGUXSsUwCv6kf6vwKGe3swj4BJz+FrJih5ofO9qgusM7oOwGidLV4HCaDMrwRS1K1Wvm3dtfFV3sLhDe2hOwKFCg6iPdcru5fXhMdB/8tBZ9XGXvQFRQ1hZoq5d8SAqhVd6rEvp33BPwiVSydStgtfLLKnCOP8rjxvNXPLyNWKdmrkyyvUH90Nz43Qac/RVhyXIsmkO4Z31+r3PsVneldFkmYYsHzbf997GQhJnvkE2DhwAUU0rdiFo5e5sQXYj7eKPRHgs2mshFXYRT9jLPycMUB2/3GFGmwekpKAvf94ndF+kpht78s8k7LNvGglpFdWhRTRGQ6aUMiZmdwrP3X6fYmiCxdc4puSac6RyqpCeV9PF6ylQEnJaDLq/i8AUOuzRgPJ4wVpYXm2e8+o8vhGgz2UySYdUNDCnE25p2EZERFMIiuducxPPemann0Je47sZHe+QGUMrOuIZ31PMhEe5OMJ6ojGTNKgCXmHcJYC07tqYnWlKC9GJyoQu5DUVSCh1uDKQmtn+gTCvIWZwykuN+vb5amgXKHaGCAsnQiLXLTPKWv/eDTNJ+p61eqLGQxUV1rG7VSYBy75siEsUS/ZWVZ53FuFEmRZEMRWTmI2QMjPgp5i7GHpOTLLEcdEqcsnr11qOGsKXoIn4J8Dw3ugceg7XMZ3QnEwx0D0O1nLBptPjSyD4kUBJnv396QVrxoQKFPSRDlthyfsvHweWr90g07Qh9X4+Euh/2RHaFVh70EbGgYe/jX90djBDxVvTYyxhUwNyYufQxkfmk9pIVWjeY1Ld7KRRB/FCH5Gfv2TJCIVKzWU+HagV5bfB7uzCEXIQDLQSBfwiGgmNXFULluwlYAwvQe+69cLzTkoZq389qLr/9uAa2dAGlbbDl+TT02+Lc8WoqfM4yRVB25jbYRdsAOW+wj5BKTdNVpdwBNZtYxucdNUOZIGZ/DahoqG3tvEzEKjOPW5Vz9+Oz7U+faE2J77qXzRB9LKQdSygTeSq1qE7KL/RPt6b8dUDD7vqFTv4hXjlYG6XX6Nt0GUWi0H0zxCw3pYosGop0GnfJAFEie+2MLOdLRaqMuapigfe6BTN7GCUUwj3M8UROW3wjEoCgZ3ygv4qZ3WsbnrvQds/2sO5XbMFRAuY/REnwx+VeiNd0cVV5BtHKXk6YyRtlrc93wMhjiZ5qk+aYUxGhm4QW/j5XQ/U49kqQ08b73qmo2sPgfJWugwWipJDC3Ha8WmQRtqIVkT7C3MN2+eY3kLm+eGiU1yIdJvchEk6pJjnxtuxRNREqx7i1/mOcPAV0Zc7CbuUFs5/H0gy5f+HCokBK/nxabERb6shF1eX4OOV+P3g6J8wVaBNEbBvLR++13F0HSl3S6OfgjN+kQjG9bfjDD2GiFm66vcgVsmG/90P4GIaqpZO/wkKuMZpcs4q1I6tVdZ2XFo9QiQidOZZHYg7QtpLBXZlv/NV34BlZh2iQ+FF+fJ3Ih6m0TICz+dw9JCfd7KkokpYfb8Ftb6qCjG1QLEeaUPMZWBwCNMNnxtSnir3l5VL5FepZFZPkd0v6BbAjHNaDQFGX1Awp2Hb/xPr90OzrfZMrnUj5waXJoMVtnhJyBI8ijseyqHIJWZg1+Awu933JLPFUB1HZrQtwQofx046hn/lBjcyDv4oFPResvjLLXh+nzyA8VRlTowcO09SIRJickEcCJZ0aTlTHu6uzaXVmGxhx374Q7sptfvyU+ShQZCLvvCEn75ddV7WEdXXse+7m5pXvo9bRqnKJsma2sESKO4Y+n0VxNjw+xjomRYEzUatv38ASECXXe75VLL9MAOSfXcgfulCPBksk44fGrbfvJKx4joBeN8hJEaqdTL3SJhlc4M2vQfZIXk+MbJnk6gLSEBh3pade0HM0x+mzXXxAzOhkDmhRTc3/S7sbWYLbQSWiuebmJx9+66rAyR29/c1vZQZmEXoDr3CpUGSFWELQ+WcJVl4eXJhRroj5JWwbPxv9B7JAJdv+DeaQFKETIAWyzitVpWWcPxv7B5rLsAKx73krnhNutoQ3o7J6p54FtXld3QFHKdQSnuX5GyqG1iywNP+agn3hn3cHW7WlxyR6IKwbNUyRW0J+zPMMn0iGujCvuWTfKbEycBi9IMPGpTX66BtVaqxCqkl4N6O4mnqssn7JW2wJ1BsKv9K/fPsjii/ONc7oKo+twDjYnML/QLt8Ky7dXzWAlxIpWFxJZE+ZuFuA23otAYI+37YVNyOyEJdbvJ80j65otI4pm5X917/2pUAymQpCD/q2bi4IGMti/zmzIVGGv/YUhXozyxGHD8weCObqTIQhoE4NvYKHXuGrLpa1hrzm/OxHCLIGLfmCBAb029iES07eciORVC71q1elCsxlH/hqH2bsoF8IP83A7xR1mN0eMJDJ5DFoo5bzijulQNQ8zkEQbcfJgfPYS9BkHTcjRMyTyx/yG0KhJbuidbg1v37URcD6GLGSI5TYPuyoPllrDH5Ma5R3e3/1yuwvinaYxJ7RitekF6XMHJSKwbcV4z8i9lyyT1ksfuFb/18Mv51oTUNy/I36yVGWaMnzv9o6NlIHU+YgVgL+GmB5LgSrD7bHO4E4uEkZ3zogtzTVD0N36QVS/hctVXjEGWIeGuyCeu7pvku2qAxYzvzOh8JL07C/yxINRZS/rhR6pWN38hoP8DxO2YAfww5zaAP0Oc+s81+ebKT7NcPC2TNslQSGkp4Xm3IZNygWgvxvlf3y/GVl3g1Zuyif08fIRAZF7ZRaJpm+YYTtjThWqwy/Y0cLoQeRmcn4w36b7KqgMiS9Vd59sVajDOIDWZRTLabXGn+qK4qUkzZa/cP1dj1yRKWyRcbbmT3f69+y4+IVXCxlJpq1iNMnyJvODpPxIuWXcR9qF6O+C3vRJOcuP1xB6y+N4ouk+DEaRW5JtvQGbYcuX/IUnGEbBKkcO1q3LHWAS/HFy3lZ4kJsqg01hfWUwOd+m0Q1acyBMY5m/O+2OytqucfapnjCDV9Wvv7tsBc/pm5OsVuZjq1aVxDxVhGUGmQS1KfwkZupTVwRO8uwV+OxTl4upvAslhIH5dDzxxU2Ar5A73XrPB8J62B4kpyoQiCNW7maYHcNwPycix6QjD7pxQOEGmHo3XQRsMUXI/V1HufEGmfXz/9ltKRxMq25nuDaWC+4kU4IknF5nGE0rDXqWlfCV1RLUFC1SaF29aGj1c07+l6c8wl4YULlcDctc5zC3SNloyPtV8s4NkPTbxCfK2//QaOdb5v5yf6MqcN5Mw8TxBYyUAJFHVeJfNGVuK52ce9Vl+c6qW/5jxaDNssPGCEl5jAFHeBmGjTNKFcYqZLBpi02DKsNzBOzmZuPjnj0+4VujCzglEffqHO2dUJnDB5Sl7ZSupjXRBOOjJeG0AOv6Dn2TU4q4VSN0GXYmnGCSkedwU/OwSOModivHnYV2TF7XE7BWd2AcSujE0rFgrmm9nYV/KqQyechAqa+KlkVeBYrSZdWcqovDQXTYSxEWjanqa3LUFjQRuT6dJZxIjAAqD9gfO7hKSPlfEo7R6P2gd8qOvOnK5270abv+dpwHxbNlSvySV1wXvA0da48QZLc7GfAJTpWrNLRS3KkFDfdJIcG0+Q99gFckDMFOaEy1uMRH9vQRJp9s88WbHDw1oHE7vbQbNgQwsi/xax7QBreZu/rVgKSvQeM1XltLeQZeBjHgVDQrYncMYMiKgw+sCUDeHCz5HTubHmE2vxRckPqUO2Pt2AczDFrZvzkJyGjLKGKjO95P54ncDVr17Jv6vFzjbnRO0A7rH+eVUJmg1d7FvkPlAbYAz0PCX4jEpAUPw63i3vhDrFpH9yV15MsAagQJRyRk+/aaPN3KNGNSpcDMSmR7n/eUtTkkBimoUz8quAYOTv3cRwYLwuEBp+ccJK1Z/8oKLJug2Zg1VHcDkN3QSCkU+7+7DJAXkCcv07yMR2j662z2L/FBbqn+oX7JxGhHGuGcUa67ikQIcv2m7Gp32UlxZIikDQo2ziAySnMH05hd24ASYifA+LCScc8id2bX1RtbPPG5EGKlCEsbWB3zf+VFd+fnZC1cobCKdNg6r7H6UvZCwIp3RqPKeDkA2jlSH5I2pJQqByhOteJU6ZzaaRLJXeh3mY/tQ1q/tMWa7ACMuWMyoiFCp2fMxL6ZeaBhHB2Ov3bOjvqhSly4+a+IRuD9pFQKHJLCK14lnk44VXAu5QDHGyHJRObXVrz09tE56519j8yHxVMm8TS0wFexFjbzBkd40U2JP/ow0Ed73jyjDCeoJEsd2s1rfjkg12Dmq1BUrnAMmZ7wdZdaoBW8IfwtRikQDFH7aSpCQMoN46g7l6CRh2HXwKyRxc7jZjC36gyUUJCh+NbHA9pmjIShbyeaOZWni/Dj3f8B7I4kINdPhJk1g8ZFIV2wzMWzlNRmCAnD2R3hWTZkaYOv2JT8pBFFs2cK9v4imsnOmrZyGRQOLNMn9Bxp6vkxfMqB2+oR7NKQiV+87DMu31B3rOrHr1mVNn10sG6aarAc1bPJUBvolQvcX6JOZnkkhNiKLa8qAZ+zfw5aZ//75/Pp///388/fFTVdO7bIZZp0Aq1f949aGJSrmMzMQUrhYGs5/TdJRSqUxyW0lVwJe'))
vstup = [int(x) for x in input().split()]
print(f4(vstup))
Na vstupe je jediný riadok medzerou oddelených čísel. Počet čísel je $n$ a $2 \leq n \leq 50$. Hodnoty sú celé čísla v intervale $0$ až $1000$.
1 2 3 4 5
15
Odovzdávate program, ktorý načíta na jedinom riadku jedno číslo z množiny ${1, 2, 3, 4}$. Váš program má na výstup vypísať vstup pre danú podúlohu, na ktorom Miškov program vypíše zlý výstup.
Napríklad v Pythone:
uloha = int(input())
if uloha == 1:
print('''sem napíš vstup,
môže byť aj na viac riadkov''')
if uloha == 2:
print('''a sem vstup pre druhú úlohu''')
# a tak ďalej
Ak neviete prísť na to, čo Miškove programy robia, alebo kde by mohla byť chyba v Miškových riešeniach, može vám pomôcť program spustiť. Taktiež ho môžete nejak upravovať (napr. pridať pomocné výpisy).
Vzoráky z tohto kola si môžeš pozrieť aj ako video
Program najprv nájde najväčšie číslo a potom nájde najväčšie spomedzi tých, ktoré sa nerovnajú tomu najväčšiemu. Problém je, že keď je viac čísel najväčších, tak to druhé najväčšie je to isté ako to najväčšie, ale náš program vypíše menšie číslo. Program teda pokazí napríklad tento vstup:
1 2 3 4 4
Program postupne číta výšky na vstupe a pamätá si, ktoré miesta sú zatiaľ na vrchu kopca, teda zľava majú niečo menšie. Ak sa ukáže, že v skutočnosti nie sú na vrchu (teda sprava majú niečo ešte väčšie), tak ich vymaže, inak ich vypíše. Problém je, že pri tom vymazávaní vymaže vždy jeden vrchol, ale keď ich je tam viac, tak tie zvyšné tam ostanú. Potrebujeme teda taký vstup, ktorý má dlhšiu rovinku, naľavo od nej niečo nižšie a napravo od nej väčší vrch:
1 2 2 3 1
Môžeme si predstaviť, že Strižo na začiatku nikoho nepozná a postupne spoznáva svojich kamarátov a ich kamarátov. Vždy, keď spozná niekoho nového, tak odpočítame jedného človeka, ktorého zatiaľ nepozná. Keď spozná nejakého svojho kamaráta, potom spozná aj všetkých jeho kamarátov, vrátane seba. To zvyčajne funguje, ale keby Strižo nemal žiadnych kamarátov, tak potom týmto spôsobom nespozná ani seba.
4 3 0
1 2
2 3
3 1
Keď nevieme, čo program robí, jediné čo vieme robiť je skúšať ho púšťať s rôznymi vstupmi a dúfať, že niekedy takto odhalíme nesprávny vstup. Robiť to ručne by zabralo strašne veľa času, takže to chceme robiť automaticky – vygenerovať si náhodný vstup a k nemu správny výstup, spustiť na ňom program a porovnať výstupy. To by sa zvyčajne dalo robiť takto:
import random
_ = lambda __ : #... (sem dám pôvodný program)
def vygeneruj_vstup():
dlzka = random.randrange(2, 50)
cisla = [random.randrange(1000) for _ in range(dlzka)]
return cisla, sum(cisla) % 256
while True:
vstup, spravne = vygeneruj_vstup()
odpoved = f4(vstup)
if spravne != odpoved:
print(*vstup)
Tento kód síce ešte nefunguje (k tomu sa dostaneme), ale aj tak je toto najdôležitejšie ponaučenie z tejto úlohy. Keď máte nejaký kód, ktorý nefunguje, neviete prečo, a kód je príliš zložitý, stále ho môžete testovať tak, že na ňom vyskúšate pustiť veľa náhodných vstupov a pozriete sa na výstupy.
Ak tento program necháte pár minút bežať, tak vám naozaj nájde nejaký vraj nesprávny vstup. Lenže keď vyskúšate znovu pustiť program zo zadania na tomto vstupe, tak vám aj tak dá správny výsledok. Kde je problém?
Tá funkcia f4 je veľmi zákerná a pamätá si nejaký stav, takže keď ju pustíte s nejakým vstupom druhýkrát, tak môže dať iný výstup ako prvýkrát. Riešenie by bolo teda robiť to isté, ale nevolať len tú funkciu, ale vždy nanovo spustiť celý ten program, dať mu nejaký vstup a prečítať jeho výstup. Váš počítač má konzolu (shell), kde viete púšťať iné programy, napríklad je dosť možné že Python púšťate tak, že tam zadáte python3 moj-program.py. A toto vie robiť Python aj automaticky.
Keď si vygooglite niečo ako “python run shell command”, tak sa viete dostať k nejakým návodom, ako to robiť (ja som sa tiež naučil, ako sa to robí v Pythone, až keď som riešil túto úlohu :)). Sú tam nejaké technické detaily, ale netreba sa báť vyhľadávať a čítať návody. Program, ktorý som použil, potom vyzeral takto:
import subprocess
import random
def vygeneruj_vstup():
dlzka = random.randrange(2, 50)
cisla = [random.randrange(1000) for _ in range(dlzka)]
# encode a potom neskor decode znamena, ze ked sa pise na vstup/vystup,
# tak znaky sa musia nejak zakodovat a poslat ako bajty (lebo vsetko v pocitacoch su bajty)
# utf-8 je to co sa standardne pouziva, napriklad 65=A, 66=B a tak dalej.
return (" ".join(map(str, cisla)) + "\n").encode("utf-8"), sum(cisla) % 256
while True:
vstup, spravne = vygeneruj_vstup()
vystup = subprocess.run("python3 magia.py", input = vstup, capture_output = True, shell = True)
# stdout je STanDard OUTput - standardny vystup,
# to je to kam pise vas program, ked v pythone napriklad date print
odpoved = int(vystup.stdout.decode("utf-8"))
if spravne != odpoved:
print(vstup.decode("utf-8"), end = "")
Toto už našlo správny vstup.
Asi vás zaujíma, čo to ten program v zadaní vlastne robil? No, spočíta bitový xor (ako sčítavanie bez prechodov cez desiatku, ale v dvojkovej sústave) čísel na vstupe, a ak je na vstupe viac ako $5$ čísel a ich bitový xor je presne $233$, tak vypíše $1$, a inak správnu odpoveď. Teda nejaký hlúpy program, kde je naschvál nejaká skoro neodhaliteľná chyba. Ak si ale vstupy generujete náhodne, tak aj bitový xor bude náhodný, takže máte šancu približne $1/256$, že sa trafíte a nájdete chybný vstup.
To, prečo ten program robil toto, nechávame ako cvičenie :)