[PJWSTK] ASD – Wprowadzenie – przykładowe rozwiazania

Gdyby ktoś nie pamiętał adresu do testowania kodu:
http://asd.spox.spoj.pl/

Najlepsze rozwiązanie to kod w C, używa najmniej pamięci i wykonuje się w 0.09 sec (wynik: 100%).

#include <stdio.h>
int main()
{
    unsigned int iloscDoWczytania;
    fscanf(stdin, "%u", &iloscDoWczytania);
    unsigned int podstawa;
    fscanf(stdin, "%u", &podstawa);
    unsigned int suma = 0;
    unsigned short int wczytany = 1;
    while(iloscDoWczytania-- > 0)
    {
        fscanf(stdin, "%hu", &wczytany);
        suma += wczytany;
    }
    unsigned int iloscZnakow = 1;
    if(podstawa == 0)
    {
        iloscZnakow = 0;
    }
    else if(podstawa == 1)
    {
        iloscZnakow = suma;
    }
    else
    {
        while(suma > podstawa)
        {
            iloscZnakow++;
            suma = suma / podstawa;
        }
    }
    fprintf(stdout, "%u", iloscZnakow);
    return 0;
}

Inne (o dziwo – jak w kolejnych zadaniach będzie coś z tablicami to raczej PHP nie ma szans na wykonanie obliczeń w wymaganym czasie) dobre rozwiązanie to użycie PHP, wykonuje się w 0.68 sec. (wynik: 100%):

<?PHP
$message = file_get_contents('php://stdin');
$d = explode(chr(0x20), $message);
$iloscDoWczytania = $d[0];
$podstawa = $d[1];
$suma = 0;
$idDoWczytania = 2;
while($iloscDoWczytania-- > 0)
{
    $suma += $d[$idDoWczytania++];
}
$iloscZnakow = 1;
if($podstawa == 0)
{
	$iloscZnakow = 0;
}
else if($podstawa == 1)
{
	$iloscZnakow = $suma;
}
else
{
	while($suma > $podstawa)
	{
		$iloscZnakow++;
		$suma = (int) ($suma / $podstawa);
	}
}
echo $iloscZnakow;

Dla osób co liczyły na pisanie w Javie mam niestety smutną wiadomość: Java jest za wolna! Ostatni test (w którym jest podane ponad 65000 parametrów/liczb) wykonuje się ponad 2 sekundy i nie zalicza ostatniego testu (wynik: 80% [4 z 5 testów]).

import java.util.Scanner;

public class Main
{
    public static void main(String[] argumenty)
	{
		Scanner in = new Scanner(System.in);
	    int iloscDoWczytania = in.nextInt();
	    int podstawa = in.nextInt();
	    int suma = 0;
	    while(iloscDoWczytania-- > 0)
	    {
	        suma += in.nextInt();
	    }
	    int iloscZnakow = 1;
	    if(podstawa == 0)
	    {
	        iloscZnakow = 0;
	    }
	    else if(podstawa == 1)
	    {
	        iloscZnakow = suma;
	    }
	    else
	    {
	        while(suma > podstawa)
	        {
	            iloscZnakow++;
	            suma = suma / podstawa;
	        }
	    }
	    System.out.print(iloscZnakow);
	}
}
Ten wpis został opublikowany w kategorii PJWSTK, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

4 odpowiedzi na [PJWSTK] ASD – Wprowadzenie – przykładowe rozwiazania

  1. garry pisze:

    eee, też to rozwiązywałem, w Javie, na 100% …. 🙂

    • Jerzy Skalski pisze:

      To napisz jak wczytujesz dane w Javie, bo parę osób oddaje zadania w Javie na 100%, a mi samo wczytanie danych zajmuje więcej niż limit. Jak na razie najszybszy okazał się StringTokenizer, ale i tak 80% w 'Projekcie 1′.

  2. Duke pisze:

    Bo jak się używa najgorszej i katowanej na pjwstk metody na wczytywanie, to takie są efekty.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *