Кајгана CodeOpen. Reopened!

deXterche · 4 јули 2008

Не стигнав вчера вечер имав некој обврски...nevermind

Пошто лошо помина лавиринтот, малце ќе ја спуштам топката и ќе дадам еден типично математички проблем

Проблемот е:

Следен палиндром

Позитивен интеџер се нарекува палиндорм ако е зададен во децимален систем и се чита исто од лево кон десно и обратно. За даден позитивен интеџер К кој не е поголем од 1 000 000, испишија вредноста од најмалиод палиндром поголем од К за излез.

Влез:
Првата линија содрижи интеџер t ( <= 1000 ), што означува број на тест случаи. Интеџерот K се задава на следната линија.

Излез:
За секој K, испишиго најмалиот палиндром поголем од K.

Пример

Влез:
2
808
2133

Излез:
818
2222

Бодување

3 поени + мандат за наредниот циклус - првото најпотимално решение
2 поени - првиот што ќе ми испрати решение
1 поени - сите наредни
0 поени - неточни, и решениа кои одскокнуваат од шемата зададена погоре

Краен рок

05.07.2008 - 15:00

Случаеви на кои се бара одговор

Влез:
3
123052
9670
9238

Излез: ?

TheJoco · 4 јули 2008

Мислам дека е добро при поставување на задачата да се даде и опис на функцијата, конкретно во овај случај би дошло:

int[] closestPalindroms(int len, int[] nums)

Во јава би имале излишен аргумент len, во nums.length би ја имале таа информација.

back_rest · 5 јули 2008

Нема проблем, флексибилни сме. Може и со BufferedReader (или cin за C-сашите) да се земе целиот влез или пак да се направи само функција со пренос на полето. Ваша желба.

Иначе, добро што увиде, треба да се напомене тоа за наредниве задачи.

deXterche · 5 јули 2008

Резултати

3 поени за најоптимално решение добива "јас"
-го добива мандатот за следна задача (гледај да биде полесна, не да заглавиме како со лавиринтот

)

PHP:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class pal {

    public static int nextPal(int a){
        StringBuffer in = new StringBuffer(""+a);
        int sr=(in.length()-1)/2;
        int os=(in.length())%2;
        int tmp = Integer.parseInt((in.substring(0, sr+1)+new StringBuffer(in.substring(0, sr+1-os)).reverse()));
        if (tmp>=a)return tmp;
        String zg=""+(Integer.parseInt(in.substring(0, sr+1))+1);
        tmp = Integer.parseInt(zg+new StringBuffer(zg.substring(0, zg.length()-os)).reverse());
        return tmp;
    }
    
    public static void main(String[] args) throws FileNotFoundException,IOException{
        BufferedReader in = new BufferedReader(new FileReader("vlez.in"));
        int lines = Integer.parseInt(in.readLine());
        for(int i =0;i<lines;i++){
            int n = Integer.parseInt(in.readLine());
            System.out.println(nextPal(n));
        }
    }

}

2 поена за прво испратено решение добива TheJoco
- решението е класичен брутфорс

PHP:

public class Palindroms {
    public boolean isPalindrom(int num) {
        int n1 = num;
        int n2 = 0;
        while (n1 != 0) {
            n2 = n2 * 10 + n1 % 10;
            n1 /= 10;
        }
        return num == n2;
    }

    public int[] closestPalindroms(int len, int[] nums) {    
        for(int i=0; i<len; i++) {
            int broj = nums[i];
            while(!isPalindrom(broj))
                broj++;
            nums[i] = broj;
        }
        return nums;
    }

    public static void main(String[] args) {
        int [] pals = new Palindroms().closestPalindroms(3,
                new int[] { 123052, 9670, 9238 });
        for(int p : pals) {
            System.out.println(p);
        }
    }
}

1 поен добива Димитар
- класичен брутфорс
* забелешка: кодот е пхп

PHP:

<?php
function Palindrom($dol, $n)
{
    for ($i=0;$i<$dol;$i++)
    {
        $m=0;
        $broj=$n[$i];
        while($m!=$broj)
        {    
            $broj++;    
            $m = NajdiPal($broj);            
        }
        echo $m . "<br>";            
    }
}
function NajdiPal($broj)
{
    while($broj >0)
    {
        $ost=$broj %10;
        $obr*=10;
        $obr+=$ost;
        $broj=(int)($broj/10);
    }
    return $obr;
}
?>
<html xmlns="http://www.w3.org/1999/xhtml">    

<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
</head>

<body>
<?php

$numbers = array(123052, 9670, 9238);
echo "За зададени ";
foreach ($numbers as $broj) {
    echo $broj . " ";
}
echo "<br><br>";
Palindrom(3, $numbers);
?>
</body>
</html>

1 поен добива marjan_gvg
- класичен брутфорс
*забелешка: кодот е во паскал

PHP:

program palindrom;
uses crt;
var n,i:longint;
    broj:array[1..1000] of longint;
function isPalindrom(x:longint):boolean;
var i:longint;
    y,y2:string;
begin
  str(x,y);
  y2:='';
  x:=length(y);
  for i:=x downto 1 do
    y2:=y2+y[i];
  if y=y2 then isPalindrom:=true
  else isPalindrom:=false;
end;
function closestPalindrom(x:longint):longint;
var z:longint;
begin
z:=x+1;
  while isPalindrom(z)=false do
    z:=z+1;
closestPalindrom:=z;
end;

begin
clrscr;
readln(n);
for i:=1 to n do readln(broj[i]);

for i:=1 to n do
  writeln(closestPalindrom(broj[i]));
end.

deXterche · 5 јули 2008

Коментар

Незнам зошто сите (исклучок јас) сте користеле брутфорс, кога решението беше толку едноставно. За секој зададен број, пример 1257225 ќе ја земевте првата половина 1257*** и ќе ја залепевте од другата страна по обратен редослед 1257521, просто беше решението, нема потреба од циклуси и while јамки. Прво седнете на хартија решете го, па после искодирајте, тоа е најслесниот дел :toe:

Димитар · 5 јули 2008

deXterche напиша:
Коментар

Незнам зошто сите (исклучок јас) сте користеле брутфорс, кога решението беше толку едноставно. За секој зададен број, пример 1257225 ќе ја земевте првата половина 1257*** и ќе ја залепевте од другата страна по обратен редослед 1257521, просто беше решението, нема потреба од циклуси и while јамки. Прво седнете на хартија решете го, па после искодирајте, тоа е најслесниот дел

Коментар 2

Не си во право

Пример број: 1673
Според ова твоето решението е 1661.... а всушност точно е 1771
(кај „јас“ е точно)

deXterche · 5 јули 2008

Димитар напиша:
Коментар 2

Не си во право

Пример број: 1673
Според ова твоето решението е 1661.... а всушност точно е 1771

Го споредуваш добиениот број со дадениот, ако е помал ја зголемуваш последната цифра од половината за 1, има неколку усолови (парен број на големина на бројка, па со модул се манипулира, од јас решението разгледајте го, таму е добро средно...), само јас' грубо објаснив...

TheJoco · 5 јули 2008

Yeap, deXterche, во право си, со ислучок на јас (аман смени го надимакот

), сите имаме глупави решенија. Иако можеби кодот некогаш ќе изгледa грдо, сепак решението ке биде најоптимално.

Тест на мојата задача на од јас за броеви од 0 - 1 000 000:

ЈАС: 74109 ms
TheJoco: 428641 ms (fail)

Во моја одбрана мојта задача работи и на негатвни броеви

. Знам не се бараше тоа...

deXterche · 5 јули 2008

Да се оптимизира решенито на јас (да се исфрлат конверзиите) ќе се добијат уште подобри бројки :vozbud:

јас · 5 јули 2008

TheJoco напиша:
Yeap, deXterche, во право си, со ислучок на јас (аман смени го надимакот ), сите имаме глупави решенија. Иако можеби кодот некогаш ќе изгледa грдо, сепак решението ке биде најоптимално.

Тест на мојата задача на од јас за броеви од 0 - 1 000 000:

ЈАС: 74109 ms
TheJoco: 428641 ms (fail)

Во моја одбрана мојта задача работи и на негатвни броеви . Знам не се бараше тоа...

@1 Ќе ме караат администраторите.

Шо му фали баш е добар никот ко ќе се обидва некој да ме цитира

)
@2 Ова е веројатно за сите броеви во опсегот?? Оти за 1000 бројки во фајлот ( според спецификацијата на декстерче) ми се извршва за околу 100ms (*1000 за миљон тест примери тука се

)
@ deXterce ти кажав набрзина беше ова и со стрингови ми беше брзо за кодирање. Ако има некој време нека проба да го преработи решението со делење за да видиме какви времиња ќе се добијат.

За следна задача ќе се потрудам да има за утре вечер (20h-21h).

јас · 6 јули 2008

CodeOpen - Round 4 - Острови

Знај кога да заврни на вимблдон за да напишам задача

Пак ќе имаме малку матрици

Значи како влез добивате матрица м*н составена од "#" и "." која треба да рапрезентира мапа од некој архипелаг.
Еве пример за влез:
........................
...#####..........##....
...#####.........#####..
...#####....###.######..
........................
"#" е копно а "." е вода. Ваша задача е да ги идентификувате копната и да ги испечатите сортирани по површина (прво е најголемото). За идентификација на копната ќе го користите најлевото поле во најгорната линија. Значи за примеров излезот треба да е "{(1,3),(1,18),(3,12)}". Повторно излезот треба да е со формат стринг без празни места.

