puzzleup 2018

newkid

#2 LETTER COUNT

The letter count of a number is defined as the number of letters in English spelling of that number. Letters in linking words such as 'and' are not counted. Find the largest number having these properties:

-Its letter count is same as sum of the letter counts of each of its digits.
-No digit is used more than twice.
-Does not start with zero.

Exampe: 5010
"FIVE THOUSAND TEN" has 15 letters.
"FIVE ZERO ONE ZERO" has 15 letters.

一个数字的字母数定义为该数字的英文拼写字母数。诸如'and'之类的连接词的字母不算在内。找出具有这些属性的最大数字：

其字母数与每个数字的字母数的总和相同。
没有任何一位数字被使用多于两次。
起始位不是零。

例如：5010
"FIVE THOUSAND TEN" 有15个字母。
“FERO ONE ONE ZERO”有15个字母。

newkid

Oracle 内置的方法都支持不了太大的数：



超过MILLION的部分：
select to_char(to_timestamp('123','FF3'),'FFSP') FROM DUAL;

TO_CHAR(TO_TIMESTAMP('123','FF3'),'FFSP')
-------------------------------------------------------
ONE HUNDRED TWENTY-THREE MILLION




小于MILLSION的部分：
SELECT to_char(to_timestamp('000' ||'456789','FF9'),'FFSP') FROM DUAL;

TO_CHAR(TO_TIMESTAMP('000'||'456789','FF9'),'FFSP')
-------------------------------------------------------------------------
FOUR HUNDRED FIFTY-SIX THOUSAND SEVEN HUNDRED EIGHTY-NINE


如果在1 和 5373484之间可利用儒略历：

SELECT to_char(to_date(1231234, 'J'), 'Jsp') from dual;

TO_CHAR(TO_DATE(1231234,'J'),'JSP')
-------------------------------------------------------------------
One Million Two Hundred Thirty-One Thousand Two Hundred Thirty-Four

大数的英语级别：
https://en.wikipedia.org/wiki/Names_of_large_numbers

题目可能用到的几个：
Million        1e6
Billion        1e9
Trillion 1e12
Quadrillion 1e15
Quintillion 1e18

自己分3位一级，然后观察插入词对总计数的影响。

solomon_007

# 2

满足条件的最大的5位数：

SQL>
SQL> WITH FUNCTION spell_number (p_number IN NUMBER)
  2  RETURN VARCHAR2
  3  AS
  4     TYPE myArray IS TABLE OF VARCHAR2 (255);
  5  
  6     l_str myArray
  7           := myArray ('',
  8                       ' thousand ',
  9                       ' million ',
10                       ' billion ',
11                       ' trillion ',
12                       ' quadrillion ',
13                       ' quintillion ',
14                       ' sextillion ',
15                       ' septillion ',
16                       ' octillion ',
17                       ' nonillion ',
18                       ' decillion ',
19                       ' undecillion ',
20                       ' duodecillion ');
21  
22     l_num      VARCHAR2 (50) DEFAULT TRUNC (p_number);
23     l_return   VARCHAR2 (4000);
24  BEGIN
25     FOR i IN 1 .. l_str.COUNT
26     LOOP
27        EXIT WHEN l_num IS NULL;
28  
29        IF (SUBSTR (l_num, LENGTH (l_num) - 2, 3) <> 0)
30        THEN
31           l_return := TO_CHAR (TO_DATE (SUBSTR (l_num, LENGTH (l_num) - 2, 3), 'J'),'Jsp')
32                       || l_str (i)
33                       || l_return;
34        END IF;
35  
36        l_num := SUBSTR (l_num, 1, LENGTH (l_num) - 3);
37     END LOOP;
38  
39     RETURN l_return;
40  END;
41  t as (select level-1 n from dual connect by level <= 10),
42  s(n,word,letter_len) as (select 0 n,'zero' word,length('zore') letter_len from dual
43             union all
44             select n,to_char(to_date(n,'j'),'jsp'),length(to_char(to_date(n,'j'),'jsp'))
45               from t
46              where n > 0),
47       r(lvl,num_str,letter_len_sum) as (select 1,
48                                                cast(n as varchar2(30)),
49                                                letter_len
50                                           from s
51                                          where n <> 0
52                                          union all
53                                         select r.lvl + 1,
54                                                r.num_str||s.n,
55                                                r.letter_len_sum + s.letter_len
56                                           from r,s
57                                          where r.lvl < 6
58                                            and regexp_count(r.num_str,s.n) <= 1
59                                            )
60  select max(to_number(num_str))
61    from r
62   where length(replace(replace(spell_number(num_str),'-',''),' ','')) = letter_len_sum
63  /
MAX(TO_NUMBER(NUM_STR))
-----------------------
                  18010


