标签: 信息奥赛

Bard升级到Gemini了,但是不怎么样

谷歌开了个发布会,挺热闹的,早上试了下bard,确实升级到Gemini了,但是不是Ultra。

测了一下做题能力,直接给题目,没有任何引导和提示。对比一下bard和GPT-4的答案。

题目:

# [USACO1.5] 回文质数 Prime Palindromes

## 题目描述

因为 $151$ 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 $151$ 是回文质数。

写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$(一亿)间的所有回文质数。

## 输入格式

第一行输入两个正整数 $a$ 和 $b$。

## 输出格式

输出一个回文质数的列表,一行一个。

## 样例 #1

### 样例输入 #1

```
5 500
```

### 样例输出 #1

```
5
7
11
101
131
151
181
191
313
353
373
383
```

## 提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数(素数).


Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数,你可能需要几个像下面这样的循环。


题目翻译来自NOCOW。

USACO Training Section 1.5


产生长度为 $5$ 的回文数:

```cpp
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

```

先看Bard的答案:(完整答案链接在这里https://g.co/bard/share/310082fb6c72)

#include <iostream>
using namespace std;

// 判断一个数是否是质数
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 生成长度为 n 的回文数
int generatePalindrome(int n) {
    int max_digit = 9;
    if (n % 2 == 0) {
        max_digit = 8;
    }
    int palindrome = 0;
    for (int i = max_digit; i >= 0; i--) {
        palindrome = palindrome * 10 + i;
    }
    return palindrome;
}

int main() {
    int a, b;
    cin >> a >> b;
    // 注意:这里只需要判断奇数,因为偶数一定不是质数
    for (int i = 3; i <= b; i += 2) {
        // 判断 i 是否是回文数
        int palindrome = generatePalindrome(i);
        if (i == palindrome && isPrime(palindrome)) {
            cout << palindrome << endl;
        }
    }
    return 0;
}

对题目的分析基本都对(可以看链接里面的文字),但是代码提交得0分。

再来看GPT 4的答案:https://chat.openai.com/share/f78d1596-90fe-4e33-9215-9a9a56086ed2

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int createPalindrome(int input, int b, bool isOdd) {
    int n = input;
    int palin = input;
    if (isOdd)
        n /= b;
    while (n > 0) {
        palin = palin * b + (n % b);
        n /= b;
    }
    return palin;
}

void generatePalindromes(int a, int b) {
    int number;
    for (int j = 0; j < 2; j++) {
        int i = 1;
        bool isOdd = (j % 2 == 0);
        while ((number = createPalindrome(i, 10, isOdd)) < b) {
            if (number >= a && isPrime(number)) {
                cout << number << endl;
            }
            i++;
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    generatePalindromes(a, b);
    return 0;
}

其实两者分析题目的结论都差不多,也都是对的,但是代码不一样。gpt得了55分

结论,都不太能打。

我让chatGPT(gpt4)做了一下CSP-J的题目,结果让人失望

今天让chatGPT做了两道2023年CSP-J的第二轮题目,比我想象的要差一些,CSP-J按道理说不是特别难的编程题目,我以为chatGPT能轻松拿下的。

第一题

[CSP-J 2023] 小苹果

题目描述

小 Y 的桌子上放着 $n$ 个苹果从左到右排成一列,编号为从 $1$ 到 $n$。

小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。

每天在拿的时候,小苞都是从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道,多少天能拿完所有的苹果,而编号为 $n$ 的苹果是在第几天被拿走的?

输入格式

输入的第一行包含一个正整数 $n$,表示苹果的总数。

输出格式

输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 $n$ 的苹果是在第几天。

chatGPT的基本解题过程如下:

先是给出了一个错误的题目理解

最后这个代码在洛谷的数据上测试,得了90分,最后一组测试数据因为数据太大内存超限了。

如果说这道题目是差强人意的话,第二道题目直接就蒙了,做了十几遍连示例数据都过不了。

[CSP-J 2023] 公路

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 $n$ 个站点,编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i + 1$ 的距离为 $v_i$ 公里。

公路上每个站点都可以加油,编号为 $i$ 的站点一升油的价格为 $a_i$ 元,且每个站点只出售整数升的油。

小苞想从站点 $1$ 开车到站点 $n$,一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 $d$ 公里。问小苞从站点 $1$ 开到站点 $n$,至少要花多少钱加油?

输入格式

输入的第一行包含两个正整数 $n$ 和 $d$,分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 $n – 1$ 个正整数 $v_1, v_2\dots v_{n-1}$,分别表示站点间的距离。

输入的第三行包含 $n$ 个正整数 $a_1, a_2 \dots a_n$,分别表示在不同站点加油的价格。

输出格式

输出一行,仅包含一个正整数,表示从站点 $1$ 开到站点 $n$,小苞至少要花多少钱加油。

前面分析的有模有样

但是给出的代码无论是动态规划还是贪心算法都不对。测试了几轮之后,我让它直接用python写算法,因为我用的是code intepreter 模型,可以直接运行python代码。我提供测试数据,让它写完代码之后把测试数据带入程序自己看输出结果是否正确,然后它就陷入了死循环。

很努力的做不对

看来在给出更清晰的引导之前,它自己是没办法作出这道题目了。

10.31更新

CCF官方给出了数据,在新的官方数据的条件下,chatGPT4这次写出了这道题目,但是不确定是数据的关系比较大还是最近GPT-4被喂了比较多算法的关系比较大

题目的理解和分析:

这道题目的核心问题是找出从站点 1 开车到站点 ( n ) 的最低油费。每个站点 ( i ) 之间的距离是 ( v_i ) 公里,站点 ( i ) 的油价是 ( a_i ) 元/升。车的油箱足够大,每升油可以行驶 ( d ) 公里。

算法思路

  1. 初始化变量:
    • min_cost 为 0,用于记录最小油费。
    • current_fuel 为 0,表示当前油能行驶的距离。
    • cheapest_price_so_far 为 ( a_1 ),即第一个站点的油价。
  2. 遍历每个站点 ( i )(从 1 到 ( n-1 )):
    • 计算从站点 ( i ) 到站点 ( i+1 ) 所需的油量 needed_fuel(以距离表示)。
    • 如果 current_fuel 小于 needed_fuel,则需要在最便宜的油站加足够的油以到达站点 ( i+1 ),然后更新 min_costcurrent_fuel
    • 更新 cheapest_price_so_far 为 ( \min(cheapest_price_so_far, a_{i+1}) )。

时间复杂度

由于我们只遍历一次所有站点,算法的时间复杂度是 ( O(n) ),这在题目给定的数据范围内是可行的。

特点

这个解决方案的一个重要特点是它的贪婪性:在任何时候,我们总是选择当前最便宜的油站进行加油。这是因为,如果有更便宜的油站,那么在那里加油总是更优的。

这样的算法也适应了各种可能的特殊情况,例如一开始油价就很高但后来变便宜,或者油价在途中突然上升等。

希望这能清晰地解释这个问题和解决方案。如果你有其他问题或需要更多的细节,请随时问。

代码:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<int> v(n - 1);
    vector<int> a(n);
    
    for (int i = 0; i < n - 1; ++i) {
        cin >> v[i];
    }
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    long long min_cost = 0;
    long long current_fuel = 0;  // Stored as distance the fuel can cover
    long long cheapest_price_so_far = a[0];
    
    for (int i = 0; i < n - 1; ++i) {
        long long needed_fuel = v[i];  // Needed fuel (converted to distance)
        
        // Add enough fuel to reach the next station (converted to distance)
        if (current_fuel < needed_fuel) {
            long long additional_fuel_needed = needed_fuel - current_fuel;
            long long liters_to_add = (additional_fuel_needed + d - 1) / d;  // Ceiling division
            min_cost += liters_to_add * cheapest_price_so_far;
            current_fuel += liters_to_add * d;  // Convert to distance
        }
        
        // Update the current fuel amount (converted to distance) and the cheapest price so far
        current_fuel -= needed_fuel;
        cheapest_price_so_far = min(cheapest_price_so_far, (long long)a[i + 1]);
    }
    
    cout << min_cost << endl;
    
    return 0;
}