草庐IT

UESTC__ACM 1264 人民币的构造

Irie-Haisenburg 2023-04-21 原文

链接地址：https://acm.uestc.edu.cn/contest/198/problem/J

我们都知道人民币的面值是1、2、5、10，为什么是这个数值呢，我们分析了下发现，从的每个数字都可以由每种面值选出至多一张通过加法和减法（找钱）来构成，（比如：1+2=3，5−1=4，5+1=6，5+2=7，1+2+5=8，10−1=9，）

但是实际上，我们只需要1、2、7三种面值就可以组成的每一个数字了

（1+2=3，7−1−2=4，7−2=5，7−1=6，7+1=8，7+2=9，7+1+2=10）

那么现在问题来了，给一个数，请问最少需要多少种不同的面值就可以构成从的所有数字，注意在构成每一个数字时同种面值不能超过张。

Standard Input

一个数字（1<=<=100000）、

Standard Output

一个数字，代表最少需要多少种不同的面值可以构成从的所有数字。

Samples

Input Output 
10
 
3
Time Limit 1000 ms
Memory Limit 64 MiB
Output Limit 64 MiB

 

题解与思路：

方法一思路：将该题的实质转化为三进制问题，如果加面额则为+1，减去面额则为-1，不用该面额的纸币则为0；所以n张纸币则有3n种情况（打个比方：如果有两张纸币，则状态共有0 0,1 0,-1 0,0 1,1 1,-1 1,0 -1,1 -1,-1 -1共9种），首先很明显能除去n张纸币状态全为0的情况，剩余3n-1种情况，剩余情况中有一半面额之和为负。举个例子：目前有两张纸币面额分别为1，3，则有32-1=8种情况，即1+0=1 , 3-1=2 , 3+0=3 , 3+1=4 , -1+0=-1 , 1-3=-2 , -3+0=-3 , -1+(-3)=-4,可以看出，正数情况和负数情况是相等的，所以正情况一共有3n-1/2种

疑问：正情况只代表了最大值和最小值的取值范围，怎么能够证明出这个范围区间内的所有值都能取到？

证明：利用数学归纳法，很明显，k=1时明显成立（1元最少只用一张纸币,纸币面额为1），k=3时，能表示[1~4]的所有面额，表示的最大数刚好为正情况的最多种数(即3n-1/2种)，假设k=n-1时也成立（纸币面额为1，3，9······3n-2)此时n-1张纸币能表示的范围为[1~3n-1-1/2]，当k=n时（纸币面额为1，3······3n-1即新增加的面额为3n-1），新增加的表示范围为[3n-1+1/2~3n-1/2]=>证明1：因为k=n-1时所能表示的正范围为[1~3n-1-1/2]，由上面的思路可得，负数和正数的情况是对称的，所以能表示的全范围应该是[-（3n-1-1/2）~3n-1-1/2]，此时加上一个新的数3n-1，则将整个区间向前位移3n-1

得新增加的区间[3n-1+1/2~3n-1/2]。此时将新增加的区间和原区间进行合并可得k=n所能表示的区间为[1~3n-1/2]（3n-1/2不是整数！），故得证；

方法二思路：不妨设目前能表示的范围为[1~M],此时增加一个数Q>M，由上面证明中的证明1可得，新增加的可表示范围为[Q-M~Q+M]，要使得增加一个数Q后的区间所能表示的范围更大，并且区间连续无中断，即Q-M=M+1 => Q=2*M+1，所以增加Q后的最大表示范围为[1~3*M+1]，由于我们能知道当人民币面额为1时所能表示的区间为[]1~1]，此时只要区间最大值M不超过n，则可以增加一个数Q，使得区间最大值变为3*M+1，直到n包含在区间内；

方法二的实现代码如下：

#include<iostream>
using namespace std;

int main(){
   int n,max=1,count=1;
   cin>>n;
   if(n==1)
   cout<<count<<endl;
   else
   {
     while(max<n)
     {
         max=3*max+1;
         count++;  
     } 
   cout<<count<<endl;
   }
   return 0;

}

 

UESTC1264spanclassmord算法与数据结构

