[-ordi-]

Olen vaikselt proovinud lahendada igasuguseid programmeerimisülesandeid.
Hetkel vaevan pead sellisega http://www.upload.ee/image/397828/Pealkirjata.jpg
Kas keegi viitsiks mõne vihje anda kuidas tuleks, võiks seda lahendada, koodi ei soovi.
Kergemad olen suht enamvähem Eesti IO ära lahendanud, aga osad on päris keerukad vähemalt minu jaoks.
Mõned on veel aga alustaks sellest.

[Deadlock]

Mina teeksin selle nii:

Kirjutaksin funktsiooni, mis annab järjestikku asuvate aialippide "põhja" pindala, ehk leiaks sisestatud aialippide põhjal visualiseerides midagi sellist:


Kuna sama funktsioon võib võtta sisendiks ka ainult ühe lipi, andes kogu lipi pindala, saan ma kasutada seda üldiselt, ning kirjutada kahekordne tsükkel, mis kontrollib kõik võimalikud järjestikku asuvad lipikombinatsioonid ära. Seega saavad arvestatud ka igasugused kahest ja ühest lipist koosnevad "pilvelõhkujad", mis pindalalt suurimad on.

Kui mingi ajapiirang ka on arvutamisel, siis ei tea, kas see just optimaalne lahendus oleks, aga vähemalt töötab...

NewScientist pakub nädalas korra lahendamist, kellel viitsimist on: http://www.newscientist.com/topic/enigma

[guest1902]

Bluebull, kuna antud piirid pole suured, siis t55tab küll. Ajaline piir on 1s.
See ylesanne on selle 6ppeaasta lahtisest v6istlusest ja ise arvasin samuti, et nii labane algo ei l2he l2bi.
Kui piirid oleksid suuremad (nt lippide k6rgus oleks 10^9), siis tuleks midagi targemat v2lja m6elda...

[-ordi-]

Ülesanne tundub lihtsam kui arvasin, vb keerukaks osutub see elementide läbikäimine kahe tsükliga aga pmst muu ma tegin ära.

Kle Elrak oled selle nt javas ära teinud ja kas mahtus aega?

[guest1902]

Ma progresingi Javas (kindluse mõttes), sest c++ süntaks tundus liiga roostes, ning mahtus aega ilusti.

[-ordi-]

Muidu ma lugesin need andmed kõik massiivi ja funktsioon, mis leiab põhja pindala on samuti kirjutatud arvestades massiivi.
Aga ma ei saa ju toda funktsiooni kasutada seal kahekordses tsüklis, sest see leiab mul kõige lühema lipi ja korrutab selle N lippide arvuga.

[Deadlock]

[guest1902]

Ma vist tegin niimoodi, et leidsin suurima ja väikseima lipi kõrguse (andmeid sisse lugedes) ja siis välimine tsükkel käib läbi väärtused minimaalsest kõrgusest maksimaalseni, enne sisemist tsüklit loob mingi loenduri, sisemises tsüklis käib läbi massiivi iga elemendi ning võrdleb seda jooksva lipi kõrgusega; kui on suurem-võrdne, siis suurendab loendurit; kui mitte, siis omistab vastusele loenduri ja jooksva lipi kõrguse korrutise juhul, kui saadud korrutis on vastusest suurem. Pole just teab mis efektiivne, kuid seda annaks lippide suure arvu korral optimeerida küll.

e: lisan oma versiooni

Spoiler

java:

