ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 24.03.2020 20:57:03

ამოცანა: ჯარისკაცები

მომხმარებელი: Nero

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







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

int Pops[2000], n;
float Height[1000];

int GetSoldiers(int);

int main(){
        scanf("%d\n", &n);

        for(int i=0; i<n; ++i)
                scanf(" %f", &Height[i]);

        for(int i=n*2; i--;)
                Pops[i]=-1;

        for(int soldier=n; soldier--;){
                Pops[soldier*2]=n-soldier-1;
                for(int i = 1; i+soldier<n; ++i)
                        if(Height[i+soldier]<Height[soldier])
                                Pops[soldier*2]=min(Pops[soldier*2], Pops[(i+soldier)*2]+i-1);
        }

        for(int soldier=0; soldier<n; ++soldier){
                Pops[soldier*2+1]=soldier;
                for(int i=1; soldier-i>=0; ++i){
                        if(Height[soldier-i]<Height[soldier])
                                Pops[soldier*2+1]=min(Pops[soldier*2+1], Pops[(soldier-i)*2+1]+i-1);
                }
        }

        int min_val=1000, tmp;
        for(int i=0; i<n; ++i)
                min_val=min(min_val, GetSoldiers(i));
        
        printf("%d", min_val);

        return 0;
}

int GetSoldiers(int soldier){
        int spaceR=n-soldier-1;
        int spaceRwitheq = spaceR;
        for(int i=1; soldier+i<n; ++i){
                if(Height[soldier]>Height[soldier+i])
                        spaceR=min(spaceR, Pops[(soldier+i)*2]+i-1);
                else if(Height[soldier]==Height[soldier+i])
                        spaceRwitheq=min(spaceRwitheq, Pops[(soldier+i)*2]+i-1);
        }

        int spaceL=soldier;
        int spaceLwitheq = spaceL;
        for(int i=1; soldier-i>=0; ++i){
                if(Height[soldier]>Height[soldier-i])
                        spaceL=min(spaceL, Pops[(soldier-i)*2+1]+i-1);
                else if(Height[soldier]==Height[soldier-i])
                        spaceLwitheq=min(spaceLwitheq, Pops[(soldier-i)*2+1]+i-1);
        }
        
        return min(min(spaceL+spaceRwitheq, spaceR+spaceLwitheq), spaceL+spaceR);
}

ტესტები

შემავალი მონაცემები
10
1.40020 1.47490 1.57840 1.22990 1.82670 1.09770 1.09220 1.54010 1.78810 1.48620
გამომავალი მონაცემები
4
თქვენი პასუხი
4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
25
1.74710 1.97660 1.58280 1.52410 1.12630 1.57420 1.05020 1.11680 1.65810 1.53630 1.67500 1.81190 1.48620 1.91360 1.12490 1.76840 1.25020 1.88210 1.91620 1.49910 1.92600 1.13040 1.28870 1.93650 1.59240
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
1.45730 1.84120 1.30180 1.49740 1.11770 1.57520 1.61620 1.70740 1.44070 1.97900 1.70250 1.09720 1.28220 1.15200 1.90910 1.41080 1.12080 1.02980 1.37720 1.42310 1.92200 1.64240 1.02120 1.27720 1.01080 1.41660 1.72770 1.91980 1.43870 1.94420 1.88450 1.1...
გამომავალი მონაცემები
76
თქვენი პასუხი
76
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
1.06620 1.90200 1.51790 1.53450 1.31900 1.07890 1.96140 1.52180 1.98280 1.42210 1.74820 1.55140 1.31310 1.51750 1.09490 1.88970 1.31500 1.49780 1.95550 1.51160 1.63080 1.17170 1.10600 1.70780 1.51980 1.60750 1.49910 1.04670 1.59990 1.53000 1.68580 1.6...
გამომავალი მონაცემები
72
თქვენი პასუხი
72
ჩეკერის პასუხი
YES
შემავალი მონაცემები
600
1.09150 1.04090 1.65210 1.04140 1.97630 1.43920 1.18580 1.77720 1.76240 1.76790 1.13230 1.58180 1.93510 1.32070 1.04460 1.39490 1.81070 1.51860 1.97530 1.96860 1.34980 1.91420 1.18640 1.85690 1.29210 1.80290 1.89200 1.56630 1.09640 1.86220 1.14290 1.4...
გამომავალი მონაცემები
539
თქვენი პასუხი
539
ჩეკერის პასუხი
YES
შემავალი მონაცემები
800
1.77530 1.19440 1.09140 1.59740 1.55290 1.30680 1.44570 1.68590 1.35290 1.95510 1.24000 1.98000 1.22320 1.24550 1.09010 1.73180 1.04240 1.41140 1.11090 1.00600 1.33370 1.81790 1.62690 1.66890 1.39920 1.57300 1.91480 1.53980 1.26040 1.16680 1.08780 1.2...
გამომავალი მონაცემები
729
თქვენი პასუხი
729
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000
1.46680 1.23000 1.15970 1.39210 1.79200 1.83040 1.70420 1.18150 1.84670 1.50180 1.36450 1.55550 1.86610 1.28810 1.44390 1.20350 1.91650 1.36000 1.74470 1.62780 1.70860 1.02020 1.27890 1.13230 1.73180 1.31410 1.01090 1.97360 1.19530 1.66940 1.74130 1....
გამომავალი მონაცემები
919
თქვენი პასუხი
919
ჩეკერის პასუხი
YES
შემავალი მონაცემები
900
1.91700 1.72750 1.08360 1.46470 1.02820 1.66980 1.91040 1.08900 1.16620 1.26930 1.59120 1.58690 1.51940 1.32220 1.12770 1.82350 1.44470 1.51730 1.23920 1.52070 1.92970 1.43660 1.80190 1.64260 1.45900 1.57200 1.37180 1.19640 1.95520 1.71900 1.58720 1.4...
გამომავალი მონაცემები
824
თქვენი პასუხი
824
ჩეკერის პასუხი
YES
შემავალი მონაცემები
5
0.2 0.3 0.1 0.3 0.2
გამომავალი მონაცემები
1
თქვენი პასუხი
1
ჩეკერის პასუხი
YES
შემავალი მონაცემები
999
1.28050 1.70090 1.73200 1.61260 1.29930 1.68180 1.25170 1.20130 1.75910 1.39020 1.97690 1.42140 1.22320 1.49730 1.28440 1.01300 1.42340 1.56690 1.26840 1.57300 1.72230 1.05600 1.18020 1.94050 1.97970 1.33160 1.95080 1.99770 1.49300 1.06400 1.59340 1.8...
გამომავალი მონაცემები
911
თქვენი პასუხი
911
ჩეკერის პასუხი
YES