Bài toán gieo hạt

[Rok_Hoang (Minh Hoàng)]

Một người có trách nhiệm gieo hạt giống cho nhiều cánh đồng liên tiếp với nhau. Ban đầu người này bắt đầu tại vị trí bất kì (các cánh đồng mở rộng sang 2 bên), người này sẽ đi qua trái và qua phải để gieo từng cánh đồng. Hãy cho biết số cánh đồng đã gieo hạt giống.

INPUT
L 12
R 10 
R 5
L 3
R 4
OUTPUT
16

Giải thích: mỗi dòng là 1 lần gieo, L 12 là từ vị trí xuất phát gieo được 12 cánh đồng bên trái, R 10 tại vị trí vừa gieo hiện tại gieo 10 cánh đồng bên phải,…

p/s: Đố vui, giới hạn số cánh đồng < 10^9, số lần gieo <10000

Update: hết đố vui, đố nghiêm túc. Nâng cấp một chút. Người chủ muốn biết người đầy tớ đã gieo một cánh đồng nhiều hơn một lần hay không. Hãy cho biết số cánh đồng đã bị gieo nhiều hơn một lần với format của INPUT và OUTPUT như trên.

[Ta_Ta_Goo (chu đức anh)]

bài này theo mình thì dùng 2 biến L R và 1 biến G là xong. Chả biết có đúng không. Đây là code mình viết bằng C++
http://ideone.com/dPaQhS

[sample (<script>alert("hacked")</script>)]

Giải thuật
Bài này khá đơn giản.
Quy ước vị trí ban đầu của người đó là 0, khi qua trái vị trí người đó sẽ giảm, khi qua phải, vị trí người đó sẽ tăng. Ta cần xác định hai vị trị tận cùng mà người đó đến được từ đó suy ra đáp số bài toán.
Code:

//code by tamlien
#include <iostream>
using namespace std;

int main()
{
    int n, cur=0, posMin=2147483647, posMax=-posMin;// khởi tạo các giá trị ban đầu.
    cin>>n;
    char Type;
    int x;
    for(int i=0; i<n; i++)
    {
        cin>>Type>>x;
        if(Type=='L') cur-=x;
        else cur+=x;
        if(cur>posMax) posMax=cur; // tối ưu lại....
        if(cur<posMin) posMin=cur;
    }
    cout<<posMax-posMin;
    return 0;
}

giaosudauto

[Rok_Hoang (Minh Hoàng)]

Hehe, đề gốc có ở phần Update nhé. Các bạn tiếp tục giải nhé.

[Gio (Gió)]

Rời rạc hoá các điểm thì sẽ có không quá 2000 đầu mút
Dùng 1 mảng đánh dấu A, các dòng input=> (x,y)
Thì mảng đánh dấu A[x]+=1; A[y+1]-=1;
Sau đó cộng dồn thì biết dc khoảng nào gieo bao nhiêu lần

[sample (<script>alert("hacked")</script>)]

Good idea …

[sample (<script>alert("hacked")</script>)]

Nhưng mà số cánh đồng ở đây là 10^9 thì nó có chạy nổi trong 1s không?

[Gio (Gió)]

Code thử

#include <bits/stdc++.h>
using namespace std;


const int maxn = 2e3+10;

typedef long long ll;
int A[maxn];
ll rev[maxn];

int main() {
    
    int cur=0,next;
    string a;
    int dst;
    vector<pair<ll,ll> > vt;
    while(cin>>a>>dst){
        
        if(a=="L"){
            next=cur-dst;
        }else{
            next=cur+dst;
        }
        vt.push_back(make_pair(min(cur,next),max(cur,next)));
        cur=next;
    }
    // roi rac hoa
    map<ll,int> m;
    for(auto p: vt){
        m[p.first]=1;
        m[p.second]=1;
    }
    int cnt=1;
    for(auto &p: m){
        rev[cnt]=p.first;
        p.second=cnt++;
    }
    //for(auto p: m){
    //    cout<<p.first<<" "<<p.second<<endl;
    //}
    fill(A,A+m.size()+1,0);
    for(auto p: vt){
        A[m[p.first]]++;
        A[m[p.second]+1]--;
    }
    for(int i=1;i<=m.size();i++){
        A[i]+=A[i-1];
    }
    
    for(int i=1;i<m.size();i++){
        cout<<rev[i]<<" "<<rev[i+1]<<" "<<A[i]<<endl;
    }
    
    return 0;
}