TheArcheologist'sDilemma

https://onlinejudge.org/external/7/701.pdf

 

#include <stdio.h>
#include <string.h>
int len;
char map[50][50];
char string[50];

int check(int s, int t, int x, int y)
{
    int l = 1;
    while (len > l)
    {
        x += s;
        y += t;
        if (x > 50 || x < 0 || y > 50 || y < 0)
            return 0;
        if (map[x][y] == string[l++])
            ;
        else
            return 0;
    }
    return 1;
}
char change(char c)
{
    if (c <= 90)
        return c + 32;
    else
        return c;
}

int main()
{
    int Case, m, n, k;
    char line[256];
    int x, y, sucess;
    int i, j;
    int t;
    scanf("%d", &Case);
    t = 0;
    while (Case--)
    {
        if (t)
            printf("\n");
        t = 1;
        gets(line);
        scanf("%d %d", &m, &n);
        for (i = 0; i < m; i++)
            scanf("%s", &map[i]);
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++)
                map[i][j] = change(map[i][j]);
        scanf("%d", &k);
        while (k--)
        {
            scanf("%s", &string);
            len = strlen(string);
            for (i = 0; i < len; i++)
                string[i] = change(string[i]);
            for (i = 0; i < m; i++)
            {
                sucess = 0;
                for (j = 0; j < n; j++)
                {
                    if (map[i][j] == string[0])
                    {
                        x = i;
                        y = j;
                        if (x >= len)
                            if (check(-1, 0, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(-1, 1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (n - y >= len)
                            if (check(0, 1, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(1, 1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (m - x >= len)
                            if (check(1, 0, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(1, -1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (y >= len)
                            if (check(0, -1, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(-1, -1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                    }
                }
                if (sucess)
                {
                    printf("%d %d\n", x + 1, y + 1);
                    break;
                }
            }
        }
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#pragma warning(disable : 4996)

#define _int64 long long
#define STORE_NUM 70777

typedef struct
{

    double value;
    int mult;
} _log2_type;

_log2_type log2_house[STORE_NUM];

int compare(const void *type1, const void *type2)
{
    _log2_type *t1 = (_log2_type *)type1;
    _log2_type *t2 = (_log2_type *)type2;
    double diff = t1->value - t2->value;
    if (diff < 0)
        return -1;
    else if (diff > 0)
        return 1;
    else
        return 0;
}

void find_candidate(double left, double right, int poss_min, int *now_min)
{
    int left_limit, right_limit, search_left, search_right;
    int mid;
    int i;

    left -= 0.00000000000001;
    right += 0.00000000000001;

    search_left = 0;
    search_right = STORE_NUM - 1;
    while (search_left <= search_right)
    {
        mid = (search_left + search_right) / 2;
        if (left < log2_house[mid].value)
            search_right = mid - 1;
        else
            search_left = mid + 1;
    }
    left_limit = search_left;

    search_left = 0;
    search_right = STORE_NUM - 1;
    while (search_left <= search_right)
    {
        mid = (search_left + search_right) / 2;
        if (right < log2_house[mid].value)
            search_right = mid - 1;
        else
            search_left = mid + 1;
    }
    right_limit = search_right;

    for (i = left_limit; i <= right_limit; i++)
        if (log2_house[i].mult >= poss_min && (*now_min == -1 || log2_house[i].mult < *now_min))
            *now_min = log2_house[i].mult;
}
void main()
{

    double log2 = log10(2.0);
    _int64 now_check, min_candidate;
    double left, right, base;
    _int64 n;
    int answer = -1;
    int p;
    for (p = 0; p < STORE_NUM; p++)
    {
        log2_house[p].value = log2 * p;
        log2_house[p].value -= (int)log2_house[p].value;
        log2_house[p].mult = p;
    }
    qsort((void *)log2_house, (size_t)STORE_NUM, sizeof(_log2_type), compare);

    while (1)
    {
        n = 0;
        now_check = 0;

        if (!scanf("%lld", &n))
            break;
        if (n == 0)
            break;

        left = log10((double)n);
        left -= (int)left;
        right = log10((double)(n + 1));
        right -= (int)right;
        if (left > right)
            right += 1.0;

        min_candidate = (int)(log10((long double)n)) + 1;
        min_candidate = min_candidate * 2;
        min_candidate = (int)(min_candidate / log2 + 0.99999999);

        while (1)
        {
            base = now_check * log2;
            answer = -1;
            base -= (_int64)base;
            base = 1 - base;
            if (left + base >= 1.0)
            {
                find_candidate(left + base - 1.0, right + base - 1.0, (int)(min_candidate - now_check), &answer);
            }
            else if (right + base >= 1.0)
            {
                find_candidate(left + base, 1.0, (int)(min_candidate - now_check), &answer);
                find_candidate(0.0, right + base - 1.0, (int)(min_candidate - now_check), &answer);
            }
            else
            {
                find_candidate(left + base, right + base, (int)(min_candidate - now_check), &answer);
            }

            if (answer >= 0)
            {
                printf("%lld\n", now_check + answer);
                break;
            }
            now_check += STORE_NUM;
        }
    }
}