12345
返回列表 發帖
ykmran

Rank: 2Rank: 2
11# 跳轉到 »
發表於 2016-3-26 00:31 | 只看該作者
純用permutations既話，可以用少過2*(8P4)既check operations
如果可以做埋char occurrence counting既話，560個check operation夠做。

TOP

hihihi123hk

Rank: 3Rank: 3Rank: 3
12#
發表於 2016-3-26 01:03 | 只看該作者
有問題的, 減唔到/加唔到的
因為 所有symbol 都係 distinct 的
1 - 0 = 1 ( non-commutative)
1+0 = ...
snoopy11hk 發表於 2016-3-26 00:12



    https://github.com/mingchuno/ABC ... nctional/output.txt

solution 喺有用 0 的

TOP

hihihi123hk

Rank: 3Rank: 3Rank: 3
13#
發表於 2016-3-26 01:19 | 只看該作者
純用permutations既話，可以用少過2*(8P4)既check operations
如果可以做埋char occurrence counting既話， ...
ykmran 發表於 2016-3-26 00:31


可以隨意用一個 Lang 做個 Solution 然後給我一個 PR 到 GitHub 嗎？

TOP

vichui

Rank: 2Rank: 2
14#
發表於 2016-3-26 02:07 | 只看該作者
本帖最後由 vichui 於 2016-3-26 14:12 編輯

回覆 2# hihihi123hk

冇眼睇，用Brute Force去做呢題， 可以話係最差的方法。。。
完全冇用到重要的資料去做。。。
1. P=1
2. F+H =11 所以只會有 2+9,3+8,4+7,5+6,6+5,7+4,8+3,9+2                  
3.E+G = 10 所以只會有 2+8,3+7,4+6,6+4,7+3,8+2
由於不能有相同====>
E+G = 2+8，F+H -> 4+7,5+6,6+5,7+4
        = 3+7，F+H -> 2+9,5+6,6+5,9+2
        = 4+6 ,  F+H -> 2+9,3+8,8+3,9+2
        = 6+4 ,  F+H -> 2+9,3+8,8+3,9+2
        = 7+3,   F+H -> 2+9,5+6,6+5,9+7
        = 8+2,   F+H -> 4+7,5+6,6+5,7+4
代入後，可能的EF-GH 就會係
   EF 24 25 26 27 32 35 36 39 42 43 48 49
   GH 87 86 85 84 79 76 75 72 69 68 63 62
   EF 87 86 85 84 79 76 75 72 69 68 63 62               
   GH 24 25 26 27 32 35 36 39 42 43 48 49
每組可能數字的ABCD數字為：
      35 34 34 35 45 24 24 45 35 25 25 35
      69 79 79 69 68 89 89 68 78 79 79 78
e.g. EF=24/87 ABCD 就會係 （3，5，6，9） 組成的, 由於A > C 所以
A-C=2==> 5-3 ==> test 56-39/59-36=24?? ==> No
如果B-D要，借位(A-1)-C=2=> A-C=3 ==> 9-6/6-3== (B <D) => 95 -63/69-35=24??? ==> No

