На примере этой задачи хорошо просматривается три варианта поиска даты.
Алиса и Боб живут вместе уже много лет. Внезапно выяснилось, что Боб совершенно не помнит дату, когда они поженились. Данный факт очень возмутил Алису. Чтобы Боб лучше запомнил эту памятную дату, она придумала игру со следующими правилами:
Алиса в тайном дневнике выписала все-все-все памятные даты, расположив их в хронологическом порядке. В один день произошло ровно одно памятное событие. Алиса ни под каким предлогом не показывает тайный дневник Бобу.
Оказалось, что дата, когда они поженились, расположилась ровно в середине списка. Причем список имеет нечетную длину. Обо всем этом Алиса сообщила Бобу.
Каждый день Боб оставляет на столе конверт, где пишет ровно одну дату - предполагаемую дату, когда они поженились. И уходит на работу.
Алиса забирает конверт, смотрит на дату, открывает свой тайный дневник и считает количество событий, которые произошли до этой даты включительно, а затем пишет Бобу ответную записку, где указывает это число.
Пункты 3-4 повторяются, пока Боб не определит точную дату памятного события.
Боб очень любит Алису и хочет как можно скорее определить дату, когда они поженились. Кроме того, Алиса установила Бобу предельное количество попыток N, за которые Боб должен угадать памятную дату. Боб просит вас написать компьютерную программу, которая поможет ему в этом.
В первой строке входных данных будет содержаться целое число N (1≤N≤20) - предельное количество попыток угадать памятную дату.
Известно, что все памятные даты Алисы находятся в промежутке [01.01.1970...31.12.2020] и что существует алгоритм, позволяющий угадать дату за требуемое количество попыток. Все даты заданы в формате «dd.mm.yyyy» (без кавычек). В таком же формате их необходимо задавать в запросах к тестирующей системе.
В следующих строках на вход вашей программе будут подаваться строки, содержащие информацию об ответе Алисы. i-я из этих строк является ответом системы на ваш i-й запрос.
Ваша программа должна выводить запросы к тестирующей системе и обрабатывать ответы от нее. После вывода каждой строки программа должна выполнить операцию flush. Ответ на запрос программа сможет прочесть из стандартного ввода. Доступные ответы системы:
«? K» (без кавычек) - ответ тестирующей системы, означающий, что до посланной проверяемой даты произошло K памятных событий (0≤K≤20000).
«!» (без кавычек) - ответ тестирующей системы, означающий, что превышено количество попыток N угадать памятную дату.
«? M» (без кавычек) - проверить, является ли дата M (01.01.1970≤M≤31.12.2020) - памятной датой.
«! M» (без кавычек) - указать, что дата M (01.01.1970≤M≤31.12.2020) является памятной.
Поиск года осложнен тем, что надо добавлять дату начала поискового периода (в данном случае 1970). И тем, что найденный нужный год не имеет однозначного подтверждения.
Поиск месяца - найденный нужный месяц не имеет однозначного подтверждения.
И только поиск дня имеет однозначное подтверждение.
С консолью работают два человека: один запрашивает, а второй отвечает. Или человек и тестирующая система.
Решение здесь:
Алгоритм записан в комментах.
fun main() { // объявление сканнера val sc = Scanner(System.`in`) // получе6ние с консоли исходных данных
println("Введите предельное число попыток N(1<=N<=20")
val n: Int = sc.nextInt() // объявление начальных значений переменных var d = 31
val m = 12
var z = 2021
var z1 = 13
val y0 = 2020
// наш вариант даты (не путать с m - значением месяца) - первый максимально возможный, для получения общего числа событий) val M0: LocalDate = LocalDate.of(y0, m, d) println("?$M0")
// получе6ние с консоли исходных данных: узнаем общее число событий val k: Int = sc.nextInt()
var i = 1 // присваиваем р значение середины диапазона поиска (чистого - без 1970) val p = (2020 - 1970) / 2 // присваиваем yi значение ДАТЫ середины диапазона поиска ( с учетом 1970) val yi = 1970 + p // наш вариант даты (не путать с m - значением месяца) var Mi: LocalDate = LocalDate.of(yi, m, d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) var ki: Int = sc.nextInt() // проверка на случайное попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
}
//определение базиса, от которого идет очередная проверка (он может смещатся в ту или иную сторону) var basis = (2020 - 1970) / 2 + 1970 // Для получения возможности сравнения вариантов поиска,
// то есть, работы с инлексными переменными создаем массивы
// массив шагов поиска var myArray = emptyArray<Int>()
myArray += p
for (r in 1..7) {
myArray += myArray[r - 1] / 2
} // исправляем (уточняя) шаги, неустраивающие нас (за счет округления) myArray[4] = 2
myArray[5] = 1
myArray[6] = 1
if (ki < k / 2 + 1) { // выбор года правая ветвь (тренд - правильная дата ЗА нашим предположением) do { // массив значений поиска var arr = emptyArray<Int>()
arr += basis
for (h in 1..7) {
arr += basis + myArray[h]
}
//проверка крайних дат диапазона поиска (годов) i++ // наш вариант даты Mi = LocalDate.of(arr[i - 1], m, d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt()
if (arr[i - 1] == 1970 || arr[i - 1] == 2020) {
z = arr[i - 1]
break
} // проверка на случайное попадание в точку if (ki == k / 2 + 1) { println("!$Mi")
return
} //ограничение по N числу попыток if (i > n) { println("!")
break
} //уточнение базиса при сохранении тренда if (ki < k / 2 + 1) {
basis += myArray[i - 1]
// проверки при перемене тренда этой ветви } else if (ki > k / 2 + 1) {
// проверка на соседство и выбор по граничному условию if ((arr[i - 1] - arr[0]) == 1) { // наш вариант даты: проверка начала года Mi = LocalDate.of(arr[i - 1], 1, 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // попал в вилку if (ki > k / 2 + 1) {
z = arr[0]
break
} else // наш вариант даты: провека начала года соседнего варианта Mi = LocalDate.of(arr[0], 1, 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // z - угаданный год (попал в вилку) if (ki > k / 2 + 1) {
z = arr[i - 1]
break // ближе к искомому не попавшие в вилку } else if (arr[i - 1] > arr[0]) {
z = arr[i - 1]
break
} else
z = arr[0]
break
} // случайное попадание между ветвями (левой и правой) } else println("!$Mi") // превышено допустимое число попыток } while (i < n)
} else if (ki > k / 2 + 1) {
// выбор года левая ветвь (тренд - правильная дата ПЕРЕД нашим предположением) do { // массив значений поиска var arr = emptyArray<Int>()
arr += basis
for (h in 1..7) {
arr += basis - myArray[h]
}
//проверка крайних дат диапазона поиска (годов) i++ // наш вариант даты Mi = LocalDate.of(arr[i - 1], m, d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt()
if (arr[i - 1] == 1970 || arr[i - 1] == 2020) {
z = arr[i - 1]
break
} // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} //ограничение по N числу попыток if (i > n) { println("!")
break
} //уточнение базиса при сохранении тренда if (ki > k / 2 + 1) {
basis += -myArray[i - 1]
// проверки при перемене тренда этой ветви
} else if (ki < k / 2 + 1) {
// проверка на соседство и выбор по граничному условию if ((arr[0] - arr[i - 1]) == 1) { // наш вариант даты: проверка начала года Mi = LocalDate.of(arr[i - 1], 1, 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // попал в вилку if (ki > k / 2 + 1) {
z = arr[0]
break
} else // наш вариант даты: провека начала года соседнего варианта Mi = LocalDate.of(arr[0], 1, 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // z - угаданный год (попал в вилку) if (ki > k / 2 + 1) {
z = arr[i - 1]
break // ближе к искомому не попавшие в вилку } else if (arr[i - 1] > arr[0]) {
z = arr[i - 1]
break
} else
z = arr[0]
break
} // случайное попадание между ветвями (левой и правой) } else println("!$Mi") // превышено допустимое число попыток } while (i < n)
} else println("!$Mi")
// выбор месяца var a = 1
var basisM = 6
i++ // наш вариант даты Mi = LocalDate.of(z, 6, 30) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // создаем массив шагов поиска var myArrayM = emptyArray<Int>()
myArrayM += basisM
for (r in 1..5) {
myArrayM += myArrayM[r - 1] / 2
} // исправляем (уточняя) шаги, не устраивающие нас (за счет округления) myArrayM[3] = 1
myArrayM[4] = 1
// массив значений по которому будем проходить шагами поиска val arrM = arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
if (ki < k / 2 + 1) { // выбор месяца правая ветвь do {
i++
a++
// уточняем числа дней в месяце в зависимости от месяца и года val yearMonthObject = YearMonth.of(z, arrM[(basisM + myArrayM[a - 1]) - 1])
d = yearMonthObject.lengthOfMonth() // наш вариант даты: проверка на конец месяца Mi = LocalDate.of(z, arrM[(basisM + myArrayM[a - 1]) - 1], d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} //ограничение по N числу попыток if (i > n) { println("!")
break
} // уточнение базиса месяца if (ki < k / 2 + 1) {
basisM += myArrayM[a - 1]
} // перемена тренда if (ki > k / 2 + 1) { // наш вариант даты Mi = LocalDate.of(z, arrM[(basisM + myArrayM[a - 1]) - 1], 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // z1 - угаданный месяц if (ki > k / 2 + 1) {
z1 = arrM[(basisM + myArrayM[a - 1]) - 2]
break
} else z1 = arrM[(basisM + myArrayM[a - 1]) - 1]
break
}
} while (i < n)
} else if (ki > k / 2 + 1) {
// выбор месяца левая ветвь do {
i++
a++ // уточняем количесво дней (в зависимости от месяца и года) val yearMonthObject = YearMonth.of(z, arrM[(basisM - myArrayM[a - 1]) - 1])
d = yearMonthObject.lengthOfMonth() // наш вариант даты Mi = LocalDate.of(z, arrM[(basisM - myArrayM[a - 1]) - 1], d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} //ограничение по N числу попыток if (i > n) { println("!")
break
} //при сохранении тренда if (ki > k / 2 + 1) { // наш вариант даты Mi = LocalDate.of(z, arrM[(basisM - myArrayM[a - 1]) - 1], 1) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
}
if (ki < k / 2 + 1) {
z1 = arrM[(basisM - myArrayM[a - 1]) - 1]
break
} // уточнение базиса месяца basisM = arrM[(basisM - myArrayM[a - 1]) - 1]
// перемена тренда } else if (ki < k / 2 + 1) { // уточняем количесво дней (в зависимости от месяца и года) val yearMonthObject1 = YearMonth.of(z, arrM[basisM - myArrayM[a - 1]])
d = yearMonthObject1.lengthOfMonth() // наш вариант даты Mi = LocalDate.of(z, arrM[basisM - myArrayM[a - 1]], d) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
} // z1 - угаданный месяц if (ki > k / 2 + 1) {
z1 = arrM[basisM - myArrayM[a - 1]]
break
} else z1 = arrM[basisM - myArrayM[a - 1] + 1]
}
} while (i < n)
} else println("!$Mi") // выбор дня var b = 1 // уточняем количесво дней (в зависимости от месяца и года) val yearMonthObject = YearMonth.of(z, z1)
d = yearMonthObject.lengthOfMonth()
var basisD = d / 2
i++ // наш вариант даты Mi = LocalDate.of(z, z1, basisD) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно) ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
}
var myArrayD = emptyArray<Int>()
myArrayD += basisD
for (r in 1..7) {
myArrayD += myArrayD[r - 1] / 2
} // исправляем (уточняя) шаги, неустраивающие нас (за счет округления) myArrayD[2] = 3
myArrayD[3] = 2
myArrayD[4] = 1
myArrayD[5] = 1
myArrayD[6] = 1
do {
i++
b++ //ограничение по N числу попыток if (i > n) { println("!")
break
} //уточнение базиса при сохранении тренда if (ki < k / 2 + 1) {
basisD += myArrayD[b - 1]
// перемена тренда } else if (ki > k / 2 + 1) {
basisD += -myArrayD[b - 1]
} else println("!$Mi") // наш вариант даты Mi = LocalDate.of(z, z1, basisD) println("?$Mi") // получе6ние с консоли числа событий происшедших до введенной нами даты (включительно)
ki = sc.nextInt() // проверка на попадание в точку (угадана вся дата) if (ki == k / 2 + 1) { println("!$Mi")
return
}
} while (i < n)
}
Подписки НЕТ!
Поиск необходимой информации осуществляется в разделах Главного меню по ссылкам.
Уважая чужой опыт, считаю ОБЯЗАТЕЛЬНЫМ наличие «Обратной связи»:
Права на материалы, размещенные на сайте, принадлежат Автору.
Все права защищены и охраняются законом.
При использовании материалов с сайта ссылка на него обязательна.