import java.io.*; import java.util.*;   public class rekl {         public static void main(String args[]) throws Exception{                 BufferedReader sis=new BufferedReader(new FileReader("rekl.sis"));                 PrintWriter val=new PrintWriter(new FileWriter("rekl.val"));                 int n=Integer.parseInt(sis.readLine());                 StringTokenizer st=new StringTokenizer(sis.readLine());                 sis.close();                 int min=Integer.MAX_VALUE;                 int max=Integer.MIN_VALUE;                 int[] a=new int[n];                 for(int i=0;i<n;i++) {                         a[i]=Integer.parseInt(st.nextToken());                         if(a[i]<min) min=a[i];                         if(a[i]>max) max=a[i];                 }                 //int result=max;                 int result=0;                 for(int i=min;i<=max;i++) {                         int counter=0;                         for(int j=0;j<n;j++) {                                 if(a[j]>=i) counter++;                                 else counter=0;                                 if(result<counter*i) result=counter*i; // see rida tuli nüüd juurde                         }                         if(result<counter*i) result=counter*i;                 }                 val.println(result);                 val.flush();         } }

[-ordi-]

Millegi pärast on mul loll komme kõik asjad väga raskesti ära lahendada .

[Renka]

Elrak, proovi oma koodi sellise sisendiga:

[-ordi-]

Testisin ka seda koodi, töötab suht ainult mõne sisendiga, nii lihtne see lahendus ikka ei ole.

[DoS]

põhimõtteliselt tal see töötab, lihtsalt vaja if(result<counter*i) result=counter*i; kopeerida ka sisemise tsükli else'i (enne counter=0)
teeks veel nii, et ei kontrollita olematuid lipi kõrgusi läbi, oleks ilmselt päris hea lahendus kuigi tundub, et antud ülesande püstitusel eriti vahet ei ole, mahub aega igat pidi

[mrkaarel]

Kahekordsetele tsüklitele vahelduseks üks rekursiivne lahendus ka. Funktsioon saab ette aialippide massiivi, leiab madalaima lipi, arvutab selle järgi pindala ja kutsub sama funktsiooni välja madalaimast lipist vasakule ja paremale poole jäävate lippide jaoks. Failist input-output osa ei tundunud erutav, see jäi välja

[Deadlock]

Proovisin ka ära, kui kõik juba proovivad:

Spoiler

public class Test {    public static void main(String[] args) {       int[] array = {8,2,2,1,3,6,2,8};       int result = getMaxRectArea(array);       System.out.println(result);    }        public static int getMaxRectArea(int[] array){       int maxArea = 0;       for(int i = 0; i < array.length; i++)          for(int j = i; j < array.length; j++){                         int val = getSurfaceArea(array, i, j);             if(val > maxArea) maxArea = val;          }       return maxArea;    }        public static int getSurfaceArea(int[] array, int startIndex, int endIndex){       Integer lowestValue = null;             for(int i = startIndex; i <= endIndex; i++){          if(lowestValue == null || array[i] < lowestValue){             lowestValue = array[i];                      }       }       return lowestValue * (endIndex - startIndex +1);          } }

[-ordi-]

No võtame järgmise ülesande?

kellelgi midagi välja pakkuda ei ole?

[guest1902]

Eelmisest ülesandest nii palju, et tookord ma suutsin ikka max p kätte saada, sest ma testisin igasuguste kombinatsioonidega. Nüüd peaks kood korras olema.
http://www.ttkool.ut.ee/comp/balt/boi96d1e.htm
Esimene ülesanne näris kunagi täiega, kuid vahepeal on ununenud. Nv proovin uuesti. Vihjeks pidavat olema kahendotsing...

[-ordi-]

[guest1902]

[virus152]

See ülesanne oli paar aastat tagasi valikvõistlusel või õppesessioonil kasutusel. Näidislahendus oli mäletamist mööda realiseeritud nii, et kattuva osa sisse üritati lihtsalt panna järjest väiksemaid ruute seni kuni kasutatava ruudu pindala oli mingi järk allpool nõutud täpsust.

[webromps]

http://uva.onlinejudge.org/

Sellel aadressil on üsna palju ülesandeid.

[virus152]

Hinnavaatlejate kogutud teosed https://foorum.hinnavaatlus.ee/viewtopic.php?t=63007

Lisasin lõppu mõned lehed, mida minu meelest seal ei olnud (USACO't lihtsalt täiendasin).

[-ordi-]

[guest1902]

Topic resurrection!!1
kk

Selline ülesanne siis (väike abstraheerimine ), et on antud k-pikkune arv alusel n (k<=n), kusjuures iga number esineb selles arvus ühe korra. Leida kõik sellised arvud, milles esimesest i numbrist moodustatud arv jagub arvuga i.

Lihtsuse mõttes olgu esialgu k=n=10.*
Permutatsioonid 10 puhul ei tohiks erilist raskust valmistada (paberi pealgi lahendatav, kuid võtab rohkem aega kui koodimine)... küll jääb mulle mõistatuseks igas ülejäänud arvusüsteemis permutatsioonide genereerimine (ja omakorda jaguvuse kontrollimine), et asi võtaks mõistuse piires aega. Jäägi leidmine mitte-kümnendsüsteemi arvudega pole just asi, millega tegelenud.

* esialgses ülesandes oligi antud just see variant ning asi lahenes (veits bruutfoorsides) valutult. Et ülesanne veidike arusaadavam oleks, siis nt 1234567890 ei sobi, sest 1234%4==2. 10_P_10 puhul leidub 1 vastus.

[troglodyte]

Jäägi leidmiseks teisendad arvu kümnendsüsteemi.

[mark11]

oletame, et I on paaris arv, siis me ei pea genereerima paarituid permutatsioone, sest paaritu % paaris > 0
kui me nüüd vaatame mitu võimalust on sellist, et paarisarv on viimane, siis tuleb meil[kui ma nüüd väga võssa ei pannud][/ot]
C(9, 5)*5! * C(5, 4) * 4! = 1814400

mis põhimõtteliselt on ju teatavasti 10!/2
ehk siis juba on näha pool võitu
sama asi kehtib teiste asjade kohta ka, näiteks 9'ga jaguvad arvud ainult siis kui ristsumma jagub 9'ga.. seega kui vahet pole millise arvu ristsumma ei jagu 9'ga siis vastus on 0 näiteks