Kayak

Kış olimpiyatlarındaki kayak parkuru M x N lik (1 <= M,N <= 500) bir arazide belirlenmiştir. Her birim kare 0 .. 1,000,000,000 arasında bir yüksekliğe sahiptir.

Bazı kareler parkur yolu olarak seçilmiştir. Kış olimpiyatı organizatörleri parkur boyunca bir zorluk seviyesi (D) olması konusunda anlaşırlar. Bu şekilde bir ineğin kayarken bir kareden diğerine geçebilmesi için aralarındaki yükseklik D yi aşamayacak şekilde olmaktadır. İnek kayarken sadece güney, kuzey, doğu ve batı yönündeki komşu birim karelere gidebilmektedir.

PROBLEM ADI: ccski

GİRDİ ŞEKLİ:

* Satır 1: M ve N sayıları.

* Satır 2..1+M: Her satır N tane yükseklik içermektedir.

* Satır 2+M..1+2M: Her satır toplam N tane olmak üzere 0 ya da 1 değerlerini içermektedir. Bu değerler parkurda gidilmesi gereken yolları göstermektedir.

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

3 5

20 21 18 99 5

19 22 20 16 26

18 17 40 60 80

1 0 0 0 1

0 0 0 0 0

0 0 0 0 1

GİRDİ AÇIKLAMASI:

Parkur 3 x 5 lik bir arazide tanımlanmıştır. Sol ve sağ üst, sağ alt gidilmesi gereken yerleri göstermektedir.

ÇIKTI ŞEKLİ:

* Satır 1: Zorluk seviyesi (Gidilmesi gereken tüm yerlere ulaşabilecek şekilde en küçük D).

ÖRNEK ÇIKTI (dosya ccski.out):

21

ÇIKTI AÇIKLAMASI:

Eğer D = 21, 3 yere de birbirinden gidilebilir. Eğer D < 21 ise, sağ üstteki noktaya diğer iki yerden varılamaz.

Çözüm Metni :

Reachable(X) diye bir fonksiyon tanımlayalım ki bu fonksiyon bize tüm gidilmesi gereken yerlere gidilebilecek derecede olan X değerinin doğru olup olmadığını versin. Bu sayede farklı X değerleri kullanıp D değerini bulabiliriz. 0 .. 1000000000 arasında tüm X değerleri yerine ikili arama yapıp D değerini elde edebiliriz.

Dmin=0, Dmax=1000000000

while Dmin < Dmax

    X = (Dmin + Dmax) / 2

    if Reachable(X)

        Dmax = X

    else 

        Dmin = X + 1

D = Dmin

Reachable fonksiyonu üstüne bir de gidilmesi gereken noktalar arasındaki yolları belirlemek için bir algoritmaya ihtiyacımız var. Aradaki yükseklik farklı D olacak şekilde belirlemek için DFS ya da BFS kullanabiliriz. Ancak DFS bazı girdilerde çok uzun dallanmalara sebebiyet vereceği için BFS ile bunu belirlemek daha iyi olacaktır.
Her Reachable fonksiyonu çağrılması O(NM) çözüm karmaşıklığına denk gelir. İkili arama fonksiyonu da O(log R) çözüm karmaşıklığındadır. (R 0..1,000,000,000 arasındadır). Toplam çözüm karmaşıklığı O(MN log R) dir.

Soru Linki : http://usaco.org/index.php?page=viewproblem2&cpid=380
Çözüm Kodu :  http://usaco.org/current/data/sol_ccski.html

Tile Exchanging

Tile Exchanging [Ray Li]

Çiftçi John ahırının zeminindeki taşları yenilemek istemektedir. John ahırının alanını bilmeden N tane kare şeklinde taş almıştır. Bu taşların sırayıla bir kenarlarının uzunluğu A_1...A_N dir. Ahırının tabanının alanının M metrekare olduğunu öğrenen John zeminini kaplamak için elindeki
taşların alanının toplamını M yapmaya karar vermiştir.

Çiftçi John markete gider ve elindeki taşları değiştirmek ister market sahibi: her bir A_i büyüklüğündeki taşını B_i büyüklüğündeki taş ile değiştiririm ancak |A_i-B_i|*|A_i-B_i| kadar maliyeti olur der.

