Bessie Yavaşlarken

İnek Bessie Kış Olimpiyatlarında kayak dalında yarışmaktadır. Başlangıçta 1 m/s ile gitmektedir. Ancak yoruldukça yavaşlamaktadır. Her yavaşladığında hızı şu şekilde düşmektedir : İlk yavaşladıktan sonraki hızı ½ m/s, ikinci yavaşlamasından sonra 1/3 m/s şeklinde gitmektedir.

Size Bessie'nin nerede ve ne zaman yavaşlayacağı olay parçaçıkları halinde verilecektir. Şuna benzer bir olay parçacığı;

T 17

Bessie'nin 17.sn de yavaşlayacağını göstermektedir. Diğer bir olay parçacığı;

D 10

Bessie'nin yarışın başladığı noktadan itibaren kaç metre sonra yavaşlayacağını bildirmektedir. (10 metre)

Verilen N olay parçacığına göre (1<=N<=10000) Bessie'nin kaç sn içinde bir km yolu alabildiğini hesaplayınız. Cevaplarınızı en yakın tam sayıya yuvarlayınız.

PROBLEM ADI: slowdown

GİRDİ ŞEKLİ:

*1.satır : N değeri.

* Satır 2..1+N: Her satır "T x" ya da "D x", şeklinde yolu ya da zamanı ifade edecek şekilde verilecektir. Her iki durumda da, x sayısı toplam alacağı bir km yol sınırlamasını sağlayacak şekilde verilecektir. Bazı olay parçacıklarının aynı anda gerçekleşmesi muhtemeldir, Bessie bundan dolayı biraz daha yavaşlayacaktır. Olay parçacıkları sırası ile verilmeyebilir.

ÖRNEK GİRDİ (dosya slowdown.in):

2

T 30

D 10

GİRDİ AÇIKLAMASI:

Bessie t = 30 da ve uzaklık d = 10 olduğunda yavaşlamaktadır.

ÇIKTI ŞEKLİ:

*1.satır : Bettie'nin 1 km yolu gitmesi için gerekli olan zaman.

ÖRNEK ÇIKTI (dosya slowdown.out):

2970

ÇIKTI AÇIKLAMASI:

Bessie ilk 10 metreyi ilk hızı 1 m/s olduğundan 10 sn de almaktadır. Sonra hızı ½ m/s ye düşüp, sonraki 10 metreyi 20 sn de almaktadır. 30.sn olay parçacığında tekrar hızı azalıp 1/3 m/s ye düşmektedir. Geri kalan 980 m yi bundan dolayı 980*3 = 2940 sn de gider. Toplam zaman 10+20+2940 = 2970 olur.

Çözüm Metni: Bessie Yavaşlarken

---

Bu problemde bize Bessie'nin yavaşladığı N olay parçası verilmekte ve 1 km yolu kaç sn de aldığı sorulmaktadır. Eğer bir şekilde bu olay parçacıklarını sıralayabilirsek soru daha kolay hala gelir. İlk olay parçacığının kolay bir şekilde ne zaman ve ne kadar uzaklıkta gerçekleştiğini hesaplayabiliriz: Başta hız 1 m/s olduğu için hız ile zamanın büyüklüğü aynı olmaktadır. Diğer olay parçacıkları için ise ne zaman YA DA ne kadar uzaklıkta gerçekleştiğini bilebiliriz. Bize verilen bilgilere göre zaman ya da uzaklıktan herhangi birini hesaplayabiliriz. Son olay parçacığının ne zaman ve nerede gerçekleştiğini bulduğumuzda, Bessie'nin yarışı ne kadar sürede bitirdiğini bulabiliriz.

Bu bilgiler ışığında alınan ilhama göre çözüm için olay parçacıklarının sıralamasını bulmalıyız. Bunun için bir yol, N olay parçacığını gözden geçirip hangisinin daha önce gerçekleştiğini tüm olay parçacıkları gerçekleşene kadar bulmak. Doğru bir yol olsa bile çözüm karmaşıklığı O(N^2) olduğundan hızlı bir çözüm olmamaktadır. Bu çözümün yavaş olan kısmı ise N olay parçacığından hangisin önce geldiğini bulmaktır. Eğer bu kısımda bir iyileştirme yapılır ise, soruyu çözebiliriz.

Bu soruyu çözmedeki püf nokta zamana göre verilen olay parçacıkları ile yola göre verilen olay parçacıkların kendi gruplarında bir sıralamaya sahip olmasıdır. Örnek olarak "D 10" olay parçacığı her zaman için "D 15" olay parçacığından ne olursa olsun önce gerçekleşmektedir. Aynı şekilde, "T 8" olay parçacığı "T 5" ten sonra gerçekleşmektedir. Bu demektir ki hangi olay parçacığının önce geldiğini bulabilmek için iki çeşit olan olay parçacıklarını kendi içlerinde sıralayabiliriz. Önce gelen iki çeşit olay parçacığı karşılaştırılıp olay parçacığı gerçekleştikten sonra aynı adımlar tekrar edilerek sorunun çözümü bulunur. Çözüm karmaşıklığı bu sayede sadece sıralama maliyetinden ötürü O(N lg N) olmaktadır.

Kalki Seksaria'nın çözümü. (Sort yerine priority_queue kullanmış, çözüm yapısı aynı olmaktadır.)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N;
priority_queue<int, vector<int>, greater<int> > timeEvents;
priority_queue<int, vector<int>, greater<int> > distanceEvents;

double currentD;
double currentT;
int speedValue; // 1/speed

int main()
{
    ifstream in ("slowdown.in");
    ofstream out ("slowdown.out");
    
    in >> N;
    for (int i = 0; i < N; i++)
    {
        char c;
        int x;
        in >> c >> x;
        if (c == 'T')
            timeEvents.push(x);
        else
            distanceEvents.push(x);
    }
    distanceEvents.push(1000);
    
    currentT = currentD = 0.0;
    speedValue = 1;
    
    while(!timeEvents.empty() || !distanceEvents.empty())
    {
        bool isNextTime = false;
        
        if(distanceEvents.empty())
            isNextTime = true;
        else if(!distanceEvents.empty() && !timeEvents.empty())
            if (timeEvents.top() < (currentT + (distanceEvents.top() - currentD)*speedValue))
                isNextTime = true;

        
        if(isNextTime)
        {
            currentD += (timeEvents.top() - currentT) / (speedValue + 0.0);
            currentT = timeEvents.top();
            timeEvents.pop();
        }
        else
        {
            currentT += (distanceEvents.top() - currentD) * speedValue;
            currentD = distanceEvents.top();
            distanceEvents.pop();
        }
        
        speedValue++;
    }
    
    int currentTime = (int) currentT;
    double fraction = currentT - currentTime;
    
    if(fraction < 0.5)
        out << currentTime << "\n";
    else
        out << currentTime + 1 << "\n";
    
    out.close();
    return 0;
}

Soru Linki : http://www.usaco.org/index.php?page=viewproblem2&cpid=379

Çözüm Linki : http://www.usaco.org/current/data/sol_slowdown.html