양의 정수가 n ≤ 500 인 경우 :
-
찾기 작은 양의 정수 K 의 소수 표현하는 모든 숫자가되도록 N * k는 어느있다 0 또는 D를 가진 ≤ D ≤ 1 9 .
-
30 초 이내에 d 를 인쇄하거나 반환 하십시오 ( 설명 및 규칙 섹션 에서 이에 대해 자세히 알아보십시오 ).
쉬운 예
다음은 d 의 처음 30 개 값입니다 .
+----+-------+---------+---+ +----+-------+---------+---+
| n | k | n * k | d | | n | k | n * k | d |
+----+-------+---------+---+ +----+-------+---------+---+
| 1 | 1 | 1 | 1 | | 16 | 5 | 80 | 8 |
| 2 | 1 | 2 | 2 | | 17 | 653 | 11101 | 1 |
| 3 | 1 | 3 | 3 | | 18 | 5 | 90 | 9 |
| 4 | 1 | 4 | 4 | | 19 | 579 | 11001 | 1 |
| 5 | 1 | 5 | 5 | | 20 | 1 | 20 | 2 |
| 6 | 1 | 6 | 6 | | 21 | 37 | 777 | 7 |
| 7 | 1 | 7 | 7 | | 22 | 1 | 22 | 2 |
| 8 | 1 | 8 | 8 | | 23 | 4787 | 110101 | 1 |
| 9 | 1 | 9 | 9 | | 24 | 25 | 600 | 6 |
| 10 | 1 | 10 | 1 | | 25 | 2 | 50 | 5 |
| 11 | 1 | 11 | 1 | | 26 | 77 | 2002 | 2 |
| 12 | 5 | 60 | 6 | | 27 | 37 | 999 | 9 |
| 13 | 77 | 1001 | 1 | | 28 | 25 | 700 | 7 |
| 14 | 5 | 70 | 7 | | 29 | 37969 | 1101101 | 1 |
| 15 | 2 | 30 | 3 | | 30 | 1 | 30 | 3 |
+----+-------+---------+---+ +----+-------+---------+---+
쉽지 않은 예제
이 과제의 한 가지 특이점은 적어도 순전히 무차별 대입 방식으로는 일부 값을 다른 값보다 찾기가 훨씬 어렵다는 것입니다. 다음은 높은 k 값으로 이어지는 n의 예입니다 .
+-----+------------+---------------+---+ +-----+------------+---------------+---+
| n | k | n * k | d | | n | k | n * k | d |
+-----+------------+---------------+---+ +-----+------------+---------------+---+
| 81 | 12345679 | 999999999 | 9 | | 324 | 13717421 | 4444444404 | 4 |
| 157 | 64338223 | 10101101011 | 1 | | 353 | 28615017 | 10101101001 | 1 |
| 162 | 13717421 | 2222222202 | 2 | | 391 | 281613811 | 110111000101 | 1 |
| 229 | 43668559 | 10000100011 | 1 | | 405 | 13717421 | 5555555505 | 5 |
| 243 | 13717421 | 3333333303 | 3 | | 439 | 22781549 | 10001100011 | 1 |
| 283 | 35371417 | 10010111011 | 1 | | 458 | 43668559 | 20000200022 | 2 |
| 299 | 33478599 | 10010101101 | 1 | | 471 | 64338223 | 30303303033 | 3 |
| 307 | 32576873 | 10001100011 | 1 | | 486 | 13717421 | 6666666606 | 6 |
| 314 | 64338223 | 20202202022 | 2 | | 491 | 203871711 | 100101010101 | 1 |
| 317 | 3154574483 | 1000000111111 | 1 | | 499 | 22244489 | 11100000011 | 1 |
+-----+------------+---------------+---+ +-----+------------+---------------+---+
설명 및 규칙
- n * k 는 항상 하나 이상의 숫자 d를 포함하지만 0을 전혀 포함하지 않을 수 있습니다.
- 이것은 code-golf 이므로 바이트 단위의 가장 짧은 코드가 이깁니다. 그러나 프로그램이나 기능은 어떤의 결과를 반환 할 수 있어야합니다 1 ≤ N ≤ 500 에서 30 초 미만 중간 범위의 하드웨어에서.
- 일부 값은 다른 값보다 찾기가 어렵다는 점에 유의하십시오. k 값을 무차별 강제로 적용하려는 프로그램 은 시간 제한 제약 조건을 준수하지 않을 것입니다 (좋은 테스트 사례는 n = 317입니다 ). d 를 찾는 데 훨씬 빠른 방법이 있습니다 .
참고 표
1 ≤ n ≤ 500에 대한 d의 모든 값 은 다음과 같습니다.
n | d
--------+--------------------------------------------------
001-025 | 1 2 3 4 5 6 7 8 9 1 1 6 1 7 3 8 1 9 1 2 7 2 1 6 5
026-050 | 2 9 7 1 3 1 8 3 2 7 9 1 2 3 4 1 6 1 4 9 2 1 6 7 5
051-075 | 3 4 1 9 5 7 1 2 1 6 1 2 9 8 5 6 1 4 3 7 1 9 1 2 3
076-100 | 4 7 6 1 8 9 2 1 4 5 2 3 8 1 9 1 4 3 2 5 6 1 7 9 1
101-125 | 1 6 1 8 7 2 1 9 1 1 1 7 1 2 5 4 9 2 7 6 1 2 3 4 5
126-150 | 6 1 8 3 1 1 6 7 2 9 8 1 6 1 7 1 2 1 9 5 2 7 4 1 3
151-175 | 1 8 9 7 5 4 1 2 1 8 7 2 1 4 3 2 1 8 1 1 3 4 1 6 7
176-200 | 8 3 2 1 9 1 2 1 8 5 6 1 4 9 1 1 6 1 2 3 7 1 9 1 2
201-225 | 3 2 7 4 5 2 9 8 1 7 1 4 1 2 5 9 7 2 3 2 1 2 1 7 9
226-250 | 2 1 4 1 1 3 8 1 6 5 4 3 7 1 6 1 2 3 4 7 6 1 8 3 5
251-275 | 1 6 1 2 3 8 1 6 7 2 9 2 1 6 5 7 3 4 1 9 1 8 3 2 5
276-300 | 6 1 2 9 7 1 2 1 4 5 2 7 9 1 1 3 4 1 7 5 8 9 2 1 3
301-325 | 7 2 3 8 5 6 1 4 3 1 1 8 1 2 9 4 1 2 1 8 1 7 1 4 5
326-350 | 2 1 8 7 3 1 4 3 2 5 8 1 2 3 2 1 6 1 8 3 2 1 4 1 7
351-375 | 9 8 1 6 5 4 7 2 1 9 1 2 3 4 5 2 1 8 9 1 7 6 1 2 3
376-400 | 8 1 9 1 2 3 2 1 6 7 2 9 4 1 3 1 7 1 2 5 9 1 2 7 4
401-425 | 1 6 1 4 5 2 1 8 1 1 3 4 7 9 5 8 1 2 1 6 1 2 3 8 5
426-450 | 2 7 4 3 1 1 9 1 7 3 4 1 6 1 4 3 2 1 4 5 2 3 7 1 9
451-475 | 1 4 3 2 5 8 1 2 9 2 1 6 1 8 3 2 1 6 7 1 3 8 1 6 5
476-500 | 7 3 2 1 6 1 2 3 4 5 6 1 8 3 7 1 6 1 2 9 8 7 6 1 5
답변
젤리 , 16 15 14 바이트
²B€Ḍ9×þF%Þ¹ḢQS
2 차 런타임 (TIO에서 25 초 미만).
대체 버전, 15 바이트
2ȷB€Ḍ9×þF%Þ¹ḢQS
일정한 런타임 (TIO에서 약 1 초).
작동 원리
²B€Ḍ9×þF%Þ¹ḢQS Main link. Argument: n
² Take the square of n.
This bound is high enough for all integers up to 500.
In fact, The highest value we need is 1387 for input 471, so
2000 (2ȷ) is also enough (and a lot faster).
B€ Binary; convert 1, ..., 4159 to base 2.
Ḍ Undecimal; convert each digit array from base 10 to integer.
This generates the array A of all positive integers up to n²
whose decimal representations consist entirely of 1's and 0's.
9×þ 9 multiply table; for each x in A, yield [x, 2x, ..., 8x, 9x].
F Flatten; concatenate the resulting arrays, yielding the vector
V. Note that V contains all numbers that match the regex ^d[0d]*$
in base 10, in ascending order.
¹ Identity; yield n.
%Þ Sort the entries for V by their remainders modulo n. This places
multiples of n at the beginning. The sorting algorithm in stable,
so the first element of sorted V is the smallest multiple of n.
Ḣ Head; extract the first element.
Q Unique; deduplicate its digits in base 10. This yields [d, 0].
S Take the sum, yielding d.
답변
자바 스크립트 (ES6), 83 바이트
n=>{for(p=1;;p=k)for(d=0;d++<9;)for(k=p;k<p+p;k++)if(k.toString(2)*d%n<1)return d;}
이제 반환 6을 위해 n=252! 재귀 적 접근법을 시도했지만 83 바이트이기도하며 더 어려운 숫자로 인해 충돌이 발생합니다.
f=(n,p=1,d=1,k=p)=>k<p+p?k.toString(2)*d%n<1?d:f(n,p,d,k+1):d>8?f(n,p+p):f(n,p,d+1)
답변
매쓰, 103 (100) 97 바이트
#&@@IntegerDigits[Sort[Join@@Table[Cases[FromDigits/@{0,i}~Tuples~13/#,_Integer],{i,9}]][[10]]#]&
0.39 초 안에 317 번을 발견
온라인으로
코드 복사 / 붙여 넣기를 시도 하고 끝에 [317]을 추가 한 다음 Shift + Enter를 눌러 실행하십시오.
@JungHwan에서 -3 바이트 Min
@Keyu Gan에서 -3 바이트
답변
파이썬 2/3 129 128 127 바이트
from itertools import*
lambda n:next(d for p in count()for d in range(1,10)for k in range(2**p,2*2**p)if d*int(bin(k)[2:])%n<1)
-1 바이트 : count(0)→ count()
-1 바이트 : ==0→ <1음수가 될 수 없으므로 →
답변
젤리 , 21 바이트
9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ
숫자를 반환하는 전체 링크 또는 전체 프로그램이 인쇄합니다.
임의의에 대해 20 초 미만이 소요 제한된 범위 무작위 포서 1 ≤ N ≤ 500 (1 바이트 코드 비용 3 초 미만 – 대체 ⁴하여 13).
어떻게?
9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ - Link: number, n
9R - range of 9 = [1,2,3,4,5,6,7,8,9]
ṭ€0 - tack €ach to 0 -> [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9]]
⁴ - literal 16
ṗ€ - Cartesian product for €ach
Ẏ - tighten (flatten by 1 level)
Ḍ - covert from decimal list to number (vectorises)
⁸ - chain's left argument (n)
Ðf - filter keep items for which this yields a truthy value:
ḍ@ - divisible? with swapped @rguments
Ṣ - sort
D - convert to decimal list (vectorises)
F - flatten into a single list
ḟ0 - filter out zeros
Ḣ - head (get the first value)