Jump to content
php.lv forumi

Domātājiem!


Recommended Posts

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 by Bremze
Link to post
Share on other sites

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ē ;)

Link to post
Share on other sites

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 by codez
Link to post
Share on other sites

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 by Kasspars
Link to post
Share on other sites

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 by ieleja
Link to post
Share on other sites

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;
}
Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...