Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Prepogosto

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Prepogosto

OdgovorNapisal/-a lukazlatecan » Če Jun 08, 2017 1:42 pm

Podan imamo seznam N števil, v katerem se nekatera števila pojavijo večkrat. Obdržali bi radi samo zadnjih K pojavitev (gledano od leve proti desni) istega števila, ostale pa želimo izbrisati. Napisati morate program, ki bo učinkovito izračunal, kakšen je novonastali seznam.

Naloga
Začetni seznam je zelo dolg, zato je podan v obliki generatorja seznama. Podani sta prvo in drugo število v seznamu (tj. števili [math]) ter pravilo za izračun naslednjih členov seznama: [math].

Napišite program, ki se bo znebil prepogostih števil in izpisal preostanek seznama od mest A do B.

Opozorila:
Bodite pozorni na količino (razpoložljivega) pomnilnika!

Omejitve
Čas: 10 s
Spomin: 512 MB


Vhodni podatki
V prvi vrstici se nahajata celi števili N in K. V drugi vrstici so podani parametri za generiranje seznama: [math] X, Y in M. Tretja vrstica pa vsebuje števili A in B, ki definirata izpis.

Omejitve vhodnih podatkov
1≤N≤70000000
1≤K,M≤1000000
0≤[math]<M
1≤A≤B
V seznamu bo ostalo najmanj B števil.
0≤B−A≤100

Izhodni podatki
Izpišite s presledki ločena števila, ki se v končnem seznamu nahajajo od mesta A do B.

Primer vhoda

Koda: Izberi vse

20 2
6 1 4 7 13
2 6


Pripadajoč izhod

Koda: Izberi vse

0 7 7 11 1


Komentar
Seznam števil opisan v testnem primeru je [6, 1, 5, 0, 7, 10, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Če obdržimo samo zadnje prepogoste pojavitve števil, dobimo seznam [6, 0, 7, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Ko izpišemo elemente od 2. do 6. mesta, dobimo iskan rezultat.
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

hinkopihpih
Prispevkov: 11
Pridružen: Ne Apr 30, 2017 2:11 pm

Re: Prepogosto

OdgovorNapisal/-a hinkopihpih » Ne Jun 25, 2017 11:35 am

Koda: Izberi vse

import java.util.*;
import java.io.*;

public class Prepogosto
{
   public static void main(String[]args)
   {
      Scanner skan;
      File vhod;

      try
      {
         vhod = new File("prepogosto.txt");
         skan = new Scanner(vhod);
      }
      catch(FileNotFoundException e)
      {
         skan = new Scanner(System.in);
      }

      int n = skan.nextInt();
      int k = skan.nextInt();
      int s2 = skan.nextInt();
      int s1 = skan.nextInt();
      int x = skan.nextInt();
      int y = skan.nextInt();
      int m = skan.nextInt();
      int a = skan.nextInt();
      int b = skan.nextInt();

      for(int i = 0; i < n - 2; i++)
      {
         int temp = s1;
         s1 = function1(s1,s2,x,y,m);
         s2 = temp;
      }

      int[] repeated = new int[m];
      repeated[s1]++;
      repeated[s2]++;
      List<Integer> sequence = new ArrayList<Integer>();

      if(s1 == s2 && k == 1)
      {
         sequence.add(s1);
      }   
      else
      {
         sequence.add(s1);
         sequence.add(s2);
      }   

      for(int i = 0; i < n - 2; i++)
      {
         int temp = s2;
         s2 = function2(s1,s2,x,y,m);
         s1 = temp;

         if(s2 < 0)
         {
            s2 += m;
         }   

         repeated[s2]++;

         if(repeated[s2] <= k)
         {
            sequence.add(s2);
         }   
      }

      for(int i = sequence.size() - a; i >= sequence.size() - b; i--)
      {
         System.out.print(sequence.get(i) + " ");
      }   
   }
   public static int function1(int s1, int s2, int x, int y, int m)
   {
      return (s2 * x + s1 * y) % m;
   }
   public static int function2(int s1, int s2, int x, int y, int m)
   {
      return ((int)(Math.pow(x,euler(m) - 1)) * (s1 - s2 * y)) % m;
   }
   public static int euler(int m)
   {
      int result = 0;

      for(int i = 1; i < m; i++)
      {
         if(gcd(i,m) == 1)
         {
            result++;
         }   
      }

      return result;
   }
   public static int gcd(int a, int b)
   {   
       while(b != 0)
       {   
             int temp = b;
             b = a % b;
             a = temp;
       }   

       return a;
    }
}


Vrni se na “3. Kolo”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost