Нэг хэмжээст массивийн хэрэглээ

SPOJ-ын бодлогын архив2889.
Орлуулга
Бодлогын дугаар: ABR0632

a1, ..., an, p болон k натурал тоонууд өгөгдөв (a1 ≤ a2 ≤ ... ≤ an, k ≤ n ≤ 2000). a1,..., an дарааллаас k дугаартай элементийг (өөрөөр хэлбэл ak) устгаж, эрэмбийг нь алдагдуулахгүйгээр p гэсэн утгатай элементийг нэм.

Input

Эхний мөрөнд n, k, p тоонууд зайгаар тусгаарлагдан өгөгдөнө. Дараагийн мөрөнд a1, ..., an тоонууд зайгаар тусгаарлагдан байрлана.

Output

Зохих хувиргалтууд хийгдсэн a1, ..., an тоонуудыг зайгаар тусгаарлан нэг мөрөнд хэвлэнэ.

Example

Input:

7 2 6
1 2 3 4 5 7 7

Output:
1 3 4 5 6 7 7

Энэ бодлогын шийдэл нь k дугаартай элементэд р гэсэн утгыг оноож үүссэн n элемэнт бүхий массиваа эрэмбэлэх явдал болно. Харин k дугаар элемэнтэд p утгыг оноохдоо массивийг 0 - ээс эхлэн дугаарладагийг мартаж болохгүй.

   1.#include <stdio.h>
   2.main()
   3.{
   4.  int n,p,k;
   5.  int a[2000];
   6.  int i,j,r;
   7.  scanf("%d%d%d",&n,&k,&p);
   8.  for(int q=0; q<n; q++)
   9.  {
  10.     scanf("%d",&a[q]);
  11.     if(q==(k-1)) a[q]=p;
  12.  }
  13.  
  14.  for(i=1;i<n;i++)
  15.  {  j=i;
  16.      while(j>0 && a[j-1]>a[j])
  17.       
  18.      {
  19.        r=a[j];
  20.        a[j]=a[j-1];
  21.        a[j-1]=r;
  22.        j--;
  23.      }
  24.  }
  25.   for(int w=0; w<n; w++)
  26.   printf("%d ",a[w]);
  27.
  28.   return 0;
  29.} 

Хоёр хэмжээст массивийн хэрэглээ

SPOJ-ын бодлогын архив2797.
Жимс
Бодлогын дугаар: CODE0004

Бяцхан сармагчин жимс цуглуулахаар явж байв. Тэрээр байгаа чулууны баруун урд, эсвэл зүүн урд чиглэлийн чулуу уруу л шилжиж чадна. Чулуу болгонд тодорхой хэмжээний жимс байх бөгөөд эцсийн шатанд сармагчиний авч чадах хамгийн их жимсний тоог ол.

InputN:

Эхний мөр нийт шилжилтийн тоо. a(i,j), 1 < = j < = i < = N Чулуу болгон дээр байгаа жимсний тоо 0 < = N, a(i,j) <= 200,

Output

Цуглуулж чадах хамгийн их жимсний тоо

Example

Input:

3

0

3 1

1 2 2

Output:

5

Шийдэл: Эхлээд N-1 дэх мөрийг авч үзье. Тэгвэл a[n-1,i] дээр max(a[n,i],a[n,i+1]) ийг нэмье.Дараа нь N-2 дэх мөрийг авч мөн уг үйлдлийг хийнэ. Энэ алхмыг үргэлжлүүлсээр 1 дэх мөр хүртэл хийнэ. Ингээд a[1,1] нь анхны бодлогын хариу болно.

#include "stdio.h"
main()
{
int n,i,j;
int a[90][90]={0};
scanf("%d",&n);
    for(i=0; i<n; i++)
    {
     for(j=0; j<=i; j++)
     scanf("%d",&a[i][j]);
    }

    for(i=n-2; i>=0; i--)
    {
    for(j=0; j<=n-2; j++)
      if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];
       else a[i][j]+=a[i+1][j+1];
    }
   printf("%d",a[0][0]);
return 0;
}

Бодлогын эх сурвалж:
Програмчлал, Алгоритм сонирхогчдод зориулав Чимэдээ ахын бодлогын сайт
Шийдлийг: Кодер.МН блог