Witajcie, może ktoś z was brał udział w tegorocznej rudzie próbnej z przed paru dni i macie jakiś pomysł na wzorcówkę do zadania z rundy próbnej bo zdobyłem z niej 3 punkty i zachodzę w głowę jak powinno wyglądać prawidłowe rozwiązanie
- Rejestracja:około 10 lat
- Ostatnio:ponad 9 lat
- Postów:3
0
- Rejestracja:ponad 10 lat
- Ostatnio:prawie 2 lata
- Postów:2500
0
Nie brałem udziału i teraz nie ma możliwości sprawdzenia, ale przyszedł mi do głowy taki pomysł:
Zakres [1, 1018] jest zbyt duży, żeby sprawdzić dla każdej liczby czy spełnia podane warunki (pewnie dlatego dostałeś 3 punkty, bo dla większych testów program po prostu za długo liczy). Ale można zauważyć pewne prawidłowości:
- Jeżeli
kjest mały, to liczby, które spełniają warunek też są małe. Jeśli powiedzmyk < 100to od razu widać, że nie ma sensu rozpatrywać liczb większych niż np. 106, bo maksymalna suma cyfr liczby 6-cyfrowej to6 * 9 * 9, więck * 6 * 9 * 9nigdy nie będzie większe niż 106 - Dla każdego
kmożna w takim razie wyznaczyć w miarę sensowny zakres możliwych trafień. Trzeba sprawdzić czy liczby 1-cyfrowe mogą, 2-cyfrowe mogą, 3-cyfrowe mogą itd. Strzelam, że taki zakres nie obejmuje więcej niż 4 rzędów wielkości. - Problem pozostaje wtedy, gdy te rzędy wielkości są duże, np. dla pewnego
kmożliwe liczby są 15-cyfrowe, 16-cyfrowe, 17-cyfrowe, 18-cyfrowe w zakresie[A, B]. Sprawdzenie wszystkich takich liczb nadal trwa za długo. Ale wtedy można zauważyć, że jeżeli takie są zakresy, tokteż musi być dużą liczbą. Strzelam, żekbędzie jakieś 2 rzędy wielkości mniejsze niżA, czyli to jakaś 13-cyfrowa liczba. - Wiedząc o tym, możemy spokojnie sprawdzić tylko liczby podzielne przez
kw zakresie[A, B]. Taka pętla zamiast 1018 iteracji będzie miała jakieś 106 iteracji, bo zwiększamy licznik nie o1tylkok.
1
Ja też nie brałem udziału, ale coś takiego działa :
#include <iostream>
using namespace std;
int main() {
long long k,a,b;
cin >> k >> a >> b;
int count = 0;
for(int i=1;i<=1539;i++) {
long long n = k * i;
long tmp = n;
int result = 0;
while(tmp > 0) {
int last = tmp % 10;
result += (last*last);
tmp /= 10;
}
if(result == i && n >= a && n <= b) {
count++;
}
}
cout << count << "\n";
return 0;
}
Ideaa jest taka, że największa suma kwadratów, czyli f(n) będzie wtedy gdy będzie siedemnascie 9 czyli ~ 1377 . W powyzszym rozwiazaniu przyjelem troche wiecej. Iterujemy sie po wszystkich mozliwych sumach. Obliczamy dla danego k jakie powinno byc n. Dla tak wyliczonego n sprawdzamy czy suma kwadratow cyfr sie zgadza. Jesli tak to inkrementujemy licznik o 1
twonek
a no tak xD
- Rejestracja:ponad 10 lat
- Ostatnio:ponad 7 lat
- Postów:83
0
using System;
using System.Linq;
namespace PotyczkiAlgoryttmiczneROW
{
class Program
{
static void Main(string[] args)
{
int[] liczby=(Console.ReadLine().Split(' ')).Select(int.Parse).ToArray();
int rozwiazanie=0;
for (int i=liczby[1]; i <= liczby[2]; i++ )
{
int wynik=0;
string liczba=i.ToString();
for (int a = 0; a != liczba.Length; a++)
wynik += int.Parse(liczba[a].ToString()) * int.Parse(liczba[a].ToString());
if (liczby[0] * wynik == i)
rozwiazanie++;
}
Console.WriteLine(rozwiazanie);
Console.ReadKey();
}
}
}
Też nie biorę udziału, ale z nudy zrobiłem.
Mógłby ktoś wyrazić opinię nt. powyższego kodu?
Zobacz pozostałe 6 komentarzy
W takich konkursach jak Potyczki programy zazwyczaj mają parę sekund na wykonanie. To oznacza, że możesz lecieć po mniej więcej 10<sup>7 elementach, ale 10</sup>18 to na pewno za dużo.
Zrób pętle po 10^18 elementów to się przekonasz.
Jeżeli sprawdzenie 10<sup>7 liczb trwa sekundę, to ile potrwa sprawdzenie 10</sup>18 liczb?
10^11 sekund