r.lvl < 6，7，8.。。.20   执行不动了。。。

newkid

六位以内可以求出来：
WITH d AS (
SELECT LEVEL-1 n,POWER(10,LEVEL-1) p
      ,decode(level,1,4,length(to_char(to_date(level-1, 'J'), 'Jsp'))) c
FROM DUAL CONNECT BY LEVEL<=10
)
,d3 as (
select lpad(max(n),3,'0') n,cnt_all,c_all,cnt_leading,c_leading,to_char(to_date(max(n), 'J'), 'Jsp') as eng,length(replace(replace(to_char(to_date(max(n), 'J'), 'Jsp'),'-'),' ')) cnt
from (SELECT to_number(d1.n||d2.n||d3.n) n
             ,d1.p+d2.p+d3.p as cnt_all
             ,d1.c+d2.c+d3.c as c_all
             ,decode(d1.n,0,0,d1.p)+(case when d1.n=0 and d2.n=0 then 0 else d2.p end)+d3.p as cnt_leading
             ,decode(d1.n,0,0,d1.c)+(case when d1.n=0 and d2.n=0 then 0 else d2.c end)+d3.c as c_leading
         FROM d d1,d d2, d d3
       )
where instr(cnt_all,'3')=0
group by cnt_all,c_all,cnt_leading,c_leading,length(replace(replace(to_char(to_date(n, 'J'), 'Jsp'),'-'),' '))
)
select to_number(max(a.n||b.n))
  from d3 a,d3 b
where instr(a.cnt_leading+b.cnt_all,'3')=0 and instr(a.cnt_leading+b.cnt_all,'4')=0
       and a.cnt+length('thousand')+b.cnt=a.c_leading+b.c_all
;   

TO_NUMBER(MAX(A.N||B.N))
------------------------
                   18010


九位以内找不到答案：

WITH d AS (
SELECT LEVEL-1 n,POWER(10,LEVEL-1) p
      ,decode(level,1,4,length(to_char(to_date(level-1, 'J'), 'Jsp'))) c
FROM DUAL CONNECT BY LEVEL<=10
)
,d3 as (
select lpad(max(n),3,'0') n,cnt_all,c_all,cnt_leading,c_leading,to_char(to_date(max(n), 'J'), 'Jsp') as eng,length(replace(replace(to_char(to_date(max(n), 'J'), 'Jsp'),'-'),' ')) cnt
from (SELECT to_number(d1.n||d2.n||d3.n) n
             ,d1.p+d2.p+d3.p as cnt_all
             ,d1.c+d2.c+d3.c as c_all
             ,decode(d1.n,0,0,d1.p)+(case when d1.n=0 and d2.n=0 then 0 else d2.p end)+d3.p as cnt_leading
             ,decode(d1.n,0,0,d1.c)+(case when d1.n=0 and d2.n=0 then 0 else d2.c end)+d3.c as c_leading
         FROM d d1,d d2, d d3
       )
where instr(cnt_all,'3')=0
group by cnt_all,c_all,cnt_leading,c_leading,length(replace(replace(to_char(to_date(n, 'J'), 'Jsp'),'-'),' '))
)
,d6 as (
select a.n||b.n n
      ,a.cnt_all+b.cnt_all cnt_all
      ,a.c_all+b.c_all c_all
      ,a.cnt+length('thousand')+b.cnt cnt
  from d3 a,d3 b
where instr(a.cnt_all+b.cnt_all,'3')=0 and instr(a.cnt_all+b.cnt_all,'4')=0
)
select TO_NUMBER(max(a.n||b.n))
  from d3 a,d6 b
