娱乐 数学算法挑战 [构造] 斯芬克斯之谜

[Nemakori]

题目背景（不阅读题目背景，对回答题目没有任何影响，因此可以随意跳过题面背景）：

云雾猫猫随着风漂到了一个干旱的地方，停在了一个宏伟的雕像门口，遇到了来此考古的学者猫

学者猫：你知道斯芬克斯之谜吗，斯芬克斯会拦下路过的人，如果回答错误的话，是会被斯芬克斯吃掉的。

（正当云雾猫猫要说话，此时雕像处传来的动静）

神秘的声音：路过的旅行者啊，请回答我的问题，否则我会降下神的惩罚

云雾猫猫（打断）：人

神秘的声音：傲慢的人类啊，你以为我会出一道题目两次吗，告诉我，这座雕像，有多少粒沙子，多少个砖块，由多少个人砌成

云雾猫猫：这怎么可能

神秘的声音：想知道答案，那就向我提问吧，不过我只有有限的耐心

题目描述：

斯芬克斯会给云雾猫猫五次机会，其中假设沙子的个数是a，砖块的个数是b，人的个数是c，每次云雾猫猫会给出三个数,k1,k2,k3，在这之后，斯芬克斯会告诉云雾猫猫k1*a+k2*b+k3*c是多少，其中一次问答中，斯芬克斯会给出错误答案

五次提问后，云雾猫猫需要回答a,b,c的值是多少，因此，你需要构造出一种提问方式，使得云雾猫猫一定能够回答出答案

 

注意：

1.题面经过修正，第一次题面有误

2.斯芬克斯会在五次回答中的一次回答给出错误答案

3.题目的答案和提问的系数，均在自然数范围内

4.答案正确且对回答做出具体解释的人会被特别表彰w

 

 

 

 

 

 

七月 17，由Nemakori修改

[Nemakori]

1 分钟前，14741077说道:

四次就行……

分别问

1，0，0

0，1，0

0，0，1

如果有答案等于0就再问一遍

理想情况下，三次分别代表对应的数字

=w=

抱歉抱歉，刚才猫猫犯蠢把题面最重要的部分落了，请注意加粗地方的补充，其中一次斯芬克斯会做出错误回答哦

[Nemakori]

注意：

1.题面经过修正，第一次题面有误

2.斯芬克斯会在五次回答中的一次回答给出错误答案

3.不阅读题目背景，对回答题目没有任何影响，因此可以随意跳过题面背景

4.题目的答案和提问的系数，均在自然数范围内

5.答案正确且对回答做出具体解释的人会被特别表彰w

七月 17，由Nemakori修改

[Nemakori]

4 分钟前，hentai14说道:

跑去問了chatGPT, 他回答的似乎有道理 <--但這人腦袋空空了

加上驗證用的兩組

• (1,1,0)
• (1,0,1)

  诶诶，怎么还有人工智能参赛选手，所以说GPT给出的理由是什么呢（补充 ： 此次询问不告知正确性 具体正确楼层与标准题解证明在明日给出）

七月 17，由Nemakori修改

[Nemakori]

20 分钟前，hentai14说道:

因為複製時不知道為何英文數字都被重複三次, 所以節錄重點

设定这五个提问之后，斯芬克斯会给出五个答案 A1,A2,A3,A4,A5，其中：

• A1=a
• A2=b
• A3=c
• A4=a+b
• A5=a+c

即使其中有一个答案是错误的，我们可以使用以下方法确定正确的 a、b 和 c 的值：

• b=A4−a=A4-A1
• c=A5−a=A5-A1

嗯... A2 != A4-A1時, 也分不出來哪個是對的...

 

 

w 其实这个做法已经很接近正确答案了哦 因为他其实可以很容易确定其中三组是正确的，但是没法通过那三组正确的答案去确定剩下的两组哪组是错误的，已经很厉害了哦

[Nemakori]

34 分钟前，刁刁茶茶丸说道:

1 0 0 =x
0 1 0 =y
0 0 1 =z

然后 根据斯芬给出的x，y，z的位数设定下次提问的k1 k2 k3的值
例如说x=21 y=555 z=9998

那么第四次提问时的k1 k2 k3的值就设定为 1 , 1000，10000000。
理想中的结果就会是 99980555021

因为通过位数将前三次提问得到的参数分离开了，所以第五次提问针对出现问题的那个值重复一次就好了w

emmmm 因为原题目是来源于算法竞赛中的一道题，有数据范围限制QwQ，所以我可能需要一段时间去消化佬的做法，不过这个思路真的很有意思

不过我有个提问 假如第四次的回答是99980555021 + 10000000000的话 该怎么确定a,b,c的值，此时第四次回答的错误均可能来源于a,b,c，比如a是21+10000000000，b是10000000+555,c是1000+9998或者第四次回答均可以产生错误，那么第五次提问该如何验证

七月 17，由Nemakori修改

[Nemakori]

11 分钟前，367ddd说道:

首先提问三组线性无关的向量a1,a2,a3，然后提问a4，a5取到在a1到a3中任取其一与两者匹配线性无关，不妨取a1+a2+a3，a1+2a2+3a3。通过a1，a2，a3的答案来验算a4，a5，如果是a4到a5中有一个错误答案，则a4和a5的验算中，只有错误的一个会验算不匹配，对于这种情况，由于我们有线性无关的三组变量a1，a2，a3，所以可以通过它们求出正解。

如果a1到a3中有一个错误答案，则a4和a5的验算全不匹配。在这种情况下，由于a1,a4,a5和a2,a4,a5和a3,a4,a5都是线性无关的三组变量，所以我们可以求出三组解，由于a1到a3中，有只仅有一个错误向量，所以这三组向量中仅有一组包含错误向量，所以易知这三组解中，有且仅有两个解相等且为正解，结束。

应该就这样了，好久没动脑子了

虽然我现在不能对你的回答给出正确与否的评价，但是我有理由怀疑佬是不是接触过OI

[Nemakori]

1 分钟前，U咩说道:

猪脑过载了

①  1  0  0 =a

②  0  1  0 =b

③  0  0  1 =c

④  1  1  0=a+b

⑤  1  0  1=a+c

通过①④和①⑤可以得到第二组b和c

若①为正确，那么两组bc中仅有b或者c不同

若①为错误，那么两组bc均不相同

 

其实在①③正确的情况下 我们这个时候通过正确的ac可以给④也解出一个b 这个时候我们有②，④解出的两个b的值 但是我们无法判断2，4的b哪个是正确的哦

[Nemakori]

刚刚，IOPU说道:

这种方式总有且仅有一个字母无法算出(我最开始用这个方法也猪脑过载了,卡在那了)

嗯嗯 所以说这是一个很接近正确答案的解法哦 其实已经很厉害啦~

[Nemakori]

3 分钟前，IOPU说道:

很接近正确解法?

我总感觉在五次询问中间应该有有一个if来判断接下来的k1,k2,k3应该是什么

但是我试了几个,仍然存在有一种情况其中一个字母无法判断

hhh 我第一次看这题的时候 也卡了很久啦 一开始就想到了上面那个做法，然后就抓住题目的依次询问，可以通过得到的答案的值来决定下一次询问，然后就卡在这个坑里了，等佬看见我的题解就知道为什么很接近正确做法了QwQ

七月 17，由Nemakori修改

[Nemakori]

17 小时前，挼挼说道:

①1 0 0

②0 1 0

③0 0 1

④1 1 1

⑤1 1 1

①错了时，④-②-③，⑤-②-③对比即得

②、③同理

④、⑤错了，①+②+③比较也能得出

这应该没问题吧？

不是很自信

有哦 ④⑤值相同可以确定前三个有错 但是怎么确定前三个错的是哪个呢

[Nemakori]

17 小时前，danielrosen4说道:

由题意，需要构造五个向量kn（k1,k2,k3），并且保证任取3个kn都互相线性无关。

不妨构造（1,0,0）（0,1,0）（0,0,1）（1,1,1）（1,-2,2）为k1、k2、k3的取值，

那么得到如下的五条方程：（Pn为第n次提问时得到的求和答案）

①P1=a

②P2=b

③P3=c

④P4=a+b+c

⑤P5=a-2b+2c

将上述五条方程中任意舍弃一条，将剩余部分构造为方程组，得到包含等式②③④⑤的方程组1、包含等式①③④⑤的方程组2、包含等式①②④⑤的方程组3、包含等式①②③⑤的方程组4、包含等式①②③④的方程组5。

这五个方程组中仅有一个会有解，那个解就是abc的值。

其实 构造思路完全正确 但是 注意审题哦 提问的值需要是自然数 不包括负数 不过无所谓啦 算你对了

[Nemakori]

1 小时前，刁刁茶茶丸说道:

如果斯芬提前知道这样的提问方式，并且有意识地来选择让数据出错的方式来专门干扰这种方式的话

仅凭第四次提问确实没办法独立完成对数据的校对，但我们可以通过拉大第五次提问的位数来对抗这种混淆

例如斯芬给出的第四次回答的位数为1*10^10，

那么第五次提问就将 k1 k2 k3设定为 1 , 1*10^(10+1)，1*10^(20+1)

或者将k1 k2 k3的顺序进行调转 例如改成 10000000，1,1000

这样...应该...就能获取足够的信息来确定abc的值了（瘫）



用具体数字来说明的话（我取个小一点的数字吧...）

不出现混淆的情况：
a：2                                      
b：3
c：5

d：50302

 

出现混淆的情况：
混淆a：2                            真实a：1000002          
b：3
c：5

d：1050302

将间隔调整为1*10^（6+1）后

e：5000000031000002

就可以获取到无混淆的abc值了....

 

（数零数到头昏）

 

暂时没发现问题 佬应该是唯一一个用到提问是一次一次提问这个条件的 点赞w

[Nemakori]

题解已出 欢迎捧场哦 顺带敬请期待下一期

@hentai14 @IOPU  @U咩 @挼挼

题解链接：

https://sstm.moe/topic/358970-【题解】数学算法挑战-斯芬克斯之谜/

[Nemakori]

7 小时前，Prism说道:

总算升级了能回复了

看上去应该可以看成一个线性方程组解问题（

每一次提问都可以构造一个向量，构成一个 5 * 4 的矩阵，总共可以取出 5 个 4 阶方阵，因为有一个结果是错误的，所以仅有一个方阵是有解的

是的 但是为了解出结果方便的话 大多数是我给的通解范围内的构造

[Nemakori]

于 2024/7/25 于 AM2点59分，Muriya Tensei说道:

才看到题，第一反应是想到一个简单的思路

基础思路是通过哈希把三个值编码到三个不同的维度，那么每次询问相当于同时校验三个值

但是存在一个可能的问题就是因为不知道值域，因此无法确定出无冲突的哈希，那么可以先通过询问确定值域

如先询问两次a+b+c（由题意三者均非负）

那么单独的a+b+c必然不会超过这个范围

接下来，把之前得到的a+b+c较大者+1作为进制p（当然取更大的素数p 或者直接取位数h 进制取 10^h也是一样的道理）

再次询问 a+b*p+c*p^2 三次（如果前两次不同的话甚至询问两次就够了）

再根据p解码出abc后，取重复出现的即可

---

去看了眼原题，果然是ICPC啊（）

题目限定了系数只能取 [0, 10] 那就肯定没法编码到三维了，那还是线代吧

应该是只要满足任选三个向量均线性无关即可

这样任意三个都能解出一组解，并且错误的解的组数小于正确的组数

不过 没有数据范围的限制感觉有更多更有意思的解法 算是意外之喜了w