Интерфејс кој треба да го почитувате при имплементација е:
String najdiOstrovi(char[][] mapa)

Еве уште некој пример:
Влез:
..........
..#######.
........#.
...###..#.
...###..#.
Излез "{(1,2),(3,3)}"
.

Делењето на поени е стандардно. 3 за најбрзо(по извршвање) решение. Останатите решенијакои функционираат по 1. За тие шо не работат 0.

Време до утре (Понеделник) 22:00.

јас · 7 јули 2008

CodeOpen - Round 4 - Резултати

За задачата добив две решенија од Димитар и TheJoco, и двете се точни. Бидејќи Димитар ми ја прати прв задачата тој го добива мандатот за следна задача и 3 поени а ТхеЈоцо добива 2 поени затоа што воопшто не се разликуваше од решението на Димитар туку само подоцна прати решение.

Еве ги решенијата:
Димитар:

Код:

[COLOR=#000000][COLOR=#0000bb]<?php
$broj[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700];
[/COLOR][COLOR=#0000bb]$red[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]10[/COLOR][COLOR=#007700];
[/COLOR][COLOR=#0000bb]$kolona[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]10[/COLOR][COLOR=#007700];
[/COLOR][COLOR=#0000bb]$mapa [/COLOR][COLOR=#007700]=
array( 
........[/COLOR][COLOR=#007700]
);

function [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700])
{
global [/COLOR][COLOR=#0000bb]$red[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$kolona[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$broj[/COLOR][COLOR=#007700];

if([/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]][[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]] == [/COLOR][COLOR=#dd0000]'#'[/COLOR][COLOR=#007700])
        {
            [/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]][[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]]=[/COLOR][COLOR=#dd0000]'.'[/COLOR][COLOR=#007700];
            [/COLOR][COLOR=#0000bb]$broj[/COLOR][COLOR=#007700]++;
            [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]-[/COLOR][COLOR=#0000bb]1[/COLOR][COLOR=#007700]);
            [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]-[/COLOR][COLOR=#0000bb]1[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]);
            [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]+[/COLOR][COLOR=#0000bb]1[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]);
            [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]+[/COLOR][COLOR=#0000bb]1[/COLOR][COLOR=#007700]);
        }
    return [/COLOR][COLOR=#0000bb]$broj[/COLOR][COLOR=#007700];
}
function [/COLOR][COLOR=#0000bb]najdiOstrovi[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700])
{
    global [/COLOR][COLOR=#0000bb]$red[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$kolona[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$broj[/COLOR][COLOR=#007700];
    [/COLOR][COLOR=#0000bb]$n[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700];
    [/COLOR][COLOR=#0000bb]$ar1 [/COLOR][COLOR=#007700]= array();
    [/COLOR][COLOR=#0000bb]$ar2 [/COLOR][COLOR=#007700]= array();
    for ([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700];[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]<[/COLOR][COLOR=#0000bb]$red[/COLOR][COLOR=#007700];[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]++)
        for ([/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700];[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]<[/COLOR][COLOR=#0000bb]$kolona[/COLOR][COLOR=#007700];[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]++)
        {
            if([/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]][[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]] == [/COLOR][COLOR=#dd0000]'#'[/COLOR][COLOR=#007700])
            {
                [/COLOR][COLOR=#0000bb]$broj [/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700];
                [/COLOR][COLOR=#0000bb]$ar2[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$n[/COLOR][COLOR=#007700]] = [/COLOR][COLOR=#dd0000]"($i,$j)"[/COLOR][COLOR=#007700];
                [/COLOR][COLOR=#0000bb]$ar1[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$n[/COLOR][COLOR=#007700]] = [/COLOR][COLOR=#0000bb]barajmapa[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700],[/COLOR][COLOR=#0000bb]$j[/COLOR][COLOR=#007700]);
                [/COLOR][COLOR=#0000bb]$n[/COLOR][COLOR=#007700]++;
            }
        }
        [/COLOR][COLOR=#0000bb]array_multisort[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$ar1[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]SORT_DESC[/COLOR][COLOR=#007700], [/COLOR][COLOR=#0000bb]$ar2[/COLOR][COLOR=#007700]);
        [/COLOR][COLOR=#0000bb]$glaven [/COLOR][COLOR=#007700]= [/COLOR][COLOR=#dd0000]"{"[/COLOR][COLOR=#007700];
        for([/COLOR][COLOR=#0000bb]$i [/COLOR][COLOR=#007700]= [/COLOR][COLOR=#0000bb]0[/COLOR][COLOR=#007700]; [/COLOR][COLOR=#0000bb]$i [/COLOR][COLOR=#007700]< [/COLOR][COLOR=#0000bb]count[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$ar2[/COLOR][COLOR=#007700]); [/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]++) 
            [/COLOR][COLOR=#0000bb]$glaven [/COLOR][COLOR=#007700]=[/COLOR][COLOR=#0000bb]$glaven [/COLOR][COLOR=#007700]. [/COLOR][COLOR=#0000bb]$ar2[/COLOR][COLOR=#007700][[/COLOR][COLOR=#0000bb]$i[/COLOR][COLOR=#007700]].[/COLOR][COLOR=#dd0000]","[/COLOR][COLOR=#007700];
        [/COLOR][COLOR=#0000bb]$glaven [/COLOR][COLOR=#007700]= [/COLOR][COLOR=#0000bb]rtrim[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$glaven[/COLOR][COLOR=#007700],[/COLOR][COLOR=#dd0000]','[/COLOR][COLOR=#007700]) . [/COLOR][COLOR=#dd0000]"}"[/COLOR][COLOR=#007700];
        
        return [/COLOR][COLOR=#0000bb]$glaven[/COLOR][COLOR=#007700];
}
[/COLOR][COLOR=#0000bb]?>
[/COLOR]
<html>
<body>
[COLOR=#0000bb]<?php
[/COLOR][COLOR=#007700]echo [/COLOR][COLOR=#0000bb]najdiOstrovi[/COLOR][COLOR=#007700]([/COLOR][COLOR=#0000bb]$mapa[/COLOR][COLOR=#007700]);
[/COLOR][COLOR=#0000bb]?>
[/COLOR]</body>
</html>[/COLOR]

Код:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Ostrovi {
    
    int tp = 0;
    
    String najdiOstrovi(char[][] mapa) {
    
        for(int i=0; i<mapa.length; i++) {
            for(int j=0; j<mapa[0].length; j++) {
                if(mapa[i][j]=='#') {
                    ff(mapa, i, j);
                    addIsland(i, j, tp);
                }
            }
        }
        
        Collections.sort(islands, new Comparator<Island>() {
            public int compare(Island o1, Island o2) {
                return o1.povrsina-o2.povrsina;
            }
        });
        String rv = "{";
        for(Island isl : islands) {
            if(rv.length()>1) rv += ",";
            rv += isl.rep;
        }
        rv+="}";
        return rv;
    }
    
    List<Island> islands = new ArrayList<Island>();
    class Island {
        String rep;
        int povrsina;
        public Island(String rep, int povrsina) {
            this.rep = rep;
            this.povrsina = povrsina;
        }
        
    }
    private void addIsland(int i, int j, int povrsina) {
        islands.add(new Island("("+i+", "+j+")", povrsina));
    }
    
    private void ff(char [][]mapa, int i, int j) {    
        if(i<0 || i>=mapa.length) return;
        if(j<0 || j>=mapa[0].length) return;
        if(mapa[i][j]!='#') return;
        mapa[i][j] = 'C';
        tp++;
        ff(mapa, i+1, j);
        ff(mapa, i, j+1);
        ff(mapa, i-1, j);
        ff(mapa, i, j-1);
    }
    public static void main(String[] args) {    
        Ostrovi o = new Ostrovi();
        String [] s = new String [] {
                "........................",
                "...#####..........##....",
                "...#####.........#####..",
                "...#####....###.######..",
                "........................"
            };
        char [][] a = new char[s.length][s[0].length()];
        int k = 0;
        for(String l : s) {
            a[k++] = l.toCharArray();
        }
        System.out.println(o.najdiOstrovi(a));
    }

}

Решенијата не ги извршив за да ги проверам туку само го анализирав кодот. Важно ми е дека пристапот ви е добар.

Димитар · 7 јули 2008

CodeOpen - Round 4 - дропки

Ајде една лесна за да има повеќе одговори

Најди си сите различни дропки подредени по големина со вредност од 0 до 1 каде деленикот и делителот не треба да се поголеми од N.
На крај испечати колку такви дропки има.

пример доколку влезот N биде 5 - излезот треба ќе биде следниот:
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
Postojat 11 dropki.

Димитар · 8 јули 2008

Ајде, едит....

Тест примери: 23, 64 и 86

Краен рок 8 јули во 23:50

skrstevsky · 8 јули 2008

Оти 5/5 не влегува а има 1/1 ?

Edit: не треба одговор видов (станав од спиење тогаш ми текна

)

Кајгана CodeOpen. Reopened!

deXterche

тадаммм

TheJoco

back_rest

ex mod coder

deXterche

тадаммм

deXterche

тадаммм

Димитар

deXterche

тадаммм

TheJoco

deXterche

тадаммм

јас

јас

јас

Димитар

Димитар

skrstevsky

Kajgana Shop