Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бодолт илгээх Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7965 - Шүхэр

Өнөөдөр их бороотой байна!

Фермэр Жон N (1 <= N <= 5’000) үнээтэй бөгөөд 1-ээс N хүртэл дугаарлагдсан. Тэр үнээнүүдээ норгохыг хүсэхгүй байгаа.

Түүний амбаар хэвтээ тэнхлэгийн дагуу 1-ээс M (1 <= M <= 100’000) хүртэл дугаарлагдсан дээвэргүй жүчээнүүдтэй бөгөөд 1 үнээ 1 л жүчээнд байрлана.

Фермэр Жон үнээнүүдээ борооноос хамгаалахын тулд шүхэр худалдаж авахаар болов.

X[i]-аас X[j] (X[i] <= X[j]) хүртэлх жүчээг хучих шүхэр X[j] – X[i] + 1 өргөнтэй гэж үзнэ.

W өргөнтэй шүхэр C[W] (1 <= C[W] <= 1’000’000) үнэтэй.

Том шүхэр жижиг шүхэрнээсээ үнэтэй байх албагүй..

Түүнд хамгийн бага зардлаар бүх үнээг борооноос хамгаалахад нь туслаарай.

Input

1-р мөр: Зайгаар тусгаарлагдсан N болон M бүхэл тоонууд.

2-р мөр: Үнээнүүдийн байрлалыг илэрхийлэх X[i] координатууд зайгаар тусгаарлагдан өгөгдөнө.

3-р мөр: Энэ мөрний W дугаар тоо нь W өргөнтэй шүхэрний үнэ болох C[W]-г илэрхийлнэ.

Output

1-р мөр: Бүх үнээг хучиж болох шүхэрнүүдийн хамгийн бага зардал.

Example

Input:

6 12

1 2 11 8 4 12

2 3 4 4 8 9 15 16 17 18 19 19

Input Details:

Нийт 12 зүчээ 6 үнээ бий. Эхний үнээ 1-р зүчээ,2 дахь үнээ 2-р зүчээ, 3 дахь үнээ 11-р зүчээнд гэх мэт. 1 өргөнтэй шүхэр 2-ын үнэтэй,

2 өргөнтэй шүхэр 3-ын үнэтэй гэх мэт 12 өргөнтэй шүхэр 19-ийн үнэтэй юм.

Output:

9

Output Details:

UUUUUUUUUU U UUUU

C C C C C C

|--|--|--|--|--|--|--|--|--|--|--|

1 2 3 4 5 6 7 8 9 10 11 12

U Шүхэр, С үнээ

4; 1; 2 өргөнтэй шүхрүүдээр хучихад

4+2+3=9-ийн үнэтэй болох ба энэ нь

боломжит хамгийн бага зардал юм.

Орчуулсан : УБ 1-р сургуулийн 11-р ангийн сурагч Б.Мөнх-Оргил 2019.11.15

 

Submit solution!
Нэмсэн:Bataa
Огноо:2013-12-29
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:USACO 2011 December Contest, Silver Division
hide comments
2019-12-27 12:44:03
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <dos.h>
#include <time.h>
#include <windows.h>

using namespace std;

const int width = 60; //Tegsh untsugtiin urt
const int heigth = 20; // Tegsh untdsugtiin urgun

int x, y, x1, x2, y1, y2, i, j;
int Score, score, d;
int fruitX, fruitY,m;
int xx,yy,X[102],Y[102];
bool gameOver;

void gotoxy (int x, int y){
COORD coordinates; // coordinates is declared as COORD
coordinates.X = x; // defining x-axis
coordinates.Y = y; //defining y-axis
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coordinates);
}

void Setup(){
x1 = 10; // Tegsh untsugtiin zuun deed bulangiin X coordinat
y1 = 5; // Tegsh untsugtiin zuun deed bulangiin Y coordinat
x2 = x1+width+1; // Tegsh untsugtiin baruun dood bulangiin X coordinat
y2 = y1+heigth+1; // Tegsh untsugtiin baruun dood bulangiin Y coordinat
gameOver = false; // Togloom duusgah eseh
score = 10; // Hool ideh bonus onoo
Score = 0; // Niit onoo
x = (x1+x2)/2; // Snake-iin ehleh X coordinat
y = (y1+y2)/2; // Snake-iin ehleh Y coordinat
X[1]=x-2;
Y[1]=y;
X[2]=x-1;
Y[2]=y;
d = 2; // Snake-iin chiglel : 2 baruun, 3 dooshoo, 4 zuun, 1 deeshee
srand (time(NULL));
fruitX = rand() % width + 1 + x1; // Jimsnii X coordinat
fruitY = rand() % heigth + 1 + y1; // Jimsnii Y coordinat
m=2;
}

void Draw(){
system("cls"); // Delgets buheld ni archih

gotoxy(x1,y1); // Cursoriig tegsh untsugtiin zuun deed bairlald avaachina
printf("%c", 218); // Zuun deed bulangiin temdegtiig hevleh
for(j=x1+1; j<x2; j++){ // Tegsh untsugtiin deed hureenii X coordinat j=x1+1 -> x2 hurehgui
printf("%c",196); // Tegsh untsugtiin deed hureenii temdegt hevleh
}
printf("%c",191); // Tegsh untsugtiin baruun deed bulangiin temdegt
for(i=y1+1; i<y2; i++){ // Tegsh untsugtiin zuun, baruun hureenii Y coordinat i=y1+1 -> y2 hurehgui
gotoxy(x1, i); // Tegsh untsugtiin zuun hureend cursor avaachih
printf("%c",179); // Zuun hureenii bosoo temdegt hevleh
gotoxy(x2,i); // Tegsh untsugtiin baruun hureend cursor avaachih
printf("%c",179); // Baruun hureenii bosoo temdegt hevleh
}
gotoxy(x1, y2); // Zuun dood buland cursor avaachina
printf("%c",192); // Tegsh untsugtiin zuun dood bulangiin temdegt
for(j=x1+1; j<x2; j++){ // Tegsh untsugtiin dood hureenii X coordinat j=x1+1 -> x2 hurehgui
printf("%c",196); // Tegsh untsugtiin deed hureenii temdegt hevleh
}
printf("%c",217); // Tegsh untsugtiin baruun dood bulangiin temdegt
gotoxy(x2-12, y1-1); // Tegsh untsugtiin baruun deed tald onoo bichih bairlald cursor avaachina
printf("Score : %4d", Score); // Score onoo hevlene

gotoxy(X[1], Y[1]); // Mogoin tolgoinii bairlald cursor avaachina
printf("-o@"); // Mogoin tolgoig hevlene
gotoxy(fruitX, fruitY); // Hool bairluulah bairlald cursor avaachina
printf("$"); // Hool temdegt hevlene
}

void Game(){
if(kbhit()){ // kbhit() tovch daragdsan eseh function, daragdsan bol True, ugui bol False
switch(getch()){ // getch() daragdsan tovchnii code butsaana; switch() daragdsan tovchnii code-oor salaalalt
case 72 : if(d != 3) d = 1; break; // 72 deeshee sumtai tovch; dooshoo chiglelees busad uyed chiglel uurchlunu
case 77 : if(d != 4) d = 2; break; // 77 baruun sumtai tovch; zuun chiglelees busad uyed chiglel uurchlunu
case 80 : if(d != 1) d = 3; break; // 80 dooshoo sumtai tovch; deeshee chiglelees busad uyed chiglel uurchlunu
case 75 : if(d != 2) d = 4; break; // 75 zuun sumtai tovch; baruun chiglelees busad uyed chiglel uurchlunu
case 27 : gameOver = true; break; // 27 Esc tovch, gameOver togloom duusgah huvisagch
}
}
//gotoxy(x, y); // Mogoin tolgoin bairlald cursor avaachina
//printf(" "); // Mogoin tolgoin temdegtiig archina
xx=x;
yy=y;
switch( d ){ // Mogoin chigleleer salaalalt
case 1 : { // Mogoin chiglel deeshee uyed mogoin tolgoin bairlal shiljilt
if(y > y1+1) y--; // coordinat y deed hureend hureegui uyed y--
else y = y2 - 1; // coordinat y deed hureend hursen uyed dood hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 2 : { // Mogoin chiglel baruun uyed mogoin tolgoin bairlal shiljilt
if(x < x2-1) x++; // coordinat x baruun hureend hureegui uyed x++
else x = x1 + 1; // coordinat x baruun hureend hursen uyed zuun hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 3 : { // Mogoin chiglel dooshoo uyed mogoin tolgoin bairlal shiljilt
if(y < y2-1) y++; // coordinat y dood hureend hureegui uyed y++
else y = y1 + 1; // coordinat y dood hureend hursen uyed deed hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 4 : { // Mogoin chiglel zuun uyed mogoin tolgoin bairlal shiljilt
if(x > x1 + 1) x--; // coordinat x zuun hureend hureegui uyed x--
else x = x2-1; // coordinat x zuun hureend hursen uyed baruun hureenees nevtreh
break; // switch() salaalaltaas garah
}
}

if(x == fruitX && y == fruitY){ // mogoi hoolond hursen eseh shalguur
Score = Score + score; // Mogoi hoolond hursen tul Score onoog score onoogoor nemegduuleh
gotoxy(x2-4, y1-1); // Score onoo bichih bairlald cursor avaachina
printf("%4d",Score); // Score onoo 4 temdegtiin zaid hoish ni shahaj bichih
fruitX = rand() % width + 1 + x1; // hoolnii bairlaliin x coordinat shine utga olgoh
fruitY = rand() % heigth + 1 + y1; // // hoolnii bairlaliin y coordinat shine utga olgoh
gotoxy(fruitX, fruitY); // hoolnii shine bairlald cursor avaachih
printf("$"); // hoolnii temdegt hevleh
}else{
gotoxy(X[1],Y[1]);
printf(" ");
for(i=1; i<m; i++){
X[i]=X[i+1];
Y[i]=Y[i+1];
}
X[m]=xx;
Y[m]=yy;
gotoxy(X[1],Y[1]);
printf("-");
gotoxy(xx, yy);
printf("0");
gotoxy(x,y) ;
printf("@");
}

Sleep(100);
}
// Program 100 nano secund zogsolt hiih; amrah
int main(){
Setup(); // Setup() function duudan ajilluulah; Huvisagchdiin anhnii utga olgoltuud hiigdene
Draw(); // Draw() function duudan ajilluulna; Mogoin yavah talbariig zurna
while(!gameOver){ // while() davtalt togloom duusah hurtel ajillana
Game(); // Game() function duudan ajilluulna; Togloom ajillana
}

gotoxy(x1, y2+1);

return 0;
}// program duusna
2019-12-27 11:25:18 Bataa
#include
#include
#include
#include
#include
#include

using namespace std;

const int urt = 80; // Tegsh untsugtiin urt
const int urgun =20; // Tegsh untdsugtiin urgun

int x, y, x1, x2, y1, y2, i, j, xx, yy;

int Onoo, onoo, d, hoolX, hoolY, ns;
int X[102], Y[102], Z[102];
bool gameOver;

void gotoxy (int x, int y){
COORD coordinates; // coordinates is declared as COORD
coordinates.X = x; // defining x-axis
coordinates.Y = y; //defining y-axis
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coordinates);
}

void Setup(){
x1 = 10; // Tegsh untsugtiin zuun deed bulangiin X coordinat
y1 = 5; // Tegsh untsugtiin zuun deed bulangiin Y coordinat
x2 = x1+urt+1; // Tegsh untsugtiin baruun dood bulangiin X coordinat
y2 = y1+urgun+1; // Tegsh untsugtiin baruun dood bulangiin Y coordinat
gameOver = false; // Togloom duusgah eseh
onoo = 10; // Hool ideh bonus onoo
Onoo = 0; // Niit onoo
d = 2; // Snake-iin chiglel : 2 baruun, 3 dooshoo, 4 zuun, 1 deeshee
srand (time(NULL)); // rand() function-iin ehnii ugiig sanamsargui bolgon uurchilnu
hoolX = rand() % urt + 1 + x1; // Jimsnii X coordinat
hoolY = rand() % urgun + 1 + y1; // Jimsnii Y coordinat
x = (x1+x2)/2; // Snake-iin ehleh X coordinat
y = (y1+y2)/2; // Snake-iin ehleh Y coordinat
X[0] = x - 2;
Y[0] = y;
X[1] = x - 1;
Y[1] = y;
ns = 1;
}

void Draw(){
system("cls"); // Delgets buheld ni archih

gotoxy(x1,y1); // Cursoriig tegsh untsugtiin zuun deed bairlald avaachina
printf("%c", 218); // Zuun deed bulangiin temdegtiig hevleh
for(j=x1+1; j x2 hurehgui
printf("%c",196); // Tegsh untsugtiin deed hureenii temdegt hevleh
}
printf("%c",191); // Tegsh untsugtiin baruun deed bulangiin temdegt
for(i=y1+1; i y2 hurehgui
gotoxy(x1, i); // Tegsh untsugtiin zuun hureend cursor avaachih
printf("%c",179); // Zuun hureenii bosoo temdegt hevleh
gotoxy(x2,i); // Tegsh untsugtiin baruun hureend cursor avaachih
printf("%c",179); // Baruun hureenii bosoo temdegt hevleh
}
gotoxy(x1, y2); // Zuun dood buland cursor avaachina
printf("%c",192); // Tegsh untsugtiin zuun dood bulangiin temdegt
for(j=x1+1; j x2 hurehgui
printf("%c",196); // Tegsh untsugtiin deed hureenii temdegt hevleh
}
printf("%c",217); // Tegsh untsugtiin baruun dood bulangiin temdegt
gotoxy(x2-12, y1-1); // Tegsh untsugtiin baruun deed tald onoo bichih bairlald cursor avaachina
printf("Onoo : %5d", Onoo); // Score onoo hevlene
gotoxy(x-2, y); // Mogoin tolgoinii bairlald cursor avaachina
printf("-"); // Mogoin tolgoig hevlene
printf("o");
printf("@");
gotoxy(hoolX, hoolY); // Hool bairluulah bairlald cursor avaachina
printf("$"); // Hool temdegt hevlene
}

