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
Которые содержатся в тестах к этой задаче.

My python 3.3 program has TLE in problem 12.
Has anyone a hint to speed up this algorithm.

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

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!

k=2 => k-1 = 1. But everything is divisible by 1, what's wrong?

What is Test case #5 for question 1104

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

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

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.

Help me please!

What is test case 8?

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.