プチコン 非公式コミュニティ
トピック
こういち
◆ou0jbJnEJ0Kb
2019/1/18 12:36
2019/1/18 12:36
大会
トラック
良い感じのプログラミングの問題を作ったので、ちょっとしたプログラミングコンテストを開催します。
ルール
･言語はもちろんSmileBasicです。
･最初に正解した人、最も高速に解けるコードを書いた人、正解の中で最も短いコードを書いた人、その他自分がすげぇと思ったコードを書いた人はほめてあげるかも。
･期限は1月いっぱい。多少遅れても大丈夫です。
･投稿方法は、問題を解くプログラムを書いて、その公開キー、スクショ、ソースコードをこのトピックにネタバレ付きで投稿すればOKです。
･一人何回でも投稿可能です。
･ボクも参加します。(審査の対象外)
･BIGやPi Starterでしか動かないプログラム、高度サウンドユニット必須のプログラムも投稿可能です。ただし、BIGやPi Starter専用の場合、審査できないかもしれません。
ルール
･言語はもちろんSmileBasicです。
･最初に正解した人、最も高速に解けるコードを書いた人、正解の中で最も短いコードを書いた人、その他自分がすげぇと思ったコードを書いた人はほめてあげるかも。
･期限は1月いっぱい。多少遅れても大丈夫です。
･投稿方法は、問題を解くプログラムを書いて、その公開キー、スクショ、ソースコードをこのトピックにネタバレ付きで投稿すればOKです。
･一人何回でも投稿可能です。
･ボクも参加します。(審査の対象外)
･BIGやPi Starterでしか動かないプログラム、高度サウンドユニット必須のプログラムも投稿可能です。ただし、BIGやPi Starter専用の場合、審査できないかもしれません。
コメント
こういち
2019/1/18 12:37
◆ou0jbJnEJ0Kb
問題
トラックが倉庫に荷物を運びます。
トラックは1,2,3,…の重さの荷物を積むことが出来るものが1台ずつあり、1,2,4,8,16,…の重さの荷物を限界まで積み、積める重さが小さいものから順に倉庫に荷物を運びます。
倉庫の大きさには限界があり、荷物をN個までしか収納できません。何台目までのトラックが運んだ荷物を全て積むことが出来るでしょう。ただし、各重さの荷物は無限にあるとします。
トラックが倉庫に荷物を運びます。
トラックは1,2,3,…の重さの荷物を積むことが出来るものが1台ずつあり、1,2,4,8,16,…の重さの荷物を限界まで積み、積める重さが小さいものから順に倉庫に荷物を運びます。
倉庫の大きさには限界があり、荷物をN個までしか収納できません。何台目までのトラックが運んだ荷物を全て積むことが出来るでしょう。ただし、各重さの荷物は無限にあるとします。
こういち
2019/1/18 12:38
◆ou0jbJnEJ0Kb
制限
0 <= N <= 2,147,483,647
例
入力
10
出力
6
(1台目のトラックが1、2台目が2、3台目が1と2、4台目が4、5台目が1と4、6台目が2と4の荷物を運ぶことができます。)
0 <= N <= 2,147,483,647
例
入力
10
出力
6
(1台目のトラックが1、2台目が2、3台目が1と2、4台目が4、5台目が1と4、6台目が2と4の荷物を運ぶことができます。)
こういち
2019/1/18 12:54
◆ou0jbJnEJ0Kb
しかし自分で作っておいて言うのもあれだが、このトラックたちは何がしたいのだろうか…
しんいち
2019/1/18 13:51
◆lHy.hAWXbthn
入力が10のときは、出力6になるのでは?(6台目のトラックが2と4の荷物)
こういち
2019/1/18 14:32
◆ou0jbJnEJ0Kb
6ですね。
なおしときます。
なおしときます。
こういち
2019/1/18 14:38 ネタバレ
◆ou0jbJnEJ0Kb
ツララ
2019/1/18 15:09
◆ArUdBYOYME1V
入力値が倉庫に格納できる荷物の限界個数で、出力値が運搬後に荷台を空にできるトラックの台数ってことですね。
なぜかトラックは全て積載重量が同じものは無くて、限界まで積載して出発する。
なお、積載重量はトラックの出発順番と等しく、荷物の重量は２のべき乗単位で用意されていて合計個数が最小になる組み合わせで積み込むとする。
で、倉庫の容量制限の中でトラックの台数は最大で何台になるでしょう？
というのが問いですな。
例文の数値には単位をつけたほうが分かりやすいかも。
なぜかトラックは全て積載重量が同じものは無くて、限界まで積載して出発する。
なお、積載重量はトラックの出発順番と等しく、荷物の重量は２のべき乗単位で用意されていて合計個数が最小になる組み合わせで積み込むとする。
で、倉庫の容量制限の中でトラックの台数は最大で何台になるでしょう？
というのが問いですな。
例文の数値には単位をつけたほうが分かりやすいかも。
ツララ
2019/1/18 15:22
◆ArUdBYOYME1V
あれ？
でも荷物の量は無限ってことは、逆に荷物の重量セットの種類には上限というか制限があるってことなのかな？
だとすると話がちょっと複雑になってくるかも。
でも荷物の量は無限ってことは、逆に荷物の重量セットの種類には上限というか制限があるってことなのかな？
だとすると話がちょっと複雑になってくるかも。
こういち
2019/1/18 17:30
◆ou0jbJnEJ0Kb
たしかに単位がないと不便ですね。
重さはkgということにしておきます。
荷物の種類は31個あって一番重いのは1073741824kgの荷物ですね。
実質無制限です。
考えるときに不都合なら増やしても特に問題ないと思います。
重さはkgということにしておきます。
荷物の種類は31個あって一番重いのは1073741824kgの荷物ですね。
実質無制限です。
考えるときに不都合なら増やしても特に問題ないと思います。
しんいち
2019/1/18 17:51 ネタバレ
◆lHy.hAWXbthn
ツララ
2019/1/18 18:03
◆ArUdBYOYME1V
いやいや
例の
入力10、出力6は
入力10個、出力6台 の方が分かりやすいなってことですん。
単位というか自然数的な数え方の単位ですな。
31種類ってのはビット演算子バリバリ使いこなしてる人には大ヒントっぽいですけど
もうちょっと少ない方向で制限あった方が面白いかも。
例の
入力10、出力6は
入力10個、出力6台 の方が分かりやすいなってことですん。
単位というか自然数的な数え方の単位ですな。
31種類ってのはビット演算子バリバリ使いこなしてる人には大ヒントっぽいですけど
もうちょっと少ない方向で制限あった方が面白いかも。
こういち
2019/1/19 13:19
◆ou0jbJnEJ0Kb
しんいちさん
正解です。
初回答賞ゲットおめでとうございます。
正解です。
初回答賞ゲットおめでとうございます。
こういち
2019/1/19 13:21
◆ou0jbJnEJ0Kb
ツララさん
なるほど。そっちですか。確かにあったほうが分かりやすいですね。
あっ。荷物の種類は変えるつもりないです。
なるほど。そっちですか。確かにあったほうが分かりやすいですね。
あっ。荷物の種類は変えるつもりないです。
笹身
2019/1/19 13:49 ネタバレ
◆AUnhmHIpE1fp
こういち
2019/1/19 15:32
◆ou0jbJnEJ0Kb
笹身さん
おぉ。速い。
O(log(n)^2)かな？
しかも範囲外でも答え出る。
文句なしの正解です。
おぉ。速い。
O(log(n)^2)かな？
しかも範囲外でも答え出る。
文句なしの正解です。
まるだい
2019/1/20 10:41
◆AdwyE6qhnxpV
ついてけん
こういち
2019/1/20 11:41
◆ou0jbJnEJ0Kb
(正直問題の難易度わりと高め)
こういち
2019/1/20 12:04 ネタバレ
◆ou0jbJnEJ0Kb
しんいち
2019/1/21 20:07 ネタバレ
◆lHy.hAWXbthn
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります