Domātājiem!

[Bremze]

Sveiki! Tātad es piektdien dodos uz informātikas / matemātikas olimpiādi. Nezinu kā sanāks, bet dzīvē viss jāpamēģina :D.

Tātad ejot cauri uzdevumiem, nonācu pie šī te.

Varbūt kāds nevēlētos palīdzēt uziet uz domu gājiena, kā tad šis te būtu jāaprēķina!

Izmantot var visa veida programmatūru Pascal, PHP, Exel kautvai HTML, ja palīdz.

Pazīstams, nedaudz, esmu tikai ar PHP, tapēc nekādu izeju pašlaik neredzu. Te arī būs tas uzdevums:

 

 

http://puu.sh/6Bs1S

Edited January 28, 2014 by Bremze

[Kasspars]

Visos informātika olimpiādes uzdevumos ir iespējama "brute force" metode. Vienīgais mīnuss šai metodes - pārāk ilgi izpildās :D

 

Ja tava atzīme matemātikā ir mazāka par 9, tad tevi sagaida drūma izgāšanās olimpiādē ;)

[metal-0-1]

Hm, ja dalas ar 2013 bez atlikuma, tad tas ir vesels skaitlis.

Ja decimalaja pieraksta visi cipari atskirigi, tad tas ir maksimums 9 ciparu skaitlis.

 

Nevajadzetu but nemaz tik gruti brutforsot.

[codez]

Uztaisām 2 funkcijas, kas nosaka vai visi cipari dažādi un vai satur 2013.
Laižam cauri visiem variantiem, kas daļās ar 2013, tas ir katru 2013-to, līdz 9876543210, kurš ir lielākais skaitlis ar dažādiem cipariem:

http://ideone.com/VrTAnd

#include <iostream>

using namespace std;

bool isDigitsDiff(long long a){
  int r[10]={0};
  while (a>0){
    int d=a%10;
    if (r[d]==1) return false;
    r[d]=1;
    a=a/10;
  }
  return true;

}
bool isContain2013(long long a){
  while (a>0){
    if (a%10000==2013) return true;
    a=a/10;
  }
  return false;
}

int main()
{
    long long a=0;
    while (a<9876543210) {
      a=a+2013;
      if (isDigitsDiff(a) and isContain2013(a)) {
        cout << a << endl;
      }
    }
}

rezultāts ir 2 skaitļi:

 

2013

584720136

 

 

P.S. Bet īsti nesaprotu, kas tā tev par olimpiādi - īstā informātikas (programmēšanas) olimpiāde ir šeit: http://vip.latnet.lv/lio/

Edited January 28, 2014 by codez

[metal-0-1]

Cik aatri tas kods izpildiijaas, codez?

[codez]

Pēc teorijas, tas ir 10^10 / 2*10^3= 5*10^6 dažādu skaitļu. Katram skaitlim līdz 10 darbībām - kopā ap 500M darbības (cikli).

Praksē - uz mana kompja 0.6 sek.

[Kasspars]

Cik aatri tas kods izpildiijaas, codez?

 

Šitas jau īsti nav bruteforce. Brute force būtu a=a+1 :D

 

@codez, ja nav grūti uztaisi ciklu ar tīru visu skaitļu pārlasi. Interesanti cik ilgi tad izpildīsies

 

Vajadzētu būt kādām 20 min, ne?

Edited January 28, 2014 by Kasspars

[ieleja]

mana variācija C++ ar stringiem 1,5 sekundes

 

ja pārlasītu ne tikai katru 2013., bet visus, tad vajadzētu būt 2012x ilgāk

int main (void)
{
	for (long long i = 2013; i <= 9876543210; i = i + 2013)
	{
		std::string figString = std::to_string (static_cast<long long> (i));

		if (figString.find ("2013") != std::string::npos)
			if (prepFig (figString))
				std::cout << i << '\n';
	}

	return 0;
}

int prepFig (std::string figString)
{
	int fig[10] = { };

	for (unsigned int i = 0; i < figString.length (); i++)
		if (++fig[figString[i] - 48] > 1)
			return 0;

	return 1;
}

Edited January 28, 2014 by ieleja

[rATRIJS]

Izmantojam codez variantu, lai atrastu skaitļus un tad submitojam:

#include <iostream>
using namespace std;


int main() {


    cout << "2013, 584720136";


    return 0;


}

for premium performance.

[ieleja]

ir tāda bibliotēka:

https://github.com/vitaut/format

 

ar to 0,552 sekundes

int main (void)
{
	for (long long i = 2013; i <= 9876543210; i = i + 2013)
	{
		fmt::Writer fS;
		fS << i;
		std::string figString = fS.str();

		if (figString.find ("2013") != std::string::npos)
			if (prepFig (figString))
				std::cout << i << '\n';
	}

	return 0;
}

int prepFig (std::string figString)
{
	int fig[10] = { };

	for (unsigned int i = 0; i < figString.length (); i++)
		if (++fig[figString[i] - 48] > 1)
			return 0;

	return 1;
}

[jurchiks]

P.S. Bet īsti nesaprotu, kas tā tev par olimpiādi - īstā informātikas (programmēšanas) olimpiāde ir šeit: http://vip.latnet.lv/lio/

Saucās informātikas olimpiāde, it kā taču tur vajadzētu būt inteliģentiem cilvēkiem rīkotāju lomā, bet lapas dizains zem katras kritikas...

[Kavacky]

Informātikas olimpiāde, nevis datordizaina, cik saburtoju.

[jurchiks]

Lapa ir lapa.

[daGrevis]

Clojure (Lisp) variants. http://vpaste.net/u0pzI

[codez]

Ja jau, tad jau. Scala:

0L to 9876543210L by 2013 map(_.toString())filter(a=>(a.distinct.size==a.size && a.contains("2013"))) map println