where instr(a.cnt_leading+b.cnt_all,'3')=0 and instr(a.cnt_leading+b.cnt_all,'4')=0
       and a.cnt+length('Million')+b.cnt=a.c_leading+b.c_all
;

TO_NUMBER(MAX(A.N||B.N))
------------------------


Elapsed: 00:01:08.59

solomon_007

newkid 发表于 2018-8-12 09:29
六位以内可以求出来：
WITH d AS (
SELECT LEVEL-1 n,POWER(10,LEVEL-1) p

如果9位已内都没有找到其他的话，因为每上升3位，英文拼写的都会增加至少7位，
而数字逐个翻译的，与3位数字的英文拼写长度相差最大也只5位（绝大部分还不如拼写的长），
所以我猜，18010 可能就是最大的了。

SQL> with t as (select level-1 n from dual connect by level <= 10),
  2       s(n,word,letter_len) as (select 0 n,
  3                                      'zero' word,
  4                                      length('zore') letter_len
  5                                 from dual
  6                                union all
  7                                select n,
  8                                       to_char(to_date(n,'j'),'jsp'),
  9                                       length(to_char(to_date(n,'j'),'jsp'))
10                                  from t
11                                 where n > 0),
12       r(lvl,n_str,word_str,spell_str) as (select 1,
13                                                  cast (s.n as varchar2(30)),
14                                                  s.word,
15                                                  s.word
16                                             from s
17                                            where n > 0
18                                            union all
19                                           select r.lvl + 1,
20                                                  r.n_str||s.n,
21                                                  r.word_str||' '||s.word,
22                                                  to_char(to_date(r.n_str||s.n,'j'),'jsp')
23                                             from r,s
24                                            where r.lvl < 3)
25  select max(length(word_str) - length(spell_str)) from r
26  /
MAX(LENGTH(WORD_STR)-LENGTH(SP
------------------------------
                             5

newkid

solomon_007 发表于 2018-8-12 14:06
如果9位已内都没有找到其他的话，因为每上升3位，英文拼写的都会增加至少7位，
而数字逐个翻译的，与3 ...

我也注意到这个差距是随着位数增多越来越大，不可能再跟上的。但这个答案也太配不上这个狗血的题目设定了吧？等数学哥出来说说。

lugionline

每三位数最大的差是4位 10 = ten = onezero,这还是有0的情况，所以100万以内最多差 8 位加少读2个零
每个三位组都必须读，因为最多只有2个零，所以 million，billion这种都必须读，这样超过 1billion后
thousand + million + billion = 22 位 > 4*3+8，所以不会超过1百万，同样也不会超过 100,000，随便搜

newkid

solomon_007 发表于 2018-8-12 14:06
如果9位已内都没有找到其他的话，因为每上升3位，英文拼写的都会增加至少7位，
而数字逐个翻译的，与3 ...

既然M哥也这么说，就给你发个章随便你挑。

solomon_007

newkid 发表于 2018-8-14 23:34
既然M哥也这么说，就给你发个章随便你挑。

凯迪拉克

newkid

#3 CARDS


You have a deck of 10 black cards. You will add at least one and at most five more cards. Each of the new cards can be red, yellow or blue. How many different color sequences can you create after adding the new cards?

Example: If you could add only one new card, the answer would be 33.

你有十张黑卡。你将会加入至少一张卡，最多五张卡。 每张新卡可以是红色，黄色或蓝色。 添加新卡后，你可以创建多少种不同的颜色序列？

示例：如果只能添加一张新卡，则答案为33。

----------
用SQL很简单，用公式可以练练脑子，预防老年痴呆。