void Game(){
if(kbhit()){ // kbhit() tovch daragdsan eseh function, daragdsan bol True, ugui bol False
switch(getch()){ // getch() daragdsan tovchnii code butsaana; switch() daragdsan tovchnii code-oor salaalalt
case 72 : if(d != 3) d = 1; break; // 72 deeshee sumtai tovch; dooshoo chiglelees busad uyed chiglel uurchlunu
case 77 : if(d != 4) d = 2; break; // 77 baruun sumtai tovch; zuun chiglelees busad uyed chiglel uurchlunu
case 80 : if(d != 1) d = 3; break; // 80 dooshoo sumtai tovch; deeshee chiglelees busad uyed chiglel uurchlunu
case 75 : if(d != 2) d = 4; break; // 75 zuun sumtai tovch; baruun chiglelees busad uyed chiglel uurchlunu
case 27 : gameOver = true; break; // 27 Esc tovch, gameOver togloom duusgah huvisagch
}
}
xx=x; yy=y;
switch( d ){ // Mogoin chigleleer salaalalt
case 1 : { // Mogoin chiglel deeshee uyed mogoin tolgoin bairlal shiljilt
if(y > y1+1) y--; // coordinat y deed hureend hureegui uyed y--
else y = y2 - 1; // coordinat y deed hureend hursen uyed dood hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 2 : { // Mogoin chiglel baruun uyed mogoin tolgoin bairlal shiljilt
if(x < x2-1) x++; // coordinat x baruun hureend hureegui uyed x++
else x = x1 + 1; // coordinat x baruun hureend hursen uyed zuun hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 3 : { // Mogoin chiglel dooshoo uyed mogoin tolgoin bairlal shiljilt
if(y < y2-1) y++; // coordinat y dood hureend hureegui uyed y++
else y = y1 + 1; // coordinat y dood hureend hursen uyed deed hureenees nevtreh
break; // switch() salaalaltaas garah
}
case 4 : { // Mogoin chiglel zuun uyed mogoin tolgoin bairlal shiljilt
if(x > x1 + 1) x--; // coordinat x zuun hureend hureegui uyed x--
else x = x2-1; // coordinat x zuun hureend hursen uyed baruun hureenees nevtreh
break; // switch() salaalaltaas garah
}
}
if(x == hoolX && y == hoolY){ // mogoi hoolond hursen eseh shalguur
Onoo = Onoo + onoo; // Mogoi hoolond hursen tul Score onoog score onoogoor nemegduuleh
gotoxy(x2-4, y1-1); // Score onoo bichih bairlald cursor avaachina
printf("%5d",Onoo); // Score onoo 4 temdegtiin zaid hoish ni shahaj bichih
ns++;
X[ns] = xx;
Y[ns] = yy;
hoolX = rand() % urt + 1 + x1; // hoolnii bairlaliin x coordinat shine utga olgoh
hoolY = rand() % urgun + 1 + y1; // // hoolnii bairlaliin y coordinat shine utga olgoh
gotoxy(hoolX, hoolY); // hoolnii shine bairlald cursor avaachih
printf("$"); // hoolnii temdegt hevleh

} else {
gotoxy(X[0], Y[0]);
printf(" ");
for(i = 0; i < ns; i++){
X[i]=X[i+1];
Y[i]=Y[i+1];
}
X[ns] = xx;
Y[ns] = yy;
gotoxy(X[0], Y[0]);
printf("_");
}
gotoxy(xx, yy);
printf("o");
gotoxy(x, y);
printf("@");

Sleep(100); // Program 100 nano secund zogsolt hiih; amrah
}

int main() {
Setup(); // Setup() function duudan ajilluulah; Huvisagchdiin anhnii utga olgoltuud hiigdene
Draw(); // Draw() function duudan ajilluulna; Mogoin yavah talbariig zurna
while(!gameOver){ // while() davtalt togloom duusah hurtel ajillana
Game(); // Game() function duudan ajilluulna; Togloom ajillana
}

gotoxy(x1, y2+1);

return 0; // program duusna
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.