Test Cases 大約係 24* 3*2*2～～ 288
最後。。Coding 唔算太齊整
  1. public class Solver {
  2.         static int count=0;
  3.         static int[] EF={24,25,26,27,32,35,36,39,42,43,48,49,87, 86, 85, 84, 79, 76, 75, 72, 69, 68, 63, 62};
  4.         static int[] GH={87, 86, 85, 84, 79, 76, 75, 72, 69, 68, 63, 62,24,25,26,27,32,35,36,39,42,43,48,49};
  5.         static int[][] ABCD={
  6.                         {3,5,6,9},
  7.                         {3,4,7,9},
  8.                         {3,4,7,9},
  9.                         {3,5,6,9},
  10.                         {4,5,6,8},
  11.                         {2,4,8,9},
  12.                         {2,4,8,9},
  13.                         {4,5,6,8},
  14.                         {3,5,7,8},
  15.                         {2,5,7,9},
  16.                         {2,5,7,9},
  17.                         {3,5,7,8},
  18.                         {3,5,6,9},
  19.                         {3,4,7,9},
  20.                         {3,4,7,9},
  21.                         {3,5,6,9},
  22.                         {4,5,6,8},
  23.                         {2,4,8,9},
  24.                         {2,4,8,9},
  25.                         {4,5,6,8},
  26.                         {3,5,7,8},
  27.                         {2,5,7,9},
  28.                         {2,5,7,9},
  29.                         {3,5,7,8},
  30.                 };
  31.         public static void main(String[] args) {
  32.                 for (int i =0 ; i < EF.length ; i++){
  33.                         testAC(EF[i],GH[i],ABCD[i]);
  34.                 }
  35.         }
  36.         private static void testAC(int ef,int gh, int[] abcd) {
  37.                 // test A-C=E where A > C
  38.                 int e = ef/10;
  39.                 int f = ef-e*10;
  40.                 for (int i =3 ; i >=0 ; i--){
  41.                         for (int j=i-1;j >=0 ; j--){
  42.                                 if(abcd[i]-abcd[j]==e){
  43.                                         int[] canidate = new int[4];
  44.                                         System.arraycopy(abcd, 0, canidate , 0, abcd.length);
  45.                                         swap(canidate,3,i);
  46.                                         swap(canidate,2,j);                                       
  47.                                         if (((canidate[3]*10 + canidate[0]) - (canidate[2]*10 + canidate[1])) == ef){
  48.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 + canidate[0],canidate[2]*10 + canidate[1],ef,gh);       
  49.                                         }
  50.                                         if (((canidate[3]*10 + canidate[1]) - (canidate[2]*10 + canidate[0])) == ef){
  51.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 + canidate[1],canidate[2]*10 + canidate[0],ef,gh);                                                       
  52.                                         }
  53.                                 }                               
  54.                         }
  55.                 }

  57.                 //test A-C=E+1
  58.                 for (int i =3 ; i >=0 ; i--){
  59.                         for (int j=i-1;j >=0 ; j--){
  60.                                 if(abcd[i] - 1 -abcd[j]==e){
  61.                                         int[] canidate = new int[4];
  62.                                         System.arraycopy(abcd, 0, canidate , 0, abcd.length);
  63.                                         swap(canidate,3,i);
  64.                                         swap(canidate,2,j);
  65.                                         if (((canidate[3]*10 + canidate[0]) - (canidate[2]*10 + canidate[1])) == ef){
  66.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 + canidate[0],canidate[2]*10 + canidate[1],ef,gh);                                                       
  67.                                         }
  68.                                         if (((canidate[3]*10 + canidate[1]) - (canidate[2]*10 + canidate[0])) == ef){
  69.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 + canidate[1],canidate[2]*10 + canidate[0],ef,gh);       
  70.                                         }
  71.         if (((canidate[3]*10 + 0) - (canidate[2]*10 + canidate[1])) == ef){
  72.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 ,canidate[2]*10 + canidate[1],ef,gh);                                                       
  73.                                         }
  74.                                         if (((canidate[3]*10 + 0) - (canidate[2]*10 + canidate[0])) == ef){
  75.                                                 System.out.printf("%d: %d - %d = %d + %d = 111 \n",count++,canidate[3]*10 ,canidate[2]*10 + canidate[0],ef,gh);       
  76.                                         }
  77.                                 }
  78.                         }
  79.                 }
  80.         }
  81.        
  82.         public static void swap(int[] array,int i, int j ) {
  83.         int temp = array[i];
  84.         array[i] = array[j];
  85.         array[j] = temp;
  86.     }
  87. }
複製代碼
---> output :
0: 90 - 63 = 27 + 84 = 111
1: 86 - 54 = 32 + 79 = 111
2: 85 - 46 = 39 + 72 = 111
3: 95 - 27 = 68 + 43 = 111
4: 90 - 27 = 63 + 48 = 111

TOP

hihihi123hk

Rank: 3Rank: 3Rank: 3
15#
發表於 2016-3-26 02:22 | 只看該作者
本帖最後由 hihihi123hk 於 2016-3-26 03:10 編輯
回覆  hihihi123hk

冇眼睇，用Brute Force去做呢題， 可以話係最差的方法。。。
完全冇用到重要的資料去 ...
vichui 發表於 2016-3-26 02:07



    但係答案未算完整 Solution

你段 Code 仲缺少咗 2個包含 0 的答案

你呢個 Approach 我係寫 permutation 之前已經諗過，總共有 4條 大 Branch，2條正路 ，但都因為有太多 Possible Trial 。
(1) A > C  , A > 0 , C > 0 , E > 0 , G > 0
(2) P = 1