Sizden istenen N,M ve A_i dizisi veriliğinde alanı kaplamak için gereken minimum maliyeti bulmanızdır.Eğer toplamını M yapmanız imkansızsa -1 yazdırınız.

SORU KODU: tilechng

GİRDİ BİÇİMİ:

* Satır 1: Boşlukla ayrılmış iki sayı, N (1<=N<=10) and M (1<=M<=10,000).

* Satır 2..1+N: Her bir satırda A_1 den A_N'e kadar olan diziyi temsil eden N sayı yer alacaktır.
        (1<=A_i<=100).

ÖRNEK GİRDİ (file tilechng.in):

3 6
3
3
1

GİRDİ AÇIKLAMASI:

3 tane taş vardır boyutları sırasıyla 3x3, 3x3 ve 1x1 dir. Amacımız bunların toplamını M yapacak şekilde değiştirmektir.

ÇIKTI BİÇİMİ:

* Line 1: Toplamı M yapmak için gereken minimum maliyet eğer çözüm yoksa -1 yazdırınız.

ÖRNEK ÇIKTI (file tilechng.out):

5

ÇIKTI AÇIKLAMASI:

3x3 lerin bir tanesi 2x2 ile değiştirilir ve 3x3 lerin bir tanesi 1x1 ile değitririlir. Toplam mailiyet 1+4=5 olur.

--------------------------------------------------------------------------------------------------------------------------
Gönderilebilecek link:http://usaco.org/index.php?page=nov11problems
Test dataları:http://usaco.org/current/data/tilechng.zip
--------------------------------------------------------------------------------------------------------------------------


Çözüm Metni

Problem dinamik programlama ile çözülebilir. Best[i][j] sunu temsil etsin. 1 den j ye kadar olan taslari degistirerek i alani elde etmek icin minimum gerekli maliyet. Baslangic durumu olarak
best[0][0]=0 ve best[i>0][0]=sonsuz. Diger durumlar icin recursive bir cozum gelistirebiliriz.

best[i][j]=0<=k<=sqrt(i) icin min( (k-A[j])^2 + best[i-k*k][j-1] );

k j tasinin k ile degistirilmesini temsil etmektedir. Best[i][j] nin degeri A_j hangi k degeriyle degistirilirse minimum olur bunu bulup saklamaktadir. k yeni alinacak tasin bir kenar uzunlugunu belirtmektedir (k-A[j])^2 degisim maliyetini ve i-k*k 1...j-1 araligindan elde edilmesi gereken toplam alani ve best[i-k*k][j] ise bu alani 1...j-1 taslari degistirilerek elde edilmesinin minimum maliyetini saklamaktadir.

Calisma zamani hesaplamasi k*k<=i<=M ve j<=N oldugu icin 10*100*10000=10 milyon bu da demektir ki cozumumuz 1 sn de calisir.

Not: 0 boyutlu kareler olabilmektedir kod a bunu dahil etmeliyiz 100 alabilmek icin.

--------------------------------------------------------------------------------------------------------------------------

Çözüm kodu:

#include <stdio.h>

#define MAX_M 10000
#define MAX_N 10
#define INF 1000000000

int best[MAX_M+1][MAX_N+1];
int A[MAX_M+1];

int main(void)
{
  int M, N, i, j, k;

  freopen ("tilechng.in", "r", stdin);
  freopen ("tilechng.out", "w", stdout);

  scanf ("%d %d", &N, &M);
  for (i=1; i<=N; i++)
    scanf ("%d", &A[i]);

  for (i=1; i<=M; i++)
    best[i][0] = INF;

  for (j=1; j<=N; j++)
    for (i=0; i<=M; i++) {
      best[i][j] = INF;
      for (k=1; k*k<=i; k++)
      if ((A[j]-k)*(A[j]-k) + best[i-k*k][j-1] < best[i][j])
        best[i][j] = (A[j]-k)*(A[j]-k) + best[i-k*k][j-1];
    }

  if (best[M][N]==INF)
    printf ("-1\n");
  else
    printf ("%d\n", best[M][N]);

  return 0;
}