Skip to content

11004: 【原1004】西西弗斯式的命运

题目

题目描述

author: 吴杰 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1004

Description

古希腊有个关于西西弗斯的神话:

西西弗斯被众神判决推运一块石头至山顶。由于巨石本身的重量,它被推到山顶却又总要滚下山脚。于是西西弗斯又得把石块推上山去。如此反复,永无止境,没有尽头。众神认为,让西西弗斯服这永恒的劳役是最严酷的惩罚。

二哥被押入地狱。他被众神判决扛着一块巨砖在山路上走,再原路返回,如此反复,没有尽头。

众神规定二哥独自走山路的时间不得超过M秒( \( 1 \leq M \leq 10,000,000 \) )。整条山路被划分成T个长度相同的小段( \( 1 \leq T \leq 100,000 \) ),并且,众神用Si表示第i个小段的路况。Si为u,f,d这3个字母之一,它们分别表示第i个小段是上坡、平地、下坡。

二哥要花U秒( \( 1 \leq U \leq 100 \) )才能走完一段上坡路,走完一段平地的耗时是F秒( \( 1 \leq F \leq 100 \) ),走完一段下坡路要花D秒( \( 1 \leq D \leq 100 \) )。注意,沿山路原路返回的时候,原本是上坡的路段变成了下坡路,原本是下坡的路段变成了上坡路。

二哥对生活充满激情,但他遭受着难以用言语尽述的非人折磨:痛苦扭曲的脸,被巨砖死死压住的抖动的肩膀,沾满泥土的双脚,呕心沥血,不停的工作。这是典型的西西弗斯式的命运。贝多芬,歌德,叔本华,你才,还有高斯,爱因斯坦的命运,都是典型的西西弗斯式的命运,无一例外。

众神想让二哥能在按时返回的前提下,走最远的路。所以众神向知道他最多能在这条山路上走多远。

Input Format

第1行:5个空格隔开的整数:M,T,U,F,D。

第2..T+1行:第i+1行有一个字母Si,描述第i段山路的路况。

Output Format

一行,有一个整数为二哥在按时回到起点前提下,最多能跑到多远。

Sample Input

13 5 3 2 1
u
f
u
d
f

Sample Output

3

样例解释

众神规定二哥的最大耗时为13秒,他跑步的山路一共被划分成5段。二哥走完一段上坡的耗时为3秒,平地为2秒,下坡为1秒。

二哥走完山路的前3段,然后返回,总耗时为3+2+3+1+2+1=12秒,如果他跑得更远,就无法按时回到起点。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/16.
//
// 线性探测

#include <iostream>

using namespace std;

int main() {
    int M, T, U, F, D;
    cin >> M >> T >> U >> F >> D;
    int ans = 0;
    int curr = 0;
    for (int i = 0; i < T; ++i) {
        char c;
        cin >> c;
        switch (c) {
            case 'u':
            case 'd':
                curr += U + D;
                break;
            case 'f':
                curr += 2 * F;
                break;
        }
        if (curr > M) {
            cout << ans << endl;
            return 0;
        }
        ++ans;
    }
    cout << T << endl;
}

CallMeInk's solution

#include <iostream>

using namespace std;

int main()
{
    int i,m,t,u,f,d;
    char ch;
    cin >> m >> t >> u >> f >> d;
    cin.get();
    for(i=1;i<=t;i++)
    {
        cin.get(ch);
        cin.get();
        if (ch == 'u' || ch == 'd') m -= (u+d);
        else m -= f + f;
        if (m < 0)
        {
            cout << i - 1 << endl;
            break;
        }
    }
    return 0;
}

FineArtz's solution

/* 西西弗斯式的命运 */
#include <iostream>
using namespace std;

int main(){
    int m, t, u, f, d;
    cin >> m >> t >> u >> f >> d;
    char road;
    int NowTime = 0;
    for (int i = 0; i != t; ++i){
        cin >> road;
        switch(road){
            case 'u': case 'd':
                NowTime = NowTime + u + d;
                break;
            case 'f':
                NowTime += 2 * f;
                break;
            default:
                break;
        }
        if (NowTime > m){
            cout << i << endl;
            return 0;
        }
    }
    cout << t << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int M, T, U, F, D;
    cin >> M >> T >> U >> F >> D;

    int ans = 0;
    for (int i = 0, cur_time = 0; i < T; ++i) {
        char c;
        cin >> c;
        if (c == 'u'||c=='d') {
            if (cur_time + U + D <= M)
                ++ans;
            cur_time += U + D;
        }
        else {
            if (cur_time + 2 * F <= M)
                ++ans;
            cur_time += 2 * F;
        }
    }
    cout << ans;
    return 0;
}

q4x3's solution

/**
 * 模拟
 * 上坡下坡效果相同(因为有返程)
 **/
#include <iostream>
using namespace std;

int main() {
    int M, T, U, F, D;
    int cnt = 0, tot = 0;
    cin >> M >> T >> U >> F >> D;
    char tmp;
    for(int i = 0;i < T;++ i) {
        cin >> tmp;
        if(tmp == 'f') {
            tot += F * 2;
        } else {
            tot += (U + D);
        }
        if(tot > M) break;
        else ++ cnt;
    }
    cout << cnt <<endl;
    return 0;
}

skyzh's solution

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

char rd[100002];
int main() {
    int M, T, U, F, D;
    scanf("%d%d%d%d%d\n", &M, &T, &U, &F, &D);
    for (int i = 0; i < T; i++) {
        scanf("%c\n", &rd[i]);
    }
    int T_ALL = 0;
    for (int i = 0; i < T; i++) {
        if (rd[i] == 'u' || rd[i] == 'd') T_ALL += U + D;
        if (rd[i] == 'f') T_ALL += F * 2;
        if (T_ALL > M) {
            cout << i << endl;
            return 0;
        }
    }
    cout << T << endl;
    return 0;
}

victrid's solution

#include <iostream>

using namespace std;

int main() {
    int M, T, U, F, D;
    cin >> M >> T >> U >> F >> D;

    char c;
    int tf = 0, udt = U + D, fft = F + F;
    for (int i = 0; i < T; i++) {
        cin >> c;
        if (c != 'f')
            tf += udt;
        else
            tf += fft;
        if (tf > M) {
            cout << i;
            break;
        }
    }
    return 0;
}

yyong119's solution

#include <iostream>
long m,u,f,d,t,i,n;
char si[100001];
int main(){
    using namespace std;
    cin>>m>>t>>u>>f>>d;
    for (i=1; i<=t; i++) cin>>si[i];
    while(m>=0){
        n++;
        if ((si[n]=='u')||(si[n]=='d')) m=m-u-d;
        else if(si[n]=='f') m=m-f-f;
    }
    cout<<n-1;
    return 0;
}