有关UESTC__ACM 1264 人民币的构造的更多相关文章

  1. ruby - 我如何从 Rational(或任何没有构造函数的类)继承？ - 2

    例如，我可以很容易地继承自String，如下所示:classMyString'thingsandstuff'但是我如何继承没有构造函数的Rational呢？例如:defMyRatNoMethodError:undefinedmethod`new'forMyRat:ClassMyRat(10).inc#=>NoMethodError:undefinedmethod`MyRat'formain:ObjectMyRat.send(:initialize,10).inc#=>TypeError:alreadyinitializedclass#???#Noneofitworks!我找不到初始化新

  2. ruby - 这种类似哈希/树状的构造称为什么？ - 2

    我想创建一个介于散列和树之间的“Config”类。它只是用于存储全局值，可以有一个上下文。下面是我的使用方法:Config.get("root.parent.child_b")#=>"value"类可能如下所示:classConstructdefget(path)#splitpathby"."#searchtreefornodesenddefset(key,value)#splitpathby"."#createtreenodeifnecessary#settreevalueenddeftree{:root=>{:parent=>{:child_a=>"value",:child_b=

  3. NEUQ-acm 预备队训练Week4—BFS/DFS - 2

    1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S

  4. ruby - 将构造函数参数转换为实例变量 - 2

    这个问题在这里已经有了答案:关闭11年前。PossibleDuplicate:Idiomaticobjectcreationinruby很多时候我有一个initialize方法，看起来像这样:classFoodefinitializebar,buz,...@bar,@buz,...=bar,buz,...endend有没有办法用一个简单的命令来做到这一点，比如:classFooattr_constructor:bar,:buz,...end其中的符号代表实例变量的名称(具有attr_accessor、attr_reader、attr_writer的精神/风格)？我想知道是否有内置的方式

  5. 通过传递构造函数的 Ruby YAML 解析器 - 2

    我正在开发一个应用程序，该应用程序从YAML文件获取输入，将它们解析为对象，然后让它们执行它们的操作。我现在遇到的唯一问题是YAML解析器似乎忽略了对象“初始化”方法。我指望构造函数用默认值填充YAML文件缺少的任何实例变量，并将一些东西存储在类变量中。这是一个例子:classTest@@counter=0definitialize(a,b)@a=a@b=b@a=29if@b==3@@counter+=1enddefself.how_manyp@@counterendattr_accessor:a,:bendrequire'YAML'a=Test.new(2,3)s=a.to_yaml

  6. Ruby 构造函数和异常 - 2

    Ruby新手，我想弄清楚使用什么习惯用法来将某些整数值限制为类的构造函数。根据我目前所做的，如果我在initialize()中引发异常，该对象仍会创建，但将处于无效状态(例如，某些nil实例变量中的值)。我不太明白我应该如何限制这些值而不进入看起来不必要的大步骤，例如限制对new()的访问。所以我的问题是，我可以通过什么机制来限制实例化对象的值范围？ 最佳答案 嗯，你是完全正确的，即使initialize引发异常，对象仍然存在。然而，任何人都很难坚持引用，除非你从initialize中泄漏self就像我刚写的下面的代码一样:>>cl

  7. ruby-on-rails - 如何使用 Ruby 中哈希的查询参数构造 URI - 2

    如何通过传递哈希来构造带有查询参数的URI对象？我可以生成查询:URI::HTTPS.build(host:'example.com',query:"a=#{hash[:a]},b=#{[hash:b]}")产生https://example.com?a=argument1&b=argument2但是我认为为许多参数构造查询字符串将不可读且难以维护。我想通过传递哈希来构造查询字符串。就像下面的例子:hash={a:'argument1',b:'argument2'#...dozenmorearguments}URI::HTTPS.build(host:'example.com',que

  8. ruby - 如何更改 Ruby 中类构造函数的返回值？ - 2

    我有课，Foo。我希望能够向构造函数传递一个Foo实例，foo并返回相同的实例。换句话说，我希望这个测试通过:classFoo;endfoo=Foo.newbar=Foo.new(foo)assert_equalfoo,bar有人知道我该怎么做吗？我试过这个:classFoodefinitialize(arg=nil)returnargifargendendfoo=Foo.newbar=Foo.new(foo)assert_equalfoo,bar#=>fails但它不起作用。帮忙吗？编辑因为很多人问过我的理由:我正在对大量数据(许多TB)进行快速分析，并且我将拥有大量对象的大量实例。

  9. ruby-on-rails - 文字和构造函数之间的区别？ ([] 与 Array.new 和 {} 与 Hash.new) - 2

    我很想知道[]和Array.new以及{}和Hash.new之间的更多区别我对它进行了相同的基准测试，似乎简写是赢家require'benchmark'many=500000Benchmark.bmdo|b|b.report("[]\t"){many.times{[].object_id}}b.report("Array.new\t"){many.times{Array.new.object_id}}b.report("{}\t"){many.times{{}.object_id}}b.report("Hash.new\t"){many.times{Hash.new.object_id

  10. ruby - 构造函数覆盖 - 2

    我有一个类:classOnedefinitialize;endend我需要像这样用我自己的构造函数创建一个新类:classTwo但是当我启动代码时，出现错误:thingtest.rb:10:in`initialize':wrongnumberofarguments(1for0)(ArgumentError) 最佳答案 super在这种情况下(没有括号)是一种特殊形式。它使用原始参数调用父类(superclass)方法。尝试调用super() 关于ruby-构造函数覆盖，我们在StackO

随机推荐