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

m = []
g = []
d, b = map(int, input().split(' '))
for i in range(1, b+1):
    n = int(input())
    m.append(n)
for i in range(1, d+1):
    g.append(i)
for i in range(d):
    f = 0
    for y in range(b):
        if m[y] == g[i]:
            f += 1/b*100
    f = round(f, 2)
    a = str(f)
    if len(a) == 4:
        print(a+'0%')
    else:
        print(a+'%')

this is a succsesful answer in C, but I want to understand it. Who can help me?

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, x=1, FM;
    int arr[1000];
    scanf("%d", &n);

   if(n<=1000 && n>=3)
   {
     for(int i=0; i<n; i++)
     {
         scanf("%d", &arr[i]);
     }

     FM=arr[0]+arr[1]+arr[2];

     for(int i=1; i<n-2; i++)
     {
         if(arr[i]+arr[i+1]+arr[i+2]>FM)
         {
             FM=arr[i]+arr[i+1]+arr[i+2];
             x=i+1;
         }
     }
   }
     printf("%d %d", FM, x+1);
     return 0;
}

Edited by author 10.10.2019 12:53

#include <iostream>

using namespace std;

int main()
{
    long int n, k;
    cin >> n >> k;
    long int a = 1;
    long int h = 0;
    if(n == 1){
        cout << 0;
    }
    else if(n == 2){
        cout << 1;
    }
    else{
    while(n != 0){
            if(a > k && a < n){
                a = k;
        n -= a;
        h++;
        }
        else if(a > n){
            n = 0;
            h++;
        }

        else{
            n -= a;
        a *= 2;
        if(a > k){
            a = k;
        }
        h++;
        }
    }
    cout << h;
}
}

Getting WA#11, give some tests pls

Please tell me what could be the problem...
WA14, Time limit exceeded, Time work 1.014

Visual C#:


if (x!=10.0){
    sum=ToInt32((x+0.05)*n);
    while (sum/n>=x+0.049999999999) sum--;
    }
    else
    {
        sum=x*n;
    }
while  (((ans+sum)/(ans+n))>=y+0.0499999999999 ) ans++;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;

namespace _1484Kino
{
    class Program
    {
        static void Main(string[] args)
        {
            var userInput = Console.ReadLine().Split();
            var x = double.Parse(userInput[0],CultureInfo.InvariantCulture);
            var y = double.Parse(userInput[1], CultureInfo.InvariantCulture);
            var n = int.Parse(userInput[2], CultureInfo.InvariantCulture);
            int count = 0;
            if (y > 0.9 && x<=10.0)
            {
                while (Math.Round(x, 1 )> 1)
                {
                    x = ((x * n + 1) / (n + 1));
                    n += 1;
                    count++;
                }
                Console.WriteLine(count);
            }
            else
                Console.WriteLine("Impossible");

        }
    }
}

a=input().split('\n')
j=[]

for x in a:
    for xx in x.split(" ") :
        if(len(xx)>0):
            j.append( float(xx)**0.5)



for i in range(len(j)-1,-1,-1):
     print(format(j[i],'.4f'))

Time limit test 20 failed on python. Rewrited on C# - everything OK.

Edited by author 04.10.2019 02:08

Edited by author 04.10.2019 02:08

I tried to solve this problem in java since we have to accept as many number of lines given in input I wrote a while loop as follows

while (in.hasNextLine()) // in is scanner object
{
     // read input and do stuff
}

but this loop seems to run forever how do I stop the loop from running.

Several highly optimized solutions were TLE in Python3.6, though on local run in Linux it shows half of a time on your server. Is there some mistake?

#include <iostream>
#include <stack>

using namespace std;
int main()
{
    unsigned short n1, n2, n3;
    int a, n=0;
    stack<int> group1;
    cin >> n1;
    for (int i = 0; i <n1; i++) {
        scanf_s("%d", &a);  group1.push(a);
    }

    stack<int> group2;
    cin >> n2;
    for (int i = 0; i < n2; i++) {
        scanf_s("%d", &a);  group2.push(a);
    }

    stack<int> group3;
    cin >> n3;
    for (int i = 0; i < n3; i++) {
        scanf_s("%d", &a);  group3.push(a);
    }

    while (!group1.empty()) {
        if (group1.top() == group2.top()) {
            if (group1.top() == group3.top()) {
                n++;
                group1.pop();
                group2.pop();
                group3.pop();
                if ((group1.empty()) || group2.empty() || group3.empty()) break;
            }
            else if (group1.top() > group3.top()) {
                group1.pop();
                group2.pop();
                if (group1.empty() || group2.empty()) break;
            }
            else group3.pop();
        }
        if (group1.top() > group2.top())group1.pop();
        if (group1.empty()) break;
        if (group1.top() < group2.top())group2.pop();
        if (group2.empty()) break;
    }
    cout << n;

}

what's wrong?

We have got 3 distinct number, A < B < C.
Let's imagine that the minimum difference Z = (C - B) goes between numbers A and B, closer to B, so new sequence will be A < Z < B < C. And the next minimum difference Y = (B - Z), goes between A and Z, closer to Z, A < Y < Z < B < C and so on.
You see Y + Z = B, Z + B = C, the next number in the sequence (in order from left to right) is equal to the sum of current and previous members (looks like Fibonacci numbers).
Now try to find the sequence with described property.

Look at the example: 1 4 6 10 16 26 ... We can continue this sequence until the last two members will be 519390993822245170 and 840392281454979346. Their sum is more than 10^18. It takes only 83 iterations to build this sequence.

The test case would be: 1 519390993822245170 840392281454979346

So, in the worst case, the number of iteration N < 100.

The naive algorithm, when we just put the minimum diff to the array and sort it again will work. The time complexity will be O(N^2 log N).

Edited by author 01.10.2019 14:24

7 1

answer:
6
2
7 1

helped for me
3 17

answer
1
3
3 18 17

I can't find mistake, and have WA on test 7.
Someone can give some cases?

Edited by author 13.11.2011 18:38

//pseudo code
divider = first_input-1;
dividend = second_input-1;
result: divider + dividend - FindCrossesOnTheWay(dividend,divider)
*FindCrossesOnTheWay
if(divider < dividend) swap()
for(i=1;i<=divider;i++)
if((dividend * i) % divider == 0) crosses++

I've implemented this problem two different ways and I have WA9 on both of them. I'm possibly interpreting the problem wrong, but I've read the problem over and over again and I cannot come up with an alternative interpretation. Can someone please shine some light?