found = False s= str(input()) for k in range (2, 37): try: h = int(s, k) if h%(k-1)==0: print(k) found = True break except: pass
if not found: print('No solution')
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ Answer: 36 Ну я вспомнил что число в десятичной системе счисления Делится на 9 (то есть на 10-1) Если сумма его цифр делится на 9 Я предположил что в любой k-ичной системе счисления верно Что если сумма цифр некоторого числа делится на k-1 то и это число делится на k-1 И это оказалось правдой для тех k Которые содержатся в тестах к этой задаче. Большое спасибо! Эта подсказка мне помогла. Доказательство вашего утверждения: Пусть мы сейчас в k-ой системе счисления и если прочитать наше число X слева направо, то получим цифры a_n, a_{n - 1}, ... , a_1, a_0 (при этом 0 <= a_i <= k - 1 для всех i). Тогда в десятичной системе счисления оно будет равно X = a_n * k ^ n + a_{n - 1} * k ^ {n - 1} + ... + a_1 * k + a_0. Так как k = 1 (mod (k - 1)), то X = a_n + a_{n - 1} + ... + a_1 + a_0 (mod (k - 1)). Значит, X делится на (k - 1) тогда и только тогда, когда его сумма цифр делится на (k - 1). My python 3.3 program has TLE in problem 12. Has anyone a hint to speed up this algorithm. Changing to python 2.7.5 was enough to get AC Tried to solve in Python 2.7.18 and Python 3.8.2. Time limit exceeded on test 12 with time 1.015 s. Rewrote it in C and got 'accepted' with 0.031 s. Can anybody help Edited by author 20.03.2020 19:35 Try these test cases. Test 1: 0 Ans:2 Test 2: 1 Ans:2 Test 3: 2 Ans:3 Test 4: Z0Z Ans:36 Test 5: 21 Ans:4 Test 6: ZIZ Ans:No solution. (Don't forget to put the full-stop at the end!!!) Test 7: AERGUFG12312OP Ans:32 Test 8: 234DFG67 Ans:23 And this problem can be solved within int range. Edited by author 09.12.2015 20:14 only test 7 I can't get right ans. I have 33 And WA4 Removed my post, because apparently I can't alphabet :) Edited by author 12.07.2016 14:45 IN TEST CASE 2, FOR INPUT 0 , WHY ANS IS ONLY 2 IT CAN BE 1,2,3,4,5.......35. BECAUSE ZERO IS DIVISIBLE BY ALL. You can't divide by 0! So 1 isn't a solution and therefore it's 2: If you get WA for the first test in C# using System; namespace Timus1104 { class Program { static void Main(string[] args) { var inputNumber = Console.ReadLine(); Console.WriteLine("22"); } } } just add return value using System; namespace Timus1104 { class Program { static int Main(string[] args) { var inputNumber = Console.ReadLine(); Console.WriteLine("22"); return 0; } } } 1104 Task Help me please, I cant understand how can i do my calculations faster? I think that problem with slow input, but how else can i write it? p.s. using stdin, stdout get Time Limit as well maximal = 0 max_digit = -1 arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', \ 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', \ 'U', 'V', 'W', 'X', 'Y', 'Z'] for s in input(): number = arr.index(s) if max_digit < number: max_digit = number maximal += number if max_digit == 0: print(2) else: answer = '' for k in range(max_digit, 37): if not maximal % k: answer = k + 1 break if answer == '': print('No solution.') else: print(answer) Edited by author 14.10.2019 07:30 Edited by author 14.10.2019 07:41 I WAed many many times, and finally got AC. Test6 is 0, whose answer is 2. Test 7 is probably 1 or 2, which my previous program had given incorrect answer to. The answer to Test 8 has to be 36, because I used "for(i=x;i<36;i++)" and wa8. (I also saw some prog posted on this forum had the same problem) When I found this and changed into "<=", AC at last. Sorry for my poor English. Hope these can help you guys somehow. Good luck! Thank to your help. Sorry for my poor English,too. Thank you, your hints helped me to get AC. I got Crash (integer division by zero) before. unfortunately, it didn't help me :( still get WA8, any ideas?? I WAed many many times, and finally got AC. Test6 is 0, whose answer is 2. Test 7 is probably 1 or 2, which my previous program had given incorrect answer to. The answer to Test 8 has to be 36, because I used "for(i=x;i<36;i++)" and wa8. (I also saw some prog posted on this forum had the same problem) When I found this and changed into "<=", AC at last. Sorry for my poor English. Hope these can help you guys somehow. Good luck! Thanks... Thanks, my program went in cycle to 35 instead of 36) k=2 => k-1 = 1. But everything is divisible by 1, what's wrong? Not all numbers could be written in binary number system What is Test case #5 for question 1104 Output is "No solution.". (!) BE CAREFUL NOT "No solution" but "No solution." Output is "No solution.". (!) BE CAREFUL NOT "No solution" but "No solution." Thanks... Why min base number of the sample is 11? In statement I can't find that k should be >= max digit in an initial number. BTW if I convert any number to binary it will always be divisible by 1 and as far as I see will satisfy every condition from the statement (the given number, written in k-based system is divisible by k−1, 2 ≤ k ≤ 36). Thanks. Edited by author 13.04.2017 17:00 What "A" digit means if base is less then 11? Could you transform "A1A" to base 10 from base... 7 for example? Thanks a lot, now I read the statement in a different way. The following is my program,i want to know why it always be "wrong answer". #include <stdio.h> #include <string.h> #include <math.h> int main() { int i,k,m,n; double s; bool f,t; char a[100000]; while(scanf("%s",a)!=EOF) { int d=strlen(a); char max=a[0]; for(i=1;i<d;i++) { if(a[i]>max) max=a[i]; } if(max>='A'&&max<='Z') m=max-65+10; else m=max-'0'; for(k=2;k<=36;k++) { s=0; f=false; t=true; if(m>=k) continue; for(i=0;i<d;i++) { if(a[i]>='A'&&a[i]<='Z') n=a[i]-65+10; else n=(int)a[i]-48; if(n==0&&t) continue; else t=false; s=s+n*pow(k,d-i-1); }
if((int)s%(k-1)==0) { f=true; break; } } if(f) printf("%d\n",k); else printf("No solution.\n"); } return 0; } #include <iostream> #include <cmath> using namespace std; void main(){ int a[100001]; char s[100001]; gets_s(s); int max = 0; for (int i = 0; i <= strlen(s); i++) { if (s[i] >= 'A'&& s[i] <= 'Z'){ a[i] = s[i] - 55; if (max < a[i]){ max = a[i]; } } else{////if digits a[i] = s[i] - 48; if (max < a[i]){ max = a[i]; } }; }; int k; long long res; max++; bool found = 1; for (k = max; k <= 36; k++) { res = 0; for (int i = strlen(s) - 1; i >= 0; i--) { res = res + pow(k, i)*a[i]; } if (res % (k - 1) == 0){ found = 0; break; } } if (found==0){ cout << k; } else{ cout << "No solution."; } system("pause"); } I think that problem in large numbers in tests, am I right? Edited by author 09.07.2016 22:05 Edited by author 09.07.2016 22:26 According to the description the input can have 10^6 digits this means that the input string can be a million characters long. This will definitely overflow even "long long" :) There is a solution to this problem described below. They shown a proof that all the calculations that You need to do is summing up the digits. I'm experimenting with a different approach. I try to simulate "pen and paper" division, and get the remainder. And finally I got AC with my approach. Edited by author 12.07.2016 14:48 First of all. If you get WA#1, check how you scan input stream, cause they've put some trash in file. I used the following idea. The whole number with base k divisible by ( k - 1 ), if sum( div( digit[ i ] ) ) is divisible by ( k - 1 ). Where digit[ i ] is k-based digit in input number ( char from input stream ); div( digit[ i ] ) is a remainder of division digit[ i ] * k by ( k - 1 ). Let see digit on i-th position, for example, it's A. So in decimal implementation it's equal to A * k ^ i. A * k ^ i = A * k^i - A * k^(i-1) + A * k^(i-1) = A * k^(i-1) * ( k - 1 ) + A * k^(i-1) A * k^(i-1) * ( k - 1 ) is divisible by ( k - 1 ), so we have to check only A * k^(i-1). If we repeat the same logic to this expression (i - 2) times, we see, that we have to check division A * k / ( k - 1 ). I tried my best to explain the main idea, sorry if it can't be understood. You don't need your "div()". Isn't it okay to just find the digital sum of the given number and add 1? Thank you. And we even can go a step further. Now see, A * k = A * k - A + A = A(k - 1) + A, So what we need to examine is just whether sum( digit[i]) is divisible by ( k - 1). Help me please! min base for 123 is 4 not 3. so for 123 the correct answer is 4. min base for 123 is 4 not 3. so for 123 the correct answer is 4. Thank u so much... ^_^ What is test case 8? I met the same problem.Have you solved?? The test gives "wrong answer". What is the test input? A1A=10 1 10 For k=4, 10*(4^0)+1*(4^1)+10*(4^2)=174 174 is divisible by 3 so the answer for sample test case turns out to be 4. What am I doing wrong? Thanks Got WA on test 16. I've read previos posts about test "123", i have base 4 for this test. |
|