puzzleup 2016

〇〇

newkid 发表于 2016-8-3 22:44
第一题附加题的SQL,

https://segmentfault.com网站不错

〇〇

solomon_007 发表于 2016-8-4 00:13
NEWKID 大神，膜拜啊

第二题：

怎么算的,P是什么意思？

lugionline

的确是9

〇〇

lugionline 发表于 2016-8-4 10:11
的确是9

加菲猫真聪明

udfrog

第一题都撸出血了，懵圈了。scala
import scala.math._
import scala.collection.mutable.Set

object test5 {
  def main(args: Array[String]) {
    def notCross(p1: (Int, Int, Int), p2: (Int, Int, Int), p3: (Int, Int, Int), p4: (Int, Int, Int)) = {
      if ((p2._2 - p1._2) * (p4._1 - p3._1) - (p2._1 - p1._1) * (p4._2 - p3._2) == 0)
        true
      else {
        val x1 = min(p1._1, p2._1)
        val x2 = max(p1._1, p2._1)
        val x3 = min(p3._1, p4._1)
        val x4 = max(p3._1, p4._1)
        val x = ((p2._1 - p1._1) * (p4._1 * p3._2 - p3._1 * p4._2) + (p4._1 - p3._1) * (p1._1 * p2._2 - p2._1 * p1._2)) / ((p2._2 - p1._2) * (p4._1 - p3._1) - (p2._1 - p1._1) * (p4._2 - p3._2))
        if (x > x2 || x < x1 || x > x4 || x < x3)
          true
        else
          false
      }
    }

    def notStraight(p1: (Int, Int, Int), p2: (Int, Int, Int), p3: (Int, Int, Int)) = {
      if ((p1._1 + p2._1 == p3._1 * 2 && p1._2 + p2._2 == p3._2 * 2) || (p1._1 + p3._1 == p2._1 * 2 && p1._2 + p3._2 == p2._2 * 2) || (p2._1 + p3._1 == p1._1 * 2 && p2._2 + p3._2 == p1._2 * 2))
        false
      else
        true
    }

    def translate(s: String, s_src: String, s_tgt: String): String = {
      var s1 = ""
      s.foreach(c => s1 += (if (s_src.indexOf(c) >= 0) s_tgt.charAt(s_src.indexOf(c)) else c))
      s1
    }

    def naiveShape(s: String): String = s(0) match {
      case '3' => translate(s, "369258147", "123456789")
      case '7' => translate(s, "741852963", "123456789")
      case '9' => translate(s, "987654321", "123456789")
      case _ => s
    }

    def rotate(s: String): String = {
      val ss = Set(s, s.substring(0, 1) + s(4) + s(3) + s(2) + s(1))
      for (i <- 0 to 4) {
        ss.foreach(s =>
          if (s.substring(i, 5).matches("^[1379].*")) {
            ss += naiveShape(s.substring(i, 5) + s.substring(0, i))
            ss += translate(naiveShape(s.substring(i, 5) + s.substring(0, i)), "236478", "478236")
          }
        )
      }
      ss.min
    }

    val v0 = (0, 0, 1)
    var r = Set.empty[String]
    val p = Set((10, 1, 2), (20, 2, 3), (-1, 10, 4), (9, 11, 5), (19, 12, 6), (-2, 20, 7), (8, 21, 8), (18, 22, 9))
    for (v1 <- p)
      for (v2 <- p - v1 if notStraight(v2, v1, v0))
        for (v3 <- p - v1 - v2 if notCross(v3, v2, v0, v1) && notStraight(v3, v2, v1))
          for (v4 <- p - v1 - v2 - v3)
            if (notCross(v3, v4, v0, v1) && notCross(v3, v4, v2, v1) && notCross(v0, v4, v2, v1) && notCross(v0, v4, v2, v3) && notStraight(v4, v3, v2) && notStraight(v0, v4, v3)) {
              r += rotate(List(v0._3, v1._3, v2._3, v3._3, v4._3).mkString)
            }
    println(r.size)
    println(r)
  }
}

22
Set(12685, 12694, 13597, 12597, 12687, 13567, 12598, 13568, 12567, 12657, 12568, 12658, 12697, 12957, 12675, 12594, 12538, 12958, 15268, 12975, 12945, 12684)

Process finished with exit code 0
再加上一个2开头的共23个

〇〇

udfrog 发表于 2016-8-4 15:36
第一题都撸出血了，懵圈了。scala
import scala.math._
import scala.collection.mutable.Set

2开头为什么要单算

udfrog

第二题的公式为：
p=1-(100-n)*..*(102-2*n)/(100*..*(102-n))
据说当n>9时，p>0.5？倒也还没去算，4和5的结果和加菲的数据完全一样
感觉自己一年不如一年了，高中数学精编a组题的水平，想了一下午才绕出来。。

udfrog

〇〇 发表于 2016-8-4 15:39
2开头为什么要单算

之前以为能省事，后来发现没什么分别，也懒得改了。。。

udfrog

不过还好，在路上思考问题的能力还没丧失，最后在地铁上想出来的公式。搞定了小牛蛙赶紧过来验证下

〇〇

udfrog 发表于 2016-8-4 19:52
第二题的公式为：
p=1-(100-n)*..*(102-2*n)/(100*..*(102-n))
据说当n>9时，p>0.5？倒也还没去算，4和5 ...

我更笨,都看不懂你的公式,加个注释