(3)
B > D
=> F > 0
=> if F + H = 1
=> Either one must be 1  
=>No Solution

(4)
B > D
=> F > 0
=> H > 0 if F + H = 11
=> E + G = 10
=> Possible

(5)
B < D
=> F = F' + 10  > 0 , F' = B - D, F' < 0
=> H > F' , if F' + H = 1, then B - D + H = 1
=> E + G = 11
=> Possible

(6)
B < D
=> F = F' + 10  > 0 , F' = B - D
=> H > 0, if F' + H = 11, then  F -10 + H = 11 , then F + H = 21
=> No Solution

亦見到你睇漏咗，因為你人腦開 Branch 嘅時候已經諗漏咗 (5)

其中一個 Solution 乎合 (5)
  90
-63
-----
  27
+84
-----
111

其中一個 Solution 乎合 (5)
********
  90
-27
-----
  63
+48
-----
111
********

TOP

vichui

Rank: 2Rank: 2
16#
發表於 2016-3-26 02:46 | 只看該作者
因為包唔包0, 本身有好多講法， 如果包0的話， 0 只會出現在B和借位的情況， 因為aceg為0的話， 算式不成立， 也因為0+1=1, 重覆了 fh不可能係0, 而 x-0=, 所以d位也不能。。

所以只需於 a-1-c=e的test中加入 0, canidate[0]  和 0, canidate[1]  的test就可以

TOP

vichui

Rank: 2Rank: 2
17#
發表於 2016-3-26 03:03 | 只看該作者
但係答案未算完整 Solution

你段 Code 仲缺少咗 2個包含 0 的答案

你呢個 Approach 我係寫 permut ...
hihihi123hk 發表於 2016-3-26 02:22

睇唔到借位個case？ 呢個就係 B< D ...
我唔係諗少左， 而係只是寫1-9, 特登唔包0的，因為呢條數唔計0俾小一做係正常d,  計0 的話要高年級些才會識。。

TOP

ykmran

Rank: 2Rank: 2
18#
發表於 2016-3-26 03:11 | 只看該作者
可以隨意用一個 Lang 做個 Solution 然後給我一個 PR 到 GitHub 嗎？
hihihi123hk 發表於 2016-3-26 01:19

你都係高登post到入過黎啦...
https://s-blog.wtako.net/view/17/

TOP

hihihi123hk

Rank: 3Rank: 3Rank: 3
19#
發表於 2016-3-26 03:16 | 只看該作者
睇唔到借位個case？ 呢個就係 B< D ...
我唔係諗少左， 而係只是寫1-9, 特登唔包0的，因為呢條數唔計0俾 ...
vichui 發表於 2016-3-26 03:03



    更新咗 #15 樓

即係你話人地用 Brute Force 係最差嘅方法

然後自己個 Solution 又唔可以覆蓋哂所有 Solution ，有啲講唔過去

TOP

hihihi123hk

Rank: 3Rank: 3Rank: 3
20#
發表於 2016-3-26 12:41 | 只看該作者
本帖最後由 hihihi123hk 於 2016-3-27 17:00 編輯
你都係高登post到入過黎啦...
ykmran 發表於 2016-3-26 03:11


我不是 mingchuno

btw， 見你Python 個 example 係 Imperative Style 有啲難 Follow （經常中途斷 for / return function )，我都做咗個 Scala optimize 版本 (Declarative Style), 可以參考下  可能仲有得 Optimize
https://github.com/mingchuno/ABC ... ter/scala-optimized

原理：
Assume P = 1, 先計 EH GF
(1) 9P4 = 3024
(2)After 1st filter (  e > 0, g > 0) =  2353
(3) After 2nd filter (111 - (g * 10 + h) ==  e * 10 + f)  = 24

再用以上 Result 計 AB CD
ForEach EHGH in  (3), [0,2,3,4,5,6,7,8,9] Diff [EHGF]  => [ABCD_]

24 * 5! = 2880
After 1st filter ( a > 0 , c > 0 , a > c ) = 864
After 2nd filter ( a * 10 + b - (c * 10 + d) == e * 10 + f ) = 5

由於係 Iterator 嘅關係，總共會行
3024 +2880 = 5904 Iteration

呢個 Solution 已經比 Brute Force = 10! = 3628800
或 Assume P = 1, 9! = 362880
好好多

15ms 計完
附件: 您需要登錄才可以下載或查看附件。沒有帳號？註冊

TOP

12345
返回列表